Author: rgheck
Date: Mon May 31 23:27:17 2010
New Revision: 34560
URL: http://www.lyx.org/trac/changeset/34560
Log:
Simplify the graph code a bit. This also will allow us easily to find
all paths from point A to point B, which we'll want to do later.
This should also get rid of an annoying bug that I couldn't figure out.
Modified:
lyx-devel/trunk/src/Graph.cpp
lyx-devel/trunk/src/Graph.h
Modified: lyx-devel/trunk/src/Graph.cpp
==============================================================================
--- lyx-devel/trunk/src/Graph.cpp Mon May 31 22:20:57 2010 (r34559)
+++ lyx-devel/trunk/src/Graph.cpp Mon May 31 23:27:17 2010 (r34560)
@@ -45,12 +45,12 @@
}
-void Graph::clearMarks()
+void Graph::clearPaths()
{
- Arrows::iterator it = arrows_.begin();
- Arrows::iterator const en = arrows_.end();
+ vector<Vertex>::iterator it = vertices_.begin();
+ vector<Vertex>::iterator en = vertices_.end();
for (; it != en; ++it)
- it->marked = false;
+ it->path.clear();
}
@@ -159,21 +159,14 @@
Graph::EdgePath const Graph::getPath(int from, int to)
{
- EdgePath path;
+ static const EdgePath path;
if (from == to)
return path;
if (to < 0 || !bfs_init(from))
return path;
- // In effect, the way this works is that we construct a sub-graph
- // by starting at "from" and following the arrows outward. Instead
- // of actually constructing a sub-graph, though, we "mark" the
- // arrows we traverse as we go. Once we hit "to", we abort the
- // marking process and then call getMarkedPath() to reconstruct
- // the marked path.
- bool found = false;
- clearMarks();
+ clearPaths();
while (!Q_.empty()) {
int const current = Q_.front();
Q_.pop();
@@ -187,53 +180,23 @@
if (!vertices_[cv].visited) {
vertices_[cv].visited = true;
Q_.push(cv);
- (*cit)->marked = true;
+ // NOTE If we wanted to collect all the paths,
then
+ // we just need to collect them here and not
worry
+ // about "visited".
+ EdgePath lastpath =
vertices_[(*cit)->from].path;
+ lastpath.push_back((*cit)->id);
+ vertices_[cv].path = lastpath;
}
if (cv == to) {
- found = true;
- break;
+ return vertices_[cv].path;
}
}
}
- if (!found)
- return path;
-
- getMarkedPath(from, to, path);
+ // failure
return path;
}
-// We assume we have marked the graph, as in getPath(). We also
-// assume that we have done so in such a way as to guarantee a
-// marked path from "from" to "to".
-// We then start at "to" and find the arrow leading to it that
-// has been marked. We add that to the path we are constructing,
-// step back on that arrow, and continue the process (i.e., recurse).
-void Graph::getMarkedPath(int from, int to, EdgePath & path) {
- if (from == to) {
- reverse(path.begin(), path.end());
- return;
- }
- // find marked in_arrow
- vector<Arrow *>::const_iterator it = vertices_[to].in_arrows.begin();
- vector<Arrow *>::const_iterator const en =
vertices_[to].in_arrows.end();
- for (; it != en; ++it)
- if ((*it)->marked)
- break;
- if (it == en) {
- // debug code to try to figure out what's up.
- LYXERR0("Failed to find marked arrow.\n"
- "From: " << from << ", To: " <<
to);
- dumpGraph();
- LASSERT(false, /* */);
- path.clear();
- return;
- }
- path.push_back((*it)->id);
- getMarkedPath(from, (*it)->from, path);
-}
-
-
void Graph::init(int size)
{
vertices_ = vector<Vertex>(size);
@@ -252,6 +215,9 @@
}
+// 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();
@@ -262,16 +228,15 @@
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
- << ". Marked: " << (*iit)->marked);
+ 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
- << ". Marked: " <<
(*iit)->marked);
+ LYXERR0("From " << (*iit)->from << " to " <<
(*iit)->to);
}
}
+#endif
} // namespace lyx
Modified: lyx-devel/trunk/src/Graph.h
==============================================================================
--- lyx-devel/trunk/src/Graph.h Mon May 31 22:20:57 2010 (r34559)
+++ lyx-devel/trunk/src/Graph.h Mon May 31 23:27:17 2010 (r34560)
@@ -46,20 +46,18 @@
private:
///
bool bfs_init(int, bool clear_visited = true);
- /// clears the "marks" on the arrows. should be called
- /// before any new marking begins.
- void clearMarks();
+ /// clears the paths from a previous search. should be
+ /// called before each new one.
+ void clearPaths();
/// used to recover a marked path
void getMarkedPath(int from, int to, EdgePath & path);
- ///
- void dumpGraph() const;
/// these represent the arrows connecting the nodes of the graph.
/// this is the basic representation of the graph: as a bunch of
/// arrows.
struct Arrow {
///
Arrow(int f, int t, int i):
- from(f), to(t), id(i), marked(false) {}
+ from(f), to(t), id(i) {}
/// the vertex at the tail of the arrow
int from;
/// the vertex at the head
@@ -67,9 +65,6 @@
/// an id for this arrow, e.g., for use in describing paths
/// through the graph
int id;
- /// used for "marking" paths, i.e., constructing sub-graphs
- /// without really doing so.
- bool marked;
};
/// a container for the arrows
/// we use a list because we want pointers to the arrows,
@@ -86,6 +81,8 @@
std::vector<Arrow *> out_arrows;
/// used in the search routines
bool visited;
+ ///
+ EdgePath path;
};
/// a container for the vertices
/// the index into the vector functions as the identifier by which
