Graph.cs source code in C# .NET

                        Code:
                         / Net / Net / 3.5.50727.3053 / DEVDIV / depot / DevDiv / releases / Orcas / SP / ndp / fx / src / DataEntity / System / Data / Map / Update / Internal / Graph.cs / 3 / 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; 
namespace System.Data.Mapping.Update.Internal
{ 
    ///  
    /// A directed graph class.
    ///  
    /// 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_outgoingEdgeMap = new EdgeMap(comparer); 
            m_incomingEdgeMap = new EdgeMap(comparer); 
            m_vertices = new HashSet(comparer);
        } 
        #endregion

        #region Fields
        private EdgeMap m_outgoingEdgeMap; 
        private EdgeMap m_incomingEdgeMap;
        private HashSet m_vertices; 
        private IEqualityComparer m_comparer; 
        private HashSet m_remainder;
        #endregion 

        #region Properties
        /// 
        /// Returns the vertices of the graph (DO NOT MODIFY DIRECTLY) 
        /// 
        internal HashSet Vertices 
        { 
            get { return m_vertices; }
 
        }

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

        /// 
        /// After a topological sort, contains vertices for which no legal order exists 
        /// (they participate in a circular dependency). Must not be called before a sort
        /// has been performed. 
        ///  
        internal HashSet Remainder
        { 
            get
            {
                Debug.Assert(null != m_remainder, "Remainder property cannot be retrieved before a sort has been performed");
                return m_remainder; 
            }
        } 
        #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,
        /// do not attempt to re-add an existing edge.
        ///  
        /// 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))
            {
                m_outgoingEdgeMap.Add(from, to);
                m_incomingEdgeMap.Add(to, from); 
            }
        } 
 
        /// 
        /// Removes an edge from the graph. 
        /// 
        /// Source node
        /// Target node
        private void RemoveEdge(TVertex from, TVertex to) 
        {
            m_outgoingEdgeMap.Remove(from, to); 
            m_incomingEdgeMap.Remove(to, from); 
        }
 
        /// 
        /// DESTRUCTIVE OPERATION
        /// See TryTopologicalSort for details. This variation returns sets of vertices
        /// at each depth in the graph. 
        /// 
        /// Sets of vertices at each depth in the graph 
        internal IEnumerable TryStagedTopologicalSort() 
        {
            // populate all predecessor-less nodes to root queue 
            Stack roots = new Stack();

            foreach (TVertex vertex in m_vertices)
            { 
                if (!m_incomingEdgeMap.ContainsKey(vertex))
                { 
                    roots.Push(vertex); 
                }
            } 

            // perform sort
            while (0 < roots.Count)
            { 
                // gather all vertices at the current depth (all 'roots')
                TVertex[] froms = new TVertex[roots.Count]; 
                int index = 0; 
                while (0 < roots.Count)
                { 
                    froms[index] = roots.Pop();
                    index++;
                }
                yield return froms; 

                // now remove all vertices at the current depth from the graph 
                foreach (TVertex from in froms) 
                {
                    m_vertices.Remove(from); 

                    Set toSet;

                    if (m_outgoingEdgeMap.TryGetValue(from, out toSet)) 
                    {
                        // copy successor set to a list so that the set can be modified 
                        // as the list is enumerated 
                        List toList = new List(toSet);
 
                        foreach (TVertex to in toList)
                        {
                            RemoveEdge(from, to);
                            if (!m_incomingEdgeMap.ContainsKey(to)) 
                            {
                                // 'to' now contains no incoming arcs, so it is now a root 
                                roots.Push(to); 
                            }
                        } 
                    }
                }
            }
 
            // Check that all elements were yielded
            m_remainder = m_vertices; 
 
            yield break;
        } 

        /// 
        /// For debugging purposes.
        ///  
        /// 
        public override string ToString() 
        { 
            StringBuilder sb = new StringBuilder();
 
            foreach (KeyValuePair> outgoingEdge in m_outgoingEdgeMap)
            {
                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

        #region Nested types
        ///  
        /// Maps from node to adjacent nodes (edges)
        ///  
        private class EdgeMap : Dictionary> 
        {
            ///  
            /// Constructs a new edge map
            /// 
            /// Comparer used to determine if two node
            /// references are equivalent. 
            internal EdgeMap(IEqualityComparer comparer)
                : base(comparer) 
            { 
                m_comparer = comparer;
            } 

            private IEqualityComparer m_comparer;

            ///  
            /// Adds a new edge between two adjacent nodes. If the edge already exists, does nothing.
            ///  
            /// Node for which to add a map entry 
            /// Node to map from the key
            internal void Add(TVertex key, TVertex valueElement) 
            {
                Debug.Assert(null != key && null != valueElement, "Caller must verify arguments are not null");

                Set children; 

                if (!TryGetValue(key, out children)) 
                { 
                    children = new Set(m_comparer);
                    Add(key, children); 
                }

                if (!children.Contains(valueElement))
                { 
                    children.Add(valueElement);
                } 
            } 

            ///  
            /// Removes an edge between two adjacent nodes. Assumes the edge
            /// exists.
            /// 
            /// Node for which to remove a map entry 
            /// Mapped node
            internal void Remove(TVertex key, TVertex valueElement) 
            { 
                Debug.Assert(null != key && null != valueElement, "Caller must verify arguments are not null");
                Debug.Assert(base.ContainsKey(key) && base[key].Contains(valueElement), "Caller must not remove edge that does not exist"); 

                Set children = base[key];

                children.Remove(valueElement); 

                if (0 == children.Count) 
                { 
                    base.Remove(key);
                } 
            }
        }
        #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; 
namespace System.Data.Mapping.Update.Internal
{ 
    ///  
    /// A directed graph class.
    ///  
    /// 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_outgoingEdgeMap = new EdgeMap(comparer); 
            m_incomingEdgeMap = new EdgeMap(comparer); 
            m_vertices = new HashSet(comparer);
        } 
        #endregion

        #region Fields
        private EdgeMap m_outgoingEdgeMap; 
        private EdgeMap m_incomingEdgeMap;
        private HashSet m_vertices; 
        private IEqualityComparer m_comparer; 
        private HashSet m_remainder;
        #endregion 

        #region Properties
        /// 
        /// Returns the vertices of the graph (DO NOT MODIFY DIRECTLY) 
        /// 
        internal HashSet Vertices 
        { 
            get { return m_vertices; }
 
        }

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

        /// 
        /// After a topological sort, contains vertices for which no legal order exists 
        /// (they participate in a circular dependency). Must not be called before a sort
        /// has been performed. 
        ///  
        internal HashSet Remainder
        { 
            get
            {
                Debug.Assert(null != m_remainder, "Remainder property cannot be retrieved before a sort has been performed");
                return m_remainder; 
            }
        } 
        #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,
        /// do not attempt to re-add an existing edge.
        ///  
        /// 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))
            {
                m_outgoingEdgeMap.Add(from, to);
                m_incomingEdgeMap.Add(to, from); 
            }
        } 
 
        /// 
        /// Removes an edge from the graph. 
        /// 
        /// Source node
        /// Target node
        private void RemoveEdge(TVertex from, TVertex to) 
        {
            m_outgoingEdgeMap.Remove(from, to); 
            m_incomingEdgeMap.Remove(to, from); 
        }
 
        /// 
        /// DESTRUCTIVE OPERATION
        /// See TryTopologicalSort for details. This variation returns sets of vertices
        /// at each depth in the graph. 
        /// 
        /// Sets of vertices at each depth in the graph 
        internal IEnumerable TryStagedTopologicalSort() 
        {
            // populate all predecessor-less nodes to root queue 
            Stack roots = new Stack();

            foreach (TVertex vertex in m_vertices)
            { 
                if (!m_incomingEdgeMap.ContainsKey(vertex))
                { 
                    roots.Push(vertex); 
                }
            } 

            // perform sort
            while (0 < roots.Count)
            { 
                // gather all vertices at the current depth (all 'roots')
                TVertex[] froms = new TVertex[roots.Count]; 
                int index = 0; 
                while (0 < roots.Count)
                { 
                    froms[index] = roots.Pop();
                    index++;
                }
                yield return froms; 

                // now remove all vertices at the current depth from the graph 
                foreach (TVertex from in froms) 
                {
                    m_vertices.Remove(from); 

                    Set toSet;

                    if (m_outgoingEdgeMap.TryGetValue(from, out toSet)) 
                    {
                        // copy successor set to a list so that the set can be modified 
                        // as the list is enumerated 
                        List toList = new List(toSet);
 
                        foreach (TVertex to in toList)
                        {
                            RemoveEdge(from, to);
                            if (!m_incomingEdgeMap.ContainsKey(to)) 
                            {
                                // 'to' now contains no incoming arcs, so it is now a root 
                                roots.Push(to); 
                            }
                        } 
                    }
                }
            }
 
            // Check that all elements were yielded
            m_remainder = m_vertices; 
 
            yield break;
        } 

        /// 
        /// For debugging purposes.
        ///  
        /// 
        public override string ToString() 
        { 
            StringBuilder sb = new StringBuilder();
 
            foreach (KeyValuePair> outgoingEdge in m_outgoingEdgeMap)
            {
                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

        #region Nested types
        ///  
        /// Maps from node to adjacent nodes (edges)
        ///  
        private class EdgeMap : Dictionary> 
        {
            ///  
            /// Constructs a new edge map
            /// 
            /// Comparer used to determine if two node
            /// references are equivalent. 
            internal EdgeMap(IEqualityComparer comparer)
                : base(comparer) 
            { 
                m_comparer = comparer;
            } 

            private IEqualityComparer m_comparer;

            ///  
            /// Adds a new edge between two adjacent nodes. If the edge already exists, does nothing.
            ///  
            /// Node for which to add a map entry 
            /// Node to map from the key
            internal void Add(TVertex key, TVertex valueElement) 
            {
                Debug.Assert(null != key && null != valueElement, "Caller must verify arguments are not null");

                Set children; 

                if (!TryGetValue(key, out children)) 
                { 
                    children = new Set(m_comparer);
                    Add(key, children); 
                }

                if (!children.Contains(valueElement))
                { 
                    children.Add(valueElement);
                } 
            } 

            ///  
            /// Removes an edge between two adjacent nodes. Assumes the edge
            /// exists.
            /// 
            /// Node for which to remove a map entry 
            /// Mapped node
            internal void Remove(TVertex key, TVertex valueElement) 
            { 
                Debug.Assert(null != key && null != valueElement, "Caller must verify arguments are not null");
                Debug.Assert(base.ContainsKey(key) && base[key].Contains(valueElement), "Caller must not remove edge that does not exist"); 

                Set children = base[key];

                children.Remove(valueElement); 

                if (0 == children.Count) 
                { 
                    base.Remove(key);
                } 
            }
        }
        #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
Graph.cs source code in C# .NET

Source code for the .NET framework in C#

Code:

Link Menu
