1 //--------------------------------------------------------------------- 2 // <copyright file="Graph.cs" company="Microsoft"> 3 // Copyright (c) Microsoft Corporation. All rights reserved. 4 // </copyright> 5 // 6 // @owner Microsoft 7 // @backupOwner Microsoft 8 //--------------------------------------------------------------------- 9 10 using System.Data.Common.Utils; 11 using System.Collections.Generic; 12 using System.Diagnostics; 13 using System.Text; 14 using System.Globalization; 15 using System.Linq; 16 namespace System.Data.Mapping.Update.Internal 17 { 18 /// <summary> 19 /// A directed graph class. 20 /// </summary> 21 /// <remarks> 22 /// Notes on language (in case you're familiar with one or the other convention): 23 /// 24 /// node == vertex 25 /// arc == edge 26 /// predecessor == incoming 27 /// successor == outgoing 28 /// </remarks> 29 /// <typeparam name="TVertex">Type of nodes in the graph</typeparam> 30 internal class Graph<TVertex> 31 { 32 #region Constructors 33 /// <summary> 34 /// Initialize a new graph 35 /// </summary> 36 /// <param name="comparer">Comparer used to determine if two node references are 37 /// equivalent</param> Graph(IEqualityComparer<TVertex> comparer)38 internal Graph(IEqualityComparer<TVertex> comparer) 39 { 40 EntityUtil.CheckArgumentNull(comparer, "comparer"); 41 42 m_comparer = comparer; 43 m_successorMap = new Dictionary<TVertex, HashSet<TVertex>>(comparer); 44 m_predecessorCounts = new Dictionary<TVertex, int>(comparer); 45 m_vertices = new HashSet<TVertex>(comparer); 46 } 47 #endregion 48 49 #region Fields 50 /// <summary> 51 /// Gets successors of the node (outgoing edges). 52 /// </summary> 53 private readonly Dictionary<TVertex, HashSet<TVertex>> m_successorMap; 54 55 /// <summary> 56 /// Gets number of predecessors of the node. 57 /// </summary> 58 private readonly Dictionary<TVertex, int> m_predecessorCounts; 59 60 /// <summary> 61 /// Gets the vertices that exist in the graph. 62 /// </summary> 63 private readonly HashSet<TVertex> m_vertices; 64 private readonly IEqualityComparer<TVertex> m_comparer; 65 #endregion 66 67 #region Properties 68 /// <summary> 69 /// Returns the vertices of the graph. 70 /// </summary> 71 internal IEnumerable<TVertex> Vertices 72 { 73 get { return m_vertices; } 74 75 } 76 77 /// <summary> 78 /// Returns the edges of the graph in the form: [from, to] 79 /// </summary> 80 internal IEnumerable<KeyValuePair<TVertex, TVertex>> Edges 81 { 82 get 83 { 84 foreach (KeyValuePair<TVertex, HashSet<TVertex>> successors in m_successorMap) 85 { 86 foreach (TVertex vertex in successors.Value) 87 { 88 yield return new KeyValuePair<TVertex, TVertex>(successors.Key, vertex); 89 } 90 } 91 } 92 93 } 94 #endregion 95 96 #region Methods 97 /// <summary> 98 /// Adds a new node to the graph. Does nothing if the vertex already exists. 99 /// </summary> 100 /// <param name="vertex">New node</param> AddVertex(TVertex vertex)101 internal void AddVertex(TVertex vertex) 102 { 103 m_vertices.Add(vertex); 104 } 105 106 /// <summary> 107 /// Adds a new edge to the graph. NOTE: only adds edges for existing vertices. 108 /// </summary> 109 /// <param name="from">Source node</param> 110 /// <param name="to">Target node</param> AddEdge(TVertex from, TVertex to)111 internal void AddEdge(TVertex from, TVertex to) 112 { 113 // Add only edges relevant to the current graph vertices 114 if (m_vertices.Contains(from) && m_vertices.Contains(to)) 115 { 116 HashSet<TVertex> successors; 117 if (!m_successorMap.TryGetValue(from, out successors)) 118 { 119 successors = new HashSet<TVertex>(m_comparer); 120 m_successorMap.Add(from, successors); 121 } 122 if (successors.Add(to)) 123 { 124 // If the edge does not already exist, increment the count of incoming edges (predecessors). 125 int predecessorCount; 126 if (!m_predecessorCounts.TryGetValue(to, out predecessorCount)) 127 { 128 predecessorCount = 1; 129 } 130 else 131 { 132 ++predecessorCount; 133 } 134 m_predecessorCounts[to] = predecessorCount; 135 } 136 } 137 } 138 139 /// <summary> 140 /// DESTRUCTIVE OPERATION: performing a sort modifies the graph 141 /// Performs topological sort on graph. Nodes with no remaining incoming edges are removed 142 /// in sort order (assumes elements implement IComparable(Of TVertex)) 143 /// </summary> 144 /// <returns>true if the sort succeeds; false if it fails and there is a remainder</returns> TryTopologicalSort(out IEnumerable<TVertex> orderedVertices, out IEnumerable<TVertex> remainder)145 internal bool TryTopologicalSort(out IEnumerable<TVertex> orderedVertices, out IEnumerable<TVertex> remainder) 146 { 147 // populate all predecessor-less nodes to root queue 148 var rootsPriorityQueue = new SortedSet<TVertex>(Comparer<TVertex>.Default); 149 150 foreach (TVertex vertex in m_vertices) 151 { 152 int predecessorCount; 153 if (!m_predecessorCounts.TryGetValue(vertex, out predecessorCount) || 0 == predecessorCount) 154 { 155 rootsPriorityQueue.Add(vertex); 156 } 157 } 158 159 var result = new TVertex[m_vertices.Count]; 160 int resultCount = 0; 161 162 // perform sort 163 while (0 < rootsPriorityQueue.Count) 164 { 165 // get the vertex that is next in line in the secondary ordering 166 TVertex from = rootsPriorityQueue.Min; 167 rootsPriorityQueue.Remove(from); 168 169 // remove all outgoing edges (free all vertices that depend on 'from') 170 HashSet<TVertex> toSet; 171 if (m_successorMap.TryGetValue(from, out toSet)) 172 { 173 foreach (TVertex to in toSet) 174 { 175 int predecessorCount = m_predecessorCounts[to] - 1; 176 m_predecessorCounts[to] = predecessorCount; 177 if (predecessorCount == 0) 178 { 179 // 'to' contains no incoming edges, so it is now a root 180 rootsPriorityQueue.Add(to); 181 } 182 } 183 184 // remove the entire successor set since it has been emptied 185 m_successorMap.Remove(from); 186 } 187 188 // add the freed vertex to the result and remove it from the graph 189 result[resultCount++] = from; 190 m_vertices.Remove(from); 191 } 192 193 // check that all elements were yielded 194 if (m_vertices.Count == 0) 195 { 196 // all vertices were ordered 197 orderedVertices = result; 198 remainder = Enumerable.Empty<TVertex>(); 199 return true; 200 } 201 else 202 { 203 orderedVertices = result.Take(resultCount); 204 remainder = m_vertices; 205 return false; 206 } 207 } 208 209 /// <summary> 210 /// For debugging purposes. 211 /// </summary> 212 /// <returns></returns> ToString()213 public override string ToString() 214 { 215 StringBuilder sb = new StringBuilder(); 216 217 foreach (KeyValuePair<TVertex, HashSet<TVertex>> outgoingEdge in m_successorMap) 218 { 219 bool first = true; 220 221 sb.AppendFormat(CultureInfo.InvariantCulture, "[{0}] --> ", outgoingEdge.Key); 222 223 foreach (TVertex vertex in outgoingEdge.Value) 224 { 225 if (first) { first = false; } 226 else { sb.Append(", "); } 227 sb.AppendFormat(CultureInfo.InvariantCulture, "[{0}]", vertex); 228 } 229 230 sb.Append("; "); 231 } 232 233 return sb.ToString(); 234 } 235 #endregion 236 } 237 } 238