CGAL 5.5 - CGAL and the Boost Graph Library

Methods to split a mesh into subdomains, using the library METIS or a graphcut implementation.

Files

file  partition.h
 Convenience header file including the headers for all the partitioning-related free functions of this package.
 

Functions

template<typename Graph , typename Visitor , typename IsTerminal >
void CGAL::split_graph_into_polylines (const Graph &graph, Visitor &polyline_visitor, IsTerminal is_terminal)
 splits into polylines the graph g at vertices of degree greater than 2 and at vertices for which is_terminal(v,graph)==true. More...
 
template<typename TriangleMesh , typename NamedParameters = parameters::Default_named_parameters>
void CGAL::METIS::partition_graph (const TriangleMesh &tm, int nparts, const NamedParameters &np=parameters::default_values())
 computes a partition of the input triangular mesh into nparts parts, based on the mesh's nodal graph. More...
 
template<typename TriangleMesh , typename NamedParameters = parameters::Default_named_parameters>
void CGAL::METIS::partition_dual_graph (const TriangleMesh &tm, int nparts, const NamedParameters &np=parameters::default_values())
 computes a partition of the input triangular mesh into nparts parts, based on the mesh's dual graph. More...
 
template<typename InputGraph , typename EdgeCostMap , typename VertexLabelCostMap , typename VertexLabelMap , typename NamedParameters = parameters::Default_named_parameters>
double CGAL::alpha_expansion_graphcut (const InputGraph &input_graph, EdgeCostMap edge_cost_map, VertexLabelCostMap vertex_label_cost_map, VertexLabelMap vertex_label_map, const NamedParameters &np=parameters::default_values())
 regularizes a partition of a graph into n labels using the alpha expansion algorithm [1]. More...
 

Function Documentation

◆ alpha_expansion_graphcut()

template<typename InputGraph , typename EdgeCostMap , typename VertexLabelCostMap , typename VertexLabelMap , typename NamedParameters = parameters::Default_named_parameters>
double CGAL::alpha_expansion_graphcut ( const InputGraph &  input_graph,
EdgeCostMap  edge_cost_map,
VertexLabelCostMap  vertex_label_cost_map,
VertexLabelMap  vertex_label_map,
const NamedParameters &  np = parameters::default_values() 
)

#include <CGAL/boost/graph/alpha_expansion_graphcut.h>

regularizes a partition of a graph into n labels using the alpha expansion algorithm [1].

For a graph \((V,E)\), this function computes a partition f that minimizes the following cost function:

\[ \mathrm{C}(f) = \sum_{\{v0,v1\} \in E} C_E(v0,v1) + \sum_{v \in V} C_V(f_v) \]

where \(C_E(v0,v1)\) is the edge cost of assigning a different label to \(v0\) and \(v1\), and \(C_V(f_v)\) is the vertex cost of assigning the label \(f\) to the vertex \(v\).

Template Parameters
InputGrapha model of VertexAndEdgeListGraph
EdgeCostMapa model of ReadablePropertyMap with boost::graph_traits<InputGraph>::edge_descriptor as key and double as value
VertexLabelCostMapa model of ReadablePropertyMap with boost::graph_traits<InputGraph>::vertex_descriptor as key and std::vector<double> as value
VertexLabelMapa model of ReadWritePropertyMap with boost::graph_traits<InputGraph>::vertex_descriptor as key and std::size_t as value
NamedParametersa sequence of named parameters
Parameters
input_graphthe input graph.
edge_cost_mapa property map providing the weight of each edge.
vertex_label_mapa property map providing the label of each vertex. This map will be updated by the algorithm with the regularized version of the partition.
vertex_label_cost_mapa property map providing, for each vertex, an std::vector containing the cost of this vertex to belong to each label. Each std::vector should have the same size n (which is the number of labels), each label being indexed from 0 to n-1. For example, get(vertex_label_cost_map, vd)[label_idx] returns the cost of vertex vd to belong to the label label_idx.
npan optional sequence of Named Parameters among the ones listed below
Optional Named Parameters
  • a property map associating to each vertex of input_graph a unique index between 0 and num_vertices(input_graph) - 1
  • Type: a class model of ReadablePropertyMap with boost::graph_traits<InputGraph>::vertex_descriptor as key type and std::size_t as value type
  • Default: an automatically indexed internal map
  • Extra: If this parameter is not passed, internal machinery will create and initialize a face index property map, either using the internal property map if it exists or using an external map. The latter might result in - slightly - worsened performance in case of non-constant complexity for index access.

  • a tag used to select which implementation of the alpha expansion should be used. Available implementation tags are:
    • CGAL::Alpha_expansion_boost_adjacency_list
    • CGAL::Alpha_expansion_boost_compressed_sparse_row_tag
    • CGAL::Alpha_expansion_MaxFlow_tag
  • Default: CGAL::Alpha_expansion_boost_adjacency_list
Note
The MaxFlow implementation is provided by the Triangulated Surface Mesh Segmentation Reference under GPL license. The header <CGAL/boost/graph/Alpha_expansion_MaxFlow_tag.h> must be included if users want to use this implementation.
Examples:
BGL_graphcut/alpha_expansion_example.cpp.

◆ partition_dual_graph()

template<typename TriangleMesh , typename NamedParameters = parameters::Default_named_parameters>
void CGAL::METIS::partition_dual_graph ( const TriangleMesh &  tm,
int  nparts,
const NamedParameters &  np = parameters::default_values() 
)

