Satsuma
a delicious .NET graph library
 All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties Pages
Connectivity.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 
28 namespace Satsuma
29 {
42  public sealed class ConnectedComponents
43  {
44  [Flags]
45  public enum Flags
46  {
47  None = 0,
49  CreateComponents = 1 << 0
50  }
51 
53  public IGraph Graph { get; private set; }
55  public int Count { get; private set; }
58  public List<HashSet<Node>> Components { get; private set; }
59 
60  private class MyDfs : Dfs
61  {
62  public ConnectedComponents Parent;
63 
64  protected override void Start(out Direction direction)
65  {
66  direction = Direction.Undirected;
67  }
68 
69  protected override bool NodeEnter(Node node, Arc arc)
70  {
71  if (arc == Arc.Invalid)
72  {
73  Parent.Count++;
74  if (Parent.Components != null) Parent.Components.Add(new HashSet<Node> { node });
75  }
76  else if (Parent.Components != null) Parent.Components[Parent.Count - 1].Add(node);
77 
78  return true;
79  }
80  }
81 
82  public ConnectedComponents(IGraph graph, Flags flags = 0)
83  {
84  Graph = graph;
85  if (0 != (flags & Flags.CreateComponents)) Components = new List<HashSet<Node>>();
86  new MyDfs { Parent = this }.Run(graph);
87  }
88  }
89 
103  public sealed class Bipartition
104  {
105  [Flags]
106  public enum Flags
107  {
108  None = 0,
110  CreateRedNodes = 1 << 0,
112  CreateBlueNodes = 1 << 1
113  }
114 
116  public IGraph Graph { get; private set; }
118  public bool Bipartite { get; private set; }
122  public HashSet<Node> RedNodes { get; private set; }
126  public HashSet<Node> BlueNodes { get; private set; }
127 
128  private class MyDfs : Dfs
129  {
130  public Bipartition Parent;
131  private HashSet<Node> redNodes;
132 
133  protected override void Start(out Direction direction)
134  {
135  direction = Direction.Undirected;
136  Parent.Bipartite = true;
137  redNodes = Parent.RedNodes ?? new HashSet<Node>();
138  }
139 
140  protected override bool NodeEnter(Node node, Arc arc)
141  {
142  if ((Level & 1) == 0)
143  redNodes.Add(node);
144  else
145  if (Parent.BlueNodes != null) Parent.BlueNodes.Add(node);
146  return true;
147  }
148 
149  protected override bool BackArc(Node node, Arc arc)
150  {
151  Node other = Graph.Other(arc, node);
152  if (redNodes.Contains(node) == redNodes.Contains(other))
153  {
154  Parent.Bipartite = false;
155  if (Parent.RedNodes != null) Parent.RedNodes.Clear();
156  if (Parent.BlueNodes != null) Parent.BlueNodes.Clear();
157  return false;
158  }
159  return true;
160  }
161  }
162 
163  public Bipartition(IGraph graph, Flags flags = 0)
164  {
165  Graph = graph;
166  if (0 != (flags & Flags.CreateRedNodes)) RedNodes = new HashSet<Node>();
167  if (0 != (flags & Flags.CreateBlueNodes)) BlueNodes = new HashSet<Node>();
168  new MyDfs { Parent = this }.Run(graph);
169  }
170  }
171 
174  public sealed class TopologicalOrder
175  {
176  [Flags]
177  public enum Flags
178  {
179  None = 0,
181  CreateOrder = 1 << 0
182  }
183 
185  public IGraph Graph { get; private set; }
187  public bool Acyclic { get; private set; }
191  public List<Node> Order { get; private set; }
192 
193  private class MyDfs : Dfs
194  {
195  public TopologicalOrder Parent;
196  private HashSet<Node> exited;
197 
198  protected override void Start(out Direction direction)
199  {
200  direction = Direction.Forward;
201  Parent.Acyclic = true;
202  exited = new HashSet<Node>();
203  }
204 
205  protected override bool NodeEnter(Node node, Arc arc)
206  {
207  if (arc != Arc.Invalid && Graph.IsEdge(arc))
208  {
209  Parent.Acyclic = false;
210  return false;
211  }
212  return true;
213  }
214 
215  protected override bool NodeExit(Node node, Arc arc)
216  {
217  if (Parent.Order != null) Parent.Order.Add(node);
218  exited.Add(node);
219  return true;
220  }
221 
222  protected override bool BackArc(Node node, Arc arc)
223  {
224  Node other = Graph.Other(arc, node);
225  if (!exited.Contains(other))
226  {
227  Parent.Acyclic = false;
228  return false;
229  }
230  return true;
231  }
232 
233  protected override void StopSearch()
234  {
235  if (Parent.Order != null)
236  {
237  if (Parent.Acyclic) Parent.Order.Reverse();
238  else Parent.Order.Clear();
239  }
240  }
241  }
242 
243  public TopologicalOrder(IGraph graph, Flags flags = 0)
244  {
245  Graph = graph;
246  if (0 != (flags & Flags.CreateOrder)) Order = new List<Node>();
247  new MyDfs { Parent = this }.Run(graph);
248  }
249  }
250 
253  public sealed class StrongComponents
254  {
255  [Flags]
256  public enum Flags
257  {
258  None = 0,
260  CreateComponents = 1 << 0
261  }
262 
264  public IGraph Graph { get; private set; }
266  public int Count { get; private set; }
270  public List<HashSet<Node>> Components { get; private set; }
271 
272  private class ForwardDfs : Dfs
273  {
274  public List<Node> ReverseExitOrder;
275 
276  protected override void Start(out Direction direction)
277  {
278  direction = Direction.Forward;
279  ReverseExitOrder = new List<Node>();
280  }
281 
282  protected override bool NodeExit(Node node, Arc arc)
283  {
284  ReverseExitOrder.Add(node);
285  return true;
286  }
287 
288  protected override void StopSearch()
289  {
290  ReverseExitOrder.Reverse();
291  }
292  }
293 
294  private class BackwardDfs : Dfs
295  {
296  public StrongComponents Parent;
297 
298  protected override void Start(out Direction direction)
299  {
300  direction = Direction.Backward;
301  }
302 
303  protected override bool NodeEnter(Node node, Arc arc)
304  {
305  if (arc == Arc.Invalid)
306  {
307  Parent.Count++;
308  if (Parent.Components != null) Parent.Components.Add(new HashSet<Node> { node });
309  }
310  else if (Parent.Components != null) Parent.Components[Parent.Components.Count - 1].Add(node);
311 
312  return true;
313  }
314  }
315 
316  public StrongComponents(IGraph graph, Flags flags = 0)
317  {
318  Graph = graph;
319  if (0 != (flags & Flags.CreateComponents)) Components = new List<HashSet<Node>>();
320 
321  var forwardDfs = new ForwardDfs();
322  forwardDfs.Run(graph);
323  var backwardDfs = new BackwardDfs { Parent = this };
324  backwardDfs.Run(graph, forwardDfs.ReverseExitOrder);
325  }
326  }
327 
329  internal class LowpointDfs : Dfs
330  {
331  protected Dictionary<Node, int> level;
332  protected Dictionary<Node, int> lowpoint;
333 
334  private void UpdateLowpoint(Node node, int newLowpoint)
335  {
336  if (lowpoint[node] > newLowpoint) lowpoint[node] = newLowpoint;
337  }
338 
339  protected override void Start(out Direction direction)
340  {
341  direction = Direction.Undirected;
342  level = new Dictionary<Node, int>();
343  lowpoint = new Dictionary<Node, int>();
344  }
345 
346  protected override bool NodeEnter(Node node, Arc arc)
347  {
348  level[node] = Level;
349  lowpoint[node] = Level;
350  return true;
351  }
352 
353  protected override bool NodeExit(Node node, Arc arc)
354  {
355  if (arc != Arc.Invalid)
356  {
357  Node parent = Graph.Other(arc, node);
358  UpdateLowpoint(parent, lowpoint[node]);
359  }
360  return true;
361  }
362 
363  protected override bool BackArc(Node node, Arc arc)
364  {
365  Node other = Graph.Other(arc, node);
366  UpdateLowpoint(node, level[other]);
367  return true;
368  }
369 
370  protected override void StopSearch()
371  {
372  level = null;
373  lowpoint = null;
374  }
375  }
376 
377  internal class BridgeDfs : LowpointDfs
378  {
379  public int ComponentCount;
380  public HashSet<Arc> Bridges;
381 
382  protected override void Start(out Direction direction)
383  {
384  base.Start(out direction);
385  ComponentCount = 0;
386  Bridges = new HashSet<Arc>();
387  }
388 
389  protected override bool NodeExit(Node node, Arc arc)
390  {
391  if (arc == Arc.Invalid) ComponentCount++;
392  else
393  {
394  if (lowpoint[node] == Level)
395  {
396  Bridges.Add(arc);
397  ComponentCount++;
398  }
399  }
400 
401  return base.NodeExit(node, arc);
402  }
403  }
404 
406  public sealed class BiEdgeConnectedComponents
407  {
408  [Flags]
409  public enum Flags
410  {
411  None = 0,
413  CreateComponents = 1 << 0,
415  CreateBridges = 1 << 1
416  }
417 
419  public IGraph Graph { get; private set; }
421  public int Count { get; private set; }
424  public List<HashSet<Node>> Components { get; private set; }
427  public HashSet<Arc> Bridges { get; private set; }
428 
429  public BiEdgeConnectedComponents(IGraph graph, Flags flags = 0)
430  {
431  Graph = graph;
432  var dfs = new BridgeDfs();
433  dfs.Run(graph);
434 
435  Count = dfs.ComponentCount;
436  if (0 != (flags & Flags.CreateBridges)) Bridges = dfs.Bridges;
437  if (0 != (flags & Flags.CreateComponents))
438  {
439  Subgraph withoutBridges = new Subgraph(graph);
440  foreach (var arc in dfs.Bridges) withoutBridges.Enable(arc, false);
441  Components = new ConnectedComponents(withoutBridges, ConnectedComponents.Flags.CreateComponents).Components;
442  }
443  }
444  }
445 
449  {
450  [Flags]
451  public enum Flags
452  {
453  None = 0,
455  CreateComponents = 1 << 0,
457  CreateCutvertices = 1 << 1
458  }
459 
461  public IGraph Graph { get; private set; }
463  public int Count { get; private set; }
466  public List<HashSet<Node>> Components { get; private set; }
471  public Dictionary<Node, int> Cutvertices { get; private set; }
472 
473  private class BlockDfs : LowpointDfs
474  {
475  public BiNodeConnectedComponents Parent;
476  private Stack<Node> blockStack;
477  private bool oneNodeComponent;
478 
479  protected override void Start(out Direction direction)
480  {
481  base.Start(out direction);
482  if (Parent.Components != null) blockStack = new Stack<Node>();
483  }
484 
485  protected override bool NodeEnter(Node node, Arc arc)
486  {
487  if (!base.NodeEnter(node, arc)) return false;
488 
489  if (Parent.Cutvertices != null && arc == Arc.Invalid) Parent.Cutvertices[node] = -1;
490  if (Parent.Components != null) blockStack.Push(node);
491  oneNodeComponent = (arc == Arc.Invalid);
492  return true;
493  }
494 
495  protected override bool NodeExit(Node node, Arc arc)
496  {
497  if (arc == Arc.Invalid)
498  {
499  if (oneNodeComponent)
500  {
501  Parent.Count++;
502  if (Parent.Components != null) Parent.Components.Add(new HashSet<Node> { node });
503  }
504 
505  if (Parent.Cutvertices != null && Parent.Cutvertices[node] == 0) Parent.Cutvertices.Remove(node);
506  if (Parent.Components != null) blockStack.Clear();
507  }
508  else
509  {
510  // parent is a cutvertex or root?
511  Node parent = Graph.Other(arc, node);
512  if (lowpoint[node] >= Level - 1)
513  {
514  if (Parent.Cutvertices != null)
515  {
516  int degree;
517  Parent.Cutvertices[parent] = (Parent.Cutvertices.TryGetValue(parent, out degree) ? degree : 0) + 1;
518  }
519 
520  Parent.Count++;
521  if (Parent.Components != null)
522  {
523  HashSet<Node> block = new HashSet<Node>();
524  while (true)
525  {
526  Node n = blockStack.Pop();
527  block.Add(n);
528  if (n == node) break;
529  }
530  block.Add(parent);
531  Parent.Components.Add(block);
532  }
533  }
534  }
535 
536  return base.NodeExit(node, arc);
537  }
538  }
539 
540  public BiNodeConnectedComponents(IGraph graph, Flags flags = 0)
541  {
542  Graph = graph;
543  if (0 != (flags & Flags.CreateComponents)) Components = new List<HashSet<Node>>();
544  if (0 != (flags & Flags.CreateCutvertices)) Cutvertices = new Dictionary<Node, int>();
545  new BlockDfs { Parent = this }.Run(graph);
546  }
547  }
548 
550  public static class FindPathExtensions
551  {
552  private class PathDfs : Dfs
553  {
554  // input
555  public Direction PathDirection;
556  public Func<Node, bool> IsTarget;
557 
558  // output
559  public Node StartNode;
560  public List<Arc> Path;
561  public Node EndNode;
562 
563  protected override void Start(out Direction direction)
564  {
565  direction = PathDirection;
566 
567  StartNode = Node.Invalid;
568  Path = new List<Arc>();
569  EndNode = Node.Invalid;
570  }
571 
572  protected override bool NodeEnter(Node node, Arc arc)
573  {
574  if (arc == Arc.Invalid)
575  StartNode = node;
576  else Path.Add(arc);
577 
578  if (IsTarget(node))
579  {
580  EndNode = node;
581  return false;
582  }
583 
584  return true;
585  }
586 
587  protected override bool NodeExit(Node node, Arc arc)
588  {
589  if (arc != Arc.Invalid && EndNode == Node.Invalid)
590  Path.RemoveAt(Path.Count - 1);
591  return true;
592  }
593  }
594 
600  public static IPath FindPath(this IGraph graph, IEnumerable<Node> source, Func<Node, bool> target,
601  Dfs.Direction direction)
602  {
603  var dfs = new PathDfs() { PathDirection = direction, IsTarget = target };
604  dfs.Run(graph, source);
605  if (dfs.EndNode == Node.Invalid) return null;
606 
607  var result = new Path(graph);
608  result.Begin(dfs.StartNode);
609  foreach (var arc in dfs.Path) result.AddLast(arc);
610  return result;
611  }
612 
614  public static IPath FindPath(this IGraph graph, Node source, Node target,
615  Dfs.Direction direction)
616  {
617  return FindPath(graph, new Node[] { source }, x => x == target, direction);
618  }
619  }
620 }