DGtal  1.5.beta
Functions
graphTraversal.cpp File Reference
DGtal Examples
#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"
Include dependency graph for graphTraversal.cpp:

Go to the source code of this file.

Functions

int main (int, char **)
 

Detailed Description

Author
Jacques-Olivier Lachaud (jacqu.nosp@m.es-o.nosp@m.livie.nosp@m.r.la.nosp@m.chaud.nosp@m.@uni.nosp@m.v-sav.nosp@m.oie..nosp@m.fr ) Laboratory of Mathematics (CNRS, UMR 5127), University of Savoie, France
Jérémy Gaillard (jerem.nosp@m.y.ga.nosp@m.illar.nosp@m.d@in.nosp@m.sa-ly.nosp@m.on.f.nosp@m.r )
Date
2013/01/31

An example file named graphTraversal.

This file is part of the DGtal library.

Definition in file graphTraversal.cpp.

Function Documentation

◆ main()

int main ( int  ,
char **   
)

[graphTraversal-graph-instanciation]

[graphTraversal-graph-instanciation]

[graphTraversal-graph-enumeration]

[graphTraversal-graph-enumeration]

[graphTraversal-vertex-edge-enumeration]

[graphTraversal-vertex-edge-enumeration]

[graphTraversal-graph-bfs]

[graphTraversal-graph-bfs]

[graphTraversal-graph-dfs-range]

[graphTraversal-graph-dfs-range]

Definition at line 58 of file graphTraversal.cpp.

