DGtal  0.9.4beta
graph/graphTraversal.cpp

Traverses a 2D graph in different ways (enumeration, breadth-first traversal, depth-first traversal).

See also
Using graphs
# Commands
$ ./examples/graph/graphTraversal
# see files graphTraversal-enum.eps, graphTraversal-bfs.eps, graphTraversal-dfs-range.eps.
graphTraversal-enum.png
Coloring vertices of an object graph according to the enumeration order.
graphTraversal-bfs.png
Coloring vertices of an object graph according to the topological distance to a seed (breadth-first traversal).
graphTraversal-dfs-range.png
Coloring vertices of an object graph according to their order given by a depth-first traversal.
#include <iostream>
#include <vector>
#include <iterator>
#include "DGtal/io/Color.h"
#include "DGtal/io/colormaps/GradientColorMap.h"
#include "DGtal/io/colormaps/HueShadeColorMap.h"
#include "DGtal/io/boards/Board2D.h"
#include "DGtal/helpers/StdDefs.h"
#include "DGtal/shapes/Shapes.h"
#include "DGtal/topology/Object.h"
#include "DGtal/graph/BreadthFirstVisitor.h"
#include "DGtal/graph/DepthFirstVisitor.h"
#include "DGtal/graph/GraphVisitorRange.h"
#include "DGtal/graph/CUndirectedSimpleGraph.h"
using namespace std;
using namespace DGtal;
int main( int /* argc */, char** /* argv */ )
{
using namespace Z2i;
Point p1( -41, -36 ), p2( 18, 18 );
Domain domain( p1, p2 );
DigitalSet shape_set( domain );
Shapes<Domain>::addNorm2Ball( shape_set, Point( -2, -1 ), 9 );
Shapes<Domain>::addNorm1Ball( shape_set, Point( -14, 5 ), 9 );
Shapes<Domain>::addNorm1Ball( shape_set, Point( -30, -15 ), 10 );
Shapes<Domain>::addNorm2Ball( shape_set, Point( -10, -20 ), 12 );
Shapes<Domain>::addNorm1Ball( shape_set, Point( 12, -1 ), 4 );
Object4_8 g( dt4_8, shape_set ); // 4-adjacency graph.
typedef Object4_8 Graph;
typedef Point Vertex;
BOOST_CONCEPT_ASSERT(( concepts::CUndirectedSimpleGraph< Graph > ));
HueShadeColorMap<int> cmap_hue( 0, 400, 10 );
GradientColorMap<int> cmap_grad( 0, 52);
cmap_grad.addColor( Color( 0, 0, 255 ) );
cmap_grad.addColor( Color( 0, 255, 255 ) );
cmap_grad.addColor( Color( 0, 255, 0 ) );
cmap_grad.addColor( Color( 255, 255, 0 ) );
cmap_grad.addColor( Color( 255, 0, 0 ) );
cmap_grad.addColor( Color( 255, 0, 255 ) );
Board2D board;
board << SetMode( domain.className(), "Paving" )
<< domain << SetMode( p1.className(), "Paving" );
string specificStyle = p1.className() + "/Paving";
int n = 0;
for ( Graph::ConstIterator it = g.begin(), itEnd = g.end();
it != itEnd; ++it, ++n )
{ // Vertex are colored in order.
Vertex vtx = *it;
board << CustomStyle( specificStyle,
new CustomColors( Color::Black,
cmap_hue( n ) ) )
<< vtx;
}
board.saveEPS("graphTraversal-enum.eps");
{
int nn = 0;
int mm = 0;
std::vector<Vertex> neighbors;
for ( Graph::ConstIterator it = g.begin(), itEnd = g.end();
it != itEnd; ++it, ++nn )
{
Vertex vtx = *it;
std::back_insert_iterator< std::vector<Vertex> > neighIt
= std::back_inserter( neighbors );
g.writeNeighbors( neighIt, vtx );
mm += neighbors.size();
neighbors.clear();
}
trace.info() << "Graph has " << nn << " vertices and "
<< (mm/2) << " edges." << std::endl;
}
board.clear();
board << SetMode( domain.className(), "Paving" )
<< domain << SetMode( p1.className(), "Paving" );
typedef BFSVisitor::Node Node;
BFSVisitor bfv( g, Point( -2, -1 ) );
while( ! bfv.finished() )
{ // Vertex are colored according to the distance to initial seed.
Node node = bfv.current();
board << CustomStyle( specificStyle,
new CustomColors( Color::Black,
cmap_grad( node.second ) ) )
<< node.first; // the vertex
bfv.expand();
}
board.saveEPS("graphTraversal-bfs.eps");
board.clear();
board << SetMode( domain.className(), "Paving" )
<< domain << SetMode( p1.className(), "Paving" );
typedef GraphVisitorRange<DFSVisitor> VisitorRange;
VisitorRange range( new DFSVisitor( g, Point( -2, -1 ) ) );
n = 0;
for ( VisitorRange::ConstIterator it = range.begin(), itEnd = range.end();
it != itEnd; ++it, ++n )
{ // Vertex are colored according to their order (depth first order here).
Vertex vtx = *it;
board << CustomStyle( specificStyle,
new CustomColors( Color::Black,
cmap_hue( n ) ) )
<< vtx;
}
board.saveEPS("graphTraversal-dfs-range.eps");
return 0;
}