mcs/class/referencesource/System.Data.Entity/System/Data/Mapping/Update/Internal/UndirectedGraph.cs

   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
  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.
  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.
  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
  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
  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 {
 108             internal ComponentNum(int compNum) {
 109                 componentNum = compNum;
 110             }
 111             internal int componentNum;
 112             public override string ToString() {
 113                 return StringUtil.FormatInvariant("{0}", componentNum);
 114             }
 115
 116         };
 117         #endregion
 118     }
 119 }