X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=src%2FGraph.cpp;h=97427bcf1a662566b720ca1a89612099523eb072;hb=0430132aa049f2a97280bcbcff69f71d42ed7d98;hp=bfb61dc3f3456bdad25e1df35c6e79dcc49a766e;hpb=50a81deff4a67de46b4c183623f72bef715eb7d1;p=lyx.git

diff --git a/src/Graph.cpp b/src/Graph.cpp
index bfb61dc3f3..97427bcf1a 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,38 +39,30 @@ 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::clearPaths()
-{
-	vector<Vertex>::iterator it = vertices_.begin();
-	vector<Vertex>::iterator en = vertices_.end();
-	for (; it != en; ++it)
-		it->path.clear();
-}
-
-
-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();
+	while (!Q.empty()) {
+		int const current = Q.front();
+		Q.pop();
 		if (current != target || formats.get(target).name() != "lyx")
 			result.push_back(current);
 
@@ -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,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);
@@ -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,17 +155,18 @@ bool Graph::isReachable(int from, int to)
 
 Graph::EdgePath const Graph::getPath(int from, int to)
 {
-	static const EdgePath path;
 	if (from == to)
-		return path;
+		return EdgePath();
 
-	if (to < 0 || !bfs_init(from))
-		return path;
+	queue<int> Q;
+	if (to < 0 || !bfs_init(from, true, Q))
+		return EdgePath();
 
-	clearPaths();
-	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<Arrow *>::const_iterator cit =
 			vertices_[current].out_arrows.begin();
@@ -179,21 +176,21 @@ 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);
+				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 = vertices_[(*cit)->from].path;
+				EdgePath lastpath = pathes[(*cit)->from];
 				lastpath.push_back((*cit)->id);
-				vertices_[cv].path = lastpath;
+				pathes[cv] = lastpath;
 			}
 			if (cv == to) {
-				return vertices_[cv].path;
+				return pathes[cv];
 			}
 		}
 	}
 	// failure
-	return path;
+	return EdgePath();
 }