UndirectedGraph.cs source code in C# .NET

Source code for the .NET framework in C#

                        
Code:

                         / 4.0 / 4.0 / untmp / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / DataEntity / System / Data / Map / Update / Internal / UndirectedGraph.cs / 1305376 / UndirectedGraph.cs
                        

                        
                            //---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner [....]
// @backupOwner [....] 
//--------------------------------------------------------------------- 

using System.Data.Common.Utils; 
using System.Collections.Generic;
using System.Text;
namespace System.Data.Mapping.Update.Internal {
    // Maintains a graph where the direction of the edges is not important 
    class UndirectedGraph : InternalBase {
 
        #region Constructor 
        internal UndirectedGraph(IEqualityComparer comparer) {
            m_graph = new Graph(comparer); 
            m_comparer = comparer;
        }
        #endregion
 
        #region Fields
        private Graph m_graph; // Directed graph where we added both edges 
        private IEqualityComparer m_comparer; 
        #endregion
 
        #region Properties
        internal IEnumerable Vertices {
            get { return m_graph.Vertices; }
        } 

        ///  
        /// Returns the edges of the graph 
        /// 
        internal IEnumerable> Edges { 
            get {
                return m_graph.Edges;
            }
        } 
        #endregion
 
        #region Methods 
        // effects: Adds a new node to the graph. Does nothing if the vertex already exists.
        internal void AddVertex(TVertex vertex) { 
            m_graph.AddVertex(vertex);
        }

        // requires: first and second must exist. An edge between first and 
        // second must not already exist
        // effects: Adds a new unidirectional edge to the graph. 
        internal void AddEdge(TVertex first, TVertex second) { 
            m_graph.AddEdge(first, second);
            m_graph.AddEdge(second, first); 
        }


        // effects: Given a graph of T, returns a map such that nodes in the 
        // same connected component are in the same list in the KeyToListMap
        internal KeyToListMap GenerateConnectedComponents() { 
            int count = 0; 
            // Set the "component number" for each node
            Dictionary componentMap = new Dictionary(m_comparer); 
            foreach (TVertex vertex in Vertices) {
                componentMap.Add(vertex, new ComponentNum(count));
                count++;
            } 

            // Run the connected components algorithm (Page 441 of the CLR -- Cormen, Rivest, Lieserson) 
            foreach (KeyValuePair edge in Edges) { 
                if (componentMap[edge.Key].componentNum != componentMap[edge.Value].componentNum) {
                    // Set the component numbers of both of the nodes to be the same 
                    int oldValue = componentMap[edge.Value].componentNum;
                    int newValue = componentMap[edge.Key].componentNum;
                    componentMap[edge.Value].componentNum = newValue;
                    // Since we are resetting edge.Value's component number, find all components whose value 
                    // is oldValue and reset it to the new value
                    foreach (TVertex vertex in componentMap.Keys) { 
                        if (componentMap[vertex].componentNum == oldValue) { 
                            componentMap[vertex].componentNum = newValue;
                        } 
                    }
                }
            }
 
            // Now just grab the vertices which have the same set numbers
            KeyToListMap result = new KeyToListMap(EqualityComparer.Default); 
            foreach (TVertex vertex in Vertices) { 
                int componentNum = componentMap[vertex].componentNum;
                result.Add(componentNum, vertex); 
            }
            return result;
        }
 

 
 
        internal override void ToCompactString(StringBuilder builder) {
            builder.Append(m_graph.ToString()); 
        }


        // A class just for ensuring that we do not modify the hash table 
        // while iterating over it. Keeps track of the component number for a
        // connected component 
        private class ComponentNum { 
            internal ComponentNum(int compNum) {
                componentNum = compNum; 
            }
            internal int componentNum;
            public override string ToString() {
                return StringUtil.FormatInvariant("{0}", componentNum); 
            }
 
        }; 
        #endregion
    } 
}

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.

Link Menu

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK