Code:
/ Dotnetfx_Vista_SP2 / Dotnetfx_Vista_SP2 / 8.0.50727.4016 / DEVDIV / depot / DevDiv / releases / Orcas / QFE / 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
- DoubleLinkList.cs
- TextWriter.cs
- DockPattern.cs
- WebPartVerb.cs
- OrderToken.cs
- DuplexChannel.cs
- SemanticTag.cs
- SafeRsaProviderHandle.cs
- CryptoApi.cs
- GridSplitterAutomationPeer.cs
- SmtpAuthenticationManager.cs
- SqlDataSourceView.cs
- DataError.cs
- ShutDownListener.cs
- XmlEncoding.cs
- ConnectionProviderAttribute.cs
- ArrayWithOffset.cs
- Configuration.cs
- Timer.cs
- ProtectedConfigurationSection.cs
- PeerTransportBindingElement.cs
- EncryptedData.cs
- PrintDialogException.cs
- ProgressPage.cs
- X509SecurityTokenAuthenticator.cs
- ComPlusTraceRecord.cs
- EnumMember.cs
- TraceListeners.cs
- DataGridViewRowHeightInfoPushedEventArgs.cs
- RijndaelManagedTransform.cs
- RelationshipEndCollection.cs
- SR.cs
- StringAnimationUsingKeyFrames.cs
- StreamGeometry.cs
- WindowsIPAddress.cs
- RuleSetBrowserDialog.cs
- Brush.cs
- CoTaskMemHandle.cs
- TableAdapterManagerGenerator.cs
- ClientFormsIdentity.cs
- SqlPersonalizationProvider.cs
- HtmlTableRow.cs
- BinHexEncoder.cs
- ManipulationInertiaStartingEventArgs.cs
- EntityDataSourceSelectingEventArgs.cs
- AssociationSetEnd.cs
- FontEmbeddingManager.cs
- AppDomainFactory.cs
- BinaryConverter.cs
- UserPreferenceChangingEventArgs.cs
- InputLanguage.cs
- WebPartConnectionsConfigureVerb.cs
- AppendHelper.cs
- SectionUpdates.cs
- RichTextBoxAutomationPeer.cs
- IndentedTextWriter.cs
- ProxyHelper.cs
- TextTreeFixupNode.cs
- PanelStyle.cs
- EndpointBehaviorElement.cs
- Vertex.cs
- FixedSOMPage.cs
- SqlProviderManifest.cs
- TagPrefixInfo.cs
- Visitor.cs
- PerformanceCountersElement.cs
- InlineUIContainer.cs
- ArrayListCollectionBase.cs
- TagMapInfo.cs
- Select.cs
- Membership.cs
- DetailsViewDeleteEventArgs.cs
- RangeContentEnumerator.cs
- RadioButton.cs
- BehaviorDragDropEventArgs.cs
- Encoding.cs
- XmlSerializerVersionAttribute.cs
- AuthenticationServiceManager.cs
- LambdaCompiler.cs
- UnknownBitmapEncoder.cs
- SafeFileMappingHandle.cs
- rsa.cs
- LambdaExpression.cs
- Section.cs
- FtpWebRequest.cs
- CodeAttributeDeclarationCollection.cs
- Function.cs
- Trace.cs
- InvokePattern.cs
- XmlSerializationReader.cs
- RowToFieldTransformer.cs
- ColumnMapTranslator.cs
- CodeStatementCollection.cs
- PermissionSet.cs
- AuthenticationService.cs
- MergeLocalizationDirectives.cs
- NumberFormatter.cs
- FastEncoder.cs
- LambdaCompiler.Generated.cs
- ChangeConflicts.cs