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 fill(visited_.begin(), visited_.end(), false);
32 if (visited_[s] == false) {
41 Graph::getReachableTo(int target, bool clear_visited)
44 if (!bfs_init(target, clear_visited))
47 // Here's the logic, which is shared by the other routines.
48 // Q_ holds a list of nodes we have been able to reach (in this
49 // case, reach backwards). It is initailized to the current node
50 // by bfs_init, and then we recurse, adding the nodes we can reach
51 // from the current node as we go.
53 int const current = Q_.front();
55 if (current != target || formats.get(target).name() != "lyx")
56 result.push_back(current);
58 vector<int>::iterator it = vertices_[current].in_vertices.begin();
59 vector<int>::iterator end = vertices_[current].in_vertices.end();
60 for (; it != end; ++it) {
73 Graph::getReachable(int from, bool only_viewable,
77 if (!bfs_init(from, clear_visited))
81 int const current = Q_.front();
83 Format const & format = formats.get(current);
84 if (!only_viewable || !format.viewer().empty())
85 result.push_back(current);
86 else if (format.isChildFormat()) {
87 Format const * const parent =
88 formats.getFormat(format.parentFormat());
89 if (parent && !parent->viewer().empty())
90 result.push_back(current);
93 vector<OutEdge>::const_iterator cit =
94 vertices_[current].out_arrows.begin();
95 vector<OutEdge>::const_iterator end =
96 vertices_[current].out_arrows.end();
97 for (; cit != end; ++cit) {
98 int const cv = cit->vertex;
110 bool Graph::isReachable(int from, int to)
115 if (to < 0 || !bfs_init(from))
118 while (!Q_.empty()) {
119 int const current = Q_.front();
124 vector<OutEdge>::const_iterator cit =
125 vertices_[current].out_arrows.begin();
126 vector<OutEdge>::const_iterator end =
127 vertices_[current].out_arrows.end();
128 for (; cit != end; ++cit) {
129 int const cv = cit->vertex;
141 Graph::EdgePath const Graph::getPath(int from, int to)
147 if (to < 0 || !bfs_init(from))
150 // pair<vertex, edge>
151 vector<pair<int, int> > prev(vertices_.size());
154 while (!Q_.empty()) {
155 int const current = Q_.front();
162 vector<OutEdge>::const_iterator const beg =
163 vertices_[current].out_arrows.begin();
164 vector<OutEdge>::const_iterator cit = beg;
165 vector<OutEdge>::const_iterator end =
166 vertices_[current].out_arrows.end();
167 for (; cit != end; ++cit) {
168 int const cv = cit->vertex;
172 // FIXME This will not do for finding multiple paths.
173 // Perhaps we need a vector, or a set.
174 prev[cv] = pair<int, int>(current, cit->edge);
182 path.push_back(prev[to].second);
185 reverse(path.begin(), path.end());
190 void Graph::init(int size)
192 vertices_ = vector<Vertex>(size);
193 visited_.resize(size);
198 void Graph::addEdge(int from, int to)
200 vertices_[to].in_vertices.push_back(from);
201 vertices_[from].out_arrows.push_back(OutEdge(to, numedges_++));
205 vector<Graph::Vertex> Graph::vertices_;