4 * This file is part of LyX, the document processor.
5 * Licence details can be found in the file COPYING.
9 * Full author contact details are available in file CREDITS.
22 /// Represents a directed graph, possibly with multiple edges
23 /// connecting the vertices.
26 Graph() : numedges_(0) {}
28 typedef std::vector
<int> EdgePath
;
29 /// \return a vector of the vertices from which "to" can be reached
30 std::vector
<int> const getReachableTo(int to
, bool clear_visited
);
31 /// \return a vector of the vertices that can be reached from "from"
32 std::vector
<int> const
33 getReachable(int from
, bool only_viewable
, bool clear_visited
);
34 /// Can "from" be reached from "to"?
35 bool isReachable(int from
, int to
);
36 /// Find a path from "from" to "to".
37 EdgePath
const getPath(int from
, int to
);
38 /// Called repeatedly to build the graph.
39 void addEdge(int from
, int to
);
40 /// Reset the internal data structures.
45 bool bfs_init(int, bool clear_visited
= true);
49 OutEdge(int v
, int e
): vertex(v
), edge(e
) {}
55 /// vertices that point at this one
56 std::vector
<int> in_vertices
;
57 /// paths out from here
58 std::vector
<OutEdge
> out_arrows
;
61 static std::vector
<Vertex
> vertices_
;
62 /// used to keep track of which vertices we have seen
63 std::vector
<bool> visited_
;