Code:
/ Net / Net / 3.5.50727.3053 / DEVDIV / depot / DevDiv / releases / Orcas / SP / ndp / fx / src / DataEntity / System / Data / Map / Update / Internal / UndirectedGraph.cs / 1 / UndirectedGraph.cs
//---------------------------------------------------------------------- //// Copyright (c) Microsoft Corporation. All rights reserved. // // // @owner [....] // @backupOwner [....] //--------------------------------------------------------------------- using System.Data.Common.Utils; using System.Collections.Generic; using System.Text; namespace System.Data.Mapping.Update.Internal { // Maintains a graph where the direction of the edges is not important class UndirectedGraph: InternalBase { #region Constructor internal UndirectedGraph(IEqualityComparer comparer) { m_graph = new Graph (comparer); m_comparer = comparer; } #endregion #region Fields private Graph m_graph; // Directed graph where we added both edges private IEqualityComparer m_comparer; #endregion #region Properties internal IEnumerable Vertices { get { return m_graph.Vertices; } } /// /// Returns the edges of the graph /// internal IEnumerable> Edges { get { return m_graph.Edges; } } #endregion #region Methods // effects: Adds a new node to the graph. Does nothing if the vertex already exists. internal void AddVertex(TVertex vertex) { m_graph.AddVertex(vertex); } // requires: first and second must exist. An edge between first and // second must not already exist // effects: Adds a new unidirectional edge to the graph. internal void AddEdge(TVertex first, TVertex second) { m_graph.AddEdge(first, second); m_graph.AddEdge(second, first); } // effects: Given a graph of T, returns a map such that nodes in the // same connected component are in the same list in the KeyToListMap internal KeyToListMap GenerateConnectedComponents() { int count = 0; // Set the "component number" for each node Dictionary componentMap = new Dictionary (m_comparer); foreach (TVertex vertex in Vertices) { componentMap.Add(vertex, new ComponentNum(count)); count++; } // Run the connected components algorithm (Page 441 of the CLR -- Cormen, Rivest, Lieserson) foreach (KeyValuePair edge in Edges) { if (componentMap[edge.Key].componentNum != componentMap[edge.Value].componentNum) { // Set the component numbers of both of the nodes to be the same int oldValue = componentMap[edge.Value].componentNum; int newValue = componentMap[edge.Key].componentNum; componentMap[edge.Value].componentNum = newValue; // Since we are resetting edge.Value's component number, find all components whose value // is oldValue and reset it to the new value foreach (TVertex vertex in componentMap.Keys) { if (componentMap[vertex].componentNum == oldValue) { componentMap[vertex].componentNum = newValue; } } } } // Now just grab the vertices which have the same set numbers KeyToListMap result = new KeyToListMap (EqualityComparer .Default); foreach (TVertex vertex in Vertices) { int componentNum = componentMap[vertex].componentNum; result.Add(componentNum, vertex); } return result; } internal override void ToCompactString(StringBuilder builder) { builder.Append(m_graph.ToString()); } // A class just for ensuring that we do not modify the hash table // while iterating over it. Keeps track of the component number for a // connected component private class ComponentNum { internal ComponentNum(int compNum) { componentNum = compNum; } internal int componentNum; public override string ToString() { return StringUtil.FormatInvariant("{0}", componentNum); } }; #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.Text; namespace System.Data.Mapping.Update.Internal { // Maintains a graph where the direction of the edges is not important class UndirectedGraph: InternalBase { #region Constructor internal UndirectedGraph(IEqualityComparer comparer) { m_graph = new Graph (comparer); m_comparer = comparer; } #endregion #region Fields private Graph m_graph; // Directed graph where we added both edges private IEqualityComparer m_comparer; #endregion #region Properties internal IEnumerable Vertices { get { return m_graph.Vertices; } } /// /// Returns the edges of the graph /// internal IEnumerable> Edges { get { return m_graph.Edges; } } #endregion #region Methods // effects: Adds a new node to the graph. Does nothing if the vertex already exists. internal void AddVertex(TVertex vertex) { m_graph.AddVertex(vertex); } // requires: first and second must exist. An edge between first and // second must not already exist // effects: Adds a new unidirectional edge to the graph. internal void AddEdge(TVertex first, TVertex second) { m_graph.AddEdge(first, second); m_graph.AddEdge(second, first); } // effects: Given a graph of T, returns a map such that nodes in the // same connected component are in the same list in the KeyToListMap internal KeyToListMap GenerateConnectedComponents() { int count = 0; // Set the "component number" for each node Dictionary componentMap = new Dictionary (m_comparer); foreach (TVertex vertex in Vertices) { componentMap.Add(vertex, new ComponentNum(count)); count++; } // Run the connected components algorithm (Page 441 of the CLR -- Cormen, Rivest, Lieserson) foreach (KeyValuePair edge in Edges) { if (componentMap[edge.Key].componentNum != componentMap[edge.Value].componentNum) { // Set the component numbers of both of the nodes to be the same int oldValue = componentMap[edge.Value].componentNum; int newValue = componentMap[edge.Key].componentNum; componentMap[edge.Value].componentNum = newValue; // Since we are resetting edge.Value's component number, find all components whose value // is oldValue and reset it to the new value foreach (TVertex vertex in componentMap.Keys) { if (componentMap[vertex].componentNum == oldValue) { componentMap[vertex].componentNum = newValue; } } } } // Now just grab the vertices which have the same set numbers KeyToListMap result = new KeyToListMap (EqualityComparer .Default); foreach (TVertex vertex in Vertices) { int componentNum = componentMap[vertex].componentNum; result.Add(componentNum, vertex); } return result; } internal override void ToCompactString(StringBuilder builder) { builder.Append(m_graph.ToString()); } // A class just for ensuring that we do not modify the hash table // while iterating over it. Keeps track of the component number for a // connected component private class ComponentNum { internal ComponentNum(int compNum) { componentNum = compNum; } internal int componentNum; public override string ToString() { return StringUtil.FormatInvariant("{0}", componentNum); } }; #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
- DataServiceExpressionVisitor.cs
- Freezable.cs
- WindowsIdentity.cs
- Label.cs
- CompressionTracing.cs
- SizeKeyFrameCollection.cs
- TableCell.cs
- wmiprovider.cs
- JapaneseCalendar.cs
- ObjectDataSourceSelectingEventArgs.cs
- OleDbFactory.cs
- DurableTimerExtension.cs
- XmlComplianceUtil.cs
- DataGridViewDataErrorEventArgs.cs
- DesignColumnCollection.cs
- WorkflowInstance.cs
- XmlSchemaNotation.cs
- TableItemStyle.cs
- LineGeometry.cs
- StreamReader.cs
- DataContext.cs
- ZipIOExtraFieldZip64Element.cs
- CollectionContainer.cs
- BaseDataListComponentEditor.cs
- TableCellsCollectionEditor.cs
- WorkflowApplicationIdleEventArgs.cs
- CodeDomDecompiler.cs
- ToolboxItemCollection.cs
- unitconverter.cs
- TdsParameterSetter.cs
- DataQuery.cs
- ResXDataNode.cs
- DesignObjectWrapper.cs
- ConfigurationStrings.cs
- NamespaceCollection.cs
- InstanceDataCollection.cs
- CompilerScope.Storage.cs
- ConstraintEnumerator.cs
- RijndaelManaged.cs
- HMACRIPEMD160.cs
- LookupNode.cs
- ElementProxy.cs
- SessionSwitchEventArgs.cs
- DetailsViewRow.cs
- DataServiceRequestOfT.cs
- ClrPerspective.cs
- XmlTextReader.cs
- WhitespaceRuleReader.cs
- DeclarationUpdate.cs
- BindingExpressionUncommonField.cs
- CommandID.cs
- EndpointAddressAugust2004.cs
- XmlnsPrefixAttribute.cs
- ControlPaint.cs
- RuntimeConfigLKG.cs
- WsdlHelpGeneratorElement.cs
- IdentityModelDictionary.cs
- SymbolPair.cs
- TcpChannelListener.cs
- CharacterBufferReference.cs
- HtmlElement.cs
- CodeGenerator.cs
- SQLMembershipProvider.cs
- XsdDuration.cs
- ResourceDisplayNameAttribute.cs
- RequestQueue.cs
- brushes.cs
- InternalMappingException.cs
- Compiler.cs
- MessageFormatterConverter.cs
- ThreadExceptionDialog.cs
- IntMinMaxAggregationOperator.cs
- RedirectionProxy.cs
- AnnouncementInnerClient11.cs
- Label.cs
- DefaultTextStoreTextComposition.cs
- CodeLinePragma.cs
- TableStyle.cs
- AnimationStorage.cs
- BitmapEffectCollection.cs
- XmlILAnnotation.cs
- SpinLock.cs
- EmptyStringExpandableObjectConverter.cs
- _ListenerAsyncResult.cs
- ExpressionLexer.cs
- EventLogConfiguration.cs
- JournalEntryListConverter.cs
- PortCache.cs
- Int32Rect.cs
- MenuItemStyleCollection.cs
- TypeConverterHelper.cs
- DataGridViewCellValueEventArgs.cs
- TargetInvocationException.cs
- UnitySerializationHolder.cs
- SymmetricAlgorithm.cs
- ProfileSettingsCollection.cs
- JsonReader.cs
- CheckableControlBaseAdapter.cs
- RealProxy.cs
- ContentWrapperAttribute.cs