30#include "DGtalCatch.h"
33#include <boost/property_map/property_map.hpp>
34#include <boost/pending/queue.hpp>
35#include "DGtal/base/Common.h"
36#include "DGtal/graph/ObjectBoostGraphInterface.h"
37#include "DGtal/helpers/StdDefs.h"
38#include "DGtal/topology/Object.h"
39#include "DGtal/topology/DigitalTopology.h"
40#include "DGtal/topology/SurfelAdjacency.h"
44#include <boost/graph/graph_concepts.hpp>
45#include <boost/graph/adjacency_list.hpp>
46#include <boost/graph/copy.hpp>
47#include <boost/graph/breadth_first_search.hpp>
48#include <boost/graph/connected_components.hpp>
49#include <boost/graph/stoer_wagner_min_cut.hpp>
50#include <boost/graph/boykov_kolmogorov_max_flow.hpp>
51#include <boost/graph/filtered_graph.hpp>
59struct Fixture_object_diamond_with_hole {
66 using FixtureDigitalTopology =
68 using FixtureDigitalSet =
75 FixtureObject obj_fixture;
81 Fixture_object_diamond_with_hole() {
82 using namespace DGtal;
85 Point p1( -10, -10, -10 );
86 Point p2( 10, 10, 10 );
91 FixtureDigitalSet diamond_set(
domain );
94 if ( (*it - c ).norm1() <= 3 ) diamond_set.insertNew( *it );
96 diamond_set.erase( c );
101 obj_fixture = FixtureObject(topo,diamond_set);
110struct vertex_position_t {
111 using kind = boost::vertex_property_tag ;
114struct vertex_position {
116 vertex_position() : myP()
122 boost::property<vertex_position_t, vertex_position> > ;
124template <
typename Graph1,
typename Graph2,
typename VertexIndexMap>
125struct my_vertex_copier {
126 using graph_vertex_index_map =
typename boost::property_map< Graph2, boost::vertex_index_t>::type ;
127 using graph_vertex_position_map =
typename boost::property_map< Graph2, vertex_position_t>::type ;
128 using Vertex1 =
typename boost::graph_traits< Graph1 >::vertex_descriptor ;
129 using Vertex2 =
typename boost::graph_traits< Graph2 >::vertex_descriptor ;
132 graph_vertex_index_map graph_vertex_index;
133 graph_vertex_position_map graph_vertex_position;
134 VertexIndexMap & myIndexMap;
136 my_vertex_copier(
const Graph1& g1, Graph2& g2, VertexIndexMap & indexMap )
138 graph_vertex_index( boost::get( boost::vertex_index_t(), g2 ) ),
139 graph_vertex_position( boost::get( vertex_position_t(), g2) ),
140 myIndexMap( indexMap )
143 void operator()(
const Vertex1& v1,
const Vertex2& v2 )
const {
146 put( graph_vertex_position, v2, pos);
149template <
typename Graph1,
typename Graph2>
150struct my_edge_copier {
151 my_edge_copier(
const Graph1& , Graph2& )
153 template <
typename Edge1,
typename Edge2>
154 void operator()(
const Edge1& , Edge2& )
const {
160TEST_CASE_METHOD(Fixture_object_diamond_with_hole,
"Basic Graph functions",
"[interface]" ){
161 GIVEN(
"A diamond object with graph properties" ){
162 THEN(
"Vertices, Num Vertices" ){
165 size_t count_verts{0};
166 for(
auto v = verts.first; v != verts.second; ++v, ++count_verts){};
167 REQUIRE(count_verts == num_verts);
169 THEN(
"Edges, Num Edges" ){
172 size_t count_edges{0};
173 for(
auto v = edges.first; v != edges.second; ++v, ++count_edges){};
174 REQUIRE(count_edges == num_edges);
176 THEN(
"Out Edges, Out Degree, Degree, and Adjacencies of a vertex" ){
178 std::map<Point, size_t> point_numedges;
179 Point north{ 0 , 0 , 3 };
180 point_numedges[north] = 5;
182 Point x3{ 3 , 0 , 0 };
183 point_numedges[x3] = 5;
185 Point x1y1z1{ 1 , 1 , 1 };
186 point_numedges[x1y1z1] = 15;
188 Point cz2{ 0 , 0 , 2 };
189 point_numedges[cz2] = 14;
191 Point cz1{ 0 , 0 , 1 };
192 point_numedges[cz1] = 21;
194 for(
auto && pm : point_numedges){
196 size_t count_edges{0};
197 for(
auto v = out_edges.first; v != out_edges.second; ++v, ++count_edges){};
198 REQUIRE(count_edges == pm.second);
200 REQUIRE(out_degree == count_edges);
201 auto degree = obj_fixture.degree(pm.first);
204 size_t count_verts{0};
205 for(
auto v = adj_vp.first; v != adj_vp.second; ++v, ++count_verts){};
206 REQUIRE(count_verts == degree);
213 GIVEN(
"A diamond object with graph properties" ){
214 using Graph = FixtureObject ;
216 THEN(
"Check Graph Concepts" ){
227TEST_CASE_METHOD(Fixture_object_diamond_with_hole,
"Breadth first visit and search",
"[breadth]" ){
228 GIVEN(
"A diamond object with graph properties" ){
229 using Graph = FixtureObject ;
230 using vertex_descriptor = boost::graph_traits<Graph>::vertex_descriptor ;
231 using vertex_iterator = boost::graph_traits<Graph>::vertex_iterator ;
234 using StdColorMap = std::map< vertex_descriptor, boost::default_color_type > ;
235 StdColorMap colorMap;
236 boost::associative_property_map< StdColorMap > propColorMap( colorMap );
238 using StdDistanceMap = std::map< vertex_descriptor, uint64_t > ;
239 StdDistanceMap distanceMap;
240 boost::associative_property_map< StdDistanceMap > propDistanceMap( distanceMap );
241 boost::queue< vertex_descriptor > Q;
243 vertex_descriptor start {
Point{ 0, 0, 3 } };
245 THEN(
"Test IncidenceGraph interface with breadth_first_search" ){
246 using PredecessorMap = std::map< vertex_descriptor, vertex_descriptor > ;
247 PredecessorMap predecessorMap;
248 boost::associative_property_map< PredecessorMap >
249 propPredecessorMap( predecessorMap );
251 boost::breadth_first_search(
255 boost::make_bfs_visitor( boost::record_predecessors( propPredecessorMap, boost::on_tree_edge() ) ),
259 INFO(
"predecessorMap" );
260 INFO(
"starting point: " << *( obj_fixture.begin() ) );
262 for(
auto && v : predecessorMap){
264 INFO( v.first <<
" : " << v.second );
267 CHECK((visited + 1) == obj_fixture.size());
270 THEN(
"Test IncidenceGraph interface with breadth_first_visit" ){
272 trace.
beginBlock (
"Testing IncidenceGraph interface with breadth_first_visit..." );
273 boost::breadth_first_visit
277 boost::make_bfs_visitor( boost::record_distances( propDistanceMap, boost::on_tree_edge() ) ),
282 vertex_descriptor furthest = start;
284 for ( std::pair<vertex_iterator, vertex_iterator>
285 vp =
boost::vertices( obj_fixture ); vp.first != vp.second; ++vp.first, ++nbV )
287 uint64_t d = boost::get( propDistanceMap, *vp.first );
291 furthest = *vp.first;
295 REQUIRE( nbV == obj_fixture.size() );
296 trace.
info() <<
"- Start: d[ " << start <<
" ] = " << boost::get( propDistanceMap, start) << std::endl;
297 trace.
info() <<
"- Furthest: d[ " << furthest <<
" ] = " << maxD << std::endl;
301 THEN(
"Test Wagner Stoer min-cut"){
303 using vertices_size_type = boost::graph_traits<Graph>::vertices_size_type ;
304 using edge_descriptor = boost::graph_traits<Graph>::edge_descriptor ;
306 trace.
beginBlock (
"Testing UndirectedGraph interface with Wagner-Stoer min cut ..." );
308 using weight_type = double ;
309 using StdWeightMap = std::map< edge_descriptor, weight_type > ;
310 StdWeightMap weightMap;
311 boost::associative_property_map< StdWeightMap > propWeightMap( weightMap );
312 using StdVertexIndexMap = std::map< vertex_descriptor, vertices_size_type > ;
313 StdVertexIndexMap vertexIndexMap;
314 boost::associative_property_map< StdVertexIndexMap > propVertexIndexMap( vertexIndexMap );
315 vertices_size_type idxV = 0;
319 vp.first != vp.second; ++vp.first, ++idxV )
321 vertex_descriptor v1 = *vp.first;
322 vertexIndexMap[ v1 ] = idxV;
324 ve.first != ve.second; ++ve.first )
329 weight_type weight = (
330 (v1[2] == Approx(0) && v2[2] != Approx(0) ) ||
331 (v2[2] == Approx(0) && v1[2] != Approx(0) )
333 weightMap[ *ve.first ] = weight;
334 weightMap[ obj_fixture.opposite( *ve.first ) ] = weight;
339 using StdParityMap = std::map< vertex_descriptor, bool > ;
340 StdParityMap parityMap;
341 boost::associative_property_map< StdParityMap > propParityMap( parityMap );
343 weight_type total_weight =
344 boost::stoer_wagner_min_cut
347 boost::parity_map( propParityMap )
348 .vertex_index_map( propVertexIndexMap )
350 INFO(
"- total weight = " << total_weight);
354 vp.first != vp.second; ++vp.first, ++idxV )
356 vertex_descriptor v1 = *vp.first;
357 if ( parityMap[ v1 ] ) ++nb1;
360 trace.
info() <<
"parityMap: True components: " << nb1 <<
" False: " << nb0 << std::endl;
361 trace.
info() <<
"- parity[ " << start <<
" ] = " << parityMap[ start ] << std::endl;
362 trace.
info() <<
"- parity[ " << furthest <<
" ] = " << parityMap[ furthest ] << std::endl;
363 CHECK( parityMap[start] != parityMap[furthest]);
364 CHECK( total_weight < 1.0);
368 THEN(
"Test Boykov-Kolmogorov max flow"){
370 using edge_iterator = boost::graph_traits<Graph>::edge_iterator ;
371 trace.
beginBlock (
"Testing EdgeListGraph and IncidenceGraph interfaces with Boykov-Kolmogorov max flow ..." );
372 using capacity_type = double ;
374 using StdEdgeCapacityMap = std::map< edge_descriptor, weight_type > ;
375 StdEdgeCapacityMap edgeCapacityMap;
376 boost::associative_property_map< StdEdgeCapacityMap > propEdgeCapacityMap( edgeCapacityMap );
378 using StdEdgeResidualCapacityMap = std::map< edge_descriptor, weight_type > ;
379 StdEdgeResidualCapacityMap edgeResidualCapacityMap;
380 boost::associative_property_map< StdEdgeResidualCapacityMap > propEdgeResidualCapacityMap( edgeResidualCapacityMap );
382 using StdReversedEdgeMap = std::map< edge_descriptor, edge_descriptor > ;
383 StdReversedEdgeMap reversedEdgeMap;
384 boost::associative_property_map< StdReversedEdgeMap > propReversedEdgeMap( reversedEdgeMap );
386 using StdPredecessorMap = std::map< vertex_descriptor, edge_descriptor > ;
387 StdPredecessorMap predecessorMap;
388 boost::associative_property_map< StdPredecessorMap > propPredecessorMap( predecessorMap );
393 for ( std::pair<edge_iterator, edge_iterator>
394 ve =
boost::edges( obj_fixture ); ve.first != ve.second; ++ve.first, ++nbEdges )
396 edge_descriptor e = *ve.first;
397 edge_descriptor rev_e = obj_fixture.opposite( e );
404 capacity_type capacity = (
405 (v1[2] == Approx(0) && v2[2] != Approx(0) ) ||
406 (v2[2] == Approx(0) && v1[2] != Approx(0) )
408 edgeCapacityMap[ e ] = capacity;
409 edgeCapacityMap[ obj_fixture.opposite( e ) ] = capacity;
410 reversedEdgeMap[ e ] = obj_fixture.opposite( e );
411 reversedEdgeMap[ obj_fixture.opposite( e ) ] = e;
414 trace.
info() <<
"- nb edges = " << nbEdges << std::endl;
417 capacity_type max_flow =
418 boost::boykov_kolmogorov_max_flow
420 propEdgeCapacityMap, propEdgeResidualCapacityMap,
421 propReversedEdgeMap, propPredecessorMap, propColorMap, propDistanceMap, propVertexIndexMap,
423 trace.
info() <<
"- max flow = " << max_flow << std::endl;
424 CHECK(abs(max_flow) == Approx(total_weight));
433 GIVEN(
"A diamond object with graph properties and an isolated vertex" ){
434 using Graph = FixtureObject ;
435 using vertex_descriptor = boost::graph_traits<Graph>::vertex_descriptor ;
436 using edge_descriptor = boost::graph_traits<Graph>::edge_descriptor ;
437 using vertices_size_type = boost::graph_traits<Graph>::vertices_size_type ;
440 obj_fixture.pointSet().insertNew(FixtureObject::Point(0,0,7));
442 THEN(
"VertexListGraph interface with connected_components" ){
445 using StdColorMap = std::map< vertex_descriptor, boost::default_color_type > ;
446 StdColorMap colorMap;
447 boost::associative_property_map< StdColorMap > propColorMap( colorMap );
449 using StdComponentMap = std::map< vertex_descriptor, vertices_size_type > ;
450 StdComponentMap componentMap;
451 boost::associative_property_map< StdComponentMap > propComponentMap( componentMap );
452 vertices_size_type nbComp =
453 boost::connected_components
456 boost::color_map( propColorMap )
460 THEN(
"Filter graph and get components" ){
461 using ComponentGraph =
462 boost::filtered_graph<
464 function<bool(edge_descriptor)>,
465 function<bool(vertex_descriptor)>
467 auto &g = obj_fixture;
469 std::vector<ComponentGraph> component_graphs;
471 for (
size_t i = 0; i < nbComp; i++)
472 component_graphs.emplace_back(g,
473 [componentMap,i,&g](edge_descriptor e) {
474 return componentMap.at(boost::source(e,g) )==i
475 || componentMap.at(boost::target(e,g))==i;
477 [componentMap,i](vertex_descriptor v) {
478 return componentMap.at(v)==i;
482 CHECK( component_graphs.size() == 2);
483 std::vector<FixtureObject> obj_components;
485 FixtureObject obj_copy(obj_fixture);
486 obj_copy.pointSet().clear();
489 for (
auto && c : component_graphs){
490 obj_components.push_back(obj_copy);
491 for (
auto && vp =
boost::vertices(c); vp.first != vp.second ; ++vp.first){
492 obj_components.back().pointSet().insertNew(*vp.first);
503 GIVEN(
"A diamond object with graph properties" ){
504 using Graph = FixtureObject ;
505 using vertex_descriptor = boost::graph_traits<Graph>::vertex_descriptor ;
506 using vertices_size_type = boost::graph_traits<Graph>::vertices_size_type ;
507 THEN(
"Test copy_graph"){
509 using StdVertexIndexMap = std::map< vertex_descriptor, vertices_size_type > ;
510 StdVertexIndexMap vertexIndexMap;
511 boost::associative_property_map< StdVertexIndexMap > propVertexIndexMap( vertexIndexMap );
512 using BGraph = boost::adjacency_list< boost::vecS, boost::vecS, boost::undirectedS, VertexProperties > ;
514 boost::copy_graph( obj_fixture, bG,
515 boost::vertex_copy( my_vertex_copier<Graph,BGraph,StdVertexIndexMap>( obj_fixture, bG, vertexIndexMap ) )
516 .edge_copy( my_edge_copier<Graph,BGraph>( obj_fixture, bG ) )
517 .vertex_index_map( propVertexIndexMap )
519 using vertex_descriptor_2 = boost::graph_traits< BGraph >::vertex_descriptor ;
520 using vertex_iterator_2 = boost::graph_traits< BGraph >::vertex_iterator ;
521 using GraphVertexPositionMap = boost::property_map< BGraph, vertex_position_t>::type ;
522 GraphVertexPositionMap vertexPos( boost::get( vertex_position_t(), bG) );
523 for ( std::pair<vertex_iterator_2, vertex_iterator_2>
526 vertex_descriptor_2 v1 = *vp.first;
527 vertex_position pos = boost::get( vertexPos, v1 );
529 INFO(
"after copy: Boost graph has " << num_vertices( bG ) <<
" vertices.");
Aim: A wrapper class around a STL associative container for storing sets of digital points within som...
TForegroundAdjacency ForegroundAdjacency
TBackgroundAdjacency BackgroundAdjacency
const ConstIterator & begin() const
const ConstIterator & end() const
Aim: An object (or digital object) represents a set in some digital space associated with a digital t...
void beginBlock(const std::string &keyword="")
HyperRectDomain< Space > Domain
DigitalTopology< Adj26, Adj6 > DT26_6
DGtal is the top-level namespace which contains all DGtal functions and types.
boost::uint64_t uint64_t
unsigned 64-bit integer.
std::pair< typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_iterator, typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_iterator > edges(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edges_size_type num_edges(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
std::pair< typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::adjacency_iterator, typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::adjacency_iterator > adjacent_vertices(typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor u, const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertices_size_type num_vertices(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor source(typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_descriptor edge, const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::degree_size_type out_degree(typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor u, const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
std::pair< typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::out_edge_iterator, typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::out_edge_iterator > out_edges(typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor u, const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
std::pair< typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_iterator, typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_iterator > vertices(const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::vertex_descriptor target(typename graph_traits< DGtal::DigitalSurface< TDigitalSurfaceContainer > >::edge_descriptor edge, const DGtal::DigitalSurface< TDigitalSurfaceContainer > &digSurf)
Go to http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/AdjacencyGraph.html.
Go to http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/EdgeListGraph.html.
Go to http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/IncidenceGraph.html.
Go to http://www.boost.org/doc/libs/1_52_0/libs/graph/doc/VertexListGraph.html.
GIVEN("A cubical complex with random 3-cells")
boost::property< boost::vertex_index_t, std::size_t, boost::property< surfel_position_t, surfel_position > > VertexProperties
TEST_CASE_METHOD(Fixture_object_diamond_with_hole, "Basic Graph functions", "[interface]")
REQUIRE(domain.isInside(aPoint))