Graph.cs source code in C# .NET

Source code for the .NET framework in C#

                        
Code:

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

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

using System.Data.Common.Utils; 
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;
using System.Globalization; 
using System.Linq;
namespace System.Data.Mapping.Update.Internal 
{ 
    /// 
    /// A directed graph class. 
    /// 
    /// 
    /// Notes on language (in case you're familiar with one or the other convention):
    /// 
    /// node == vertex
    /// arc == edge 
    /// predecessor == incoming 
    /// successor == outgoing
    ///  
    /// Type of nodes in the graph
    internal class Graph
    {
        #region Constructors 
        /// 
        /// Initialize a new graph 
        ///  
        /// Comparer used to determine if two node references are
        /// equivalent 
        internal Graph(IEqualityComparer comparer)
        {
            EntityUtil.CheckArgumentNull(comparer, "comparer");
 
            m_comparer = comparer;
            m_successorMap = new Dictionary>(comparer); 
            m_predecessorCounts = new Dictionary(comparer); 
            m_vertices = new HashSet(comparer);
        } 
        #endregion

        #region Fields
        ///  
        /// Gets successors of the node (outgoing edges).
        ///  
        private readonly Dictionary> m_successorMap; 

        ///  
        /// Gets number of predecessors of the node.
        /// 
        private readonly Dictionary m_predecessorCounts;
 
        /// 
        /// Gets the vertices that exist in the graph. 
        ///  
        private readonly HashSet m_vertices;
        private readonly IEqualityComparer m_comparer; 
        #endregion

        #region Properties
        ///  
        /// Returns the vertices of the graph.
        ///  
        internal IEnumerable Vertices 
        {
            get { return m_vertices; } 

        }

        ///  
        /// Returns the edges of the graph in the form: [from, to]
        ///  
        internal IEnumerable> Edges 
        {
            get 
            {
                foreach (KeyValuePair> successors in m_successorMap)
                {
                    foreach (TVertex vertex in successors.Value) 
                    {
                        yield return new KeyValuePair(successors.Key, vertex); 
                    } 
                }
            } 

        }
        #endregion
 
        #region Methods
        ///  
        /// Adds a new node to the graph. Does nothing if the vertex already exists. 
        /// 
        /// New node 
        internal void AddVertex(TVertex vertex)
        {
            m_vertices.Add(vertex);
        } 

        ///  
        /// Adds a new edge to the graph. NOTE: only adds edges for existing vertices. 
        /// 
        /// Source node 
        /// Target node
        internal void AddEdge(TVertex from, TVertex to)
        {
            // Add only edges relevant to the current graph vertices 
            if (m_vertices.Contains(from) && m_vertices.Contains(to))
            { 
                HashSet successors; 
                if (!m_successorMap.TryGetValue(from, out successors))
                { 
                    successors = new HashSet(m_comparer);
                    m_successorMap.Add(from, successors);
                }
                if (successors.Add(to)) 
                {
                    // If the edge does not already exist, increment the count of incoming edges (predecessors). 
                    int predecessorCount; 
                    if (!m_predecessorCounts.TryGetValue(to, out predecessorCount))
                    { 
                        predecessorCount = 1;
                    }
                    else
                    { 
                        ++predecessorCount;
                    } 
                    m_predecessorCounts[to] = predecessorCount; 
                }
            } 
        }

        /// 
        /// DESTRUCTIVE OPERATION: performing a sort modifies the graph 
        /// Performs topological sort on graph. Nodes with no remaining incoming edges are removed
        /// in sort order (assumes elements implement IComparable(Of TVertex)) 
        ///  
        /// true if the sort succeeds; false if it fails and there is a remainder
        internal bool TryTopologicalSort(out IEnumerable orderedVertices, out IEnumerable remainder) 
        {
            // populate all predecessor-less nodes to root queue
            var rootsPriorityQueue = new SortedSet(Comparer.Default);
 
            foreach (TVertex vertex in m_vertices)
            { 
                int predecessorCount; 
                if (!m_predecessorCounts.TryGetValue(vertex, out predecessorCount) || 0 == predecessorCount)
                { 
                    rootsPriorityQueue.Add(vertex);
                }
            }
 
            var result = new TVertex[m_vertices.Count];
            int resultCount = 0; 
 
            // perform sort
            while (0 < rootsPriorityQueue.Count) 
            {
                // get the vertex that is next in line in the secondary ordering
                TVertex from = rootsPriorityQueue.Min;
                rootsPriorityQueue.Remove(from); 

                // remove all outgoing edges (free all vertices that depend on 'from') 
                HashSet toSet; 
                if (m_successorMap.TryGetValue(from, out toSet))
                { 
                    foreach (TVertex to in toSet)
                    {
                        int predecessorCount = m_predecessorCounts[to] - 1;
                        m_predecessorCounts[to] = predecessorCount; 
                        if (predecessorCount == 0)
                        { 
                            // 'to' contains no incoming edges, so it is now a root 
                            rootsPriorityQueue.Add(to);
                        } 
                    }

                    // remove the entire successor set since it has been emptied
                    m_successorMap.Remove(from); 
                }
 
                // add the freed vertex to the result and remove it from the graph 
                result[resultCount++] = from;
                m_vertices.Remove(from); 
            }

            // check that all elements were yielded
            if (m_vertices.Count == 0) 
            {
                // all vertices were ordered 
                orderedVertices = result; 
                remainder = Enumerable.Empty();
                return true; 
            }
            else
            {
                orderedVertices = result.Take(resultCount); 
                remainder = m_vertices;
                return false; 
            } 
        }
 
        /// 
        /// For debugging purposes.
        /// 
        ///  
        public override string ToString()
        { 
            StringBuilder sb = new StringBuilder(); 

            foreach (KeyValuePair> outgoingEdge in m_successorMap) 
            {
                bool first = true;

                sb.AppendFormat(CultureInfo.InvariantCulture, "[{0}] --> ", outgoingEdge.Key); 

                foreach (TVertex vertex in outgoingEdge.Value) 
                { 
                    if (first) { first = false; }
                    else { sb.Append(", "); } 
                    sb.AppendFormat(CultureInfo.InvariantCulture, "[{0}]", vertex);
                }

                sb.Append("; "); 
            }
 
            return sb.ToString(); 
        }
        #endregion 
    }
}

// File provided for Reference Use Only by Microsoft Corporation (c) 2007.
//---------------------------------------------------------------------- 
// 
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// 
// 
// @owner [....]
// @backupOwner [....] 
//--------------------------------------------------------------------- 

using System.Data.Common.Utils; 
using System.Collections.Generic;
using System.Diagnostics;
using System.Text;
using System.Globalization; 
using System.Linq;
namespace System.Data.Mapping.Update.Internal 
{ 
    /// 
    /// A directed graph class. 
    /// 
    /// 
    /// Notes on language (in case you're familiar with one or the other convention):
    /// 
    /// node == vertex
    /// arc == edge 
    /// predecessor == incoming 
    /// successor == outgoing
    ///  
    /// Type of nodes in the graph
    internal class Graph
    {
        #region Constructors 
        /// 
        /// Initialize a new graph 
        ///  
        /// Comparer used to determine if two node references are
        /// equivalent 
        internal Graph(IEqualityComparer comparer)
        {
            EntityUtil.CheckArgumentNull(comparer, "comparer");
 
            m_comparer = comparer;
            m_successorMap = new Dictionary>(comparer); 
            m_predecessorCounts = new Dictionary(comparer); 
            m_vertices = new HashSet(comparer);
        } 
        #endregion

        #region Fields
        ///  
        /// Gets successors of the node (outgoing edges).
        ///  
        private readonly Dictionary> m_successorMap; 

        ///  
        /// Gets number of predecessors of the node.
        /// 
        private readonly Dictionary m_predecessorCounts;
 
        /// 
        /// Gets the vertices that exist in the graph. 
        ///  
        private readonly HashSet m_vertices;
        private readonly IEqualityComparer m_comparer; 
        #endregion

        #region Properties
        ///  
        /// Returns the vertices of the graph.
        ///  
        internal IEnumerable Vertices 
        {
            get { return m_vertices; } 

        }

        ///  
        /// Returns the edges of the graph in the form: [from, to]
        ///  
        internal IEnumerable> Edges 
        {
            get 
            {
                foreach (KeyValuePair> successors in m_successorMap)
                {
                    foreach (TVertex vertex in successors.Value) 
                    {
                        yield return new KeyValuePair(successors.Key, vertex); 
                    } 
                }
            } 

        }
        #endregion
 
