[Boost-users] [C++] Problems with undirected_dfs and color maps

Subject: [Boost-users] [C++] Problems with undirected_dfs and color maps
From: Zemmerie (perkypyro_at_[hidden])
Date: 2008-12-20 11:34:22

I'm trying to use an undirected_dfs to find cycles in a graph. I have a
visitor all ready to go, but I'm having trouble with the actual
undirected_dfs() call. It wants me to give it a vertex color map and an edge
color map, and I think that's where my problem is coming from. 

I managed to get something that will compile, but when it runs, it goes to
the root node, then to one connected to it, then back to the root node, and
just repeats. I think what's happening is that the color maps aren't working
properly, so it doesn't know that the root node has already been discovered.

Can anyone take a look at this and let me know what I'm doing wrong and how
I can fix it? At this point I'm about ready to just write my own dfs
algorithm!

Thanks
-Kate

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp> 
#include <boost/graph/undirected_dfs.hpp>
#include <boost/property_map.hpp>
#include <boost/graph/graph_archetypes.hpp>
#include <iostream>
#include "CycleFinder.h"

using namespace boost;
using namespace std;

//easier access to common types
typedef boost::adjacency_list<vecS, vecS, undirectedS> Graph;
typedef boost::graph_traits<Graph>::vertex_iterator vertex_iterator;
typedef boost::graph_traits<Graph>::edge_iterator edge_iterator;
typedef boost::graph_traits<Graph>::vertex_descriptor vertex_descriptor;
typedef boost::graph_traits<Graph>::edge_descriptor edge_descriptor;

int ConstraintsSolver::reduceClusterGraph(Graph cluster)
{
        //search for 6-cycles and reduce them
        pair<vertex_iterator, vertex_iterator> vertexPair = vertices(cluster);
        vertex_descriptor rootNode = *vertexPair.first;
        CycleFinder finder;
        
        read_write_property_map_archetype<vertex_descriptor, default_color_type>
vertexColorMap;
        read_write_property_map_archetype<edge_descriptor, default_color_type>
edgeColorMap;

        undirected_dfs(cluster, finder, vertexColorMap, edgeColorMap, rootNode);

        return 0;
}
-- 
View this message in context: http://www.nabble.com/-C%2B%2B--Problems-with-undirected_dfs-and-color-maps-tp21106641p21106641.html
Sent from the Boost - Users mailing list archive at Nabble.com.