mcs/class/Mono.CodeContracts/Mono.CodeContracts.Static.DataStructures/DepthFirst.cs

   1 //
   2 // DepthFirst.cs
   3 //
   4 // Authors:
   5 //      Alexander Chebaturkin (chebaturkin@gmail.com)
   6 //
   7 // Copyright (C) 2011 Alexander Chebaturkin
   8 //
   9 // Permission is hereby granted, free of charge, to any person obtaining
  10 // a copy of this software and associated documentation files (the
  11 // "Software"), to deal in the Software without restriction, including
  12 // without limitation the rights to use, copy, modify, merge, publish,
  13 // distribute, sublicense, and/or sell copies of the Software, and to
  14 // permit persons to whom the Software is furnished to do so, subject to
  15 // the following conditions:
  16 //
  17 // The above copyright notice and this permission notice shall be
  18 // included in all copies or substantial portions of the Software.
  19 //
  20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  27 //
  28
  29 using System;
  30 using System.Collections.Generic;
  31
  32 namespace Mono.CodeContracts.Static.DataStructures {
  33         static class DepthFirst {
  34                 public static void Visit<Node, EdgeInfo> (IGraph<Node, EdgeInfo> graph,
  35                                                           Predicate<Node> nodeStartVisitor,
  36                                                           EdgeVisitor<Node, EdgeInfo> edgeVisitor)
  37                 {
  38                         new Visitor<Node, EdgeInfo> (graph, nodeStartVisitor, edgeVisitor).VisitAll ();
  39                 }
  40
  41                 public static void Visit<Node, EdgeInfo> (IGraph<Node, EdgeInfo> graph,
  42                                                           Node startNode,
  43                                                           Predicate<Node> nodeStartVisitor,
  44                                                           EdgeVisitor<Node, EdgeInfo> edgeVisitor)
  45                 {
  46                         new Visitor<Node, EdgeInfo> (graph, nodeStartVisitor, edgeVisitor).VisitSubGraphNonRecursive (startNode);
  47                 }
  48
  49                 #region Nested type: Info
  50                 public class Info<Node> {
  51                         public readonly Node Parent;
  52                         public readonly int StartTime;
  53
  54                         public int FinishTime;
  55                         public bool SourceOfBackEdge;
  56                         public bool TargetOfBackEdge;
  57
  58                         public Info (Node parent, int startTime)
  59                         {
  60                                 this.Parent = parent;
  61                                 this.StartTime = startTime;
  62                         }
  63                 }
  64                 #endregion
  65
  66                 #region Nested type: Visitor
  67                 public class Visitor<Node, Edge> {
  68                         private readonly HashSet<Tuple<Node, Edge, Node>> back_edges = new HashSet<Tuple<Node, Edge, Node>> ();
  69                         private readonly EdgeVisitor<Node, Edge> edge_visitor;
  70                         private readonly IGraph<Node, Edge> graph;
  71
  72                         private readonly Dictionary<Node, Info<Node>> history = new Dictionary<Node, Info<Node>> ();
  73                         private readonly Action<Node> node_finish_visitor;
  74                         private readonly Predicate<Node> node_start_visitor;
  75                         private readonly Stack<SearchFrame> todo = new Stack<SearchFrame> ();
  76                         private int time;
  77
  78                         public Visitor (IGraph<Node, Edge> graph, Predicate<Node> nodeStartVisitor, EdgeVisitor<Node, Edge> edgeVisitor)
  79                                 : this (graph, nodeStartVisitor, null, edgeVisitor)
  80                         {
  81                         }
  82
  83                         public Visitor (IGraph<Node, Edge> graph, Predicate<Node> nodeStartVisitor)
  84                                 : this (graph, nodeStartVisitor, null, null)
  85                         {
  86                         }
  87
  88                         public Visitor (IGraph<Node, Edge> graph, Predicate<Node> nodeStartVisitor, Action<Node> nodeFinishVisitor, EdgeVisitor<Node, Edge> edgeVisitor)
  89                         {
  90                                 this.graph = graph;
  91                                 this.node_start_visitor = nodeStartVisitor;
  92                                 this.node_finish_visitor = nodeFinishVisitor;
  93                                 this.edge_visitor = edgeVisitor;
  94                         }
  95
  96                         public virtual void VisitAll ()
  97                         {
  98                                 foreach (Node node in this.graph.Nodes)
  99                                         this.VisitSubGraphNonRecursive (node);
 100                         }
 101
 102                         public void VisitSubGraphNonRecursive (Node node)
 103                         {
 104                                 ScheduleNode (node, default(Node));
 105                                 IterativeDFS ();
 106                         }
 107
 108                         private void IterativeDFS ()
 109                         {
 110                                 while (this.todo.Count > 0) {
 111                                         SearchFrame frame = this.todo.Peek ();
 112                                         if (frame.Edges.MoveNext ()) {
 113                                                 Pair<Edge, Node> current = frame.Edges.Current;
 114                                                 VisitEdgeNonRecursive (frame.Info, frame.Node, current.Key, current.Value);
 115                                         } else {
 116                                                 if (this.node_finish_visitor != null)
 117                                                         this.node_finish_visitor (frame.Node);
 118                                                 frame.Info.FinishTime = ++this.time;
 119                                                 this.todo.Pop ();
 120                                         }
 121                                 }
 122                         }
 123
 124             private void VisitEdgeNonRecursive(Info<Node> sourceInfo, Node source, Edge info, Node target)
 125             {
 126                 if (!VisitEdgeCommon (sourceInfo, source, info, target))
 127                     ScheduleNode (target, source);
 128             }
 129
 130                     private void VisitEdge (Info<Node> sourceInfo, Node source, Edge info, Node target)
 131                     {
 132                         if (!VisitEdgeCommon (sourceInfo, source, info, target))
 133                             VisitSubGraph (target, source);
 134                     }
 135
 136                     private bool VisitEdgeCommon(Info<Node> sourceInfo, Node source, Edge info, Node target )
 137             {
 138                 if (this.edge_visitor != null)
 139                     this.edge_visitor(source, info, target);
 140
 141                 Info<Node> targetInfo;
 142                 if (this.history.TryGetValue(target, out targetInfo))
 143                 {
 144                     if (targetInfo.FinishTime != 0)
 145                         return true;
 146
 147                     targetInfo.TargetOfBackEdge = true;
 148                     sourceInfo.SourceOfBackEdge = true;
 149                     this.back_edges.Add(new Tuple<Node, Edge, Node>(source, info, target));
 150
 151                     return true;
 152                 }
 153
 154                         return false;
 155             }
 156
 157                     public void VisitSubGraph (Node node, Node parent)
 158                         {
 159                                 if (this.history.ContainsKey (node))
 160                                         return;
 161
 162                                 var info = new Info<Node> (parent, ++this.time);
 163                                 this.history [node] = info;
 164
 165                                 if (this.node_start_visitor != null && !this.node_start_visitor (node))
 166                                         return;
 167
 168                                 VisitSuccessors (info, node);
 169
 170                                 if (this.node_finish_visitor != null)
 171                                         this.node_finish_visitor (node);
 172
 173                                 info.FinishTime = ++this.time;
 174                         }
 175
 176                         public void ScheduleNode (Node node, Node parent)
 177                         {
 178                                 if (this.history.ContainsKey (node))
 179                                         return;
 180
 181                                 var info = new Info<Node> (parent, ++this.time);
 182                                 this.history [node] = info;
 183
 184                                 if (this.node_start_visitor != null && !this.node_start_visitor (node))
 185                                         return;
 186
 187                                 this.todo.Push (new SearchFrame (node, this.graph.Successors (node).GetEnumerator (), info));
 188                         }
 189
 190                         private void VisitSuccessors (Info<Node> info, Node node)
 191                         {
 192                                 foreach (var successor in this.graph.Successors (node))
 193                                         VisitEdge (info, node, successor.Key, successor.Value);
 194                         }
 195
 196                         public bool IsVisited (Node node)
 197                         {
 198                                 return this.history.ContainsKey (node);
 199                         }
 200
 201                         public bool IsBackEdge (Node source, Edge info, Node target)
 202                         {
 203                                 return this.back_edges.Contains (new Tuple<Node, Edge, Node> (source, info, target));
 204                         }
 205
 206                         public Info<Node> DepthFirstInfo (Node node)
 207                         {
 208                                 return this.history [node];
 209                         }
 210
 211                         #region Nested type: SearchFrame
 212                         private struct SearchFrame {
 213                                 public readonly IEnumerator<Pair<Edge, Node>> Edges;
 214                                 public readonly Info<Node> Info;
 215                                 public readonly Node Node;
 216
 217                                 public SearchFrame (Node node, IEnumerator<Pair<Edge, Node>> edges, Info<Node> info)
 218                                 {
 219                                         this.Node = node;
 220                                         this.Edges = edges;
 221                                         this.Info = info;
 222                                 }
 223                         }
 224                         #endregion
 225                 }
 226                 #endregion
 227         }
 228 }