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
- ConfigurationPermission.cs
- MatrixUtil.cs
- SoapIgnoreAttribute.cs
- VBCodeProvider.cs
- HttpApplication.cs
- TextEndOfSegment.cs
- EntityConnectionStringBuilder.cs
- MessageBox.cs
- XmlQuerySequence.cs
- DataGridViewCellLinkedList.cs
- SpecialTypeDataContract.cs
- RadioButton.cs
- XmlSchemaGroupRef.cs
- WindowsToolbar.cs
- SQLByteStorage.cs
- FixedDocumentPaginator.cs
- IntPtr.cs
- AttachedAnnotationChangedEventArgs.cs
- Win32Interop.cs
- MultilineStringEditor.cs
- SystemDiagnosticsSection.cs
- ListSortDescription.cs
- PartialArray.cs
- UdpChannelListener.cs
- KeySplineConverter.cs
- FunctionUpdateCommand.cs
- SqlParameterCollection.cs
- BamlTreeMap.cs
- WeakReferenceList.cs
- NextPreviousPagerField.cs
- DependencyPropertyKey.cs
- CommonGetThemePartSize.cs
- ReadOnlyNameValueCollection.cs
- OleDragDropHandler.cs
- ScrollEvent.cs
- PropertyEmitterBase.cs
- DbConnectionClosed.cs
- DataContractSet.cs
- Descriptor.cs
- ScriptBehaviorDescriptor.cs
- FrameworkTemplate.cs
- GenericPrincipal.cs
- _NegoState.cs
- Msec.cs
- TreePrinter.cs
- WebPartConnectionsConnectVerb.cs
- ReadOnlyActivityGlyph.cs
- TagPrefixCollection.cs
- TrimSurroundingWhitespaceAttribute.cs
- Label.cs
- SplitContainer.cs
- followingquery.cs
- UrlMapping.cs
- LicenseException.cs
- TemplateNameScope.cs
- ImageDrawing.cs
- CompletionBookmark.cs
- LinqDataSourceSelectEventArgs.cs
- ProcessDesigner.cs
- IdleTimeoutMonitor.cs
- ResourcePermissionBaseEntry.cs
- ServiceContractGenerationContext.cs
- WorkflowInstance.cs
- UseLicense.cs
- CodeTypeOfExpression.cs
- AudioFileOut.cs
- Tablet.cs
- NetNamedPipeBindingCollectionElement.cs
- ConditionalAttribute.cs
- UncommonField.cs
- XmlNodeWriter.cs
- NoneExcludedImageIndexConverter.cs
- SchemaImporter.cs
- PostBackTrigger.cs
- LookupBindingPropertiesAttribute.cs
- WindowPatternIdentifiers.cs
- FormatException.cs
- DataGridViewCellStyle.cs
- FontInfo.cs
- ImageBrush.cs
- UserPreferenceChangingEventArgs.cs
- Pair.cs
- OracleBinary.cs
- ImmutableObjectAttribute.cs
- MenuScrollingVisibilityConverter.cs
- DocumentPageHost.cs
- ArrayTypeMismatchException.cs
- CodeDomConfigurationHandler.cs
- InfoCardKeyedHashAlgorithm.cs
- SemanticResultValue.cs
- ZipIOLocalFileHeader.cs
- DatatypeImplementation.cs
- EntityException.cs
- EntitySetDataBindingList.cs
- HMAC.cs
- TimeIntervalCollection.cs
- Figure.cs
- ArraySubsetEnumerator.cs
- ToolStripPanelCell.cs
- ListContractAdapter.cs