DGtal  1.0.0
graphTraversal.cpp
Go to the documentation of this file.
1 
33 #include <iostream>
36 #include <vector>
37 #include <iterator>
38 #include "DGtal/io/Color.h"
39 #include "DGtal/io/colormaps/GradientColorMap.h"
40 #include "DGtal/io/colormaps/HueShadeColorMap.h"
41 #include "DGtal/io/boards/Board2D.h"
42 #include "DGtal/helpers/StdDefs.h"
43 #include "DGtal/shapes/Shapes.h"
44 #include "DGtal/topology/Object.h"
45 #include "DGtal/graph/BreadthFirstVisitor.h"
46 #include "DGtal/graph/DepthFirstVisitor.h"
47 #include "DGtal/graph/GraphVisitorRange.h"
48 #include "DGtal/graph/CUndirectedSimpleGraph.h"
50 
52 
53 using namespace std;
54 using namespace DGtal;
55 
57 
58 int main( int /* argc */, char** /* argv */ )
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 }
Aim: This class template may be used to (linearly) convert scalar values in a given range into a colo...
MyDigitalSurface::ConstIterator ConstIterator
Trace trace
Definition: Common.h:144
Aim: This class is useful to perform a depth-first exploration of a graph given a starting point or s...
void addColor(const Color &color)
Custom style class redefining the pen color and the fill color. You may use Board2D::Color::None for ...
Definition: Board2D.h:278
Aim: This class template may be used to (linearly) convert scalar values in a given range into a colo...
Domain domain
int main(int, char **)
void clear(const DGtal::Color &color=DGtal::Color::None)
Definition: Board.cpp:152
TriMesh::Vertex Vertex
void saveEPS(const char *filename, PageSize size=Board::BoundingBox, double margin=10.0) const
Definition: Board.cpp:805
std::string className() const
DGtal is the top-level namespace which contains all DGtal functions and types.
MyPointD Point
Definition: testClone2.cpp:383
std::string className() const
Definition: Board2D.h:197
Aim: Transforms a graph visitor into a single pass input range.
Aim: Represents the concept of local graph: each vertex has neighboring vertices, but we do not neces...
std::ostream & info()
Aim: This class is useful to perform a breadth-first exploration of a graph given a starting point or...
Modifier class in a Board2D stream. Useful to choose your own mode for a given class....
Definition: Board2D.h:247
Structure representing an RGB triple with alpha component.
Definition: Color.h:66
Aim: A utility class for constructing different shapes (balls, diamonds, and others).
Aim: This class specializes a 'Board' class so as to display DGtal objects more naturally (with <<)....
Definition: Board2D.h:70