X-Git-Url: https://git.lyx.org/gitweb/?a=blobdiff_plain;f=src%2FGraph.h;h=2f5de3de36fd6812eee65ed114a771e7ffcf9b33;hb=1bd49f9c39b103b2d8bbe079bc603cfa47509ae5;hp=f2296b85a97b56d7c3f8cefa4017ea3c11cac415;hpb=f630be890494c849981e4fb52ea4740506e92bed;p=lyx.git

diff --git a/src/Graph.h b/src/Graph.h
index f2296b85a9..2f5de3de36 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,55 +13,87 @@
 #ifndef GRAPH_H
 #define GRAPH_H
 
+
+#include <list>
 #include <queue>
+#include <set>
 #include <vector>
 
 
 namespace lyx {
 
 
+/// Represents a directed graph, possibly with multiple edges
+/// connecting the vertices.
 class Graph {
 public:
-	Graph() : numedges_(0) {};
+	Graph() : numedges_(0) {}
 	///
 	typedef std::vector<int> EdgePath;
-	///
-	std::vector<int> const
-	getReachableTo(int, bool clear_visited);
-	///
-	std::vector<int> const
-	getReachable(int, bool only_viewable,
-		     bool clear_visited);
-	///
-	bool isReachable(int, int);
-	///
-	EdgePath const getPath(int, int);
-	///
-	void addEdge(int s, int t);
-	///
+	/// \return a vector of the vertices from which "to" can be reached
+	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". always returns one of the
+	/// shortest such paths.
+	EdgePath const getPath(int from, int to);
+	/// called repeatedly to build the graph
+	void addEdge(int from, int to);
+	/// reset the internal data structures
 	void init(int size);
 
 private:
 	///
-	int bfs_init(int, bool clear_visited = true);
-
-	///
-	class Vertex {
-	public:
-		std::vector<int> in_vertices;
-		std::vector<int> out_vertices;
-		std::vector<int> out_edges;
+	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;
 	};
-	///
-	static
+	/// 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 {
+		/// 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;
+	};
+	/// 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_;
-	///
-	std::vector<bool> visited_;
-	///
-	std::queue<int> Q_;
 
+	/// 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_;
-
 };