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.
19 int Graph::bfs_init(int s, bool clear_visited)
24 Q_ = std::queue<int>();
27 fill(visited_.begin(), visited_.end(), false);
28 if (visited_[s] == false) {
37 Graph::getReachableTo(int target, bool clear_visited)
40 int const s = bfs_init(target, clear_visited);
45 int const i = Q_.front();
47 if (i != s || formats.get(target).name() != "lyx") {
51 vector<int>::iterator it = vertices_[i].in_vertices.begin();
52 vector<int>::iterator end = vertices_[i].in_vertices.end();
53 for (; it != end; ++it) {
66 Graph::getReachable(int from, bool only_viewable,
70 if (bfs_init(from, clear_visited) < 0)
74 int const i = Q_.front();
76 Format const & format = formats.get(i);
77 if (format.name() == "lyx")
79 if (!only_viewable || !format.viewer().empty() ||
80 format.isChildFormat())
83 vector<int>::const_iterator cit =
84 vertices_[i].out_vertices.begin();
85 vector<int>::const_iterator end =
86 vertices_[i].out_vertices.end();
87 for (; cit != end; ++cit)
88 if (!visited_[*cit]) {
89 visited_[*cit] = true;
98 bool Graph::isReachable(int from, int to)
103 int const s = bfs_init(from);
107 while (!Q_.empty()) {
108 int const i = Q_.front();
113 vector<int>::const_iterator cit =
114 vertices_[i].out_vertices.begin();
115 vector<int>::const_iterator end =
116 vertices_[i].out_vertices.end();
117 for (; cit != end; ++cit) {
118 if (!visited_[*cit]) {
119 visited_[*cit] = true;
129 Graph::EdgePath const
130 Graph::getPath(int from, int t)
136 int const s = bfs_init(from);
140 vector<int> prev_edge(formats.size());
141 vector<int> prev_vertex(formats.size());
144 while (!Q_.empty()) {
145 int const i = Q_.front();
152 vector<int>::const_iterator beg =
153 vertices_[i].out_vertices.begin();
154 vector<int>::const_iterator cit = beg;
155 vector<int>::const_iterator end =
156 vertices_[i].out_vertices.end();
157 for (; cit != end; ++cit)
158 if (!visited_[*cit]) {
162 int const k = cit - beg;
163 prev_edge[j] = vertices_[i].out_edges[k];
171 path.push_back(prev_edge[t]);
174 reverse(path.begin(), path.end());
178 void Graph::init(int size)
180 vertices_ = vector<Vertex>(size);
181 visited_.resize(size);
185 void Graph::addEdge(int s, int t)
187 vertices_[t].in_vertices.push_back(s);
188 vertices_[s].out_vertices.push_back(t);
189 vertices_[s].out_edges.push_back(numedges_++);
192 vector<Graph::Vertex> Graph::vertices_;