        #region Methods
        ///  
        /// Adds a new node to the graph. Does nothing if the vertex already exists. 
        /// 
        /// New node 
        internal void AddVertex(TVertex vertex)
        {
            m_vertices.Add(vertex);
        } 

        ///  
        /// Adds a new edge to the graph. NOTE: only adds edges for existing vertices. 
        /// 
        /// Source node 
        /// Target node
        internal void AddEdge(TVertex from, TVertex to)
        {
            // Add only edges relevant to the current graph vertices 
            if (m_vertices.Contains(from) && m_vertices.Contains(to))
            { 
                HashSet successors; 
                if (!m_successorMap.TryGetValue(from, out successors))
                { 
                    successors = new HashSet(m_comparer);
                    m_successorMap.Add(from, successors);
                }
                if (successors.Add(to)) 
                {
                    // If the edge does not already exist, increment the count of incoming edges (predecessors). 
                    int predecessorCount; 
                    if (!m_predecessorCounts.TryGetValue(to, out predecessorCount))
                    { 
                        predecessorCount = 1;
                    }
                    else
                    { 
                        ++predecessorCount;
                    } 
                    m_predecessorCounts[to] = predecessorCount; 
                }
            } 
        }

        /// 
        /// DESTRUCTIVE OPERATION: performing a sort modifies the graph 
        /// Performs topological sort on graph. Nodes with no remaining incoming edges are removed
        /// in sort order (assumes elements implement IComparable(Of TVertex)) 
        ///  
        /// true if the sort succeeds; false if it fails and there is a remainder
        internal bool TryTopologicalSort(out IEnumerable orderedVertices, out IEnumerable remainder) 
        {
            // populate all predecessor-less nodes to root queue
            var rootsPriorityQueue = new SortedSet(Comparer.Default);
 
            foreach (TVertex vertex in m_vertices)
            { 
                int predecessorCount; 
                if (!m_predecessorCounts.TryGetValue(vertex, out predecessorCount) || 0 == predecessorCount)
                { 
                    rootsPriorityQueue.Add(vertex);
                }
            }
 
            var result = new TVertex[m_vertices.Count];
            int resultCount = 0; 
 
            // perform sort
            while (0 < rootsPriorityQueue.Count) 
            {
                // get the vertex that is next in line in the secondary ordering
                TVertex from = rootsPriorityQueue.Min;
                rootsPriorityQueue.Remove(from); 

                // remove all outgoing edges (free all vertices that depend on 'from') 
                HashSet toSet; 
                if (m_successorMap.TryGetValue(from, out toSet))
                { 
                    foreach (TVertex to in toSet)
                    {
                        int predecessorCount = m_predecessorCounts[to] - 1;
                        m_predecessorCounts[to] = predecessorCount; 
                        if (predecessorCount == 0)
                        { 
                            // 'to' contains no incoming edges, so it is now a root 
                            rootsPriorityQueue.Add(to);
                        } 
                    }

                    // remove the entire successor set since it has been emptied
                    m_successorMap.Remove(from); 
                }
 
                // add the freed vertex to the result and remove it from the graph 
                result[resultCount++] = from;
                m_vertices.Remove(from); 
            }

            // check that all elements were yielded
            if (m_vertices.Count == 0) 
            {
                // all vertices were ordered 
                orderedVertices = result; 
                remainder = Enumerable.Empty();
                return true; 
            }
            else
            {
                orderedVertices = result.Take(resultCount); 
                remainder = m_vertices;
                return false; 
            } 
        }
 
        /// 
        /// For debugging purposes.
        /// 
        ///  
        public override string ToString()
        { 
            StringBuilder sb = new StringBuilder(); 

            foreach (KeyValuePair> outgoingEdge in m_successorMap) 
            {
                bool first = true;

                sb.AppendFormat(CultureInfo.InvariantCulture, "[{0}] --> ", outgoingEdge.Key); 

                foreach (TVertex vertex in outgoingEdge.Value) 
                { 
                    if (first) { first = false; }
                    else { sb.Append(", "); } 
                    sb.AppendFormat(CultureInfo.InvariantCulture, "[{0}]", vertex);
                }

                sb.Append("; "); 
            }
 
            return sb.ToString(); 
        }
        #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