Buffer: Rename function names:

[lyx.git] / src / Graph.cpp

diff --git a/src/Graph.cpp b/src/Graph.cpp
index 8f2568b608260c79c2810eec7003a0cec0d610b7..bfb61dc3f3456bdad25e1df35c6e79dcc49a766e 100644 (file)
--- a/src/Graph.cpp
+++ b/src/Graph.cpp
@@ -3,7 +3,8 @@
  * This file is part of LyX, the document processor.
  * Licence details can be found in the file COPYING.
  *
- * \author Dekel Tsur
+ * \author Dekel Tsur (original code)
+ * \author Richard Heck (re-implementation)
  *
  * Full author contact details are available in file CREDITS.
  */
@@ -13,6 +14,9 @@
 #include "Graph.h"
 #include "Format.h"
 
+#include "support/debug.h"
+#include "support/lassert.h"
+
 #include <algorithm>
 
 using namespace std;
@@ -41,6 +45,15 @@ bool Graph::bfs_init(int s, bool clear_visited)
 }
 
 
+void Graph::clearPaths()
+{
+       vector<Vertex>::iterator it = vertices_.begin();
+       vector<Vertex>::iterator en = vertices_.end();
+       for (; it != en; ++it)
+               it->path.clear();
+}
+
+
 vector<int> const
        Graph::getReachableTo(int target, bool clear_visited)
 {
@@ -60,10 +73,10 @@ vector<int> const
                if (current != target || formats.get(target).name() != "lyx")
                        result.push_back(current);
 
-               vector<Arrow>::iterator it = vertices_[current].in_arrows.begin();
-               vector<Arrow>::iterator const end = vertices_[current].in_arrows.end();
+               vector<Arrow *>::iterator it = vertices_[current].in_arrows.begin();
+               vector<Arrow *>::iterator const end = vertices_[current].in_arrows.end();
                for (; it != end; ++it) {
-                       const int cv = it->vertex;
+                       const int cv = (*it)->from;
                        if (!vertices_[cv].visited) {
                                vertices_[cv].visited = true;
                                Q_.push(cv);
@@ -96,12 +109,12 @@ vector<int> const
                                result.push_back(current);
                }
 
-               vector<Arrow>::const_iterator cit =
+               vector<Arrow *>::const_iterator cit =
                        vertices_[current].out_arrows.begin();
-               vector<Arrow>::const_iterator end =
+               vector<Arrow *>::const_iterator end =
                        vertices_[current].out_arrows.end();
                for (; cit != end; ++cit) {
-                       int const cv = cit->vertex;
+                       int const cv = (*cit)->to;
                        if (!vertices_[cv].visited) {
                                vertices_[cv].visited = true;
                                Q_.push(cv);
@@ -127,12 +140,12 @@ bool Graph::isReachable(int from, int to)
                if (current == to)
                        return true;
 
-               vector<Arrow>::const_iterator cit =
+               vector<Arrow *>::const_iterator cit =
                        vertices_[current].out_arrows.begin();
-               vector<Arrow>::const_iterator end =
+               vector<Arrow *>::const_iterator end =
                        vertices_[current].out_arrows.end();
                for (; cit != end; ++cit) {
-                       int const cv = cit->vertex;
+                       int const cv = (*cit)->to;
                        if (!vertices_[cv].visited) {
                                vertices_[cv].visited = true;
                                Q_.push(cv);
@@ -146,68 +159,84 @@ bool Graph::isReachable(int from, int to)
 
 Graph::EdgePath const Graph::getPath(int from, int to)
 {
-       EdgePath path;
+       static const EdgePath path;
        if (from == to)
                return path;
 
        if (to < 0 || !bfs_init(from))
                return path;
 
-       // pair<vertex, edge>
-       vector<pair<int, int> > prev(vertices_.size());
-
-       bool found = false;
+       clearPaths();
        while (!Q_.empty()) {
                int const current = Q_.front();
                Q_.pop();
 
-               vector<Arrow>::const_iterator const beg =
+               vector<Arrow *>::const_iterator cit =
                        vertices_[current].out_arrows.begin();
-               vector<Arrow>::const_iterator cit = beg;
-               vector<Arrow>::const_iterator end =
+               vector<Arrow *>::const_iterator end =
                        vertices_[current].out_arrows.end();
                for (; cit != end; ++cit) {
-                       int const cv = cit->vertex;
+                       int const cv = (*cit)->to;
                        if (!vertices_[cv].visited) {
                                vertices_[cv].visited = true;
                                Q_.push(cv);
-                               // FIXME This will not do for finding multiple paths.
-                               // Perhaps we need a vector, or a set. We'll also want
-                               // to add this info, even if the node is visited, so
-                               // outside this conditional.
-                               prev[cv] = pair<int, int>(current, cit->edge);
+                               // NOTE If we wanted to collect all the paths, then
+                               // we just need to collect them here and not worry
+                               // about "visited".
+                               EdgePath lastpath = vertices_[(*cit)->from].path;
+                               lastpath.push_back((*cit)->id);
+                               vertices_[cv].path = lastpath;
                        }
                        if (cv == to) {
-                               found = true;
-                               break;
+                               return vertices_[cv].path;
                        }
                }
        }
-       if (!found)
-               return path;
-
-       while (to != from) {
-               path.push_back(prev[to].second);
-               to = prev[to].first;
-       }
-       reverse(path.begin(), path.end());
+       // failure
        return path;
 }
 
-       
+
 void Graph::init(int size)
 {
        vertices_ = vector<Vertex>(size);
+       arrows_.clear();
        numedges_ = 0;
 }
 
 
 void Graph::addEdge(int from, int to)
 {
-       vertices_[to].in_arrows.push_back(Arrow(from, numedges_));
-       vertices_[from].out_arrows.push_back(Arrow(to, numedges_));
-       ++numedges_;
+       arrows_.push_back(Arrow(from, to, numedges_));
+       numedges_++;
+       Arrow * ar = &(arrows_.back());
+       vertices_[to].in_arrows.push_back(ar);
+       vertices_[from].out_arrows.push_back(ar);
+}
+
+
+// At present, we do not need this debugging code, but
+// I am going to leave it here in case we need it again.
+#if 0
+void Graph::dumpGraph() const
+{
+       vector<Vertex>::const_iterator it = vertices_.begin();
+       vector<Vertex>::const_iterator en = vertices_.end();
+       for (; it != en; ++it) {
+               LYXERR0("Next vertex...");
+               LYXERR0("In arrows...");
+               std::vector<Arrow *>::const_iterator iit = it->in_arrows.begin();
+               std::vector<Arrow *>::const_iterator ien = it->in_arrows.end();
+               for (; iit != ien; ++iit)
+                       LYXERR0("From " << (*iit)->from << " to " << (*iit)->to);
+               LYXERR0("Out arrows...");
+               iit = it->out_arrows.begin();
+               ien = it->out_arrows.end();
+               for (; iit != ien; ++iit)
+                       LYXERR0("From " << (*iit)->from << " to " << (*iit)->to);
+       }
 }
+#endif
 
 
 } // namespace lyx