X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=src%2FGraph.cpp;h=97427bcf1a662566b720ca1a89612099523eb072;hb=90f7007a2e6c78ffd031e4636ff909ab1bc2ddec;hp=f5e37b9c5dd583b370f01e609de05f0c45147761;hpb=15718875118d6804029fa768d8af095d877c7fac;p=lyx.git

diff --git a/src/Graph.cpp b/src/Graph.cpp
index f5e37b9c5d..97427bcf1a 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,47 +24,55 @@ using namespace std;
 namespace lyx {
 
 
-bool Graph::bfs_init(int s, bool clear_visited)
+bool Graph::bfs_init(int s, bool clear_visited, queue<int> & Q)
 {
 	if (s < 0)
 		return false;
-
-	Q_ = queue<int>();
-
-	if (clear_visited)
-		fill(visited_.begin(), visited_.end(), false);
-	if (visited_[s] == false) {
-		Q_.push(s);
-		visited_[s] = true;
+	
+	if (!Q.empty())
+		Q = queue<int>();
+
+	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);
+		vertices_[s].visited = true;
 	}
 	return true;
 }
 
 
-vector<int> const
+Graph::EdgePath const
 	Graph::getReachableTo(int target, bool clear_visited)
 {
-	vector<int> result;
-	if (!bfs_init(target, clear_visited))
+	EdgePath result;
+	queue<int> Q;
+	if (!bfs_init(target, clear_visited, Q))
 		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 initailized to the current node
+	// 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.
-	while (!Q_.empty()) {
-		int const current = Q_.front();
-		Q_.pop();
+	// from the current node as we go. That makes it a breadth-first
+	// search.
+	while (!Q.empty()) {
+		int const current = Q.front();
+		Q.pop();
 		if (current != target || formats.get(target).name() != "lyx")
 			result.push_back(current);
 
-		vector<int>::iterator it = vertices_[current].in_vertices.begin();
-		vector<int>::iterator end = vertices_[current].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);
 			}
 		}
 	}
@@ -69,17 +81,18 @@ vector<int> const
 }
 
 
-vector<int> const
+Graph::EdgePath const
 	Graph::getReachable(int from, bool only_viewable,
-		bool clear_visited)
+		bool clear_visited, set<int> excludes)
 {
-	vector<int> result;
-	if (!bfs_init(from, clear_visited))
+	EdgePath result;
+	queue<int> Q;
+	if (!bfs_init(from, clear_visited, Q))
 		return result;
 
-	while (!Q_.empty()) {
-		int const current = Q_.front();
-		Q_.pop();
+	while (!Q.empty()) {
+		int const current = Q.front();
+		Q.pop();
 		Format const & format = formats.get(current);
 		if (!only_viewable || !format.viewer().empty())
 			result.push_back(current);
@@ -90,15 +103,16 @@ vector<int> const
 				result.push_back(current);
 		}
 
-		vector<OutEdge>::const_iterator cit =
+		vector<Arrow *>::const_iterator cit =
 			vertices_[current].out_arrows.begin();
-		vector<OutEdge>::const_iterator end =
+		vector<Arrow *>::const_iterator end =
 			vertices_[current].out_arrows.end();
 		for (; cit != end; ++cit) {
-			int const cv = cit->vertex;
-			if (!visited_[cv]) {
-				visited_[cv] = true;
-				Q_.push(cv);
+			int const cv = (*cit)->to;
+			if (!vertices_[cv].visited) {
+				vertices_[cv].visited = true;
+				if (excludes.find(cv) == excludes.end())
+					Q.push(cv);
 			}
 		}
 	}
@@ -112,24 +126,25 @@ bool Graph::isReachable(int from, int to)
 	if (from == to)
 		return true;
 
-	if (to < 0 || !bfs_init(from))
+	queue<int> Q;
+	if (to < 0 || !bfs_init(from, true, Q))
 		return false;
 
-	while (!Q_.empty()) {
-		int const current = Q_.front();
-		Q_.pop();
+	while (!Q.empty()) {
+		int const current = Q.front();
+		Q.pop();
 		if (current == to)
 			return true;
 
-		vector<OutEdge>::const_iterator cit =
+		vector<Arrow *>::const_iterator cit =
 			vertices_[current].out_arrows.begin();
-		vector<OutEdge>::const_iterator end =
+		vector<Arrow *>::const_iterator end =
 			vertices_[current].out_arrows.end();
 		for (; cit != end; ++cit) {
-			int const cv = cit->vertex;
-			if (!visited_[cv]) {
-				visited_[cv] = true;
-				Q_.push(cv);
+			int const cv = (*cit)->to;
+			if (!vertices_[cv].visited) {
+				vertices_[cv].visited = true;
+				Q.push(cv);
 			}
 		}
 	}
@@ -140,71 +155,85 @@ bool Graph::isReachable(int from, int to)
 
 Graph::EdgePath const Graph::getPath(int from, int to)
 {
-	EdgePath path;
 	if (from == to)
-		return path;
-
-	if (to < 0 || !bfs_init(from))
-		return path;
+		return EdgePath();
 
-	// pair<vertex, edge>
-	vector<pair<int, int> > prev(vertices_.size());
+	queue<int> Q;
+	if (to < 0 || !bfs_init(from, true, Q))
+		return EdgePath();
 
-	bool found = false;
-	while (!Q_.empty()) {
-		int const current = Q_.front();
-		Q_.pop();
+	vector<EdgePath> pathes;
+	pathes.resize(vertices_.size());
+	while (!Q.empty()) {
+		int const current = Q.front();
+		Q.pop();
 
-		vector<OutEdge>::const_iterator const beg =
+		vector<Arrow *>::const_iterator cit =
 			vertices_[current].out_arrows.begin();
-		vector<OutEdge>::const_iterator cit = beg;
-		vector<OutEdge>::const_iterator end =
+		vector<Arrow *>::const_iterator end =
 			vertices_[current].out_arrows.end();
 		for (; cit != end; ++cit) {
-			int const cv = cit->vertex;
-			if (!visited_[cv]) {
-				visited_[cv] = 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);
+			int const cv = (*cit)->to;
+			if (!vertices_[cv].visited) {
+				vertices_[cv].visited = true;
+				Q.push(cv);
+				// NOTE If we wanted to collect all the paths, then
+				// we just need to collect them here and not worry
+				// about "visited".
+				EdgePath lastpath = pathes[(*cit)->from];
+				lastpath.push_back((*cit)->id);
+				pathes[cv] = lastpath;
 			}
 			if (cv == to) {
-				found = true;
-				break;
+				return pathes[cv];
 			}
 		}
 	}
-	if (!found)
-		return path;
-
-	while (to != from) {
-		path.push_back(prev[to].second);
-		to = prev[to].first;
-	}
-	reverse(path.begin(), path.end());
-	return path;
+	// failure
+	return EdgePath();
 }
 
 
 void Graph::init(int size)
 {
 	vertices_ = vector<Vertex>(size);
-	visited_.resize(size);
+	arrows_.clear();
 	numedges_ = 0;
 }
 
 
 void Graph::addEdge(int from, int to)
 {
-	vertices_[to].in_vertices.push_back(from);
-	vertices_[from].out_arrows.push_back(OutEdge(to, 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_;
+// 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