DGtal  1.3.beta
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 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;
}
ConstIterator
MyDigitalSurface::ConstIterator ConstIterator
Definition: greedy-plane-segmentation-ex2.cpp:93
DGtal::HyperRectDomain< Space >
DGtal::GraphVisitorRange
Aim: Transforms a graph visitor into a single pass input range.
Definition: GraphVisitorRange.h:71
DGtal::Color
Structure representing an RGB triple with alpha component.
Definition: Color.h:67
Aim: This class template may be used to (linearly) convert scalar values in a given range into a colo...
DGtal::trace
Trace trace
Definition: Common.h:154
Aim: This class is useful to perform a breadth-first exploration of a graph given a starting point or...
DGtal::HyperRectDomain::className
std::string className() const
LibBoard::Board::clear
void clear(const DGtal::Color &color=DGtal::Color::None)
Definition: Board.cpp:152
Vertex
TriMesh::Vertex Vertex
Definition: testTriangulatedSurface.cpp:57
DGtal::CustomStyle
Definition: Board2D.h:217
DGtal::Trace::info
std::ostream & info()
DGtal
DGtal is the top-level namespace which contains all DGtal functions and types.
DGtal::CustomColors
Custom style class redefining the pen color and the fill color. You may use Board2D::Color::None for ...
Definition: Board2D.h:278
DGtal::Z2i::Object4_8
Object< DT4_8, DigitalSet > Object4_8
Definition: StdDefs.h:101
DGtal::concepts::CUndirectedSimpleGraph
Aim: Represents the concept of local graph: each vertex has neighboring vertices, but we do not neces...
Definition: CUndirectedSimpleGraph.h:102
main
int main(int argc, char **argv)
Definition: testArithmeticDSS-benchmark.cpp:147
DGtal::Board2D
Aim: This class specializes a 'Board' class so as to display DGtal objects more naturally (with <<)....
Definition: Board2D.h:70
DGtal::Shapes
Aim: A utility class for constructing different shapes (balls, diamonds, and others).
Definition: DGtal/shapes/Shapes.h:71
LibBoard::Board::saveEPS
void saveEPS(const char *filename, PageSize size=Board::BoundingBox, double margin=10.0) const
Definition: Board.cpp:805
domain
Domain domain
Definition: testProjection.cpp:88
DGtal::DepthFirstVisitor
Aim: This class is useful to perform a depth-first exploration of a graph given a starting point or s...
Definition: DepthFirstVisitor.h:95
DGtal::SetMode
Modifier class in a Board2D stream. Useful to choose your own mode for a given class....
Definition: Board2D.h:247
Point
MyPointD Point
Definition: testClone2.cpp:383