Subject: Re: [Boost-users] Cycle detection in a directed graph with adjacency_matrix
From: albert kao (albertkao3_at_[hidden])
Date: 2011-04-12 22:59:56
The compile errors are now:
adjacency_matrix_is_cyclic.cpp:9: error: expected class-name before ‘{’
token
adjacency_matrix_is_cyclic.cpp: In function ‘bool has_cycle(const Graph&)’:
adjacency_matrix_is_cyclic.cpp:26: error: no matching function for call to
‘depth_first_search(const boost::adjacency_matrix<boost::directedS,
boost::no_property, boost::no_property, boost::no_property,
std::allocator<bool> >&, cycle_detector&)’
$ cat adjacency_matrix_is_cyclic.cpp
#include <iostream>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/adjacency_matrix.hpp>
typedef boost::adjacency_matrix<boost::directedS> Graph;
typedef boost::graph_traits<Graph>::edge_descriptor edge_t;
struct cycle_detector : public boost::dfs_visitor_default
{
cycle_detector(bool & cycle): has_cycle(cycle)
{
}
void
back_edge(edge_t, const Graph &)
{
has_cycle = true;
}
bool & has_cycle;
};
bool
has_cycle(const Graph & g)
{
bool has_cycle = false;
cycle_detector vis(has_cycle);
boost::depth_first_search(g, vis);
return has_cycle;
}
enum { A, B, C, D, E, F, N };
const char* name = "ABCDEF";
int main(int argc, char *argv[])
{
Graph g(N);
add_edge(B, C, g);
add_edge(B, F, g);
add_edge(C, A, g);
add_edge(C, C, g);
add_edge(D, E, g);
add_edge(E, D, g);
add_edge(F, A, g);
std::cout << "vertex set: ";
boost::print_vertices(g, name);
std::cout << std::endl;
std::cout << "edge set: ";
boost::print_edges(g, name);
std::cout << std::endl;
std::cout << "out-edges: " << std::endl;
boost::print_graph(g, name);
std::cout << std::endl;
std::cout << "has_cycle(g) " << has_cycle(g) << std::endl;
return 0;
}
On Tue, Apr 12, 2011 at 10:40 PM, Jeremiah Willcock <jewillco_at_[hidden]>wrote:
> On Tue, 12 Apr 2011, albert kao wrote:
>
> After adding "boost::" before "graph_traits", the compile errors are:
>> adjacency_matrix_is_cyclic.cpp:9: error: expected class-name before ‘{’
>> token
>> adjacency_matrix_is_cyclic.cpp: In function ‘bool has_cycle(const
>> Graph&)’:
>> adjacency_matrix_is_cyclic.cpp:26: error: ‘generic_dfs_v1’ was not
>> declared in this scope
>>
>> adjacency_matrix_is_cyclic.cpp:
>> #include <iostream>
>> #include <boost/graph/graph_utility.hpp>
>> #include <boost/graph/adjacency_matrix.hpp>
>>
>> typedef boost::adjacency_matrix<boost::directedS> Graph;
>> typedef boost::graph_traits<Graph>::edge_descriptor edge_t;
>>
>> struct cycle_detector : public dfs_visitor_default
>> {
>> cycle_detector(bool & cycle): has_cycle(cycle)
>> {
>> }
>> void
>> back_edge(edge_t, const Graph &)
>> {
>> has_cycle = true;
>> }
>> bool & has_cycle;
>> };
>>
>> bool
>> has_cycle(const Graph & g)
>> {
>> bool has_cycle = false;
>> cycle_detector vis(has_cycle);
>> generic_dfs_v1(g, vis);
>> return has_cycle;
>> }
>>
>> enum { A, B, C, D, E, F, N };
>> const char* name = "ABCDEF";
>>
>> int main(int argc, char *argv[])
>> {
>> Graph g(N);
>> add_edge(B, C, g);
>> add_edge(B, F, g);
>> add_edge(C, A, g);
>> add_edge(C, C, g);
>> add_edge(D, E, g);
>> add_edge(E, D, g);
>> add_edge(F, A, g);
>>
>> std::cout << "vertex set: ";
>> boost::print_vertices(g, name);
>> std::cout << std::endl;
>>
>> std::cout << "edge set: ";
>> boost::print_edges(g, name);
>> std::cout << std::endl;
>>
>> std::cout << "out-edges: " << std::endl;
>> boost::print_graph(g, name);
>> std::cout << std::endl;
>>
>> std::cout << "has_cycle(g) " << has_cycle(g) << std::endl;
>>
>> return 0;
>> }
>>
>
> You also need boost:: before dfs_visitor_default. You should also use
> boost::depth_first_search instead of generic_dfs_v1 (which is internal).
>
> -- Jeremiah Willcock