1 //--------------------------------------------------------------------- 2 // <copyright file="UndirectedGraph.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.Text; 13 namespace System.Data.Mapping.Update.Internal { 14 // Maintains a graph where the direction of the edges is not important 15 class UndirectedGraph<TVertex> : InternalBase { 16 17 #region Constructor UndirectedGraph(IEqualityComparer<TVertex> comparer)18 internal UndirectedGraph(IEqualityComparer<TVertex> comparer) { 19 m_graph = new Graph<TVertex>(comparer); 20 m_comparer = comparer; 21 } 22 #endregion 23 24 #region Fields 25 private Graph<TVertex> m_graph; // Directed graph where we added both edges 26 private IEqualityComparer<TVertex> m_comparer; 27 #endregion 28 29 #region Properties 30 internal IEnumerable<TVertex> Vertices { 31 get { return m_graph.Vertices; } 32 } 33 34 /// <summary> 35 /// Returns the edges of the graph 36 /// </summary> 37 internal IEnumerable<KeyValuePair<TVertex, TVertex>> Edges { 38 get { 39 return m_graph.Edges; 40 } 41 } 42 #endregion 43 44 #region Methods 45 // effects: Adds a new node to the graph. Does nothing if the vertex already exists. AddVertex(TVertex vertex)46 internal void AddVertex(TVertex vertex) { 47 m_graph.AddVertex(vertex); 48 } 49 50 // requires: first and second must exist. An edge between first and 51 // second must not already exist 52 // effects: Adds a new unidirectional edge to the graph. AddEdge(TVertex first, TVertex second)53 internal void AddEdge(TVertex first, TVertex second) { 54 m_graph.AddEdge(first, second); 55 m_graph.AddEdge(second, first); 56 } 57 58 59 // effects: Given a graph of T, returns a map such that nodes in the 60 // same connected component are in the same list in the KeyToListMap GenerateConnectedComponents()61 internal KeyToListMap<int, TVertex> GenerateConnectedComponents() { 62 int count = 0; 63 // Set the "component number" for each node 64 Dictionary<TVertex, ComponentNum> componentMap = new Dictionary<TVertex, ComponentNum>(m_comparer); 65 foreach (TVertex vertex in Vertices) { 66 componentMap.Add(vertex, new ComponentNum(count)); 67 count++; 68 } 69 70 // Run the connected components algorithm (Page 441 of the CLR -- Cormen, Rivest, Lieserson) 71 foreach (KeyValuePair<TVertex, TVertex> edge in Edges) { 72 if (componentMap[edge.Key].componentNum != componentMap[edge.Value].componentNum) { 73 // Set the component numbers of both of the nodes to be the same 74 int oldValue = componentMap[edge.Value].componentNum; 75 int newValue = componentMap[edge.Key].componentNum; 76 componentMap[edge.Value].componentNum = newValue; 77 // Since we are resetting edge.Value's component number, find all components whose value 78 // is oldValue and reset it to the new value 79 foreach (TVertex vertex in componentMap.Keys) { 80 if (componentMap[vertex].componentNum == oldValue) { 81 componentMap[vertex].componentNum = newValue; 82 } 83 } 84 } 85 } 86 87 // Now just grab the vertices which have the same set numbers 88 KeyToListMap<int, TVertex> result = new KeyToListMap<int, TVertex>(EqualityComparer<int>.Default); 89 foreach (TVertex vertex in Vertices) { 90 int componentNum = componentMap[vertex].componentNum; 91 result.Add(componentNum, vertex); 92 } 93 return result; 94 } 95 96 97 98 ToCompactString(StringBuilder builder)99 internal override void ToCompactString(StringBuilder builder) { 100 builder.Append(m_graph.ToString()); 101 } 102 103 104 // A class just for ensuring that we do not modify the hash table 105 // while iterating over it. Keeps track of the component number for a 106 // connected component 107 private class ComponentNum { ComponentNum(int compNum)108 internal ComponentNum(int compNum) { 109 componentNum = compNum; 110 } 111 internal int componentNum; ToString()112 public override string ToString() { 113 return StringUtil.FormatInvariant("{0}", componentNum); 114 } 115 116 }; 117 #endregion 118 } 119 } 120