#ifndef GRAPH_H
#define GRAPH_H
+
#include <list>
#include <queue>
+#include <set>
#include <vector>
///
typedef std::vector<int> EdgePath;
/// \return a vector of the vertices from which "to" can be reached
- std::vector<int> const getReachableTo(int to, bool clear_visited);
- /// \return a vector of the vertices that can be reached from "from"
- std::vector<int> const
- getReachable(int from, bool only_viewable, bool clear_visited);
+ EdgePath const getReachableTo(int to, bool clear_visited);
+ /// \return a vector of the reachable vertices, avoiding all "excludes"
+ EdgePath const getReachable(int from, bool only_viewable,
+ bool clear_visited, std::set<int> excludes = std::set<int>());
/// can "from" be reached from "to"?
bool isReachable(int from, int to);
/// find a path from "from" to "to". always returns one of the
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();
- /// used to recover a marked path
- void getMarkedPath(int from, int to, EdgePath & path);
- ///
- void dumpGraph() const;
+ bool bfs_init(int, bool clear_visited, std::queue<int> & Q);
/// these represent the arrows connecting the nodes of the graph.
- /// this is the basic representation of the graph: as a bunch of
+ /// 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) {}
+ Arrow(int f, int t, int i):
+ from(f), to(t), id(i) {}
/// the vertex at the tail of the arrow
int from;
/// the vertex at the head
int to;
- /// an id for this arrow, e.g., for use in describing paths
+ /// 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,
/// of Format, this is easy, since the Format objects already have ints
/// as identifiers.)
std::vector<Vertex> vertices_;
- ///
- std::queue<int> Q_;
+
/// a counter that we use to assign id's to the arrows
/// FIXME This technique assumes a correspondence between the
/// ids of the arrows and ids associated with Converters that