Satsuma
a delicious .NET graph library
 All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties Pages
SpanningForest.cs
Go to the documentation of this file.
1 #region License
2 /*This file is part of Satsuma Graph Library
3 Copyright © 2013 Balázs Szalkai
4 
5 This software is provided 'as-is', without any express or implied
6 warranty. In no event will the authors be held liable for any damages
7 arising from the use of this software.
8 
9 Permission is granted to anyone to use this software for any purpose,
10 including commercial applications, and to alter it and redistribute it
11 freely, subject to the following restrictions:
12 
13  1. The origin of this software must not be misrepresented; you must not
14  claim that you wrote the original software. If you use this software
15  in a product, an acknowledgment in the product documentation would be
16  appreciated but is not required.
17 
18  2. Altered source versions must be plainly marked as such, and must not be
19  misrepresented as being the original software.
20 
21  3. This notice may not be removed or altered from any source
22  distribution.*/
23 #endregion
24 
25 using System;
26 using System.Collections.Generic;
27 using System.Linq;
28 
29 namespace Satsuma
30 {
55  public sealed class Prim<TCost>
56  where TCost : IComparable<TCost>
57  {
58  public IGraph Graph { get; private set; }
59  public Func<Arc, TCost> Cost { get; private set; }
60 
62  public HashSet<Arc> Forest { get; private set; }
63 
64  public Prim(IGraph graph, Func<Arc, TCost> cost)
65  {
66  Graph = graph;
67  Cost = cost;
68  Forest = new HashSet<Arc>();
69 
70  Run();
71  }
72 
73  private void Run()
74  {
75  Forest.Clear();
76  PriorityQueue<Node, TCost> priorityQueue = new PriorityQueue<Node, TCost>();
77  HashSet<Node> processed = new HashSet<Node>();
78  Dictionary<Node, Arc> parentArc = new Dictionary<Node, Arc>();
79 
80  // start with one point from each component
81  var components = new ConnectedComponents(Graph, ConnectedComponents.Flags.CreateComponents);
82  foreach (var c in components.Components)
83  {
84  Node root = c.First();
85  processed.Add(root);
86  foreach (var arc in Graph.Arcs(root))
87  {
88  Node v = Graph.Other(arc, root);
89  parentArc[v] = arc;
90  priorityQueue[v] = Cost(arc);
91  }
92  }
93  components = null;
94 
95  while (priorityQueue.Count != 0)
96  {
97  Node n = priorityQueue.Peek();
98  priorityQueue.Pop();
99  processed.Add(n);
100  Forest.Add(parentArc[n]);
101 
102  foreach (var arc in Graph.Arcs(n))
103  {
104  Node v = Graph.Other(arc, n);
105  if (processed.Contains(v)) continue;
106 
107  TCost arcCost = Cost(arc);
108  if (arcCost.CompareTo(priorityQueue[v]) < 0)
109  {
110  priorityQueue[v] = arcCost;
111  parentArc[v] = arc;
112  }
113  }
114  }
115  }
116  }
117 
139  public sealed class Kruskal<TCost>
140  where TCost : IComparable<TCost>
141  {
143  public IGraph Graph { get; private set; }
145  public Func<Arc, TCost> Cost { get; private set; }
151  public Func<Node, int> MaxDegree { get; private set; }
152 
156  public HashSet<Arc> Forest { get; private set; }
158  public Dictionary<Node, int> Degree { get; private set; }
159 
160  private IEnumerator<Arc> arcEnumerator; // Enumerates the arcs by cost increasing.
161  private int arcsToGo;
162  private DisjointSet<Node> components; // The components of the current spanning forest.
163 
164  public Kruskal(IGraph graph, Func<Arc, TCost> cost, Func<Node, int> maxDegree = null)
165  {
166  Graph = graph;
167  Cost = cost;
168  MaxDegree = maxDegree;
169 
170  Forest = new HashSet<Arc>();
171  Degree = new Dictionary<Node, int>();
172  foreach (var node in Graph.Nodes()) Degree[node] = 0;
173 
174  List<Arc> arcs = Graph.Arcs().ToList();
175  arcs.Sort((a, b) => Cost(a).CompareTo(Cost(b)));
176  arcEnumerator = arcs.GetEnumerator();
177  arcsToGo = Graph.NodeCount() - new ConnectedComponents(Graph).Count;
178  components = new DisjointSet<Node>();
179  }
180 
184  public bool Step()
185  {
186  if (arcsToGo <= 0 || arcEnumerator == null || !arcEnumerator.MoveNext())
187  {
188  arcEnumerator = null;
189  return false;
190  }
191 
192  AddArc(arcEnumerator.Current);
193  return true;
194  }
195 
197  public void Run()
198  {
199  while (Step()) ;
200  }
201 
206  public bool AddArc(Arc arc)
207  {
208  var u = Graph.U(arc);
209  if (MaxDegree != null && Degree[u] >= MaxDegree(u)) return false;
210  DisjointSetSet<Node> x = components.WhereIs(u);
211 
212  var v = Graph.V(arc);
213  if (MaxDegree != null && Degree[v] >= MaxDegree(v)) return false;
214  DisjointSetSet<Node> y = components.WhereIs(v);
215 
216  if (x == y) return false; // cycle
217 
218  Forest.Add(arc);
219  components.Union(x, y);
220  Degree[u]++;
221  Degree[v]++;
222  arcsToGo--;
223  return true;
224  }
225  }
226 }