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 int 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 int const s = bfs_init(target, clear_visited);
49 int const i = Q_.front();
51 if (i != s || formats.get(target).name() != "lyx") {
55 vector<int>::iterator it = vertices_[i].in_vertices.begin();
56 vector<int>::iterator end = vertices_[i].in_vertices.end();
57 for (; it != end; ++it) {
70 Graph::getReachable(int from, bool only_viewable,
74 if (bfs_init(from, clear_visited) < 0)
78 int const i = Q_.front();
80 Format const & format = formats.get(i);
81 if (!only_viewable || !format.viewer().empty())
83 else if (format.isChildFormat()) {
84 Format const * const parent =
85 formats.getFormat(format.parentFormat());
86 if (parent && !parent->viewer().empty())
90 vector<int>::const_iterator cit =
91 vertices_[i].out_vertices.begin();
92 vector<int>::const_iterator end =
93 vertices_[i].out_vertices.end();
94 for (; cit != end; ++cit)
95 if (!visited_[*cit]) {
96 visited_[*cit] = true;
105 bool Graph::isReachable(int from, int to)
110 int const s = bfs_init(from);
114 while (!Q_.empty()) {
115 int const i = Q_.front();
120 vector<int>::const_iterator cit =
121 vertices_[i].out_vertices.begin();
122 vector<int>::const_iterator end =
123 vertices_[i].out_vertices.end();
124 for (; cit != end; ++cit) {
125 if (!visited_[*cit]) {
126 visited_[*cit] = true;
136 Graph::EdgePath const
137 Graph::getPath(int from, int t)
143 int const s = bfs_init(from);
147 vector<int> prev_edge(formats.size());
148 vector<int> prev_vertex(formats.size());
151 while (!Q_.empty()) {
152 int const i = Q_.front();
159 vector<int>::const_iterator beg =
160 vertices_[i].out_vertices.begin();
161 vector<int>::const_iterator cit = beg;
162 vector<int>::const_iterator end =
163 vertices_[i].out_vertices.end();
164 for (; cit != end; ++cit)
165 if (!visited_[*cit]) {
169 int const k = cit - beg;
170 prev_edge[j] = vertices_[i].out_edges[k];
178 path.push_back(prev_edge[t]);
181 reverse(path.begin(), path.end());
185 void Graph::init(int size)
187 vertices_ = vector<Vertex>(size);
188 visited_.resize(size);
192 void Graph::addEdge(int s, int t)
194 vertices_[t].in_vertices.push_back(s);
195 vertices_[s].out_vertices.push_back(t);
196 vertices_[s].out_edges.push_back(numedges_++);
199 vector<Graph::Vertex> Graph::vertices_;