Code:
/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / DataEntity / System / Data / Map / Update / Internal / UndirectedGraph.cs / 1305376 / 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
- MappingModelBuildProvider.cs
- CheckBoxRenderer.cs
- WindowsGraphics2.cs
- BaseCodeDomTreeGenerator.cs
- TimelineGroup.cs
- InstanceStore.cs
- CurrencyManager.cs
- RelationalExpressions.cs
- MergePropertyDescriptor.cs
- CalendarData.cs
- SerializationHelper.cs
- CompilationSection.cs
- SerTrace.cs
- ImageSourceConverter.cs
- Label.cs
- XComponentModel.cs
- ContentElement.cs
- RectangleConverter.cs
- HttpCookiesSection.cs
- ObjectTypeMapping.cs
- ValidationError.cs
- FontUnit.cs
- SqlCacheDependencySection.cs
- DataControlField.cs
- TdsParserHelperClasses.cs
- RootBrowserWindow.cs
- SqlInfoMessageEvent.cs
- MexHttpsBindingElement.cs
- ClientSettingsStore.cs
- RawStylusActions.cs
- AsyncCompletedEventArgs.cs
- RuleInfoComparer.cs
- SynchronousChannel.cs
- OracleDataAdapter.cs
- OdbcEnvironmentHandle.cs
- HwndSourceKeyboardInputSite.cs
- ProcessManager.cs
- TextOutput.cs
- SerializableAttribute.cs
- SiteMapNodeItem.cs
- AncestorChangedEventArgs.cs
- SQLUtility.cs
- TableLayoutRowStyleCollection.cs
- HttpPostLocalhostServerProtocol.cs
- PopupRootAutomationPeer.cs
- EdmSchemaError.cs
- SemanticBasicElement.cs
- StackBuilderSink.cs
- DiscoveryService.cs
- XhtmlBasicFormAdapter.cs
- SqlDataSourceEnumerator.cs
- Point3DAnimation.cs
- CryptoApi.cs
- regiisutil.cs
- FontStyleConverter.cs
- MembershipValidatePasswordEventArgs.cs
- EntityPropertyMappingAttribute.cs
- QuotedPrintableStream.cs
- DirtyTextRange.cs
- CommandManager.cs
- TypeConverterAttribute.cs
- SqlNodeAnnotation.cs
- CodeRegionDirective.cs
- CodeIterationStatement.cs
- UIElement3D.cs
- METAHEADER.cs
- SerializationException.cs
- MouseButton.cs
- StringUtil.cs
- FrameworkPropertyMetadata.cs
- XomlCompilerHelpers.cs
- Line.cs
- GetRecipientRequest.cs
- StorageSetMapping.cs
- UInt64Storage.cs
- ResXFileRef.cs
- SecurityDescriptor.cs
- WSSecurityOneDotZeroReceiveSecurityHeader.cs
- ClientScriptManager.cs
- ApplicationBuildProvider.cs
- WebPartMinimizeVerb.cs
- Visitor.cs
- HtmlUtf8RawTextWriter.cs
- TextEditorParagraphs.cs
- UserPreferenceChangingEventArgs.cs
- CancellationHandlerDesigner.cs
- DataServiceException.cs
- DependencyPropertyAttribute.cs
- MachineKeySection.cs
- SQLBoolean.cs
- CodeArrayIndexerExpression.cs
- XmlElementCollection.cs
- SkinBuilder.cs
- ProviderSettingsCollection.cs
- MultiSelector.cs
- Pkcs7Recipient.cs
- ServiceOperation.cs
- AssemblyNameProxy.cs
- MarkupCompiler.cs
- PngBitmapEncoder.cs