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
- ServiceModelSectionGroup.cs
- HttpMethodAttribute.cs
- ContextMenuService.cs
- RemotingSurrogateSelector.cs
- XsltConvert.cs
- Lasso.cs
- WebPermission.cs
- _FixedSizeReader.cs
- HttpModuleCollection.cs
- RepeaterItemEventArgs.cs
- ImageListStreamer.cs
- DataTableClearEvent.cs
- DataGridRowHeader.cs
- DictionaryEntry.cs
- HttpFileCollection.cs
- CheckableControlBaseAdapter.cs
- SqlExpressionNullability.cs
- SettingsProviderCollection.cs
- GetIsBrowserClientRequest.cs
- ContainerActivationHelper.cs
- HtmlEmptyTagControlBuilder.cs
- HttpHeaderCollection.cs
- WebPartCatalogAddVerb.cs
- SqlInternalConnection.cs
- QuaternionConverter.cs
- JsonUriDataContract.cs
- RectKeyFrameCollection.cs
- MultilineStringConverter.cs
- EventLogPermission.cs
- ConstraintCollection.cs
- SHA384.cs
- EventSinkHelperWriter.cs
- ItemCheckedEvent.cs
- HttpWriter.cs
- DiffuseMaterial.cs
- hresults.cs
- PrintPreviewControl.cs
- ViewgenGatekeeper.cs
- ListControlConvertEventArgs.cs
- VisualTransition.cs
- EventTrigger.cs
- CalendarKeyboardHelper.cs
- AmbiguousMatchException.cs
- MetadataWorkspace.cs
- BitmapImage.cs
- XmlWriterTraceListener.cs
- InputGestureCollection.cs
- OracleInfoMessageEventArgs.cs
- Accessible.cs
- TextTabProperties.cs
- PrintPageEvent.cs
- Substitution.cs
- DataListItemEventArgs.cs
- ObjectKeyFrameCollection.cs
- PathStreamGeometryContext.cs
- SiteMapPath.cs
- SystemWebExtensionsSectionGroup.cs
- NullableDecimalMinMaxAggregationOperator.cs
- VerificationAttribute.cs
- WhitespaceRuleReader.cs
- GridViewPageEventArgs.cs
- TypeLibConverter.cs
- TextEditor.cs
- GridItem.cs
- CodeTypeParameterCollection.cs
- HttpPostedFile.cs
- ToolBar.cs
- SecurityKeyType.cs
- AndMessageFilter.cs
- UTF32Encoding.cs
- LoginCancelEventArgs.cs
- ProfileGroupSettings.cs
- ExtendedProperty.cs
- XmlSchemaGroupRef.cs
- FullTextState.cs
- ToolStripDropDownItem.cs
- AsyncOperationContext.cs
- ObjectStateEntryOriginalDbUpdatableDataRecord.cs
- DefaultWorkflowSchedulerService.cs
- ThreadInterruptedException.cs
- IPCCacheManager.cs
- XPathEmptyIterator.cs
- KeyboardNavigation.cs
- HasCopySemanticsAttribute.cs
- CodeAccessPermission.cs
- XmlResolver.cs
- HelpProvider.cs
- DateTimePicker.cs
- HScrollBar.cs
- SignedXml.cs
- PageCodeDomTreeGenerator.cs
- SimpleType.cs
- RadioButtonBaseAdapter.cs
- WsdlWriter.cs
- WebControlAdapter.cs
- InputGestureCollection.cs
- SymbolPair.cs
- WizardStepBase.cs
- DefaultValueAttribute.cs
- ConstructorNeedsTagAttribute.cs