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 / 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
- KeyConstraint.cs
- assemblycache.cs
- FileFormatException.cs
- sqlmetadatafactory.cs
- CustomAttributeFormatException.cs
- CuspData.cs
- SignatureDescription.cs
- EdmTypeAttribute.cs
- CommunicationObjectFaultedException.cs
- UnmanagedBitmapWrapper.cs
- OperationCanceledException.cs
- Ipv6Element.cs
- ProcessHostMapPath.cs
- XmlDataImplementation.cs
- HttpWriter.cs
- ControlBuilder.cs
- WebPartEventArgs.cs
- XmlIgnoreAttribute.cs
- ReleaseInstanceMode.cs
- TheQuery.cs
- RadioButtonPopupAdapter.cs
- Container.cs
- EncryptedPackage.cs
- XmlAggregates.cs
- LocalizationComments.cs
- MediaPlayer.cs
- ImageCodecInfoPrivate.cs
- DesignerView.cs
- SocketInformation.cs
- SecurityElementBase.cs
- QilBinary.cs
- FrameworkTemplate.cs
- PbrsForward.cs
- TextInfo.cs
- BufferedStream2.cs
- FlowDocumentView.cs
- XmlDocumentSerializer.cs
- DataGridTable.cs
- MediaContext.cs
- ReadOnlyHierarchicalDataSource.cs
- DocumentViewerBaseAutomationPeer.cs
- DbDataRecord.cs
- CngProperty.cs
- BaseTreeIterator.cs
- odbcmetadatafactory.cs
- InspectionWorker.cs
- RuleSettingsCollection.cs
- RunWorkerCompletedEventArgs.cs
- NotCondition.cs
- CharEnumerator.cs
- CompilationUtil.cs
- TableParaClient.cs
- UTF8Encoding.cs
- HostingEnvironmentSection.cs
- TypeBuilder.cs
- FileReader.cs
- ManagementException.cs
- XsltQilFactory.cs
- HierarchicalDataBoundControlAdapter.cs
- RoleBoolean.cs
- ZipPackage.cs
- RightsManagementInformation.cs
- TableCellAutomationPeer.cs
- PersonalizationProvider.cs
- wgx_commands.cs
- validationstate.cs
- FontStretchConverter.cs
- ConsumerConnectionPointCollection.cs
- BufferModeSettings.cs
- SchemaType.cs
- Symbol.cs
- ClockGroup.cs
- Type.cs
- DataGridHeadersVisibilityToVisibilityConverter.cs
- UserNamePasswordValidator.cs
- PartialTrustVisibleAssemblyCollection.cs
- MemberDomainMap.cs
- DetailsViewDeletedEventArgs.cs
- UnsafeNativeMethodsTablet.cs
- GradientStopCollection.cs
- BinaryObjectInfo.cs
- EventBuilder.cs
- WsatTransactionFormatter.cs
- LineVisual.cs
- CompensableActivity.cs
- EncoderBestFitFallback.cs
- TextDecoration.cs
- RoleBoolean.cs
- ProxyWebPart.cs
- SimplePropertyEntry.cs
- DesignSurfaceEvent.cs
- Crc32Helper.cs
- XmlLinkedNode.cs
- System.Data_BID.cs
- SelectedDatesCollection.cs
- TreeNodeCollection.cs
- control.ime.cs
- DataColumnPropertyDescriptor.cs
- PolicyException.cs
- Axis.cs