Code:
/ Dotnetfx_Vista_SP2 / Dotnetfx_Vista_SP2 / 8.0.50727.4016 / DEVDIV / depot / DevDiv / releases / Orcas / QFE / ndp / fx / src / DataEntity / System / Data / Map / Update / Internal / Graph.cs / 2 / 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(IEqualityComparercomparer) { 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 HashSetVertices { 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 HashSetRemainder { 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 IEnumerableTryStagedTopologicalSort() { // 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(IEqualityComparercomparer) : 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"); Setchildren; 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"); Setchildren = 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(IEqualityComparercomparer) { 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 HashSetVertices { 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 HashSetRemainder { 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 IEnumerableTryStagedTopologicalSort() { // 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(IEqualityComparercomparer) : 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"); Setchildren; 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"); Setchildren = 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
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- MsdtcClusterUtils.cs
- ResizeGrip.cs
- DelegateBodyWriter.cs
- JsonEncodingStreamWrapper.cs
- WebPartConnection.cs
- ReadWriteSpinLock.cs
- DbParameterCollectionHelper.cs
- CallbackValidator.cs
- DbUpdateCommandTree.cs
- CodeExporter.cs
- NumberSubstitution.cs
- ActiveXHost.cs
- MaterialGroup.cs
- SmtpTransport.cs
- BaseComponentEditor.cs
- dataprotectionpermission.cs
- DbgUtil.cs
- UserControlParser.cs
- UrlMappingCollection.cs
- SqlWebEventProvider.cs
- XmlBinaryReader.cs
- DataPagerFieldCommandEventArgs.cs
- JulianCalendar.cs
- Rijndael.cs
- SoapIncludeAttribute.cs
- ByteStream.cs
- BidOverLoads.cs
- Content.cs
- ObjectIDGenerator.cs
- BinaryObjectReader.cs
- XmlObjectSerializerReadContext.cs
- WizardForm.cs
- LinqDataSourceSelectEventArgs.cs
- FillErrorEventArgs.cs
- OleDbCommandBuilder.cs
- HtmlObjectListAdapter.cs
- columnmapkeybuilder.cs
- ReadOnlyMetadataCollection.cs
- UnmanagedMemoryStream.cs
- HtmlButton.cs
- ImageListDesigner.cs
- EventTrigger.cs
- ReadOnlyPropertyMetadata.cs
- DefaultHttpHandler.cs
- Size3D.cs
- StructuredTypeEmitter.cs
- ExpanderAutomationPeer.cs
- StateMachineSubscription.cs
- SecurityKeyType.cs
- DataGridParentRows.cs
- PageRequestManager.cs
- SelectionEditingBehavior.cs
- Token.cs
- Highlights.cs
- DrawingImage.cs
- QueryOperationResponseOfT.cs
- TreeWalker.cs
- EntityParameter.cs
- ArrayList.cs
- ToolStripItemEventArgs.cs
- InkCanvasInnerCanvas.cs
- TrackingSection.cs
- AsyncPostBackTrigger.cs
- UrlAuthFailureHandler.cs
- DataGridView.cs
- ComponentEvent.cs
- SslStream.cs
- DataTableClearEvent.cs
- InputBinding.cs
- SqlCacheDependencySection.cs
- TimersDescriptionAttribute.cs
- SQLBinaryStorage.cs
- WindowsListViewItem.cs
- RadioButton.cs
- SectionUpdates.cs
- DES.cs
- InstancePersistenceException.cs
- ReadOnlyPropertyMetadata.cs
- DataViewManager.cs
- PenLineCapValidation.cs
- DefaultValueTypeConverter.cs
- SecurityKeyType.cs
- IMembershipProvider.cs
- ScrollProviderWrapper.cs
- _ProxyChain.cs
- FontClient.cs
- AsymmetricAlgorithm.cs
- PrinterUnitConvert.cs
- MailAddress.cs
- CodePrimitiveExpression.cs
- cookie.cs
- EnvironmentPermission.cs
- DefaultAutoFieldGenerator.cs
- WindowsSolidBrush.cs
- TextParaClient.cs
- NotifyParentPropertyAttribute.cs
- TextEditorContextMenu.cs
- PartitionResolver.cs
- UniqueEventHelper.cs
- SchemaCollectionCompiler.cs