Hello all,
I have included below a header file for a module I'm working on. Please
note the line marked "***** ERROR HERE *****". At this line, the type dl_t
is not being seen for some reason. Can anybody see why this is?
Thanks,
Dave
#ifndef DIRECTED_GRAPH_ INCLUDED
#define DIRECTED_GRAPH_ INCLUDED
#include <algorithm>
#include <map>
#include <set>
#include <utility>
#include <vector>
namespace directed_graph
{
// Template parameter T specifies the type of the values used to uniquely
// identify vertices.
template<typena me T>
class directed_graph_ t
{
public:
directed_graph_ t();
// The only way this can fail is if the source or destination does
not
// exist. A request to add an already-existing edge is a no-op.
In
// the event of a failure, an exception will be thrown containing
the
// offending vertex ID.
void add_edge(const T &source_id, const T &destination_id );
// This will never fail. A request to add an already-existing
vertex
// is a no-op.
void add_vertex(cons t T &vertex_id);
void clear();
// For each vertex, determine all vertices reachable from that
vertex.
dl_t get_descendents (); // ***** ERROR HERE *****
std::vector<T> get_dfs_discove ry_times();
std::vector<T> get_dfs_finish_ times();
bool is_acyclic();
// This function will return a topological sort of the vertex set,
if
// possible. The only case when this can't be done is if the graph
is
// not acyclic. In this case, an exception will be thrown.
std::vector<T> topological_sor t();
private:
// Disable copying and assignment.
directed_graph_ t(const directed_graph_ t &);
directed_graph_ t &operator=(cons t directed_graph_ t &);
enum vertex_color_t
{
WHITE,
GRAY,
BLACK
};
// Types related to the adjacency list representation of a graph
typedef std::map<T, std::set<T> > al_t;
typedef typename al_t::iterator al_iter_t;
// Types related to descendents of vertices (i.e. other reachable
// vertices)
typedef std::map<T, std::set<T> > dl_t;
typedef typename dl_t::iterator dl_iter_t;
// Types used to store the colors of vertices
typedef std::map<T, vertex_color_t> vc_t;
typedef typename vc_t::iterator vc_iter_t;
bool acyclic;
al_t adjacency_list;
std::vector<T> dfs_discovery_t imes;
std::vector<T> dfs_finish_time s;
bool dfs_search_perf ormed;
vc_t vertex_colors;
void dfs_visit(const T &vertex_id);
void perform_dfs_sea rch();
};
}
// Include the definition of functions declared above.
#include "directed_graph .inl"
#endif
