3 * This file is part of LyX, the document processor.
4 * Licence details can be found in the file COPYING.
8 * Full author contact details are available in file CREDITS.
23 bool Graph::bfs_init(int s, bool clear_visited)
31 vector<Vertex>::iterator it = vertices_.begin();
32 vector<Vertex>::iterator en = vertices_.end();
33 for (; it != en; ++it)
36 if (!vertices_[s].visited) {
38 vertices_[s].visited = true;
45 Graph::getReachableTo(int target, bool clear_visited)
48 if (!bfs_init(target, clear_visited))
51 // Here's the logic, which is shared by the other routines.
52 // Q_ holds a list of nodes we have been able to reach (in this
53 // case, reach backwards). It is initailized to the current node
54 // by bfs_init, and then we recurse, adding the nodes we can reach
55 // from the current node as we go. That makes it a breadth-first
58 int const current = Q_.front();
60 if (current != target || formats.get(target).name() != "lyx")
61 result.push_back(current);
63 vector<int>::iterator it = vertices_[current].in_vertices.begin();
64 vector<int>::iterator end = vertices_[current].in_vertices.end();
65 for (; it != end; ++it) {
66 if (!vertices_[*it].visited) {
67 vertices_[*it].visited = true;
78 Graph::getReachable(int from, bool only_viewable,
82 if (!bfs_init(from, clear_visited))
86 int const current = Q_.front();
88 Format const & format = formats.get(current);
89 if (!only_viewable || !format.viewer().empty())
90 result.push_back(current);
91 else if (format.isChildFormat()) {
92 Format const * const parent =
93 formats.getFormat(format.parentFormat());
94 if (parent && !parent->viewer().empty())
95 result.push_back(current);
98 vector<OutEdge>::const_iterator cit =
99 vertices_[current].out_arrows.begin();
100 vector<OutEdge>::const_iterator end =
101 vertices_[current].out_arrows.end();
102 for (; cit != end; ++cit) {
103 int const cv = cit->vertex;
104 if (!vertices_[cv].visited) {
105 vertices_[cv].visited = true;
115 bool Graph::isReachable(int from, int to)
120 if (to < 0 || !bfs_init(from))
123 while (!Q_.empty()) {
124 int const current = Q_.front();
129 vector<OutEdge>::const_iterator cit =
130 vertices_[current].out_arrows.begin();
131 vector<OutEdge>::const_iterator end =
132 vertices_[current].out_arrows.end();
133 for (; cit != end; ++cit) {
134 int const cv = cit->vertex;
135 if (!vertices_[cv].visited) {
136 vertices_[cv].visited = true;
146 Graph::EdgePath const Graph::getPath(int from, int to)
152 if (to < 0 || !bfs_init(from))
155 // pair<vertex, edge>
156 vector<pair<int, int> > prev(vertices_.size());
159 while (!Q_.empty()) {
160 int const current = Q_.front();
163 vector<OutEdge>::const_iterator const beg =
164 vertices_[current].out_arrows.begin();
165 vector<OutEdge>::const_iterator cit = beg;
166 vector<OutEdge>::const_iterator end =
167 vertices_[current].out_arrows.end();
168 for (; cit != end; ++cit) {
169 int const cv = cit->vertex;
170 if (!vertices_[cv].visited) {
171 vertices_[cv].visited = true;
173 // FIXME This will not do for finding multiple paths.
174 // Perhaps we need a vector, or a set. We'll also want
175 // to add this info, even if the node is visited, so
176 // outside this conditional.
177 prev[cv] = pair<int, int>(current, cit->edge);
189 path.push_back(prev[to].second);
192 reverse(path.begin(), path.end());
197 void Graph::init(int size)
199 vertices_ = vector<Vertex>(size);
204 void Graph::addEdge(int from, int to)
206 vertices_[to].in_vertices.push_back(from);
207 vertices_[from].out_arrows.push_back(OutEdge(to, numedges_++));