#include <CGAL/boost/graph/METIS/partition_dual_graph.h>

computes a partition of the input triangular mesh into nparts parts, based on the mesh's dual graph.

The resulting partition is stored in the vertex and/or face property maps that are passed as parameters using Named Parameters.

Parameters
tma triangle mesh
npartsthe number of parts in the final partition
npan optional sequence of Named Parameters among the ones listed below
Template Parameters
TriangleMeshis a model of the FaceListGraph concept
NamedParametersa sequence of Named Parameters
Optional Named Parameters
  • a property map associating to each vertex of tm a unique index between 0 and num_vertices(tm) - 1
  • Type: a class model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and std::size_t as value type
  • Default: an automatically indexed internal map
  • Extra: If this parameter is not passed, internal machinery will create and initialize a face index property map, either using the internal property map if it exists or using an external map. The latter might result in - slightly - worsened performance in case of non-constant complexity for index access.

  • a parameter used in to pass options to the METIS mesh partitioner
  • Type: an array of size METIS_NOPTIONS with value type idx_t (an integer type defined by METIS)
  • Default: an array of size METIS_NOPTIONS with value type idx_t, initialized using the function METIS_SetDefaultOptions()
  • Extra: The many options of METIS are not described here. Instead, users should refer to the documentation of METIS directly.

  • a property map that contains (after the function has been run) the ID of the subpart for each vertex of tm
  • Type: a class model of ReadWritePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and int as value type
  • Default: unused

  • a property map that contains (after the function has been run) the ID of the subpart for each face of tm
  • Type: a class model of ReadWritePropertyMap with boost::graph_traits<TriangleMesh>::face_descriptor as key type and int as value type
  • Default: unused
Precondition
tm is a pure triangular surface mesh: there are no edges without at least one incident face
Examples:
BGL_surface_mesh/surface_mesh_partition.cpp.

◆ partition_graph()

template<typename TriangleMesh , typename NamedParameters = parameters::Default_named_parameters>
void CGAL::METIS::partition_graph ( const TriangleMesh &  tm,
int  nparts,
const NamedParameters &  np = parameters::default_values() 
)

#include <CGAL/boost/graph/METIS/partition_graph.h>

computes a partition of the input triangular mesh into nparts parts, based on the mesh's nodal graph.

The resulting partition is stored in the vertex and/or face property maps that are passed as parameters using Named Parameters.

Parameters
tma triangle mesh
npartsthe number of parts in the final partition
npan optional sequence of Named Parameters among the ones listed below
Template Parameters
TriangleMeshis a model of the FaceListGraph concept.
NamedParametersa sequence of Named Parameters
Optional Named Parameters
  • a property map associating to each vertex of tm a unique index between 0 and num_vertices(tm) - 1
  • Type: a class model of ReadablePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and std::size_t as value type
  • Default: an automatically indexed internal map
  • Extra: If this parameter is not passed, internal machinery will create and initialize a face index property map, either using the internal property map if it exists or using an external map. The latter might result in - slightly - worsened performance in case of non-constant complexity for index access.

  • a parameter used in to pass options to the METIS mesh partitioner
  • Type: an array of size METIS_NOPTIONS with value type idx_t (an integer type defined by METIS)
  • Default: an array of size METIS_NOPTIONS with value type idx_t, initialized using the function METIS_SetDefaultOptions()
  • Extra: The many options of METIS are not described here. Instead, users should refer to the documentation of METIS directly.

  • a property map that contains (after the function has been run) the ID of the subpart for each vertex of tm
  • Type: a class model of ReadWritePropertyMap with boost::graph_traits<TriangleMesh>::vertex_descriptor as key type and int as value type
  • Default: unused

  • a property map that contains (after the function has been run) the ID of the subpart for each face of tm
  • Type: a class model of ReadWritePropertyMap with boost::graph_traits<TriangleMesh>::face_descriptor as key type and int as value type
  • Default: unused
Precondition
tm is a pure triangular surface mesh: there are no edges without at least one incident face
Examples:
BGL_polyhedron_3/polyhedron_partition.cpp.

◆ split_graph_into_polylines()

template<typename Graph , typename Visitor , typename IsTerminal >
void CGAL::split_graph_into_polylines ( const Graph &  graph,
Visitor &  polyline_visitor,
IsTerminal  is_terminal 
)

#include <CGAL/boost/graph/split_graph_into_polylines.h>

splits into polylines the graph g at vertices of degree greater than 2 and at vertices for which is_terminal(v,graph)==true.

The polylines are reported using a visitor.

Template Parameters
Grapha model of the boost concepts VertexListGraph and EdgeListGraph.
Visitora class that provides:
  • void start_new_polyline() called when starting the description of a polyline.
  • void add_node(typename boost::graph_traits<Graph>::vertex_descriptor v) called for each vertex v of the polyline currently described. If the polyline is closed this function will be called twice for the first vertex of the cycle picked (once after calling start_new_polyline() and once before the call to end_polyline().
  • void end_polyline() called when the description of a polyline is finished.
IsTerminalA functor providing bool operator()(boost::graph_traits<Graph>::vertex_descriptor v, const Graph& g) const returning true if the vertex v of degree 2 is a polyline endpoint and false otherwise.

An overload without is_terminal is provided if no vertices but those of degree different from 2 are polyline endpoints.

Examples:
Surface_mesh_skeletonization/simple_mcfskel_example.cpp.