summaryrefslogtreecommitdiff
path: root/Source/cmComputeComponentGraph.cxx
diff options
context:
space:
mode:
authorAnas Nashif <anas.nashif@intel.com>2012-10-30 15:39:57 -0700
committerAnas Nashif <anas.nashif@intel.com>2012-10-30 15:39:57 -0700
commit035c7fabc3b82cbc9a346c11abe2e9462b4c0379 (patch)
tree7e40f5a790eae329a8c5d3e59f046451767956ff /Source/cmComputeComponentGraph.cxx
downloadcmake-035c7fabc3b82cbc9a346c11abe2e9462b4c0379.tar.gz
cmake-035c7fabc3b82cbc9a346c11abe2e9462b4c0379.tar.bz2
cmake-035c7fabc3b82cbc9a346c11abe2e9462b4c0379.zip
Imported Upstream version 2.8.9upstream/2.8.9
Diffstat (limited to 'Source/cmComputeComponentGraph.cxx')
-rw-r--r--Source/cmComputeComponentGraph.cxx159
1 files changed, 159 insertions, 0 deletions
diff --git a/Source/cmComputeComponentGraph.cxx b/Source/cmComputeComponentGraph.cxx
new file mode 100644
index 000000000..5bec6a1ec
--- /dev/null
+++ b/Source/cmComputeComponentGraph.cxx
@@ -0,0 +1,159 @@
+/*============================================================================
+ CMake - Cross Platform Makefile Generator
+ Copyright 2000-2009 Kitware, Inc., Insight Software Consortium
+
+ Distributed under the OSI-approved BSD License (the "License");
+ see accompanying file Copyright.txt for details.
+
+ This software is distributed WITHOUT ANY WARRANTY; without even the
+ implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
+ See the License for more information.
+============================================================================*/
+#include "cmComputeComponentGraph.h"
+
+#include <algorithm>
+
+#include <assert.h>
+
+//----------------------------------------------------------------------------
+cmComputeComponentGraph::cmComputeComponentGraph(Graph const& input):
+ InputGraph(input)
+{
+ // Identify components.
+ this->Tarjan();
+
+ // Compute the component graph.
+ this->ComponentGraph.resize(0);
+ this->ComponentGraph.resize(this->Components.size());
+ this->TransferEdges();
+}
+
+//----------------------------------------------------------------------------
+cmComputeComponentGraph::~cmComputeComponentGraph()
+{
+}
+
+//----------------------------------------------------------------------------
+void cmComputeComponentGraph::Tarjan()
+{
+ int n = static_cast<int>(this->InputGraph.size());
+ TarjanEntry entry = {0,0};
+ this->TarjanEntries.resize(0);
+ this->TarjanEntries.resize(n, entry);
+ this->TarjanComponents.resize(0);
+ this->TarjanComponents.resize(n, -1);
+ this->TarjanWalkId = 0;
+ this->TarjanVisited.resize(0);
+ this->TarjanVisited.resize(n, 0);
+ for(int i = 0; i < n; ++i)
+ {
+ // Start a new DFS from this node if it has never been visited.
+ if(!this->TarjanVisited[i])
+ {
+ assert(this->TarjanStack.empty());
+ ++this->TarjanWalkId;
+ this->TarjanIndex = 0;
+ this->TarjanVisit(i);
+ }
+ }
+}
+
+//----------------------------------------------------------------------------
+void cmComputeComponentGraph::TarjanVisit(int i)
+{
+ // We are now visiting this node.
+ this->TarjanVisited[i] = this->TarjanWalkId;
+
+ // Initialize the entry.
+ this->TarjanEntries[i].Root = i;
+ this->TarjanComponents[i] = -1;
+ this->TarjanEntries[i].VisitIndex = ++this->TarjanIndex;
+ this->TarjanStack.push(i);
+
+ // Follow outgoing edges.
+ EdgeList const& nl = this->InputGraph[i];
+ for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
+ {
+ int j = *ni;
+
+ // Ignore edges to nodes that have been reached by a previous DFS
+ // walk. Since we did not reach the current node from that walk
+ // it must not belong to the same component and it has already
+ // been assigned to a component.
+ if(this->TarjanVisited[j] > 0 &&
+ this->TarjanVisited[j] < this->TarjanWalkId)
+ {
+ continue;
+ }
+
+ // Visit the destination if it has not yet been visited.
+ if(!this->TarjanVisited[j])
+ {
+ this->TarjanVisit(j);
+ }
+
+ // If the destination has not yet been assigned to a component,
+ // check if it has a better root for the current object.
+ if(this->TarjanComponents[j] < 0)
+ {
+ if(this->TarjanEntries[this->TarjanEntries[j].Root].VisitIndex <
+ this->TarjanEntries[this->TarjanEntries[i].Root].VisitIndex)
+ {
+ this->TarjanEntries[i].Root = this->TarjanEntries[j].Root;
+ }
+ }
+ }
+
+ // Check if we have found a component.
+ if(this->TarjanEntries[i].Root == i)
+ {
+ // Yes. Create it.
+ int c = static_cast<int>(this->Components.size());
+ this->Components.push_back(NodeList());
+ NodeList& component = this->Components[c];
+
+ // Populate the component list.
+ int j;
+ do
+ {
+ // Get the next member of the component.
+ j = this->TarjanStack.top();
+ this->TarjanStack.pop();
+
+ // Assign the member to the component.
+ this->TarjanComponents[j] = c;
+ this->TarjanEntries[j].Root = i;
+
+ // Store the node in its component.
+ component.push_back(j);
+ } while(j != i);
+
+ // Sort the component members for clarity.
+ std::sort(component.begin(), component.end());
+ }
+}
+
+//----------------------------------------------------------------------------
+void cmComputeComponentGraph::TransferEdges()
+{
+ // Map inter-component edges in the original graph to edges in the
+ // component graph.
+ int n = static_cast<int>(this->InputGraph.size());
+ for(int i=0; i < n; ++i)
+ {
+ int i_component = this->TarjanComponents[i];
+ EdgeList const& nl = this->InputGraph[i];
+ for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
+ {
+ int j = *ni;
+ int j_component = this->TarjanComponents[j];
+ if(i_component != j_component)
+ {
+ // We do not attempt to combine duplicate edges, but instead
+ // store the inter-component edges with suitable multiplicity.
+ this->ComponentGraph[i_component].push_back(
+ cmGraphEdge(j_component, ni->IsStrong()));
+ }
+ }
+ }
+}