From 7be2617b5a52529ce0ca33e6c878a0294e1e2781 Mon Sep 17 00:00:00 2001
From: Brad King <brad.king@kitware.com>
Date: Fri, 20 Aug 2010 14:11:18 -0400
Subject: Split notion of node lists and edge lists

---
 Source/cmComputeComponentGraph.cxx |  8 ++++----
 Source/cmComputeComponentGraph.h   |  3 ++-
 Source/cmComputeLinkDepends.cxx    | 20 ++++++++++----------
 Source/cmComputeLinkDepends.h      |  1 +
 Source/cmComputeTargetDepends.cxx  | 16 ++++++++--------
 Source/cmComputeTargetDepends.h    |  1 +
 Source/cmGraphAdjacencyList.h      |  3 ++-
 7 files changed, 28 insertions(+), 24 deletions(-)

diff --git a/Source/cmComputeComponentGraph.cxx b/Source/cmComputeComponentGraph.cxx
index 3f2a361..165af10 100644
--- a/Source/cmComputeComponentGraph.cxx
+++ b/Source/cmComputeComponentGraph.cxx
@@ -71,8 +71,8 @@ void cmComputeComponentGraph::TarjanVisit(int i)
   this->TarjanStack.push(i);
 
   // Follow outgoing edges.
-  NodeList const& nl = this->InputGraph[i];
-  for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
+  EdgeList const& nl = this->InputGraph[i];
+  for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
     {
     int j = *ni;
 
@@ -142,8 +142,8 @@ void cmComputeComponentGraph::TransferEdges()
   for(int i=0; i < n; ++i)
     {
     int i_component = this->TarjanComponents[i];
-    NodeList const& nl = this->InputGraph[i];
-    for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
+    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];
diff --git a/Source/cmComputeComponentGraph.h b/Source/cmComputeComponentGraph.h
index 855a141..a2ce946 100644
--- a/Source/cmComputeComponentGraph.h
+++ b/Source/cmComputeComponentGraph.h
@@ -33,6 +33,7 @@ class cmComputeComponentGraph
 public:
   // Represent the graph with an adjacency list.
   typedef cmGraphNodeList NodeList;
+  typedef cmGraphEdgeList EdgeList;
   typedef cmGraphAdjacencyList Graph;
 
   cmComputeComponentGraph(Graph const& input);
@@ -41,7 +42,7 @@ public:
   /** Get the adjacency list of the component graph.  */
   Graph const& GetComponentGraph() const
     { return this->ComponentGraph; }
-  NodeList const& GetComponentGraphEdges(int c) const
+  EdgeList const& GetComponentGraphEdges(int c) const
     { return this->ComponentGraph[c]; }
 
   /** Get map from component index to original node indices.  */
diff --git a/Source/cmComputeLinkDepends.cxx b/Source/cmComputeLinkDepends.cxx
index 24410ec..4b0214e 100644
--- a/Source/cmComputeLinkDepends.cxx
+++ b/Source/cmComputeLinkDepends.cxx
@@ -285,7 +285,7 @@ cmComputeLinkDepends::AllocateLinkEntry(std::string const& item)
     lei = this->LinkEntryIndex.insert(index_entry).first;
   this->EntryList.push_back(LinkEntry());
   this->InferredDependSets.push_back(0);
-  this->EntryConstraintGraph.push_back(NodeList());
+  this->EntryConstraintGraph.push_back(EdgeList());
   return lei;
 }
 
@@ -669,7 +669,7 @@ void cmComputeLinkDepends::CleanConstraintGraph()
     cmsys_stl::sort(i->begin(), i->end());
 
     // Make the edge list unique.
-    NodeList::iterator last = cmsys_stl::unique(i->begin(), i->end());
+    EdgeList::iterator last = cmsys_stl::unique(i->begin(), i->end());
     i->erase(last, i->end());
     }
 }
@@ -681,9 +681,9 @@ void cmComputeLinkDepends::DisplayConstraintGraph()
   cmOStringStream e;
   for(unsigned int i=0; i < this->EntryConstraintGraph.size(); ++i)
     {
-    NodeList const& nl = this->EntryConstraintGraph[i];
+    EdgeList const& nl = this->EntryConstraintGraph[i];
     e << "item " << i << " is [" << this->EntryList[i].Item << "]\n";
-    for(NodeList::const_iterator j = nl.begin(); j != nl.end(); ++j)
+    for(EdgeList::const_iterator j = nl.begin(); j != nl.end(); ++j)
       {
       e << "  item " << *j << " must follow it\n";
       }
@@ -758,8 +758,8 @@ cmComputeLinkDepends::DisplayComponents()
       fprintf(stderr, "  item %d [%s]\n", i,
               this->EntryList[i].Item.c_str());
       }
-    NodeList const& ol = this->CCG->GetComponentGraphEdges(c);
-    for(NodeList::const_iterator oi = ol.begin(); oi != ol.end(); ++oi)
+    EdgeList const& ol = this->CCG->GetComponentGraphEdges(c);
+    for(EdgeList::const_iterator oi = ol.begin(); oi != ol.end(); ++oi)
       {
       fprintf(stderr, "  followed by Component (%d)\n", *oi);
       }
