ctkDependencyGraph.cpp

Go to the documentation of this file.
00001 /*=========================================================================
00002 
00003   Library:   CTK
00004  
00005   Copyright (c) 2010  Kitware Inc.
00006 
00007   Licensed under the Apache License, Version 2.0 (the "License");
00008   you may not use this file except in compliance with the License.
00009   You may obtain a copy of the License at
00010 
00011       http://www.commontk.org/LICENSE
00012 
00013   Unless required by applicable law or agreed to in writing, software
00014   distributed under the License is distributed on an "AS IS" BASIS,
00015   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00016   See the License for the specific language governing permissions and
00017   limitations under the License.
00018  
00019 =========================================================================*/
00020 
00021 // Qt includes
00022 #include <QQueue>
00023 #include <QVarLengthArray>
00024 #include <QDebug>
00025 
00026 // CTK includes
00027 #include "ctkDependencyGraph.h"
00028 
00029 // STD includes
00030 #include <iostream>
00031 
00032 #define MAXV 100
00033 #define MAXDEGREE 50
00034 
00035 //----------------------------------------------------------------------------
00036 class ctkDependencyGraph::ctkInternal
00037 {
00038 public:
00039   ctkInternal(ctkDependencyGraph* p);
00040   
00042   void computeIndegrees(QVarLengthArray<int, MAXV>& computedIndegrees);
00043   
00045   void traverseUsingDFS(int v);
00046   
00048   void processEdge(int from, int to); 
00049   
00051   void processVertex(int v);
00052 
00054   void findPathDFS(int from, int to, QList<int>& path);
00055 
00057   void findPathsRec(int from, int to, QList<int>* path, QList<QList<int>* >& paths);
00058   
00059   void setEdge(int vertice, int degree, int value);
00060   int edge(int vertice, int degree);
00061   
00063   QVarLengthArray<QVarLengthArray<int,MAXDEGREE>*, MAXV+1> Edges;
00064   QVarLengthArray<int, MAXV+1> Degree;
00065   int NVertices;
00066   int NEdges;
00067   
00070   QVarLengthArray<bool, MAXV> Processed;  // processed vertices
00071   QVarLengthArray<bool, MAXV> Discovered; // discovered vertices
00072   QVarLengthArray<int, MAXV>  Parent;     // relation discovered
00073   
00074   bool    Abort;  // Flag indicating if traverse should be aborted
00075   bool    Verbose; 
00076   bool    CycleDetected; 
00077   int     CycleOrigin; 
00078   int     CycleEnd;
00079   
00080   QList<int> ListOfEdgeToExclude;
00081   
00083   ctkDependencyGraph* P;
00084 };
00085 
00086 //----------------------------------------------------------------------------
00087 // ctkInternal methods
00088 
00089 //----------------------------------------------------------------------------
00090 ctkDependencyGraph::ctkInternal::ctkInternal(ctkDependencyGraph* p)
00091 {
00092   Q_ASSERT(p);
00093   this->P = p;
00094   this->NVertices = 0; 
00095   this->NEdges = 0; 
00096   this->Abort = false;
00097   this->Verbose = false;
00098   this->CycleDetected = false;
00099   this->CycleOrigin = 0;
00100   this->CycleEnd = 0;
00101 }
00102 
00103 //----------------------------------------------------------------------------
00104 void ctkDependencyGraph::ctkInternal::computeIndegrees(QVarLengthArray<int, MAXV>& computedIndegrees)
00105 {
00106   for (int i=1; i <= this->NVertices; i++)
00107     {
00108     computedIndegrees[i] = 0;
00109     }
00110 
00111   for (int i=1; i <= this->NVertices; i++) 
00112     {
00113     for (int j=0; j < this->Degree[i]; j++) 
00114       {
00115       computedIndegrees[ this->edge(i,j) ] ++;
00116       }
00117     }
00118 }
00119 
00120 //----------------------------------------------------------------------------
00121 void ctkDependencyGraph::ctkInternal::traverseUsingDFS(int v)
00122 {
00123   // allow for search termination
00124   if (this->Abort)
00125     {
00126     return;
00127     }
00128 
00129   this->Discovered[v] = true;
00130   this->processVertex(v);
00131 
00132   int y; // successor vertex
00133   for (int i=0; i<this->Degree[v]; i++)
00134     {
00135     y = this->edge(v, i);
00136     if (this->P->shouldExcludeEdge(this->edge(v, i)) == false)
00137       {
00138       if (this->Discovered[y] == false)
00139         {
00140         this->Parent[y] = v;
00141         this->traverseUsingDFS(y);
00142         } 
00143       else 
00144         {
00145         if (this->Processed[y] == false)
00146           {
00147           this->processEdge(v,y);
00148           }
00149         }
00150       }
00151     if (this->Abort)
00152       {
00153       return;
00154       }
00155   }
00156 
00157   this->Processed[v] = true;
00158 }
00159 
00160 //----------------------------------------------------------------------------
00161 void ctkDependencyGraph::ctkInternal::processEdge(int from, int to)
00162 {
00163   if (this->Parent[from] != to)
00164     {
00165     this->CycleDetected = true;
00166     this->CycleOrigin = to; 
00167     this->CycleEnd = from;
00168     if (this->Verbose)
00169       {
00170       QList<int> path;
00171       this->findPathDFS(from, to, path);
00172       qWarning() << "Cycle detected from " << to << " to " << from;
00173       qWarning() << " " << path;
00174       path.clear();
00175       this->findPathDFS(to, from, path);
00176       qWarning() << " " << path;
00177       }
00178     this->Abort = true;
00179     }
00180 }
00181 
00182 //----------------------------------------------------------------------------
00183 void ctkDependencyGraph::ctkInternal::processVertex(int v)
00184 {
00185   if (this->Verbose)
00186     {
00187     qDebug() << "processed vertex " << v;
00188     }
00189 }
00190 
00191 //----------------------------------------------------------------------------
00192 void ctkDependencyGraph::ctkInternal::setEdge(int vertice, int degree, int value)
00193 {
00194   Q_ASSERT(vertice <= this->NVertices);
00195   Q_ASSERT(degree < MAXDEGREE);
00196   (*this->Edges[vertice])[degree] = value; 
00197 }
00198 
00199 //----------------------------------------------------------------------------
00200 int ctkDependencyGraph::ctkInternal::edge(int vertice, int degree)
00201 {
00202   Q_ASSERT(vertice <= this->NVertices);
00203   Q_ASSERT(degree < MAXDEGREE);
00204   return (*this->Edges[vertice])[degree];
00205 }
00206 
00207 //----------------------------------------------------------------------------
00208 void ctkDependencyGraph::ctkInternal::findPathDFS(int from, int to, QList<int>& path)
00209 {
00210   if ((from == to) || (to == -1))
00211     {
00212     path << from;
00213     }
00214   else 
00215     {
00216     this->findPathDFS(from, this->Parent[to], path);
00217     path << to;
00218     }
00219 }
00220 
00221 //----------------------------------------------------------------------------
00222 void ctkDependencyGraph::ctkInternal::findPathsRec(
00223   int from, int to, QList<int>* path, QList<QList<int>* >& paths)
00224 {
00225   if (from == to)
00226     {
00227     return;
00228     }
00229   
00230   QList<int> branch(*path);
00231   int child = from;
00232   for (int j=0; j < this->Degree[child]; j++)
00233     {
00234     if (j == 0)
00235       {
00236       int parent = this->edge(child, j);
00237       *path << parent;
00238       this->findPathsRec(parent, to, path, paths);
00239       }
00240     else
00241       {
00242       int parent = this->edge(child, j);
00243       // Copy path and add it to the list
00244       QList<int>* pathCopy = new QList<int>(branch);
00245       paths << pathCopy;
00246       *pathCopy << parent;
00247       this->findPathsRec(parent, to, pathCopy, paths);
00248       }
00249     }
00250 }
00251     
00252 //----------------------------------------------------------------------------
00253 // ctkDependencyGraph methods
00254 
00255 //----------------------------------------------------------------------------
00256 ctkDependencyGraph::ctkDependencyGraph(int nvertices)
00257 {
00258   this->Internal = new ctkInternal(this);
00259   
00260   this->Internal->NVertices = nvertices; 
00261   
00262   // Resize internal array
00263   this->Internal->Processed.resize(nvertices + 1);
00264   this->Internal->Discovered.resize(nvertices + 1);
00265   this->Internal->Parent.resize(nvertices + 1);
00266   this->Internal->Edges.resize(nvertices + 1);
00267   this->Internal->Degree.resize(nvertices + 1);
00268 
00269   for (int i=1; i <= nvertices; i++)
00270     {
00271     this->Internal->Degree[i] = 0;
00272     }
00273     
00274   // initialize Edge adjacency list
00275   for (int i=0; i <= nvertices; i++)
00276     {
00277     this->Internal->Edges[i] = new QVarLengthArray<int, MAXDEGREE>();
00278     this->Internal->Edges[i]->resize(MAXDEGREE);
00279     }
00280     
00281   // initialize search
00282   for (int i=1; i <= nvertices; i++)
00283     {
00284     this->Internal->Processed[i] = false;
00285     this->Internal->Discovered[i] = false;
00286     this->Internal->Parent[i] = -1;
00287     }
00288 }
00289 
00290 //----------------------------------------------------------------------------
00291 ctkDependencyGraph::~ctkDependencyGraph()
00292 {
00293   // Clean memory
00294   for (int i=0; i <= this->Internal->NVertices; i++)
00295     {
00296     delete this->Internal->Edges[i];
00297     }
00298     
00299   delete this->Internal; 
00300 }
00301 
00302 //----------------------------------------------------------------------------
00303 void ctkDependencyGraph::printAdditionalInfo()
00304 {
00305   qDebug() << "ctkDependencyGraph (" << this << ")" << endl
00306            << " NVertices:" << this->numberOfVertices() << endl
00307            << " NEdges:" << this->numberOfEdges() << endl
00308            << " Abort:" << this->Internal->Abort;
00309            
00310   qDebug() << " [Processed]";
00311   for(int i=1; i < this->Internal->Processed.size(); i++)
00312     {
00313     qDebug() << i << "->" << this->Internal->Processed[i];
00314     }
00315   qDebug() << " [Discovered]";
00316   for(int i=1; i < this->Internal->Discovered.size(); i++)
00317     {
00318     qDebug() << i << "->" << this->Internal->Discovered[i];
00319     }
00320   qDebug() << " [Parent]";
00321   for(int i=1; i < this->Internal->Parent.size(); i++)
00322     {
00323     qDebug() << i << "->" << this->Internal->Parent[i];
00324     }
00325   qDebug() << " [Graph]"; 
00326   this->printGraph();
00327 }
00328 
00329 //----------------------------------------------------------------------------
00330 void ctkDependencyGraph::printGraph()
00331 {
00332   for(int i=1; i <= this->Internal->NVertices; i++)
00333     {
00334     std::cout << i << ":";
00335     for (int j=0; j < this->Internal->Degree[i]; j++)
00336       {
00337       std::cout << " " << this->Internal->edge(i, j);
00338       }
00339     std::cout << std::endl;
00340     }
00341 }
00342 
00343 //----------------------------------------------------------------------------
00344 int ctkDependencyGraph::numberOfVertices()
00345 {
00346   return this->Internal->NVertices;
00347 }
00348 
00349 //----------------------------------------------------------------------------
00350 int ctkDependencyGraph::numberOfEdges()
00351 {
00352   return this->Internal->NEdges;
00353 }
00354 
00355 //----------------------------------------------------------------------------
00356 void ctkDependencyGraph::setVerbose(bool verbose)
00357 {
00358   this->Internal->Verbose = verbose;
00359 }
00360 
00361 //----------------------------------------------------------------------------
00362 void ctkDependencyGraph::setEdgeListToExclude(const QList<int>& list)
00363 {
00364   this->Internal->ListOfEdgeToExclude = list;
00365 }
00366 
00367 //----------------------------------------------------------------------------
00368 bool ctkDependencyGraph::shouldExcludeEdge(int edge)
00369 {
00370   return this->Internal->ListOfEdgeToExclude.contains(edge);
00371 }
00372 
00373 //----------------------------------------------------------------------------
00374 bool ctkDependencyGraph::checkForCycle()
00375 {
00376   if (this->Internal->NEdges > 0)
00377     {
00378     // get a valid vertice Id
00379     int verticeId = 1;
00380     this->Internal->traverseUsingDFS(verticeId);
00381     }
00382   return this->cycleDetected();
00383 }
00384 
00385 //----------------------------------------------------------------------------
00386 bool ctkDependencyGraph::cycleDetected()
00387 {
00388   return this->Internal->CycleDetected;
00389 }
00390 
00391 //----------------------------------------------------------------------------
00392 int ctkDependencyGraph::cycleOrigin()
00393 {
00394   return this->Internal->CycleOrigin;
00395 }
00396 
00397 //----------------------------------------------------------------------------
00398 int ctkDependencyGraph::cycleEnd()
00399 {
00400   return this->Internal->CycleEnd;
00401 }
00402 
00403 //----------------------------------------------------------------------------
00404 void ctkDependencyGraph::insertEdge(int from, int to)
00405 {
00406   Q_ASSERT(from > 0 && from <= this->Internal->NVertices);
00407   Q_ASSERT(to > 0 && to <= this->Internal->NVertices);
00408   
00409   // resize if needed
00410   int capacity = this->Internal->Edges[from]->capacity(); 
00411   if (this->Internal->Degree[from] > capacity)
00412     {
00413     this->Internal->Edges[from]->resize(capacity + capacity * 0.3);
00414     }
00415 
00416   this->Internal->setEdge(from, this->Internal->Degree[from], to);
00417   this->Internal->Degree[from]++;
00418 
00419   this->Internal->NEdges++;
00420 }
00421 
00422 //----------------------------------------------------------------------------
00423 void ctkDependencyGraph::findPaths(int from, int to, QList<QList<int>* >& paths)
00424 {
00425   QList<int>* path = new QList<int>;
00426   *path << from; 
00427   paths << path;
00428   this->Internal->findPathsRec(from, to, path, paths);
00429 
00430   QList<int> pathToRemove;
00431   // Remove list no ending with the requested element
00432   int i = 0; 
00433   while (!paths.isEmpty() && i < paths.size())
00434     {
00435     QList<int>* p = paths[i];
00436     Q_ASSERT(p);
00437     if (p->last() != to)
00438       {
00439       paths.removeAt(i);
00440       delete p; 
00441       }
00442     else
00443       {
00444       i++;
00445       }
00446     }
00447 }
00448 
00449 //----------------------------------------------------------------------------
00450 void ctkDependencyGraph::findPath(int from, int to, QList<int>& path)
00451 {
00452   int child = from;
00453   int parent = this->Internal->edge(child, 0);
00454   path << child; 
00455   while (parent > 0)
00456     {
00457     path << parent;
00458     if (parent == to)
00459       {
00460       break;
00461       }
00462     child = parent;
00463     parent = this->Internal->edge(child, 0);
00464     }
00465 }
00466 
00467 //----------------------------------------------------------------------------
00468 bool ctkDependencyGraph::topologicalSort(QList<int>& sorted)
00469 {
00470   QVarLengthArray<int, MAXV> indegree; // indegree of each vertex
00471   QQueue<int> zeroin;   // vertices of indegree 0
00472   int x, y;             // current and next vertex
00473   
00474   indegree.resize(this->Internal->NVertices + 1);
00475   
00476   // resize if needed
00477   if (this->Internal->NVertices > MAXV)
00478     {
00479     indegree.resize(this->Internal->NVertices);
00480     }
00481 
00482   this->Internal->computeIndegrees(indegree);
00483   
00484   for (int i=1; i <= this->Internal->NVertices; i++)
00485     {
00486     if (indegree[i] == 0) 
00487       {
00488       zeroin.enqueue(i);
00489       }
00490     }
00491 
00492   int j=0;
00493   while (zeroin.empty() == false) 
00494     {
00495     j = j+1;
00496     x = zeroin.dequeue();
00497     sorted << x;
00498     for (int i=0; i < this->Internal->Degree[x]; i++)
00499       {
00500       y = this->Internal->edge(x, i);
00501       indegree[y] --;
00502       if (indegree[y] == 0)
00503         {
00504         zeroin.enqueue(y);
00505         }
00506       }
00507     }
00508 
00509   if (j != this->Internal->NVertices)
00510     {
00511     return false;
00512     }
00513     
00514   return true;
00515 }
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Defines

Generated on 21 May 2010 for CTK by  doxygen 1.6.1