DGtal  0.9.2
graphTraversal.cpp
1 
15 #include <iostream>
18 #include <vector>
19 #include <iterator>
20 #include "DGtal/io/Color.h"
21 #include "DGtal/io/colormaps/GradientColorMap.h"
22 #include "DGtal/io/colormaps/HueShadeColorMap.h"
23 #include "DGtal/io/boards/Board2D.h"
24 #include "DGtal/helpers/StdDefs.h"
25 #include "DGtal/shapes/Shapes.h"
26 #include "DGtal/topology/Object.h"
27 #include "DGtal/graph/BreadthFirstVisitor.h"
28 #include "DGtal/graph/DepthFirstVisitor.h"
29 #include "DGtal/graph/GraphVisitorRange.h"
30 #include "DGtal/graph/CUndirectedSimpleGraph.h"
32 
34 
35 using namespace std;
36 using namespace DGtal;
37 
39 
40 int main( int /* argc */, char** /* argv */ )
41 {
43  using namespace Z2i;
44  Point p1( -41, -36 ), p2( 18, 18 );
45  Domain domain( p1, p2 );
46  DigitalSet shape_set( domain );
47  Shapes<Domain>::addNorm2Ball( shape_set, Point( -2, -1 ), 9 );
48  Shapes<Domain>::addNorm1Ball( shape_set, Point( -14, 5 ), 9 );
49  Shapes<Domain>::addNorm1Ball( shape_set, Point( -30, -15 ), 10 );
50  Shapes<Domain>::addNorm2Ball( shape_set, Point( -10, -20 ), 12 );
51  Shapes<Domain>::addNorm1Ball( shape_set, Point( 12, -1 ), 4 );
52  Object4_8 g( dt4_8, shape_set ); // 4-adjacency graph.
53  typedef Object4_8 Graph;
54  typedef Point Vertex;
55  BOOST_CONCEPT_ASSERT(( concepts::CUndirectedSimpleGraph< Graph > ));
57 
58  HueShadeColorMap<int> cmap_hue( 0, 400, 10 );
59  GradientColorMap<int> cmap_grad( 0, 52);
60  cmap_grad.addColor( Color( 0, 0, 255 ) );
61  cmap_grad.addColor( Color( 0, 255, 255 ) );
62  cmap_grad.addColor( Color( 0, 255, 0 ) );
63  cmap_grad.addColor( Color( 255, 255, 0 ) );
64  cmap_grad.addColor( Color( 255, 0, 0 ) );
65  cmap_grad.addColor( Color( 255, 0, 255 ) );
66 
67  Board2D board;
68  board << SetMode( domain.className(), "Paving" )
69  << domain << SetMode( p1.className(), "Paving" );
70  string specificStyle = p1.className() + "/Paving";
71 
73  int n = 0;
74  for ( Graph::ConstIterator it = g.begin(), itEnd = g.end();
75  it != itEnd; ++it, ++n )
76  { // Vertex are colored in order.
77  Vertex vtx = *it;
78  board << CustomStyle( specificStyle,
79  new CustomColors( Color::Black,
80  cmap_hue( n ) ) )
81  << vtx;
82  }
83  board.saveEPS("graphTraversal-enum.eps");
85 
86  {
88  int nn = 0;
89  int mm = 0;
90  std::vector<Vertex> neighbors;
91  for ( Graph::ConstIterator it = g.begin(), itEnd = g.end();
92  it != itEnd; ++it, ++nn )
93  {
94  Vertex vtx = *it;
95  std::back_insert_iterator< std::vector<Vertex> > neighIt
96  = std::back_inserter( neighbors );
97  g.writeNeighbors( neighIt, vtx );
98  mm += neighbors.size();
99  neighbors.clear();
100  }
101  trace.info() << "Graph has " << nn << " vertices and "
102  << (mm/2) << " edges." << std::endl;
104  }
105 
106  board.clear();
107  board << SetMode( domain.className(), "Paving" )
108  << domain << SetMode( p1.className(), "Paving" );
110  typedef BreadthFirstVisitor<Graph, std::set<Vertex> > BFSVisitor;
111  typedef BFSVisitor::Node Node;
112  BFSVisitor bfv( g, Point( -2, -1 ) );
113  while( ! bfv.finished() )
114  { // Vertex are colored according to the distance to initial seed.
115  Node node = bfv.current();
116  board << CustomStyle( specificStyle,
117  new CustomColors( Color::Black,
118  cmap_grad( node.second ) ) )
119  << node.first; // the vertex
120  bfv.expand();
121  }
122  board.saveEPS("graphTraversal-bfs.eps");
124 
125  board.clear();
126  board << SetMode( domain.className(), "Paving" )
127  << domain << SetMode( p1.className(), "Paving" );
129  typedef DepthFirstVisitor<Graph, std::set<Vertex> > DFSVisitor;
130  typedef GraphVisitorRange<DFSVisitor> VisitorRange;
131  VisitorRange range( new DFSVisitor( g, Point( -2, -1 ) ) );
132  n = 0;
133  for ( VisitorRange::ConstIterator it = range.begin(), itEnd = range.end();
134  it != itEnd; ++it, ++n )
135  { // Vertex are colored according to their order (depth first order here).
136  Vertex vtx = *it;
137  board << CustomStyle( specificStyle,
138  new CustomColors( Color::Black,
139  cmap_hue( n ) ) )
140  << vtx;
141  }
142  board.saveEPS("graphTraversal-dfs-range.eps");
144 
145  return true;
146 }
147 
DigitalSetSelector< Domain, BIG_DS+HIGH_BEL_DS >::Type DigitalSet
Definition: StdDefs.h:100
Aim: This class template may be used to (linearly) convert scalar values in a given range into a colo...
Trace trace
Definition: Common.h:130
Object< DT4_8, DigitalSet > Object4_8
Definition: StdDefs.h:101
Aim: This class is useful to perform a depth-first exploration of a graph given a starting point or s...
STL namespace.
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...
std::string className() const
void clear(const DGtal::Color &color=DGtal::Color::None)
Definition: Board.cpp:152
DGtal is the top-level namespace which contains all DGtal functions and types.
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...
std::string className() const
Definition: Board2D.h:197
void saveEPS(const char *filename, PageSize size=Board::BoundingBox, double margin=10.0) const
Definition: Board.cpp:805
Modifier class in a Board2D stream. Useful to choose your own mode for a given class. Realizes the concept CDrawableWithBoard2D.
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