@@ -784,8 +784,8 @@ void cmComputeLinkDepends::VisitComponent(unsigned int c)
   // Visit the neighbors of the component first.
   // Run in reverse order so the topological order will preserve the
   // original order where there are no constraints.
-  NodeList const& nl = this->CCG->GetComponentGraphEdges(c);
-  for(NodeList::const_reverse_iterator ni = nl.rbegin();
+  EdgeList const& nl = this->CCG->GetComponentGraphEdges(c);
+  for(EdgeList::const_reverse_iterator ni = nl.rbegin();
       ni != nl.rend(); ++ni)
     {
     this->VisitComponent(*ni);
@@ -856,8 +856,8 @@ void cmComputeLinkDepends::VisitEntry(int index)
   // are now pending.
   if(completed)
     {
-    NodeList const& ol = this->CCG->GetComponentGraphEdges(component);
-    for(NodeList::const_iterator oi = ol.begin(); oi != ol.end(); ++oi)
+    EdgeList const& ol = this->CCG->GetComponentGraphEdges(component);
+    for(EdgeList::const_iterator oi = ol.begin(); oi != ol.end(); ++oi)
       {
       // This entire component is now pending no matter whether it has
       // been partially seen already.
diff --git a/Source/cmComputeLinkDepends.h b/Source/cmComputeLinkDepends.h
index a08afb6..e196e00 100644
--- a/Source/cmComputeLinkDepends.h
+++ b/Source/cmComputeLinkDepends.h
@@ -117,6 +117,7 @@ private:
 
   // Ordering constraint graph adjacency list.
   typedef cmGraphNodeList NodeList;
+  typedef cmGraphEdgeList EdgeList;
   typedef cmGraphAdjacencyList Graph;
   Graph EntryConstraintGraph;
   void CleanConstraintGraph();
diff --git a/Source/cmComputeTargetDepends.cxx b/Source/cmComputeTargetDepends.cxx
index 94b8527..e82606c 100644
--- a/Source/cmComputeTargetDepends.cxx
+++ b/Source/cmComputeTargetDepends.cxx
@@ -150,8 +150,8 @@ cmComputeTargetDepends::GetTargetDirectDepends(cmTarget* t,
   int i = tii->second;
 
   // Get its final dependencies.
-  NodeList const& nl = this->FinalGraph[i];
-  for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
+  EdgeList const& nl = this->FinalGraph[i];
+  for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
     {
     deps.insert(this->Targets[*ni]);
     }
@@ -283,11 +283,11 @@ cmComputeTargetDepends::DisplayGraph(Graph const& graph, const char* name)
   int n = static_cast<int>(graph.size());
   for(int depender_index = 0; depender_index < n; ++depender_index)
     {
-    NodeList const& nl = graph[depender_index];
+    EdgeList const& nl = graph[depender_index];
     cmTarget* depender = this->Targets[depender_index];
     fprintf(stderr, "target %d is [%s]\n",
             depender_index, depender->GetName());
-    for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
+    for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
       {
       int dependee_index = *ni;
       cmTarget* dependee = this->Targets[dependee_index];
@@ -383,8 +383,8 @@ cmComputeTargetDepends
       << cmTarget::TargetTypeNames[depender->GetType()] << "\n";
 
     // List its dependencies that are inside the component.
-    NodeList const& nl = this->InitialGraph[i];
-    for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
+    EdgeList const& nl = this->InitialGraph[i];
+    for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
       {
       int j = *ni;
       if(cmap[j] == c)
@@ -425,8 +425,8 @@ cmComputeTargetDepends
   for(int depender_component=0; depender_component < n; ++depender_component)
     {
     int depender_component_tail = components[depender_component].back();
-    NodeList const& nl = cgraph[depender_component];
-    for(NodeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
+    EdgeList const& nl = cgraph[depender_component];
+    for(EdgeList::const_iterator ni = nl.begin(); ni != nl.end(); ++ni)
       {
       int dependee_component = *ni;
       int dependee_component_head = components[dependee_component].front();
diff --git a/Source/cmComputeTargetDepends.h b/Source/cmComputeTargetDepends.h
index 68e3e47..b18a053 100644
--- a/Source/cmComputeTargetDepends.h
+++ b/Source/cmComputeTargetDepends.h
@@ -59,6 +59,7 @@ private:
   // top-level index corresponds to a depender whose dependencies are
   // listed.
   typedef cmGraphNodeList NodeList;
+  typedef cmGraphEdgeList EdgeList;
   typedef cmGraphAdjacencyList Graph;
   Graph InitialGraph;
   Graph FinalGraph;
diff --git a/Source/cmGraphAdjacencyList.h b/Source/cmGraphAdjacencyList.h
index 7794840..41411c4 100644
--- a/Source/cmGraphAdjacencyList.h
+++ b/Source/cmGraphAdjacencyList.h
@@ -14,7 +14,8 @@
 
 #include "cmStandardIncludes.h"
 
+struct cmGraphEdgeList: public std::vector<int> {};
 struct cmGraphNodeList: public std::vector<int> {};
-struct cmGraphAdjacencyList: public std::vector<cmGraphNodeList> {};
+struct cmGraphAdjacencyList: public std::vector<cmGraphEdgeList> {};
 
 #endif
-- 
cgit v0.12