graphTraversal.cpp File Reference

#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.

{
  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 );
  GradientColorMap<int> cmap_grad( 0, 52);
  cmap_grad.addColor( Color( 0, 0, 255 ) );
  cmap_grad.addColor( Color( 0, 255, 255 ) );
  cmap_grad.addColor( Color( 0, 255, 0 ) );
  cmap_grad.addColor( Color( 255, 255, 0 ) );
  cmap_grad.addColor( Color( 255, 0, 0 ) );
  cmap_grad.addColor( Color( 255, 0, 255 ) );
 
  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 BreadthFirstVisitor<Graph, std::set<Vertex> > BFSVisitor;
  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,
                                            cmap_grad( node.second ) ) )
          << node.first; // the vertex
    bfv.expand();
  }
  board.saveEPS("graphTraversal-bfs.eps");
 
  board.clear();
  board << SetMode( domain.className(), "Paving" )
        << domain << SetMode( p1.className(), "Paving" );
  typedef DepthFirstVisitor<Graph, std::set<Vertex> > DFSVisitor;
  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;
}

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