X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=src%2FGraph.h;h=50d8bf855da73919e7ac67a5f3bdfc77f6ad2ee3;hb=3d4076b598deb18660e50ec9c327efc3b15f15d0;hp=0114402094d62a218edb673c993a2bd36bd15b27;hpb=dfbbb87e0b2fcc2b711bd50c8205dd21a6df1732;p=lyx.git

diff --git a/src/Graph.h b/src/Graph.h
index 0114402094..50d8bf855d 100644
--- a/src/Graph.h
+++ b/src/Graph.h
@@ -4,7 +4,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.
  */
@@ -12,7 +13,10 @@
 #ifndef GRAPH_H
 #define GRAPH_H
 
+
+#include <list>
 #include <queue>
+#include <set>
 #include <vector>
 
 
@@ -27,45 +31,69 @@ public:
 	///
 	typedef std::vector<int> EdgePath;
 	/// \return a vector of the vertices from which "to" can be reached
-	std::vector<int> const getReachableTo(int to, bool clear_visited);
-	/// \return a vector of the vertices that can be reached from "from"
-	std::vector<int> const
-		getReachable(int from, bool only_viewable, bool clear_visited);
-	/// Can "from" be reached from "to"?
+	EdgePath const getReachableTo(int to, bool clear_visited);
+	/// \return a vector of the reachable vertices, avoiding all "excludes"
+	EdgePath const getReachable(int from, bool only_viewable,
+		bool clear_visited, std::set<int> excludes = std::set<int>());
+	/// can "from" be reached from "to"?
 	bool isReachable(int from, int to);
-	/// Find a path from "from" to "to".
+	/// find a path from "from" to "to". always returns one of the
+	/// shortest such paths.
 	EdgePath const getPath(int from, int to);
-	/// Called repeatedly to build the graph.
+	/// called repeatedly to build the graph
 	void addEdge(int from, int to);
-	/// Reset the internal data structures.
+	/// reset the internal data structures
 	void init(int size);
 
 private:
 	///
-	bool bfs_init(int, bool clear_visited = true);
-
-	///
-	struct OutEdge {
-		OutEdge(int v, int e): vertex(v), edge(e) {}
-		int vertex;
-		int edge;
+	bool bfs_init(int, bool clear_visited, std::queue<int> & Q);
+	/// these represent the arrows connecting the nodes of the graph.
+	/// this is the basic representation of the graph: as a bunch of 
+	/// arrows.
+	struct Arrow {
+		///
+		Arrow(int f, int t, int i): 
+			from(f), to(t), id(i) {}
+		/// the vertex at the tail of the arrow
+		int from;
+		/// the vertex at the head
+		int to;
+		/// an id for this arrow, e.g., for use in describing paths 
+		/// through the graph
+		int id;
 	};
-	///
+	/// a container for the arrows
+	/// we use a list because we want pointers to the arrows,
+	/// and a vector might invalidate them
+	typedef std::list<Arrow> Arrows;
+	Arrows arrows_;
+	/// Represents a vertex of the graph. Note that we could recover
+	/// the in_arrows and out_arrows from the Arrows, so these are in
+	/// effect a kind of cache.
 	struct Vertex {
-		/// vertices that point at this one
-		std::vector<int> in_vertices;
-		/// paths out from here
-		std::vector<OutEdge> out_arrows;
+		/// arrows that point at this one
+		std::vector<Arrow *> in_arrows;
+		/// arrows out from here
+		std::vector<Arrow *> out_arrows;
+		/// used in the search routines
+		bool visited;
 	};
-	///
-	static std::vector<Vertex> vertices_;
-	/// used to keep track of which vertices we have seen
-	std::vector<bool> visited_;
-	///
-	std::queue<int> Q_;
-
+	/// a container for the vertices
+	/// the index into the vector functions as the identifier by which
+	/// these are referenced in the Arrow struct
+	/// the code making use of the Graph must keep track of the relation
+	/// between these indices and the objects they represent. (in the case
+	/// of Format, this is easy, since the Format objects already have ints
+	/// as identifiers.)
+	std::vector<Vertex> vertices_;
+	
+	/// a counter that we use to assign id's to the arrows
+	/// FIXME This technique assumes a correspondence between the
+	/// ids of the arrows and ids associated with Converters that
+	/// seems kind of fragile. Perhaps a better solution would be
+	/// to pass the ids as we create the arrows.
 	int numedges_;
-
 };