DGtal  1.2.0
graph/graphTraversal.cpp

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

Using graphs
# Commands
\$ ./examples/graph/graphTraversal
# see files graphTraversal-enum.eps, graphTraversal-bfs.eps, graphTraversal-dfs-range.eps.

Coloring vertices of an object graph according to the enumeration order.
Coloring vertices of an object graph according to the topological distance to a seed (breadth-first traversal).
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/boards/Board2D.h"
#include "DGtal/helpers/StdDefs.h"
#include "DGtal/shapes/Shapes.h"
#include "DGtal/topology/Object.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 );
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,
<< node.first; // the vertex
bfv.expand();
}
board.saveEPS("graphTraversal-bfs.eps");
board.clear();
board << SetMode( domain.className(), "Paving" )
<< domain << SetMode( p1.className(), "Paving" );
typedef DepthFirstVisitor<Graph, std::set<Vertex> > DFSVisitor;
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;
}
std::ostream & info()
MyDigitalSurface::ConstIterator ConstIterator
DigitalSetSelector< Domain, BIG_DS+HIGH_BEL_DS >::Type DigitalSet
Definition: StdDefs.h:100
Object< DT4_8, DigitalSet > Object4_8
Definition: StdDefs.h:101
DGtal is the top-level namespace which contains all DGtal functions and types.
Trace trace
Definition: Common.h:154
int main(int argc, char **argv)
MyPointD Point
Definition: testClone2.cpp:383
Domain domain
HyperRectDomain< Space > Domain
TriMesh::Vertex Vertex