59 {
61  using namespace Z2i;
62  Point p1( -41, -36 ), p2( 18, 18 );
63  Domain domain( p1, p2 );
64  DigitalSet shape_set( domain );
65  Shapes<Domain>::addNorm2Ball( shape_set, Point( -2, -1 ), 9 );
66  Shapes<Domain>::addNorm1Ball( shape_set, Point( -14, 5 ), 9 );
67  Shapes<Domain>::addNorm1Ball( shape_set, Point( -30, -15 ), 10 );
68  Shapes<Domain>::addNorm2Ball( shape_set, Point( -10, -20 ), 12 );
69  Shapes<Domain>::addNorm1Ball( shape_set, Point( 12, -1 ), 4 );
70  Object4_8 g( dt4_8, shape_set ); // 4-adjacency graph.
71  typedef Object4_8 Graph;
72  typedef Point Vertex;
73  BOOST_CONCEPT_ASSERT(( concepts::CUndirectedSimpleGraph< Graph > ));
75 
76  HueShadeColorMap<int> cmap_hue( 0, 400, 10 );
77  GradientColorMap<int> cmap_grad( 0, 52);
78  cmap_grad.addColor( Color( 0, 0, 255 ) );
79  cmap_grad.addColor( Color( 0, 255, 255 ) );
80  cmap_grad.addColor( Color( 0, 255, 0 ) );
81  cmap_grad.addColor( Color( 255, 255, 0 ) );
82  cmap_grad.addColor( Color( 255, 0, 0 ) );
83  cmap_grad.addColor( Color( 255, 0, 255 ) );
84 
85  Board2D board;
86  board << SetMode( domain.className(), "Paving" )
87  << domain << SetMode( p1.className(), "Paving" );
88  string specificStyle = p1.className() + "/Paving";
89 
91  int n = 0;
92  for ( Graph::ConstIterator it = g.begin(), itEnd = g.end();
93  it != itEnd; ++it, ++n )
94  { // Vertex are colored in order.
95  Vertex vtx = *it;
96  board << CustomStyle( specificStyle,
97  new CustomColors( Color::Black,
98  cmap_hue( n ) ) )
99  << vtx;
100  }
101  board.saveEPS("graphTraversal-enum.eps");
103 
104  {
106  int nn = 0;
107  int mm = 0;
108  std::vector<Vertex> neighbors;
109  for ( Graph::ConstIterator it = g.begin(), itEnd = g.end();
110  it != itEnd; ++it, ++nn )
111  {
112  Vertex vtx = *it;
113  std::back_insert_iterator< std::vector<Vertex> > neighIt
114  = std::back_inserter( neighbors );
115  g.writeNeighbors( neighIt, vtx );
116  mm += neighbors.size();
117  neighbors.clear();
118  }
119  trace.info() << "Graph has " << nn << " vertices and "
120  << (mm/2) << " edges." << std::endl;
122  }
123 
124  board.clear();
125  board << SetMode( domain.className(), "Paving" )
126  << domain << SetMode( p1.className(), "Paving" );
128  typedef BreadthFirstVisitor<Graph, std::set<Vertex> > BFSVisitor;
129  typedef BFSVisitor::Node Node;
130  BFSVisitor bfv( g, Point( -2, -1 ) );
131  while( ! bfv.finished() )
132  { // Vertex are colored according to the distance to initial seed.
133  Node node = bfv.current();
134  board << CustomStyle( specificStyle,
135  new CustomColors( Color::Black,
136  cmap_grad( node.second ) ) )
137  << node.first; // the vertex
138  bfv.expand();
139  }
140  board.saveEPS("graphTraversal-bfs.eps");
142 
143  board.clear();
144  board << SetMode( domain.className(), "Paving" )
145  << domain << SetMode( p1.className(), "Paving" );
147  typedef DepthFirstVisitor<Graph, std::set<Vertex> > DFSVisitor;
148  typedef GraphVisitorRange<DFSVisitor> VisitorRange;
149  VisitorRange range( new DFSVisitor( g, Point( -2, -1 ) ) );
150  n = 0;
151  for ( VisitorRange::ConstIterator it = range.begin(), itEnd = range.end();
152  it != itEnd; ++it, ++n )
153  { // Vertex are colored according to their order (depth first order here).
154  Vertex vtx = *it;
155  board << CustomStyle( specificStyle,
156  new CustomColors( Color::Black,
157  cmap_hue( n ) ) )
158  << vtx;
159  }
160  board.saveEPS("graphTraversal-dfs-range.eps");
162 
163  return 0;
164 }
DGtal::Board2D
Aim: This class specializes a 'Board' class so as to display DGtal objects more naturally (with <<)....
Definition: Board2D.h:71
DGtal::BreadthFirstVisitor
Aim: This class is useful to perform a breadth-first exploration of a graph given a starting point or...
Definition: BreadthFirstVisitor.h:95
DGtal::Color
Structure representing an RGB triple with alpha component.
Definition: Color.h:68
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:96
DGtal::DigitalSetByAssociativeContainer
Aim: A wrapper class around a STL associative container for storing sets of digital points within som...
Definition: DigitalSetByAssociativeContainer.h:90
DGtal::GradientColorMap
Aim: This class template may be used to (linearly) convert scalar values in a given range into a colo...
Definition: GradientColorMap.h:120
DGtal::GraphVisitorRange
Aim: Transforms a graph visitor into a single pass input range.
Definition: GraphVisitorRange.h:72
DGtal::HueShadeColorMap
Aim: This class template may be used to (linearly) convert scalar values in a given range into a colo...
Definition: HueShadeColorMap.h:91
DGtal::HyperRectDomain::className
std::string className() const
DGtal::Shapes
Aim: A utility class for constructing different shapes (balls, diamonds, and others).
Definition: DGtal/shapes/Shapes.h:72
DGtal::Trace::info
std::ostream & info()
LibBoard::Board::clear
void clear(const DGtal::Color &color=DGtal::Color::None)
Definition: Board.cpp:151
LibBoard::Board::saveEPS
void saveEPS(const char *filename, PageSize size=Board::BoundingBox, double margin=10.0) const
Definition: Board.cpp:804
ConstIterator
MyDigitalSurface::ConstIterator ConstIterator
Definition: greedy-plane-segmentation-ex2.cpp:93
DGtal::Z2i::Object4_8
Object< DT4_8, DigitalSet > Object4_8
Definition: StdDefs.h:101
DGtal::trace
Trace trace
Definition: Common.h:153
DGtal::CustomColors
Custom style class redefining the pen color and the fill color. You may use Board2D::Color::None for ...
Definition: Board2D.h:279
DGtal::SetMode
Modifier class in a Board2D stream. Useful to choose your own mode for a given class....
Definition: Board2D.h:247
DGtal::concepts::CUndirectedSimpleGraph
Aim: Represents the concept of local graph: each vertex has neighboring vertices, but we do not neces...
Definition: CUndirectedSimpleGraph.h:105
Point
MyPointD Point
Definition: testClone2.cpp:383
domain
Domain domain
Definition: testProjection.cpp:88
Vertex
TriMesh::Vertex Vertex
Definition: testTriangulatedSurface.cpp:57

References DGtal::GradientColorMap< PValue, PDefaultPreset, PDefaultFirstColor, PDefaultLastColor >::addColor(), DGtal::HyperRectDomain< TSpace >::className(), LibBoard::Board::clear(), domain, DGtal::Trace::info(), LibBoard::Board::saveEPS(), and DGtal::trace.