* This file is part of LyX, the document processor.
* Licence details can be found in the file COPYING.
*
- * \author Dekel Tsur
+ * \author Dekel Tsur (original code)
+ * \author Richard Kimberly Heck (re-implementation)
*
* Full author contact details are available in file CREDITS.
*/
#include "Graph.h"
#include "Format.h"
-#include <algorithm>
+#include "support/debug.h"
+#include "support/lassert.h"
using namespace std;
namespace lyx {
-int Graph::bfs_init(int s, bool clear_visited)
+bool Graph::bfs_init(int s, bool clear_visited, queue<int> & Q)
{
if (s < 0)
- return s;
+ return false;
- Q_ = queue<int>();
+ if (!Q.empty())
+ Q = queue<int>();
- if (clear_visited)
- fill(visited_.begin(), visited_.end(), false);
- if (visited_[s] == false) {
- Q_.push(s);
- visited_[s] = true;
+ if (clear_visited) {
+ vector<Vertex>::iterator it = vertices_.begin();
+ vector<Vertex>::iterator en = vertices_.end();
+ for (; it != en; ++it)
+ it->visited = false;
+ }
+ if (!vertices_[s].visited) {
+ Q.push(s);
+ vertices_[s].visited = true;
}
- return s;
+ return true;
}
-vector<int> const
-Graph::getReachableTo(int target, bool clear_visited)
+Graph::EdgePath const
+ Graph::getReachableTo(int to, bool clear_visited)
{
- vector<int> result;
- int const s = bfs_init(target, clear_visited);
- if (s < 0)
+ EdgePath result;
+ queue<int> Q;
+ if (!bfs_init(to, clear_visited, Q))
return result;
- while (!Q_.empty()) {
- int const i = Q_.front();
- Q_.pop();
- if (i != s || formats.get(target).name() != "lyx") {
- result.push_back(i);
- }
-
- vector<int>::iterator it = vertices_[i].in_vertices.begin();
- vector<int>::iterator end = vertices_[i].in_vertices.end();
+ // Here's the logic, which is shared by the other routines.
+ // Q holds a list of nodes we have been able to reach (in this
+ // case, reach backwards). It is initialized to the current node
+ // by bfs_init, and then we recurse, adding the nodes we can reach
+ // from the current node as we go. That makes it a breadth-first
+ // search.
+ while (!Q.empty()) {
+ int const current = Q.front();
+ Q.pop();
+ if (current != to || theFormats().get(to).name() != "lyx")
+ result.push_back(current);
+
+ vector<Arrow *>::iterator it = vertices_[current].in_arrows.begin();
+ vector<Arrow *>::iterator const end = vertices_[current].in_arrows.end();
for (; it != end; ++it) {
- if (!visited_[*it]) {
- visited_[*it] = true;
- Q_.push(*it);
+ const int cv = (*it)->from;
+ if (!vertices_[cv].visited) {
+ vertices_[cv].visited = true;
+ Q.push(cv);
}
}
}
}
-vector<int> const
-Graph::getReachable(int from, bool only_viewable,
- bool clear_visited)
+Graph::EdgePath const
+ Graph::getReachable(int from, bool only_viewable,
+ bool clear_visited, set<int> excludes)
{
- vector<int> result;
- if (bfs_init(from, clear_visited) < 0)
+ EdgePath result;
+ queue<int> Q;
+ if (!bfs_init(from, clear_visited, Q))
return result;
- while (!Q_.empty()) {
- int const i = Q_.front();
- Q_.pop();
- Format const & format = formats.get(i);
+ while (!Q.empty()) {
+ int const current = Q.front();
+ Q.pop();
+ Format const & format = theFormats().get(current);
if (!only_viewable || !format.viewer().empty())
- result.push_back(i);
+ result.push_back(current);
else if (format.isChildFormat()) {
Format const * const parent =
- formats.getFormat(format.parentFormat());
+ theFormats().getFormat(format.parentFormat());
if (parent && !parent->viewer().empty())
- result.push_back(i);
+ result.push_back(current);
}
- vector<int>::const_iterator cit =
- vertices_[i].out_vertices.begin();
- vector<int>::const_iterator end =
- vertices_[i].out_vertices.end();
- for (; cit != end; ++cit)
- if (!visited_[*cit]) {
- visited_[*cit] = true;
- Q_.push(*cit);
+ vector<Arrow *>::const_iterator cit =
+ vertices_[current].out_arrows.begin();
+ vector<Arrow *>::const_iterator end =
+ vertices_[current].out_arrows.end();
+ for (; cit != end; ++cit) {
+ int const cv = (*cit)->to;
+ if (!vertices_[cv].visited) {
+ vertices_[cv].visited = true;
+ if (excludes.find(cv) == excludes.end())
+ Q.push(cv);
}
+ }
}
return result;
if (from == to)
return true;
- if (to < 0 || bfs_init(from) < 0)
+ queue<int> Q;
+ if (to < 0 || !bfs_init(from, true, Q))
return false;
- while (!Q_.empty()) {
- int const i = Q_.front();
- Q_.pop();
- if (i == to)
+ while (!Q.empty()) {
+ int const current = Q.front();
+ Q.pop();
+ if (current == to)
return true;
- vector<int>::const_iterator cit =
- vertices_[i].out_vertices.begin();
- vector<int>::const_iterator end =
- vertices_[i].out_vertices.end();
+ vector<Arrow *>::const_iterator cit =
+ vertices_[current].out_arrows.begin();
+ vector<Arrow *>::const_iterator end =
+ vertices_[current].out_arrows.end();
for (; cit != end; ++cit) {
- if (!visited_[*cit]) {
- visited_[*cit] = true;
- Q_.push(*cit);
+ int const cv = (*cit)->to;
+ if (!vertices_[cv].visited) {
+ vertices_[cv].visited = true;
+ Q.push(cv);
}
}
}
Graph::EdgePath const Graph::getPath(int from, int to)
{
- EdgePath path;
if (from == to)
- return path;
-
- int const s = bfs_init(from);
- if (s < 0 || to < 0)
- return path;
-
- vector<int> prev_edge(formats.size());
- vector<int> prev_vertex(formats.size());
-
- bool found = false;
- while (!Q_.empty()) {
- int const i = Q_.front();
- Q_.pop();
- if (i == to) {
- found = true;
- break;
- }
-
- vector<int>::const_iterator const beg =
- vertices_[i].out_vertices.begin();
- vector<int>::const_iterator cit = beg;
- vector<int>::const_iterator end =
- vertices_[i].out_vertices.end();
- for (; cit != end; ++cit)
- if (!visited_[*cit]) {
- int const j = *cit;
- visited_[j] = true;
- Q_.push(j);
- int const k = cit - beg;
- prev_edge[j] = vertices_[i].out_edges[k];
- prev_vertex[j] = i;
+ return EdgePath();
+
+ queue<int> Q;
+ if (to < 0 || !bfs_init(from, true, Q))
+ return EdgePath();
+
+ vector<EdgePath> pathes;
+ pathes.resize(vertices_.size());
+ while (!Q.empty()) {
+ int const current = Q.front();
+ Q.pop();
+
+ vector<Arrow *>::const_iterator cit =
+ vertices_[current].out_arrows.begin();
+ vector<Arrow *>::const_iterator end =
+ vertices_[current].out_arrows.end();
+ for (; cit != end; ++cit) {
+ int const cv = (*cit)->to;
+ if (!vertices_[cv].visited) {
+ vertices_[cv].visited = true;
+ Q.push(cv);
+ // NOTE If we wanted to collect all the paths, then
+ // we just need to collect them here and not worry
+ // about "visited".
+ EdgePath lastpath = pathes[(*cit)->from];
+ lastpath.push_back((*cit)->id);
+ pathes[cv] = lastpath;
}
+ if (cv == to) {
+ return pathes[cv];
+ }
+ }
}
- if (!found)
- return path;
-
- while (to != s) {
- path.push_back(prev_edge[to]);
- to = prev_vertex[to];
- }
- reverse(path.begin(), path.end());
- return path;
+ // failure
+ return EdgePath();
}
void Graph::init(int size)
{
vertices_ = vector<Vertex>(size);
- visited_.resize(size);
+ arrows_.clear();
numedges_ = 0;
}
void Graph::addEdge(int from, int to)
{
- vertices_[to].in_vertices.push_back(from);
- vertices_[from].out_vertices.push_back(to);
- vertices_[from].out_edges.push_back(numedges_++);
+ arrows_.push_back(Arrow(from, to, numedges_));
+ numedges_++;
+ Arrow * ar = &(arrows_.back());
+ vertices_[to].in_arrows.push_back(ar);
+ vertices_[from].out_arrows.push_back(ar);
}
-vector<Graph::Vertex> Graph::vertices_;
+// At present, we do not need this debugging code, but
+// I am going to leave it here in case we need it again.
+#if 0
+void Graph::dumpGraph() const
+{
+ vector<Vertex>::const_iterator it = vertices_.begin();
+ vector<Vertex>::const_iterator en = vertices_.end();
+ for (; it != en; ++it) {
+ LYXERR0("Next vertex...");
+ LYXERR0("In arrows...");
+ std::vector<Arrow *>::const_iterator iit = it->in_arrows.begin();
+ std::vector<Arrow *>::const_iterator ien = it->in_arrows.end();
+ for (; iit != ien; ++iit)
+ LYXERR0("From " << (*iit)->from << " to " << (*iit)->to);
+ LYXERR0("Out arrows...");
+ iit = it->out_arrows.begin();
+ ien = it->out_arrows.end();
+ for (; iit != ien; ++iit)
+ LYXERR0("From " << (*iit)->from << " to " << (*iit)->to);
+ }
+}
+#endif
} // namespace lyx
projects / lyx.git / blobdiff