Code:
/ Dotnetfx_Win7_3.5.1 / Dotnetfx_Win7_3.5.1 / 3.5.1 / DEVDIV / depot / DevDiv / releases / Orcas / NetFXw7 / ndp / fx / src / DataEntity / System / Data / Map / Update / Internal / Graph.cs / 1 / 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
- ScriptModule.cs
- LocalizableResourceBuilder.cs
- NamedObject.cs
- BinaryObjectReader.cs
- PrintingPermissionAttribute.cs
- LabelDesigner.cs
- Axis.cs
- ServiceModelPerformanceCounters.cs
- AssemblyInfo.cs
- ButtonFlatAdapter.cs
- MonitorWrapper.cs
- SafeNativeMemoryHandle.cs
- WinEventWrap.cs
- XmlSchemaType.cs
- PeerDuplexChannel.cs
- DataGridViewCellConverter.cs
- GeometryModel3D.cs
- Rect3DConverter.cs
- ToolboxItemSnapLineBehavior.cs
- FullTextBreakpoint.cs
- Error.cs
- TextStore.cs
- APCustomTypeDescriptor.cs
- InvalidDataException.cs
- UserValidatedEventArgs.cs
- DynamicQueryStringParameter.cs
- VirtualPath.cs
- ExtendedProtectionPolicyElement.cs
- OdbcConnectionOpen.cs
- ActivityStateRecord.cs
- AndAlso.cs
- GenericIdentity.cs
- designeractionbehavior.cs
- ContextMenu.cs
- FixedSOMPage.cs
- DirectoryInfo.cs
- TableLayoutSettings.cs
- ItemCheckEvent.cs
- TextSegment.cs
- ManualResetEvent.cs
- IPipelineRuntime.cs
- ExpandableObjectConverter.cs
- OleDbConnectionPoolGroupProviderInfo.cs
- PageStatePersister.cs
- CodeStatement.cs
- ImageBrush.cs
- UrlMappingsSection.cs
- ExpressionConverter.cs
- FormsAuthenticationModule.cs
- BaseTemplateBuildProvider.cs
- Authorization.cs
- ValueSerializer.cs
- Permission.cs
- DescendentsWalker.cs
- DbCommandDefinition.cs
- DbConnectionFactory.cs
- FlowThrottle.cs
- XamlSerializerUtil.cs
- LinkedList.cs
- Helpers.cs
- SqlClientWrapperSmiStream.cs
- TransactionFlowElement.cs
- HttpRuntime.cs
- ProtocolImporter.cs
- FieldDescriptor.cs
- XmlTextReader.cs
- SmtpException.cs
- SkewTransform.cs
- ClientCultureInfo.cs
- RelationshipConverter.cs
- TypeListConverter.cs
- ResourceReferenceExpressionConverter.cs
- precedingquery.cs
- PolicyConversionContext.cs
- BackEase.cs
- ThrowHelper.cs
- PreviewKeyDownEventArgs.cs
- CompoundFileReference.cs
- PriorityRange.cs
- CalendarDesigner.cs
- RIPEMD160Managed.cs
- XmlWhitespace.cs
- XmlHelper.cs
- MultiBinding.cs
- CanonicalXml.cs
- TablePattern.cs
- ClientScriptItemCollection.cs
- SmtpTransport.cs
- DataRow.cs
- DataServiceRequestOfT.cs
- DebugTraceHelper.cs
- HandledMouseEvent.cs
- TextChangedEventArgs.cs
- TextView.cs
- XmlSchemaAnnotation.cs
- BigInt.cs
- ListViewDesigner.cs
- OuterGlowBitmapEffect.cs
- DataGridTable.cs
- Events.cs