X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=src%2FGraph.cpp;h=036bb38857359e6d8a6f78b8c568b97ca6d8c89e;hb=0120c3fc10f1f1cc062f0c2a445fcee5d336d9f3;hp=da7170b2cba91a050a4a11c139bf460e896742ec;hpb=29033002779dc9f6c340050502d8b9c3fb87d66b;p=lyx.git

diff --git a/src/Graph.cpp b/src/Graph.cpp
index da7170b2cb..036bb38857 100644
--- a/src/Graph.cpp
+++ b/src/Graph.cpp
@@ -24,12 +24,13 @@ 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 (!Q.empty())
+		Q = queue<int>();
 
 	if (clear_visited) {
 		vector<Vertex>::iterator it = vertices_.begin();
@@ -38,39 +39,31 @@ bool Graph::bfs_init(int s, bool clear_visited)
 			it->visited = false;
 	}
 	if (!vertices_[s].visited) {
-		Q_.push(s);
+		Q.push(s);
 		vertices_[s].visited = true;
 	}
 	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::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
+	// 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 current = Q_.front();
-		Q_.pop();
-		if (current != target || formats.get(target).name() != "lyx")
+	while (!Q.empty()) {
+		int const current = Q.front();
+		Q.pop();
+		if (current != target || theFormats().get(target).name() != "lyx")
 			result.push_back(current);
 
 		vector<Arrow *>::iterator it = vertices_[current].in_arrows.begin();
@@ -79,7 +72,7 @@ vector<int> const
 			const int cv = (*it)->from;
 			if (!vertices_[cv].visited) {
 				vertices_[cv].visited = true;
-				Q_.push(cv);
+				Q.push(cv);
 			}
 		}
 	}
@@ -88,23 +81,24 @@ 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();
-		Format const & format = formats.get(current);
+	while (!Q.empty()) {
+		int const current = Q.front();
+		Q.pop();
+		Format const & format = theFormats().get(current);
 		if (!only_viewable || !format.viewer().empty())
 			result.push_back(current);
 		else if (format.isChildFormat()) {
 			Format const * const parent =
-				formats.getFormat(format.parentFormat());
+				theFormats().getFormat(format.parentFormat());
 			if (parent && !parent->viewer().empty())
 				result.push_back(current);
 		}
@@ -117,7 +111,8 @@ vector<int> const
 			int const cv = (*cit)->to;
 			if (!vertices_[cv].visited) {
 				vertices_[cv].visited = true;
-				Q_.push(cv);
+				if (excludes.find(cv) == excludes.end())
+					Q.push(cv);
 			}
 		}
 	}
@@ -131,12 +126,13 @@ 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;
 
@@ -148,7 +144,7 @@ bool Graph::isReachable(int from, int to)
 			int const cv = (*cit)->to;
 			if (!vertices_[cv].visited) {
 				vertices_[cv].visited = true;
-				Q_.push(cv);
+				Q.push(cv);
 			}
 		}
 	}
@@ -159,24 +155,18 @@ 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;
-
-	// 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 current = Q_.front();
-		Q_.pop();
+		return EdgePath();
+
+	queue<int> Q;
+	if (to < 0 || !bfs_init(from, true, Q))
+		return EdgePath();
+
+	vector<EdgePath> pathes;
+	pathes.resize(vertices_.size());
+	while (!Q.empty()) {
+		int const current = Q.front();
+		Q.pop();
 
 		vector<Arrow *>::const_iterator cit =
 			vertices_[current].out_arrows.begin();
@@ -186,53 +176,24 @@ Graph::EdgePath const Graph::getPath(int from, int to)
 			int const cv = (*cit)->to;
 			if (!vertices_[cv].visited) {
 				vertices_[cv].visited = true;
-				Q_.push(cv);
-				(*cit)->marked = 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;
-
-	getMarkedPath(from, to, path);
-	return path;
+	// failure
+	return EdgePath();
 }
 
 
-// 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 const en = vertices_[to].in_arrows.end();
-	for (; it != en; ++it)
-		if ((*it)->marked) 
-			break;
-	if (it == en) {
-		// debug code to try to figure out what's up.
-		LYXERR0("Failed to find marked arrow.\n"
-						"From: " << from << ", To: " << to);
-		dumpGraph();
-		LASSERT(false, /* */);
-		return;
-	}
-	path.push_back((*it)->id);
-	getMarkedPath(from, (*it)->from, path);
-}
-
-	
 void Graph::init(int size)
 {
 	vertices_ = vector<Vertex>(size);
@@ -251,6 +212,9 @@ void Graph::addEdge(int from, int to)
 }
 
 
+// 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();
@@ -261,16 +225,15 @@ void Graph::dumpGraph() const
 		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
-					<< ". Marked: " << (*iit)->marked);
+			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
-						<< ". Marked: " << (*iit)->marked);
+			LYXERR0("From " << (*iit)->from << " to " << (*iit)->to);
 	}
 }
+#endif
 
 
 } // namespace lyx