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(IEqualityComparercomparer) { 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 Dictionarym_predecessorCounts; /// /// Gets the vertices that exist in the graph. /// private readonly HashSetm_vertices; private readonly IEqualityComparer m_comparer; #endregion #region Properties /// /// Returns the vertices of the graph. /// internal IEnumerableVertices { 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)) { HashSetsuccessors; 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 IEnumerableorderedVertices, 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(IEqualityComparercomparer) { 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 Dictionarym_predecessorCounts; /// /// Gets the vertices that exist in the graph. /// private readonly HashSetm_vertices; private readonly IEqualityComparer m_comparer; #endregion #region Properties /// /// Returns the vertices of the graph. /// internal IEnumerableVertices { 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)) { HashSetsuccessors; 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 IEnumerableorderedVertices, 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
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- SmiRecordBuffer.cs
- ExternalCalls.cs
- LinqDataSource.cs
- CalendarTable.cs
- DateBoldEvent.cs
- CorrelationManager.cs
- DocumentApplicationJournalEntry.cs
- ClipboardData.cs
- KnownTypesHelper.cs
- IFlowDocumentViewer.cs
- TagNameToTypeMapper.cs
- PersonalizationState.cs
- EntityTransaction.cs
- Point3DAnimationUsingKeyFrames.cs
- DragDropManager.cs
- RecordsAffectedEventArgs.cs
- BridgeDataRecord.cs
- XmlUtilWriter.cs
- ReturnValue.cs
- MethodAccessException.cs
- Baml2006ReaderFrame.cs
- ThemeableAttribute.cs
- FastPropertyAccessor.cs
- HttpProfileBase.cs
- BindToObject.cs
- TextEffect.cs
- MediaTimeline.cs
- x509store.cs
- WebBaseEventKeyComparer.cs
- AutomationTextAttribute.cs
- StringWriter.cs
- SynchronizedMessageSource.cs
- MouseWheelEventArgs.cs
- ProcessHostServerConfig.cs
- Message.cs
- CultureMapper.cs
- UrlPath.cs
- SectionInformation.cs
- WebPartEditVerb.cs
- UserPersonalizationStateInfo.cs
- SQLDecimalStorage.cs
- AssemblyNameProxy.cs
- DataPager.cs
- DocumentManager.cs
- FrameSecurityDescriptor.cs
- NamespaceInfo.cs
- ComponentCodeDomSerializer.cs
- NullableIntSumAggregationOperator.cs
- DataGridPagerStyle.cs
- InstanceKeyCompleteException.cs
- RequiredFieldValidator.cs
- PerformanceCounterPermissionEntry.cs
- MetaType.cs
- QuaternionAnimation.cs
- EncryptedKeyIdentifierClause.cs
- SignedXml.cs
- DragEventArgs.cs
- SecurityContextKeyIdentifierClause.cs
- FragmentQueryProcessor.cs
- ToolStripSeparatorRenderEventArgs.cs
- ListBoxItemAutomationPeer.cs
- IntPtr.cs
- XmlCDATASection.cs
- PopOutPanel.cs
- MemberRestriction.cs
- SecurityException.cs
- DoubleConverter.cs
- MarkerProperties.cs
- XmlNode.cs
- MetadataItemSerializer.cs
- XmlObjectSerializerReadContextComplex.cs
- AutomationPatternInfo.cs
- DataGridViewRowHeightInfoNeededEventArgs.cs
- TypefaceMetricsCache.cs
- ModifierKeysValueSerializer.cs
- OdbcConnectionStringbuilder.cs
- DataSourceSelectArguments.cs
- DataGridViewCellParsingEventArgs.cs
- Paragraph.cs
- PassportAuthenticationEventArgs.cs
- DataGridViewButtonColumn.cs
- UpdatePanelControlTrigger.cs
- ChameleonKey.cs
- PropertyGridEditorPart.cs
- CultureTable.cs
- DefaultParameterValueAttribute.cs
- IdnMapping.cs
- IntSecurity.cs
- ReservationNotFoundException.cs
- xamlnodes.cs
- ImageInfo.cs
- NonPrimarySelectionGlyph.cs
- ErrorRuntimeConfig.cs
- XPathMessageFilterElement.cs
- KnownBoxes.cs
- X509Utils.cs
- FlowLayout.cs
- GAC.cs
- DbConnectionFactory.cs
- DbProviderServices.cs