DGtal 1.3.0
Loading...
Searching...
No Matches
graphTraversal.cpp
Go to the documentation of this file.
1
35#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
53using namespace std;
54using namespace DGtal;
55
57
58int 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,
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" );
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,
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" );
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,
157 cmap_hue( n ) ) )
158 << vtx;
159 }
160 board.saveEPS("graphTraversal-dfs-range.eps");
162
163 return 0;
164}
Aim: This class specializes a 'Board' class so as to display DGtal objects more naturally (with <<)....
Definition: Board2D.h:71
Aim: This class is useful to perform a breadth-first exploration of a graph given a starting point or...
Structure representing an RGB triple with alpha component.
Definition: Color.h:68
static const Color Black
Definition: Color.h:413
Aim: This class is useful to perform a depth-first exploration of a graph given a starting point or s...
Aim: A wrapper class around a STL associative container for storing sets of digital points within som...
Aim: This class template may be used to (linearly) convert scalar values in a given range into a colo...
void addColor(const Color &color)
Aim: Transforms a graph visitor into a single pass input range.
Aim: This class template may be used to (linearly) convert scalar values in a given range into a colo...
std::string className() const
static void addNorm1Ball(TDigitalSet &aSet, const Point &aCenter, UnsignedInteger aRadius)
static void addNorm2Ball(TDigitalSet &aSet, const Point &aCenter, UnsignedInteger aRadius)
std::ostream & info()
void clear(const DGtal::Color &color=DGtal::Color::None)
Definition: Board.cpp:152
void saveEPS(const char *filename, PageSize size=Board::BoundingBox, double margin=10.0) const
Definition: Board.cpp:805
DGtal is the top-level namespace which contains all DGtal functions and types.
Trace trace
Definition: Common.h:154
STL namespace.
Custom style class redefining the pen color and the fill color. You may use Board2D::Color::None for ...
Definition: Board2D.h:279
Modifier class in a Board2D stream. Useful to choose your own mode for a given class....
Definition: Board2D.h:247
Aim: Represents the concept of local graph: each vertex has neighboring vertices, but we do not neces...
int main()
Definition: testBits.cpp:56
MyPointD Point
Definition: testClone2.cpp:383
Domain domain
TriMesh::Vertex Vertex