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
24 int Graph::bfs_init(int s, bool clear_visited)
29 Q_ = std::queue<int>();
32 fill(visited_.begin(), visited_.end(), false);
33 if (visited_[s] == false) {
42 Graph::getReachableTo(int target, bool clear_visited)
45 int const s = bfs_init(target, clear_visited);
50 int const i = Q_.front();
52 if (i != s || formats.get(target).name() != "lyx") {
56 vector<int>::iterator it = vertices_[i].in_vertices.begin();
57 vector<int>::iterator end = vertices_[i].in_vertices.end();
58 for (; it != end; ++it) {
71 Graph::getReachable(int from, bool only_viewable,
75 if (bfs_init(from, clear_visited) < 0)
79 int const i = Q_.front();
81 Format const & format = formats.get(i);
82 if (format.name() == "lyx")
84 if (!only_viewable || !format.viewer().empty() ||
85 format.isChildFormat())
88 vector<int>::const_iterator cit =
89 vertices_[i].out_vertices.begin();
90 vector<int>::const_iterator end =
91 vertices_[i].out_vertices.end();
92 for (; cit != end; ++cit)
93 if (!visited_[*cit]) {
94 visited_[*cit] = true;
103 bool Graph::isReachable(int from, int to)
108 int const s = bfs_init(from);
112 while (!Q_.empty()) {
113 int const i = Q_.front();
118 vector<int>::const_iterator cit =
119 vertices_[i].out_vertices.begin();
120 vector<int>::const_iterator end =
121 vertices_[i].out_vertices.end();
122 for (; cit != end; ++cit) {
123 if (!visited_[*cit]) {
124 visited_[*cit] = true;
134 Graph::EdgePath const
135 Graph::getPath(int from, int t)
141 int const s = bfs_init(from);
145 vector<int> prev_edge(formats.size());
146 vector<int> prev_vertex(formats.size());
149 while (!Q_.empty()) {
150 int const i = Q_.front();
157 vector<int>::const_iterator beg =
158 vertices_[i].out_vertices.begin();
159 vector<int>::const_iterator cit = beg;
160 vector<int>::const_iterator end =
161 vertices_[i].out_vertices.end();
162 for (; cit != end; ++cit)
163 if (!visited_[*cit]) {
167 int const k = cit - beg;
168 prev_edge[j] = vertices_[i].out_edges[k];
176 path.push_back(prev_edge[t]);
179 reverse(path.begin(), path.end());
183 void Graph::init(int size)
185 vertices_ = vector<Vertex>(size);
186 visited_.resize(size);
190 void Graph::addEdge(int s, int t)
192 vertices_[t].in_vertices.push_back(s);
193 vertices_[s].out_vertices.push_back(t);
194 vertices_[s].out_edges.push_back(numedges_++);
197 vector<Graph::Vertex> Graph::vertices_;