4 * This file is part of LyX, the document processor.
5 * Licence details can be found in the file COPYING.
7 * \author Dekel Tsur (original code)
8 * \author Richard Heck (re-implementation)
10 * Full author contact details are available in file CREDITS.
24 /// Represents a directed graph, possibly with multiple edges
25 /// connecting the vertices.
28 Graph() : numedges_(0) {}
30 typedef std::vector<int> EdgePath;
31 /// \return a vector of the vertices from which "to" can be reached
32 std::vector<int> const getReachableTo(int to, bool clear_visited);
33 /// \return a vector of the vertices that can be reached from "from"
34 std::vector<int> const
35 getReachable(int from, bool only_viewable, bool clear_visited);
36 /// can "from" be reached from "to"?
37 bool isReachable(int from, int to);
38 /// find a path from "from" to "to". always returns one of the
39 /// shortest such paths.
40 EdgePath const getPath(int from, int to);
41 /// called repeatedly to build the graph
42 void addEdge(int from, int to);
43 /// reset the internal data structures
48 bool bfs_init(int, bool clear_visited = true);
49 /// clears the "marks" on the arrows. should be called
50 /// before any new marking begins.
52 /// used to recover a marked path
53 void getMarkedPath(int from, int to, EdgePath & path);
55 void dumpGraph() const;
56 /// these represent the arrows connecting the nodes of the graph.
57 /// this is the basic representation of the graph: as a bunch of
61 Arrow(int f, int t, int i):
62 from(f), to(t), id(i), marked(false) {}
63 /// the vertex at the tail of the arrow
65 /// the vertex at the head
67 /// an id for this arrow, e.g., for use in describing paths
70 /// used for "marking" paths, i.e., constructing sub-graphs
71 /// without really doing so.
74 /// a container for the arrows
75 /// we use a list because we want pointers to the arrows,
76 /// and a vector might invalidate them
77 typedef std::list<Arrow> Arrows;
79 /// Represents a vertex of the graph. Note that we could recover
80 /// the in_arrows and out_arrows from the Arrows, so these are in
81 /// effect a kind of cache.
83 /// arrows that point at this one
84 std::vector<Arrow *> in_arrows;
85 /// arrows out from here
86 std::vector<Arrow *> out_arrows;
87 /// used in the search routines
90 /// a container for the vertices
91 /// the index into the vector functions as the identifier by which
92 /// these are referenced in the Arrow struct
93 /// the code making use of the Graph must keep track of the relation
94 /// between these indices and the objects they represent. (in the case
95 /// of Format, this is easy, since the Format objects already have ints
97 std::vector<Vertex> vertices_;
100 /// a counter that we use to assign id's to the arrows
101 /// FIXME This technique assumes a correspondence between the
102 /// ids of the arrows and ids associated with Converters that
103 /// seems kind of fragile. Perhaps a better solution would be
104 /// to pass the ids as we create the arrows.