X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=src%2FGraph.cpp;h=d30e3d4999fffd31211f2d510b9ba0c96fb6fe38;hb=f37a1b8aeaf8f3a3a66a22bf0b396f7d1ceca2ff;hp=e15a7d48ef80194ac2cd7f2036e9b9d3202d308b;hpb=9abb7db46800e554f57e865a3e768602ffd9d6f1;p=lyx.git

diff --git a/src/Graph.cpp b/src/Graph.cpp
index e15a7d48ef..d30e3d4999 100644
--- 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;
@@ -20,44 +24,62 @@ using namespace std;
 namespace lyx {
 
 
-int Graph::bfs_init(int s, bool clear_visited)
+bool Graph::bfs_init(int s, bool clear_visited)
 {
 	if (s < 0)
-		return s;
+		return false;
 
 	Q_ = queue<int>();
 
-	if (clear_visited)
-		fill(visited_.begin(), visited_.end(), false);
-	if (visited_[s] == false) {
+	if (clear_visited) {
+		vector<Vertex>::iterator it = vertices_.begin();
+		vector<Vertex>::iterator en = vertices_.end();
+		for (; it != en; ++it)
+			it->visited = false;
+	}
+	if (!vertices_[s].visited) {
 		Q_.push(s);
-		visited_[s] = true;
+		vertices_[s].visited = true;
 	}
-	return s;
+	return true;
+}
+
+
+void Graph::clearMarks()
+{
+	Arrows::iterator it = arrows_.begin();
+	Arrows::iterator const en = arrows_.end();
+	for (; it != en; ++it)
+		it->marked = false;
 }
 
 
 vector<int> const
-Graph::getReachableTo(int target, bool clear_visited)
+	Graph::getReachableTo(int target, bool clear_visited)
 {
 	vector<int> result;
-	int const s = bfs_init(target, clear_visited);
-	if (s < 0)
+	if (!bfs_init(target, clear_visited))
 		return result;
 
+	// Here's the logic, which is shared by the other routines.
+	// Q_ holds a list of nodes we have been able to reach (in this
+	// case, reach backwards). It is initialized to the current node
+	// by bfs_init, and then we recurse, adding the nodes we can reach
+	// from the current node as we go. That makes it a breadth-first
+	// search.
 	while (!Q_.empty()) {
-		int const i = Q_.front();
+		int const current = Q_.front();
 		Q_.pop();
-		if (i != s || formats.get(target).name() != "lyx") {
-			result.push_back(i);
-		}
+		if (current != target || formats.get(target).name() != "lyx")
+			result.push_back(current);
 
-		vector<int>::iterator it = vertices_[i].in_vertices.begin();
-		vector<int>::iterator end = vertices_[i].in_vertices.end();
+		vector<Arrow *>::iterator it = vertices_[current].in_arrows.begin();
+		vector<Arrow *>::iterator const end = vertices_[current].in_arrows.end();
 		for (; it != end; ++it) {
-			if (!visited_[*it]) {
-				visited_[*it] = true;
-				Q_.push(*it);
+			const int cv = (*it)->from;
+			if (!vertices_[cv].visited) {
+				vertices_[cv].visited = true;
+				Q_.push(cv);
 			}
 		}
 	}
@@ -67,35 +89,37 @@ Graph::getReachableTo(int target, bool clear_visited)
 
 
 vector<int> const
-Graph::getReachable(int from, bool only_viewable,
-		    bool clear_visited)
+	Graph::getReachable(int from, bool only_viewable,
+		bool clear_visited)
 {
 	vector<int> result;
-	if (bfs_init(from, clear_visited) < 0)
+	if (!bfs_init(from, clear_visited))
 		return result;
 
 	while (!Q_.empty()) {
-		int const i = Q_.front();
+		int const current = Q_.front();
 		Q_.pop();
-		Format const & format = formats.get(i);
+		Format const & format = formats.get(current);
 		if (!only_viewable || !format.viewer().empty())
-			result.push_back(i);
+			result.push_back(current);
 		else if (format.isChildFormat()) {
 			Format const * const parent =
 				formats.getFormat(format.parentFormat());
 			if (parent && !parent->viewer().empty())
-				result.push_back(i);
+				result.push_back(current);
 		}
 
-		vector<int>::const_iterator cit =
-			vertices_[i].out_vertices.begin();
-		vector<int>::const_iterator end =
-			vertices_[i].out_vertices.end();
-		for (; cit != end; ++cit)
-			if (!visited_[*cit]) {
-				visited_[*cit] = true;
-				Q_.push(*cit);
+		vector<Arrow *>::const_iterator cit =
+			vertices_[current].out_arrows.begin();
+		vector<Arrow *>::const_iterator end =
+			vertices_[current].out_arrows.end();
+		for (; cit != end; ++cit) {
+			int const cv = (*cit)->to;
+			if (!vertices_[cv].visited) {
+				vertices_[cv].visited = true;
+				Q_.push(cv);
 			}
+		}
 	}
 
 	return result;
@@ -107,24 +131,24 @@ bool Graph::isReachable(int from, int to)
 	if (from == to)
 		return true;
 
-	int const s = bfs_init(from);
-	if (s < 0 || to < 0)
+	if (to < 0 || !bfs_init(from))
 		return false;
 
 	while (!Q_.empty()) {
-		int const i = Q_.front();
+		int const current = Q_.front();
 		Q_.pop();
-		if (i == to)
+		if (current == to)
 			return true;
 
-		vector<int>::const_iterator cit =
-			vertices_[i].out_vertices.begin();
-		vector<int>::const_iterator end =
-			vertices_[i].out_vertices.end();
+		vector<Arrow *>::const_iterator cit =
+			vertices_[current].out_arrows.begin();
+		vector<Arrow *>::const_iterator end =
+			vertices_[current].out_arrows.end();
 		for (; cit != end; ++cit) {
-			if (!visited_[*cit]) {
-				visited_[*cit] = true;
-				Q_.push(*cit);
+			int const cv = (*cit)->to;
+			if (!vertices_[cv].visited) {
+				vertices_[cv].visited = true;
+				Q_.push(cv);
 			}
 		}
 	}
@@ -133,70 +157,95 @@ bool Graph::isReachable(int from, int to)
 }
 
 
-Graph::EdgePath const
-Graph::getPath(int from, int t)
+Graph::EdgePath const Graph::getPath(int from, int to)
 {
 	EdgePath path;
-	if (from == t)
+	if (from == to)
 		return path;
 
-	int const s = bfs_init(from);
-	if (s < 0 || t < 0)
+	if (to < 0 || !bfs_init(from))
 		return path;
 
-	vector<int> prev_edge(formats.size());
-	vector<int> prev_vertex(formats.size());
-
+	// In effect, the way this works is that we construct a sub-graph
+	// by starting at "from" and following the arrows outward. Instead
+	// of actually constructing a sub-graph, though, we "mark" the
+	// arrows we traverse as we go. Once we hit "to", we abort the 
+	// marking process and then call getMarkedPath() to reconstruct
+	// the marked path.
 	bool found = false;
+	clearMarks();
 	while (!Q_.empty()) {
-		int const i = Q_.front();
+		int const current = Q_.front();
 		Q_.pop();
-		if (i == t) {
-			found = true;
-			break;
-		}
 
-		vector<int>::const_iterator beg =
-			vertices_[i].out_vertices.begin();
-		vector<int>::const_iterator cit = beg;
-		vector<int>::const_iterator end =
-			vertices_[i].out_vertices.end();
-		for (; cit != end; ++cit)
-			if (!visited_[*cit]) {
-				int const j = *cit;
-				visited_[j] = true;
-				Q_.push(j);
-				int const k = cit - beg;
-				prev_edge[j] = vertices_[i].out_edges[k];
-				prev_vertex[j] = i;
+		vector<Arrow *>::const_iterator const beg =
+			vertices_[current].out_arrows.begin();
+		vector<Arrow *>::const_iterator cit = beg;
+		vector<Arrow *>::const_iterator end =
+			vertices_[current].out_arrows.end();
+		for (; cit != end; ++cit) {
+			int const cv = (*cit)->to;
+			if (!vertices_[cv].visited) {
+				vertices_[cv].visited = true;
+				Q_.push(cv);
+				(*cit)->marked = true;
 			}
+			if (cv == to) {
+				found = true;
+				break;
+			}
+		}
 	}
 	if (!found)
 		return path;
 
-	while (t != s) {
-		path.push_back(prev_edge[t]);
-		t = prev_vertex[t];
-	}
-	reverse(path.begin(), path.end());
+	getMarkedPath(from, to, path);
 	return path;
 }
 
+
+// We assume we have marked the graph, as in getPath(). We also
+// assume that we have done so in such a way as to guarantee a
+// marked path from "from" to "to".
+// We then start at "to" and find the arrow leading to it that
+// has been marked. We add that to the path we are constructing,
+// step back on that arrow, and continue the process (i.e., recurse).
+void Graph::getMarkedPath(int from, int to, EdgePath & path) {
+	if (from == to) {
+		reverse(path.begin(), path.end());
+		return;
+	}
+	// find marked in_arrow
+	vector<Arrow *>::const_iterator it = vertices_[to].in_arrows.begin();
+	vector<Arrow *>::const_iterator en = vertices_[to].in_arrows.end();
+	for (; it != en; ++it)
+		if ((*it)->marked) 
+			break;
+	if (it == en) {
+		LASSERT(false, /* */);
+		return;
+	}
+	path.push_back((*it)->id);
+	getMarkedPath(from, (*it)->from, path);
+}
+
+	
 void Graph::init(int size)
 {
 	vertices_ = vector<Vertex>(size);
-	visited_.resize(size);
+	arrows_.clear();
 	numedges_ = 0;
 }
 
-void Graph::addEdge(int s, int t)
+
+void Graph::addEdge(int from, int to)
 {
-	vertices_[t].in_vertices.push_back(s);
-	vertices_[s].out_vertices.push_back(t);
-	vertices_[s].out_edges.push_back(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);
 }
 
-vector<Graph::Vertex> Graph::vertices_;
-
 
 } // namespace lyx