Update/Internal/Graph.cs

//---------------------------------------------------------------------
// <copyright file="Graph.cs" company="Microsoft">
//      Copyright (c) Microsoft Corporation.  All rights reserved.
// </copyright>
//
// @owner Microsoft
// @backupOwner Microsoft
//---------------------------------------------------------------------

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
{
    /// <summary>
    /// A directed graph class.
    /// </summary>
    /// <remarks>
    /// Notes on language (in case you're familiar with one or the other convention):
    ///
    /// node == vertex
    /// arc == edge
    /// predecessor == incoming
    /// successor == outgoing
    /// </remarks>
    /// <typeparam name="TVertex">Type of nodes in the graph</typeparam>
    internal class Graph<TVertex>
    {
        #region Constructors
        /// <summary>
        /// Initialize a new graph
        /// </summary>
        /// <param name="comparer">Comparer used to determine if two node references are
        /// equivalent</param>
        internal Graph(IEqualityComparer<TVertex> comparer)
        {
            EntityUtil.CheckArgumentNull(comparer, "comparer");

            m_comparer = comparer;
            m_successorMap = new Dictionary<TVertex, HashSet<TVertex>>(comparer);
            m_predecessorCounts = new Dictionary<TVertex, int>(comparer);
            m_vertices = new HashSet<TVertex>(comparer);
        }
        #endregion

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

        /// <summary>
        /// Gets number of predecessors of the node.
        /// </summary>
        private readonly Dictionary<TVertex, int> m_predecessorCounts;

        /// <summary>
        /// Gets the vertices that exist in the graph.
        /// </summary>
        private readonly HashSet<TVertex> m_vertices;
        private readonly IEqualityComparer<TVertex> m_comparer;
        #endregion

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

        }

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

        }
        #endregion

        #region Methods
        /// <summary>
        /// Adds a new node to the graph. Does nothing if the vertex already exists.
        /// </summary>
        /// <param name="vertex">New node</param>
        internal void AddVertex(TVertex vertex)
        {
            m_vertices.Add(vertex);
        }

        /// <summary>
        /// Adds a new edge to the graph. NOTE: only adds edges for existing vertices.
        /// </summary>
        /// <param name="from">Source node</param>
        /// <param name="to">Target node</param>
        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<TVertex> successors;
                if (!m_successorMap.TryGetValue(from, out successors))
                {
                    successors = new HashSet<TVertex>(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;
                }
            }
        }

        /// <summary>
        /// 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))
        /// </summary>
        /// <returns>true if the sort succeeds; false if it fails and there is a remainder</returns>
        internal bool TryTopologicalSort(out IEnumerable<TVertex> orderedVertices, out IEnumerable<TVertex> remainder)
        {
            // populate all predecessor-less nodes to root queue
            var rootsPriorityQueue = new SortedSet<TVertex>(Comparer<TVertex>.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<TVertex> 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<TVertex>();
                return true;
            }
            else
            {
                orderedVertices = result.Take(resultCount);
                remainder = m_vertices;
                return false;
            }
        }

        /// <summary>
        /// For debugging purposes.
        /// </summary>
        /// <returns></returns>
        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();

            foreach (KeyValuePair<TVertex, HashSet<TVertex>> 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
    }
}