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(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
- StrongNameKeyPair.cs
- EpmCustomContentDeSerializer.cs
- JsonSerializer.cs
- NavigationProgressEventArgs.cs
- InstancePersistence.cs
- XmlMembersMapping.cs
- _NTAuthentication.cs
- UserPreferenceChangingEventArgs.cs
- SchemaElementDecl.cs
- SerializableAttribute.cs
- WebEventTraceProvider.cs
- RtfControlWordInfo.cs
- ExpressionDumper.cs
- DataGridViewAccessibleObject.cs
- UserPreference.cs
- XmlNullResolver.cs
- DBConnection.cs
- RSAProtectedConfigurationProvider.cs
- MatrixCamera.cs
- CriticalHandle.cs
- SystemIPInterfaceProperties.cs
- PrintPreviewGraphics.cs
- FormatException.cs
- _NetworkingPerfCounters.cs
- Rect3D.cs
- MissingMethodException.cs
- PropertySegmentSerializationProvider.cs
- ScopedKnownTypes.cs
- IdnMapping.cs
- DBBindings.cs
- LayoutEditorPart.cs
- HttpCachePolicy.cs
- ContextMarshalException.cs
- SafePEFileHandle.cs
- RemotingException.cs
- TextLineResult.cs
- RegexCharClass.cs
- Cursors.cs
- Matrix3DConverter.cs
- dataobject.cs
- DetailsViewDeleteEventArgs.cs
- RectConverter.cs
- TableLayoutCellPaintEventArgs.cs
- AliasGenerator.cs
- CodeMethodMap.cs
- CustomAttributeFormatException.cs
- OracleLob.cs
- MediaScriptCommandRoutedEventArgs.cs
- SafeFileMappingHandle.cs
- PKCS1MaskGenerationMethod.cs
- NullEntityWrapper.cs
- ToolStripSplitStackLayout.cs
- EntityAdapter.cs
- ConfigDefinitionUpdates.cs
- DateTimeFormatInfoScanner.cs
- SqlServices.cs
- ListenDesigner.cs
- StylusSystemGestureEventArgs.cs
- OracleParameterCollection.cs
- ZipIOCentralDirectoryFileHeader.cs
- wgx_render.cs
- ExpandCollapsePattern.cs
- HtmlTableRow.cs
- BuildProvider.cs
- _ProxyChain.cs
- Attributes.cs
- XmlElementAttributes.cs
- DesignTimeVisibleAttribute.cs
- WorkflowMarkupSerializationManager.cs
- SimpleExpression.cs
- PanelContainerDesigner.cs
- WindowsFormsSectionHandler.cs
- ErasingStroke.cs
- CacheEntry.cs
- QilStrConcat.cs
- RawKeyboardInputReport.cs
- shaper.cs
- XmlEncoding.cs
- PropertyTabAttribute.cs
- GeneralTransformCollection.cs
- AnimationException.cs
- AQNBuilder.cs
- SiteMapNodeItemEventArgs.cs
- Point3DKeyFrameCollection.cs
- CopyOnWriteList.cs
- UserControl.cs
- Label.cs
- PointAnimation.cs
- StrokeCollectionDefaultValueFactory.cs
- WebServiceHandler.cs
- DynamicValidator.cs
- SpellCheck.cs
- UInt16Converter.cs
- SimpleTextLine.cs
- TableLayout.cs
- DesignerActionItemCollection.cs
- AssemblyName.cs
- CommandHelpers.cs
- DefaultMemberAttribute.cs
- ListViewGroupItemCollection.cs