Satsuma
a delicious .NET graph library
 All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties Pages
Path.cs
Go to the documentation of this file.
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Threading.Tasks;
6 
7 namespace Satsuma
8 {
24  public interface IPath : IGraph
25  {
27  Node FirstNode { get; }
30  Node LastNode { get; }
34  Arc NextArc(Node node);
38  Arc PrevArc(Node node);
39  }
40 
42  public static class PathExtensions
43  {
45  public static bool IsCycle(this IPath path)
46  {
47  return path.FirstNode == path.LastNode && path.ArcCount() > 0;
48  }
49 
53  public static Node NextNode(this IPath path, Node node)
54  {
55  var arc = path.NextArc(node);
56  if (arc == Arc.Invalid) return Node.Invalid;
57  return path.Other(arc, node);
58  }
59 
63  public static Node PrevNode(this IPath path, Node node)
64  {
65  var arc = path.PrevArc(node);
66  if (arc == Arc.Invalid) return Node.Invalid;
67  return path.Other(arc, node);
68  }
69 
71  internal static IEnumerable<Arc> ArcsHelper(this IPath path, Node u, ArcFilter filter)
72  {
73  Arc arc1 = path.PrevArc(u), arc2 = path.NextArc(u);
74  if (arc1 == arc2) arc2 = Arc.Invalid; // avoid duplicates
75  for (int i = 0; i < 2; i++)
76  {
77  Arc arc = (i == 0 ? arc1 : arc2);
78  if (arc == Arc.Invalid) continue;
79  switch (filter)
80  {
81  case ArcFilter.All: yield return arc; break;
82  case ArcFilter.Edge: if (path.IsEdge(arc)) yield return arc; break;
83  case ArcFilter.Forward: if (path.IsEdge(arc) || path.U(arc) == u) yield return arc; break;
84  case ArcFilter.Backward: if (path.IsEdge(arc) || path.V(arc) == u) yield return arc; break;
85  }
86  }
87  }
88  }
89 
95  public sealed class Path : IPath, IClearable
96  {
98  public IGraph Graph { get; private set; }
99  public Node FirstNode { get; private set; }
100  public Node LastNode { get; private set; }
101 
102  private int nodeCount;
103  private Dictionary<Node, Arc> nextArc;
104  private Dictionary<Node, Arc> prevArc;
105  private HashSet<Arc> arcs;
106  private int edgeCount;
107 
109  public Path(IGraph graph)
110  {
111  Graph = graph;
112 
113  nextArc = new Dictionary<Node, Arc>();
114  prevArc = new Dictionary<Node, Arc>();
115  arcs = new HashSet<Arc>();
116 
117  Clear();
118  }
119 
121  public void Clear()
122  {
125 
126  nodeCount = 0;
127  nextArc.Clear();
128  prevArc.Clear();
129  arcs.Clear();
130  edgeCount = 0;
131  }
132 
135  public void Begin(Node node)
136  {
137  if (nodeCount > 0)
138  throw new InvalidOperationException("Path not empty.");
139 
140  nodeCount = 1;
141  FirstNode = LastNode = node;
142  }
143 
148  public void AddFirst(Arc arc)
149  {
150  Node u = U(arc), v = V(arc);
151  Node newNode = (u == FirstNode ? v : u);
152  if ((u != FirstNode && v != FirstNode) || nextArc.ContainsKey(newNode) || prevArc.ContainsKey(FirstNode))
153  throw new ArgumentException("Arc not valid or path is a cycle.");
154 
155  if (newNode != LastNode) nodeCount++;
156  nextArc[newNode] = arc;
157  prevArc[FirstNode] = arc;
158  if (!arcs.Contains(arc))
159  {
160  arcs.Add(arc);
161  if (IsEdge(arc)) edgeCount++;
162  }
163 
164  FirstNode = newNode;
165  }
166 
171  public void AddLast(Arc arc)
172  {
173  Node u = U(arc), v = V(arc);
174  Node newNode = (u == LastNode ? v : u);
175  if ((u != LastNode && v != LastNode) || nextArc.ContainsKey(LastNode) || prevArc.ContainsKey(newNode))
176  throw new ArgumentException("Arc not valid or path is a cycle.");
177 
178  if (newNode != FirstNode) nodeCount++;
179  nextArc[LastNode] = arc;
180  prevArc[newNode] = arc;
181  if (!arcs.Contains(arc))
182  {
183  arcs.Add(arc);
184  if (IsEdge(arc)) edgeCount++;
185  }
186 
187  LastNode = newNode;
188  }
189 
192  public void Reverse()
193  {
194  { var tmp = FirstNode; FirstNode = LastNode; LastNode = tmp; }
195  { var tmp = nextArc; nextArc = prevArc; prevArc = tmp; }
196  }
197 
198  public Arc NextArc(Node node)
199  {
200  Arc arc;
201  return nextArc.TryGetValue(node, out arc) ? arc : Arc.Invalid;
202  }
203 
204  public Arc PrevArc(Node node)
205  {
206  Arc arc;
207  return prevArc.TryGetValue(node, out arc) ? arc : Arc.Invalid;
208  }
209 
210  public Node U(Arc arc)
211  {
212  return Graph.U(arc);
213  }
214 
215  public Node V(Arc arc)
216  {
217  return Graph.V(arc);
218  }
219 
220  public bool IsEdge(Arc arc)
221  {
222  return Graph.IsEdge(arc);
223  }
224 
225  public IEnumerable<Node> Nodes()
226  {
227  Node n = FirstNode;
228  if (n == Node.Invalid) yield break;
229  while (true)
230  {
231  yield return n;
232  Arc arc = NextArc(n);
233  if (arc == Arc.Invalid) yield break;
234  n = Graph.Other(arc, n);
235  if (n == FirstNode) yield break;
236  }
237  }
238 
239  public IEnumerable<Arc> Arcs(ArcFilter filter = ArcFilter.All)
240  {
241  if (filter == ArcFilter.All) return arcs;
242  if (edgeCount == 0) return Enumerable.Empty<Arc>();
243  return arcs.Where(arc => IsEdge(arc));
244  }
245 
246  public IEnumerable<Arc> Arcs(Node u, ArcFilter filter = ArcFilter.All)
247  {
248  return this.ArcsHelper(u, filter);
249  }
250 
251  public IEnumerable<Arc> Arcs(Node u, Node v, ArcFilter filter = ArcFilter.All)
252  {
253  return Arcs(u, filter).Where(arc => this.Other(arc, u) == v);
254  }
255 
256  public int NodeCount()
257  {
258  return nodeCount;
259  }
260 
261  public int ArcCount(ArcFilter filter = ArcFilter.All)
262  {
263  return filter == ArcFilter.All ? arcs.Count : edgeCount;
264  }
265 
266  public int ArcCount(Node u, ArcFilter filter = ArcFilter.All)
267  {
268  return Arcs(u, filter).Count();
269  }
270 
271  public int ArcCount(Node u, Node v, ArcFilter filter = ArcFilter.All)
272  {
273  return Arcs(u, v, filter).Count();
274  }
275 
276  public bool HasNode(Node node)
277  {
278  return prevArc.ContainsKey(node) || (node != Node.Invalid && node == FirstNode);
279  }
280 
281  public bool HasArc(Arc arc)
282  {
283  return arcs.Contains(arc);
284  }
285  }
286 
296  public sealed class PathGraph : IPath
297  {
298  private readonly int nodeCount;
299  private readonly bool isCycle, directed;
300 
301  public Node FirstNode { get { return nodeCount > 0 ? new Node(1) : Node.Invalid; } }
302  public Node LastNode { get { return nodeCount > 0 ? new Node(isCycle ? 1 : nodeCount) : Node.Invalid; } }
303 
304  public enum Topology
305  {
307  Path,
309  Cycle
310  }
311 
312  public PathGraph(int nodeCount, Topology topology, Directedness directedness)
313  {
314  this.nodeCount = nodeCount;
315  isCycle = (topology == Topology.Cycle);
316  directed = (directedness == Directedness.Directed);
317  }
318 
321  public Node GetNode(int index)
322  {
323  return new Node(1L + index);
324  }
325 
328  public int GetNodeIndex(Node node)
329  {
330  return (int)(node.Id - 1);
331  }
332 
333  public Arc NextArc(Node node)
334  {
335  if (!isCycle && node.Id == nodeCount) return Arc.Invalid;
336  return new Arc(node.Id);
337  }
338 
339  public Arc PrevArc(Node node)
340  {
341  if (node.Id == 1)
342  return isCycle ? new Arc(nodeCount) : Arc.Invalid;
343  return new Arc(node.Id - 1);
344  }
345 
346  public Node U(Arc arc)
347  {
348  return new Node(arc.Id);
349  }
350 
351  public Node V(Arc arc)
352  {
353  return new Node(arc.Id == nodeCount ? 1 : arc.Id + 1);
354  }
355 
356  public bool IsEdge(Arc arc)
357  {
358  return !directed;
359  }
360 
361  public IEnumerable<Node> Nodes()
362  {
363  for (int i = 1; i <= nodeCount; i++)
364  yield return new Node(i);
365  }
366 
367  public IEnumerable<Arc> Arcs(ArcFilter filter = ArcFilter.All)
368  {
369  if (directed && filter == ArcFilter.Edge) yield break;
370  for (int i = 1, n = ArcCountInternal(); i <= n; i++)
371  yield return new Arc(i);
372  }
373 
374  public IEnumerable<Arc> Arcs(Node u, ArcFilter filter = ArcFilter.All)
375  {
376  return this.ArcsHelper(u, filter);
377  }
378 
379  public IEnumerable<Arc> Arcs(Node u, Node v, ArcFilter filter = ArcFilter.All)
380  {
381  return Arcs(u, filter).Where(arc => this.Other(arc, u) == v);
382  }
383 
384  public int NodeCount()
385  {
386  return nodeCount;
387  }
388 
389  private int ArcCountInternal()
390  {
391  return nodeCount == 0 ? 0 : (isCycle ? nodeCount : nodeCount - 1);
392  }
393 
394  public int ArcCount(ArcFilter filter = ArcFilter.All)
395  {
396  return directed && filter == ArcFilter.Edge ? 0 : ArcCountInternal();
397  }
398 
399  public int ArcCount(Node u, ArcFilter filter = ArcFilter.All)
400  {
401  return Arcs(u, filter).Count();
402  }
403 
404  public int ArcCount(Node u, Node v, ArcFilter filter = ArcFilter.All)
405  {
406  return Arcs(u, v, filter).Count();
407  }
408 
409  public bool HasNode(Node node)
410  {
411  return node.Id >= 1 && node.Id <= nodeCount;
412  }
413 
414  public bool HasArc(Arc arc)
415  {
416  return arc.Id >= 1 && arc.Id <= ArcCountInternal();
417  }
418  }
419 }