Structural Bioinformatics Library
Template C++ / Python API for developping structural bioinformatics applications.
T_Cell_complex_shelling_diagram< Cell, IsLowerCell > Class Template Reference

Diagram representing the shelling order of a cell complex. More...

#include <Cell_complex_shelling_diagram.hpp>

Public Types

typedef T_Cell_complex_shelling_diagram< Cell, IsLowerCell > Self
 
typedef T_Shelling_diagram_vertex_property< Cell, IsLowerCell > Shelling_diagram_vertex_property
 
typedef T_Directed_acyclic_graph_with_layers< Shelling_diagram_vertex_propertyBase
 
typedef Base::Graph Graph
 Underlaying graph representing the shellign diagram. More...
 
typedef Base::Vertex Shell
 
typedef Base::Vertices_iterator Shells_iterator
 
typedef Base::Layer_iterator Shells_of_same_order_iterator
 
typedef Base::Children_iterator Next_shells_iterator
 
typedef Shelling_diagram_vertex_property::Cells_of_shell_iterator Cells_of_shell_iterator
 
typedef std::map< Union_find_vertex *, Shell, Is_lower_cell > Union_find_to_shell_map
 

Public Member Functions

 T_Cell_complex_shelling_diagram (void)
 
bool is_empty_shell (Shell v) const
 
void clear (void)
 
template<class CellComplexTraits >
void build (typename CellComplexTraits::Cell_complex &complex, bool no_boundary_shell=false, const CellComplexTraits &traits=CellComplexTraits())
 Build this shelling diagram from the input cell-complex. More...
 
template<class CellComplexShellingDiagram >
void copy (const CellComplexShellingDiagram &other)
 
template<class CellComplexShellingDiagram >
void copy (const CellComplexShellingDiagram &other, typename CellComplexShellingDiagram::Shell s)
 
template<class InputIterator >
void add_cells_to_shell (InputIterator begin, InputIterator end, Shell &v)
 
void add_cell_to_shell (Cell cell, Shell &v)
 
bool remove_last_empty_shell (Shell v)
 
void remove_empty_shells (void)
 
void reorder_next_shells (Shell v)
 
const Graphget_graph (void) const
 
bool is_over_shell_of (Shell s, Shell t) const
 
unsigned get_maximal_shelling_order (void) const
 
unsigned get_number_of_shelling_trees (void) const
 
unsigned get_number_of_shells (void) const
 
unsigned get_number_of_shells_of_same_order (unsigned i) const
 
unsigned get_shelling_order_of_shell (Shell v) const
 
unsigned get_number_of_cells_in_shell (Shell v) const
 
unsigned get_number_of_cells_under_shell (Shell v) const
 
unsigned get_number_of_cells_of_shelling_order (unsigned i) const
 
unsigned get_number_of_cells (void) const
 
std::pair< Shell, bool > get_shell_of_cell (Cell cell) const
 
unsigned get_shelling_order_of_cell (Cell cell) const
 
Shells_iterator shells_begin (void) const
 
Shells_iterator shells_end (void) const
 
Shells_of_same_order_iterator shells_of_same_order_begin (unsigned i) const
 
Shells_of_same_order_iterator shells_of_same_order_end (unsigned i) const
 
Next_shells_iterator next_shells_begin (Shell v) const
 
Next_shells_iterator next_shells_end (Shell v) const
 
Cells_of_shell_iterator cells_begin (Shell v) const
 
Cells_of_shell_iterator cells_end (Shell v) const
 
Cells_of_shell_iterator cells_begin (Shell v)
 
Cells_of_shell_iterator cells_end (Shell v)
 
std::string get_color_of_shell (Shell s) const
 
template<class OutputStream >
void print (OutputStream &out) const
 

Protected Types

typedef Base::Orientation_type Orientation_type
 Orientation of the edges in the Directed Acyclic Graph. More...
 
typedef Base::Vertex Vertex
 Representation of a Vertex of the Directed Acyclic Graph. More...
 
typedef Base::Edge Edge
 Representation of an Edge of the Directed Acyclic Graph. More...
 
typedef Base::Vertices_iterator Vertices_iterator
 Iterator over all the vertices of the Directed Acyclic Graph. More...
 
typedef Base::Edges_iterator Edges_iterator
 Iterator over all the edges of the Directed Acyclic Graph. More...
 
typedef Base::Children_iterator Children_iterator
 Iterator over all the children of a given Vertex. More...
 
typedef Base::Parents_iterator Parents_iterator
 Iterator over all the parents of a given Vertex. More...
 
typedef std::set< VertexLayer
 Representation of a layer of the graph. More...
 
typedef Layer::const_iterator Layer_iterator
 Iterator over all the vertices of a given layer. More...
 
typedef boost::filter_iterator< Is_maximal_element, Vertices_iteratorMaximal_elements_iterator
 Iterator over the vertices of the Directed Acyclic Graph that are maximal elements of the corresponding partially ordered set. More...
 
typedef boost::filter_iterator< Is_minimal_element, Vertices_iteratorMinimal_elements_iterator
 Iterator over the vertices of the Directed Acyclic Graph that are minimal elements of the corresponding partially ordered set. More...
 

Layers

unsigned get_number_of_layers (void) const
 Access to the number of layers in the graph. More...
 
unsigned get_number_of_vertices (unsigned height) const
 Access to the number of vertices with the input height. More...
 
unsigned get_height (Vertex v) const
 
bool has_height (Vertex v) const
 Return true if v is an associated height. More...
 
unsigned increment_maximal_height (unsigned k=1)
 Increment the maximal height by adding k layers. More...
 
void set_height (Vertex v, unsigned)
 
Layer_iterator layer_begin (unsigned height) const
 Starts the set of vertices (possibly empty) with the input height. More...
 
Layer_iterator layer_end (unsigned height) const
 Ends the set of vertices (possibly empty) with the input height. More...
 

Vertices

unsigned get_number_of_vertices (void) const
 Access to the number of vertices in the graph. More...
 
Vertex add_vertex (unsigned height)
 Add a vertex with no property in the graph, at a height h. More...
 
Vertex add_vertex (const T_Shelling_diagram_vertex_property< Cell, std::less< Cell > > &p, unsigned height)
 Add a vertex with a property p in the graph, at a height h. More...
 
T_Shelling_diagram_vertex_property< Cell, std::less< Cell > > & operator[] (Vertex v)
 Access to the property associated to a vertex. More...
 
const T_Shelling_diagram_vertex_property< Cell, std::less< Cell > > & operator[] (Vertex v) const
 Const access to the property associated to a vertex. More...
 
bool is_empty (void) const
 Check that the graph has no vertex. More...
 
OutputIterator find_vertices_compared_to_data (const DataType &data, OutputIterator out, const Comparator &compare=Comparator()) const
 Find all the vertices in the graph having a property that compares equal to the input data. More...
 
bool find_first_vertex_compared_to_data (const DataType &data, Vertex &v, const Comparator &compare=Comparator()) const
 Find the first vertex in the graph having a property that compares equal to the input data. More...
 
Vertices_iterator vertices_begin (void) const
 Starts the set of vertices of the graph. More...
 
Vertices_iterator vertices_end (void) const
 Ends the set of vertices of the graph. More...
 
void remove_vertex (Vertex v)
 Remove the vertex v from the graph. More...
 

Vertices

Vertex add_vertex (const VertexProperty &p)
 Add a vertex with the property p to the graph. More...
 

Edges

Directed_acyclic_graph_default_propertyoperator[] (Edge e)
 Access to the property attached to e. More...
 
const Directed_acyclic_graph_default_propertyoperator[] (Edge e) const
 Const access to the property attached to e. More...
 
Edge add_edge (Vertex u, Vertex v)
 Add an edge from u to v, with no property. More...
 
Edge add_edge (Vertex u, Vertex v, const Directed_acyclic_graph_default_property &p)
 Add an edge from u to v, with the property p. More...
 
unsigned get_number_of_edges (void) const
 Access to the number of edges in the graph. More...
 
Edge get_edge (Vertex u, Vertex v) const
 
void clear_vertex (Vertex v)
 Remove all edges incident to v. More...
 
void remove_edge (Vertex u, Vertex v)
 Remove the edge from u to v. More...
 
void remove_edge (Edge e)
 Remove the edge e from the graph. More...
 
Edges_iterator edges_begin () const
 Starts the set of edges. More...
 
Edges_iterator edges_end () const
 Ends the set of edges. More...
 

Parent / Child

bool is_ancestor (Vertex u, Vertex v) const
 Check that u is an ancestor of v. More...
 
unsigned get_number_of_parents (Vertex v) const
 Access to the number of parents of v. More...
 
unsigned get_number_of_children (Vertex v) const
 Access to the number of children of v. More...
 
Vertex get_parent (Edge e) const
 Access to the source of e. More...
 
Vertex get_child (Edge e) const
 Access to the target of e. More...
 
bool is_parent (Vertex u, Vertex v) const
 Check that u is a parent of v. More...
 
void clear_children (Vertex v)
 Remove all out-going edges incident to v. More...
 
void clear_parents (Vertex v)
 Remove all in-going edges incident to v. More...
 
Children_iterator children_begin (Vertex v) const
 Starts the set of children of v. More...
 
Children_iterator children_end (Vertex v) const
 Ends the set of children of v. More...
 
Parents_iterator parents_begin (Vertex v) const
 Starts the set of parents of v. More...
 
Parents_iterator parents_end (Vertex v) const
 Ends the set of parents of v. More...
 

Partial Order Set Builder

void build_from_partially_ordered_set (InputIterator begin, InputIterator end, const PartialOrderPredicate &order)
 Construct the Directed Acyclic Graph from the partially ordered set in [begin, end). More...
 

Subgraph Manipulators

OutputIterator get_induced_subgraph (InputIterator begin, InputIterator end, OutputIterator out) const
 Construct the induced subgraph from the range of vertices in [begin, end). More...
 
OutputIterator get_descendant_ancestor_subgraph (Vertex u, Vertex v, OutputIterator out) const
 Construct the maximal subgraph such that all vertices are ancestors of u and descendants of v. More...
 
void get_subgraph (VertexIterator v_begin, VertexIterator v_end, EdgeIterator e_begin, EdgeIterator e_end, Self &subgraph) const
 Construct the subgraph from the range of vertices [v_begin, v_end) and edges in [e_begin, e_end). More...
 
void get_edge_subgraph (InputIterator begin, InputIterator end, Self &subgraph) const
 Construct the edge subgraph from the range of edges in [begin, end). More...
 

Subgraph Manipulators

template<class VertexIterator , class EdgeIterator >
void get_subgraph (VertexIterator v_begin, VertexIterator v_end, EdgeIterator e_begin, EdgeIterator e_end, Self &subgraph) const
 Construct the subgraph from the range of vertices [v_begin, v_end) and edges in [e_begin, e_end). More...
 
template<class InputIterator >
void get_edge_subgraph (InputIterator begin, InputIterator end, Self &subgraph) const
 Construct the edge subgraph from the range of edges in [begin, end). More...
 

I/O

void print_in_dot_format (OutputStream &out, bool enforced_rank=true) const
 Print in the output stream the graph in DOT format. More...
 
void print_in_dot_format (bool enforced_rank=true) const
 Print in the standard output stream the graph in DOT format. More...
 

I/O

template<class OutputStream >
void print_in_dot_format (OutputStream &out) const
 Print in the output stream the graph in DOT format. More...
 
void print_in_dot_format (void) const
 Print in the standard output stream the graph in DOT format. More...
 

Graph

Graphget_graph (void)
 Acces to the BGL graph. More...
 

Minimal / Maximal Elements

template<class OutputIterator >
OutputIterator get_minimal_elements_from (Vertex v, OutputIterator out) const
 Access to the set of minimal elements lower or equal to v. More...
 
template<class OutputIterator >
OutputIterator get_maximal_elements_from (Vertex v, OutputIterator out) const
 Access to the set of maximal elements greater or equal to v. More...
 
const Orientation_typeget_orientation (void) const
 Return the orientation of the DAG. More...
 
Orientation_typeget_orientation (void)
 Return a reference to the orientation of the DAG. More...
 
bool is_maximal_root_oriented (void) const
 Check that maximal elements are the roots of the graph. More...
 
bool is_minimal_element (Vertex u) const
 Check that u is a minimal element. More...
 
bool is_maximal_element (Vertex u) const
 Check that u is a maximal element. More...
 
bool is_lower (Vertex u, Vertex v) const
 Check that u is lower than v. More...
 
Maximal_elements_iterator maximal_elements_begin () const
 Starts the set of maximal elements. More...
 
Maximal_elements_iterator maximal_elements_end () const
 Ends the set of maximal elements. More...
 
Minimal_elements_iterator minimal_elements_begin () const
 Starts the set of minimal elements. More...
 
Minimal_elements_iterator minimal_elements_end () const
 Ends the set of minimal elements. More...
 

Detailed Description

template<class Cell, class IsLowerCell = std::less<Cell>>
class SBL::CADS::T_Cell_complex_shelling_diagram< Cell, IsLowerCell >

Diagram representing the shelling order of a cell complex.

The CellComplex has some requirements for visiting the cells:

  • given a cell, visit the adjacent cells
  • visit all the cells

3 steps:

– first, defines the cell-complex

– second, attributes the SO to each cell

– third, construct the shelling diagram

Idea: first, find the borders of a patch, i.e the 2-cells incident to a background cell

second, construct a boost graph such that: every border cells are glue on one node, any other cell is represented by a node, and two nodes are linked by an edge if the corresponding cells are adjacents.

third, run dijkstra from the border node: – all cells in the border node have a SO of 0, all other cells have a S0 equals to the distance to the border node.

Now the SO is attributed, we have to construt the SO diagram. To do so, first run a union find algorithm for finding the connected components of cells with the same SO: for each pair of adjacent cells having the same SO, union them.

The SO diagram is initialized with a node for each c.c in union-find

Do the following for each union-find c.c:

– for each cell in a c.c., search for adjacent cells with the next SO: if there is no edge in the SO diagram, ad an edge between the corresponding c.c.

Member Typedef Documentation

◆ Base

◆ Cells_of_shell_iterator

◆ Children_iterator

Iterator over all the children of a given Vertex.

◆ Edge

typedef Base::Edge Edge
inherited

Representation of an Edge of the Directed Acyclic Graph.

◆ Edges_iterator

Iterator over all the edges of the Directed Acyclic Graph.

◆ Graph

typedef Base::Graph Graph

Underlaying graph representing the shellign diagram.

◆ Layer

typedef std::set<Vertex> Layer
inherited

Representation of a layer of the graph.

◆ Layer_iterator

typedef Layer::const_iterator Layer_iterator
inherited

Iterator over all the vertices of a given layer.

◆ Maximal_elements_iterator

typedef boost::filter_iterator<Is_maximal_element, Vertices_iterator> Maximal_elements_iterator
inherited

Iterator over the vertices of the Directed Acyclic Graph that are maximal elements of the corresponding partially ordered set.

◆ Minimal_elements_iterator

typedef boost::filter_iterator<Is_minimal_element, Vertices_iterator> Minimal_elements_iterator
inherited

Iterator over the vertices of the Directed Acyclic Graph that are minimal elements of the corresponding partially ordered set.

◆ Next_shells_iterator

◆ Orientation_type

Orientation of the edges in the Directed Acyclic Graph.

Options are:

  • MAXIMAL_ROOT_ORIENTATION : the roots are the maximal elements of the Directed Acyclic Graph.
  • MINIMAL_ROOT_ORIENTATION : the roots are the minimal elements of the Directed Acyclic Graph.

◆ Parents_iterator

Iterator over all the parents of a given Vertex.

◆ Self

typedef T_Cell_complex_shelling_diagram<Cell, IsLowerCell> Self

◆ Shell

◆ Shelling_diagram_vertex_property

◆ Shells_iterator

◆ Shells_of_same_order_iterator

◆ Union_find_to_shell_map

typedef std::map<Union_find_vertex*, Shell, Is_lower_cell> Union_find_to_shell_map

◆ Vertex

typedef Base::Vertex Vertex
inherited

Representation of a Vertex of the Directed Acyclic Graph.

◆ Vertices_iterator

Iterator over all the vertices of the Directed Acyclic Graph.

Constructor & Destructor Documentation

◆ T_Cell_complex_shelling_diagram()

Member Function Documentation

◆ add_cell_to_shell()

void add_cell_to_shell ( Cell  cell,
Shell v 
)
inline

◆ add_cells_to_shell()

void add_cells_to_shell ( InputIterator  begin,
InputIterator  end,
Shell v 
)
inline

◆ add_edge() [1/2]

Add an edge from u to v, with no property.

Precondition
get_height(u) != get_height(v).
get_height(u) > get_height(v) iff the graph is maximal root oriented.

◆ add_edge() [2/2]

Add an edge from u to v, with the property p.

Precondition
get_height(u) != get_height(v).
get_height(u) > get_height(v) iff the graph is maximal root oriented.

◆ add_vertex() [1/3]

T_Directed_acyclic_graph_with_layers< T_Shelling_diagram_vertex_property< Cell, std::less< Cell > > , Directed_acyclic_graph_default_property >::Vertex add_vertex ( const T_Shelling_diagram_vertex_property< Cell, std::less< Cell > > &  p,
unsigned  height 
)
inlineinherited

Add a vertex with a property p in the graph, at a height h.

Precondition
0 < get_number_of_layers().
height < get_number_of_layers().

◆ add_vertex() [2/3]

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Vertex add_vertex ( const VertexProperty &  p)
inlineinherited

Add a vertex with the property p to the graph.

◆ add_vertex() [3/3]

T_Directed_acyclic_graph_with_layers< T_Shelling_diagram_vertex_property< Cell, std::less< Cell > > , Directed_acyclic_graph_default_property >::Vertex add_vertex ( unsigned  height)
inlineinherited

Add a vertex with no property in the graph, at a height h.

Precondition
0 < get_number_of_layers().
height < get_number_of_layers().

◆ build()

void build ( typename CellComplexTraits::Cell_complex &  complex,
bool  no_boundary_shell = false,
const CellComplexTraits &  traits = CellComplexTraits() 
)
inline

Build this shelling diagram from the input cell-complex.

◆ build_from_partially_ordered_set()

void build_from_partially_ordered_set ( InputIterator  begin,
InputIterator  end,
const PartialOrderPredicate &  order 
)
inlineinherited

Construct the Directed Acyclic Graph from the partially ordered set in [begin, end).

The range [begin, end) defines a set of pairs (height, element) allowing to associate an height to each element of the partially ordered set. Note that each element has to be unique (i.e multiplicity is not allowed).

Precondition
get_height(u) != get_height(v).
get_height(u) > get_height(v) iff the graph is maximal root oriented.

◆ cells_begin() [1/2]

T_Cell_complex_shelling_diagram< Cell, IsLowerCell >::Cells_of_shell_iterator cells_begin ( Shell  v)
inline

◆ cells_begin() [2/2]

T_Cell_complex_shelling_diagram< Cell, CellHandle >::Cells_of_shell_iterator cells_begin ( Shell  v) const
inline

◆ cells_end() [1/2]

T_Cell_complex_shelling_diagram< Cell, IsLowerCell >::Cells_of_shell_iterator cells_end ( Shell  v)
inline

◆ cells_end() [2/2]

T_Cell_complex_shelling_diagram< Cell, CellHandle >::Cells_of_shell_iterator cells_end ( Shell  v) const
inline

◆ children_begin()

Starts the set of children of v.

◆ children_end()

Ends the set of children of v.

◆ clear()

void clear ( void  )
inline

◆ clear_children()

void clear_children ( Vertex  v)
inlineinherited

Remove all out-going edges incident to v.

◆ clear_parents()

void clear_parents ( Vertex  v)
inlineinherited

Remove all in-going edges incident to v.

◆ clear_vertex()

void clear_vertex ( Vertex  v)
inlineinherited

Remove all edges incident to v.

◆ copy() [1/2]

void copy ( const CellComplexShellingDiagram &  other)
inline

◆ copy() [2/2]

void copy ( const CellComplexShellingDiagram &  other,
typename CellComplexShellingDiagram::Shell  s 
)
inline

◆ edges_begin()

T_Directed_acyclic_graph_with_layers< T_Shelling_diagram_vertex_property< Cell, std::less< Cell > > , Directed_acyclic_graph_default_property >::Edges_iterator edges_begin ( void  ) const
inlineinherited

Starts the set of edges.

◆ edges_end()

Ends the set of edges.

◆ find_first_vertex_compared_to_data()

bool find_first_vertex_compared_to_data ( const DataType &  data,
Vertex v,
const Comparator &  compare = Comparator() 
) const
inlineinherited

Find the first vertex in the graph having a property that compares equal to the input data.

Note that there is no order on the vertices, so if there are several vertices having properties comparing equal to the input data, only an arbitrary one is found.

Parameters
dataData to be compared with the properties of the vertices.
vVertex with a property that compares equal to data, if any.
compareComparator between the data and the properties of vertices.
Returns
true iff a vertex was found.

◆ find_vertices_compared_to_data()

OutputIterator find_vertices_compared_to_data ( const DataType &  data,
OutputIterator  out,
const Comparator &  compare = Comparator() 
) const
inlineinherited

Find all the vertices in the graph having a property that compares equal to the input data.

Parameters
dataData to be compared with the properties of the vertices.
outOutput iterator over a container of vertices.
compareComparator between the data and the properties of vertices.

◆ get_child()

Access to the target of e.

◆ get_color_of_shell()

std::string get_color_of_shell ( Shell  s) const
inline

◆ get_descendant_ancestor_subgraph()

OutputIterator get_descendant_ancestor_subgraph ( Vertex  u,
Vertex  v,
OutputIterator  out 
) const
inlineinherited

Construct the maximal subgraph such that all vertices are ancestors of u and descendants of v.

Parameters
uThe descendant.
vThe ancestor.
outOutput iterator over a set of edges.

◆ get_edge()

T_Directed_acyclic_graph_with_layers< T_Shelling_diagram_vertex_property< Cell, std::less< Cell > > , Directed_acyclic_graph_default_property >::Edge get_edge ( Vertex  u,
Vertex  v 
) const
inlineinherited

Access to the Edge u -> v.

Precondition
u is a parent of v.

◆ get_edge_subgraph() [1/2]

void get_edge_subgraph ( InputIterator  begin,
InputIterator  end,
Self subgraph 
) const
inlineinherited

Construct the edge subgraph from the range of edges in [begin, end).

Parameters
beginStarts the set of edges.
endEnds the set of edges.
subgraphThe output edge subgraph.

◆ get_edge_subgraph() [2/2]

void get_edge_subgraph ( InputIterator  begin,
InputIterator  end,
Self subgraph 
) const
inlineinherited

Construct the edge subgraph from the range of edges in [begin, end).

Parameters
beginStarts the set of edges.
endEnds the set of edges.
subgraphThe output edge subgraph.

◆ get_graph() [1/2]

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Graph & get_graph ( void  )
inlineinherited

Acces to the BGL graph.

◆ get_graph() [2/2]

const T_Cell_complex_shelling_diagram< Cell, IsLowerCell >::Graph & get_graph ( void  ) const
inline

◆ get_height()

unsigned get_height ( Vertex  v) const
inlineinherited

Access to the height of a vertex.

Precondition
The vertex has a height.

◆ get_induced_subgraph()

OutputIterator get_induced_subgraph ( InputIterator  begin,
InputIterator  end,
OutputIterator  out 
) const
inlineinherited

Construct the induced subgraph from the range of vertices in [begin, end).

Parameters
beginStarts the set of vertices.
endEnds the set of vertices.
outOutput iterator over a set of edges.

◆ get_maximal_elements_from()

OutputIterator get_maximal_elements_from ( Vertex  v,
OutputIterator  out 
) const
inlineinherited

Access to the set of maximal elements greater or equal to v.

◆ get_maximal_shelling_order()

unsigned get_maximal_shelling_order ( void  ) const
inline

◆ get_minimal_elements_from()

OutputIterator get_minimal_elements_from ( Vertex  v,
OutputIterator  out 
) const
inlineinherited

Access to the set of minimal elements lower or equal to v.

◆ get_number_of_cells()

unsigned get_number_of_cells ( void  ) const
inline

◆ get_number_of_cells_in_shell()

unsigned get_number_of_cells_in_shell ( Shell  v) const
inline

◆ get_number_of_cells_of_shelling_order()

unsigned get_number_of_cells_of_shelling_order ( unsigned  i) const
inline

◆ get_number_of_cells_under_shell()

unsigned get_number_of_cells_under_shell ( Shell  v) const
inline

◆ get_number_of_children()

unsigned get_number_of_children ( Vertex  v) const
inlineinherited

Access to the number of children of v.

◆ get_number_of_edges()

unsigned get_number_of_edges ( void  ) const
inlineinherited

Access to the number of edges in the graph.

◆ get_number_of_layers()

unsigned get_number_of_layers ( void  ) const
inlineinherited

Access to the number of layers in the graph.

◆ get_number_of_parents()

unsigned get_number_of_parents ( Vertex  v) const
inlineinherited

Access to the number of parents of v.

◆ get_number_of_shelling_trees()

unsigned get_number_of_shelling_trees ( void  ) const
inline

◆ get_number_of_shells()

unsigned get_number_of_shells ( void  ) const
inline

◆ get_number_of_shells_of_same_order()

unsigned get_number_of_shells_of_same_order ( unsigned  i) const
inline

◆ get_number_of_vertices() [1/2]

unsigned get_number_of_vertices ( unsigned  height) const
inlineinherited

Access to the number of vertices with the input height.

◆ get_number_of_vertices() [2/2]

unsigned get_number_of_vertices ( void  ) const
inlineinherited

Access to the number of vertices in the graph.

◆ get_orientation() [1/2]

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Orientation_type & get_orientation ( void  )
inlineinherited

Return a reference to the orientation of the DAG.

◆ get_orientation() [2/2]

const T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Orientation_type & get_orientation ( void  ) const
inlineinherited

Return the orientation of the DAG.

◆ get_parent()

Access to the source of e.

◆ get_shell_of_cell()

std::pair< typename T_Cell_complex_shelling_diagram< Cell, IsLowerCell >::Shell, bool > get_shell_of_cell ( Cell  cell) const
inline

◆ get_shelling_order_of_cell()

unsigned get_shelling_order_of_cell ( Cell  cell) const
inline

◆ get_shelling_order_of_shell()

unsigned get_shelling_order_of_shell ( Shell  v) const
inline

◆ get_subgraph() [1/2]

void get_subgraph ( VertexIterator  v_begin,
VertexIterator  v_end,
EdgeIterator  e_begin,
EdgeIterator  e_end,
Self subgraph 
) const
inlineinherited

Construct the subgraph from the range of vertices [v_begin, v_end) and edges in [e_begin, e_end).

Parameters
v_beginStarts the set of vertices.
v_endEnds the set of vertices.
e_beginStarts the set of edges.
e_endEnds the set of edges.
subgraphThe output subgraph.

◆ get_subgraph() [2/2]

void get_subgraph ( VertexIterator  v_begin,
VertexIterator  v_end,
EdgeIterator  e_begin,
EdgeIterator  e_end,
Self subgraph 
) const
inlineinherited

Construct the subgraph from the range of vertices [v_begin, v_end) and edges in [e_begin, e_end).

Parameters
v_beginStarts the set of vertices.
v_endEnds the set of vertices.
e_beginStarts the set of edges.
e_endEnds the set of edges.
subgraphThe output subgraph.

◆ has_height()

bool has_height ( Vertex  v) const
inlineinherited

Return true if v is an associated height.

◆ increment_maximal_height()

unsigned increment_maximal_height ( unsigned  k = 1)
inlineinherited

Increment the maximal height by adding k layers.

Precondition
k > 0.

◆ is_ancestor()

bool is_ancestor ( Vertex  u,
Vertex  v 
) const
inlineinherited

Check that u is an ancestor of v.

In particular, if the height of u is lower or equal to the height of v, it returns false.

◆ is_empty()

bool is_empty ( void  ) const
inlineinherited

Check that the graph has no vertex.

◆ is_empty_shell()

bool is_empty_shell ( Shell  v) const
inline

◆ is_lower()

bool is_lower ( Vertex  u,
Vertex  v 
) const
inlineinherited

Check that u is lower than v.

◆ is_maximal_element()

bool is_maximal_element ( Vertex  u) const
inlineinherited

Check that u is a maximal element.

◆ is_maximal_root_oriented()

bool is_maximal_root_oriented ( void  ) const
inlineinherited

Check that maximal elements are the roots of the graph.

◆ is_minimal_element()

bool is_minimal_element ( Vertex  u) const
inlineinherited

Check that u is a minimal element.

◆ is_over_shell_of()

bool is_over_shell_of ( Shell  s,
Shell  t 
) const
inline

◆ is_parent()

bool is_parent ( Vertex  u,
Vertex  v 
) const
inlineinherited

Check that u is a parent of v.

◆ layer_begin()

T_Directed_acyclic_graph_with_layers< T_Shelling_diagram_vertex_property< Cell, std::less< Cell > > , Directed_acyclic_graph_default_property >::Layer_iterator layer_begin ( unsigned  height) const
inlineinherited

Starts the set of vertices (possibly empty) with the input height.

◆ layer_end()

T_Directed_acyclic_graph_with_layers< T_Shelling_diagram_vertex_property< Cell, std::less< Cell > > , Directed_acyclic_graph_default_property >::Layer_iterator layer_end ( unsigned  height) const
inlineinherited

Ends the set of vertices (possibly empty) with the input height.

◆ maximal_elements_begin()

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Maximal_elements_iterator maximal_elements_begin ( void  ) const
inlineinherited

Starts the set of maximal elements.

◆ maximal_elements_end()

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Maximal_elements_iterator maximal_elements_end ( void  ) const
inlineinherited

Ends the set of maximal elements.

◆ minimal_elements_begin()

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Minimal_elements_iterator minimal_elements_begin ( void  ) const
inlineinherited

Starts the set of minimal elements.

◆ minimal_elements_end()

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Minimal_elements_iterator minimal_elements_end ( void  ) const
inlineinherited

Ends the set of minimal elements.

◆ next_shells_begin()

T_Cell_complex_shelling_diagram< Cell, IsLowerCell >::Next_shells_iterator next_shells_begin ( Shell  v) const
inline

◆ next_shells_end()

T_Cell_complex_shelling_diagram< Cell, IsLowerCell >::Next_shells_iterator next_shells_end ( Shell  v) const
inline

◆ operator[]() [1/4]

Directed_acyclic_graph_default_property & operator[] ( Edge  e)
inlineinherited

Access to the property attached to e.

◆ operator[]() [2/4]

const Directed_acyclic_graph_default_property & operator[] ( Edge  e) const
inlineinherited

Const access to the property attached to e.

◆ operator[]() [3/4]

T_Shelling_diagram_vertex_property< Cell, std::less< Cell > > & operator[] ( Vertex  v)
inlineinherited

Access to the property associated to a vertex.

◆ operator[]() [4/4]

const T_Shelling_diagram_vertex_property< Cell, std::less< Cell > > & operator[] ( Vertex  v) const
inlineinherited

Const access to the property associated to a vertex.

◆ parents_begin()

Starts the set of parents of v.

◆ parents_end()

Ends the set of parents of v.

◆ print()

void print ( OutputStream &  out) const
inline

◆ print_in_dot_format() [1/4]

void print_in_dot_format ( bool  enforced_rank = true) const
inlineinherited

Print in the standard output stream the graph in DOT format.

◆ print_in_dot_format() [2/4]

void print_in_dot_format ( OutputStream &  out) const
inherited

Print in the output stream the graph in DOT format.

◆ print_in_dot_format() [3/4]

void print_in_dot_format ( OutputStream &  out,
bool  enforced_rank = true 
) const
inlineinherited

Print in the output stream the graph in DOT format.

◆ print_in_dot_format() [4/4]

void print_in_dot_format ( void  ) const
inherited

Print in the standard output stream the graph in DOT format.

◆ remove_edge() [1/2]

void remove_edge ( Edge  e)
inlineinherited

Remove the edge e from the graph.

◆ remove_edge() [2/2]

void remove_edge ( Vertex  u,
Vertex  v 
)
inlineinherited

Remove the edge from u to v.

◆ remove_empty_shells()

void remove_empty_shells ( void  )
inline

◆ remove_last_empty_shell()

bool remove_last_empty_shell ( Shell  v)
inline

◆ remove_vertex()

void remove_vertex ( Vertex  v)
inlineinherited

Remove the vertex v from the graph.

It also removes v from its layer.

◆ reorder_next_shells()

void reorder_next_shells ( Shell  v)
inline

◆ set_height()

void set_height ( Vertex  v,
unsigned  h 
)
inlineinherited

◆ shells_begin()

T_Cell_complex_shelling_diagram< Cell, IsLowerCell >::Shells_iterator shells_begin ( void  ) const
inline

◆ shells_end()

T_Cell_complex_shelling_diagram< Cell, IsLowerCell >::Shells_iterator shells_end ( void  ) const
inline

◆ shells_of_same_order_begin()

T_Cell_complex_shelling_diagram< Cell, IsLowerCell >::Shells_of_same_order_iterator shells_of_same_order_begin ( unsigned  i) const
inline

◆ shells_of_same_order_end()

T_Cell_complex_shelling_diagram< Cell, IsLowerCell >::Shells_of_same_order_iterator shells_of_same_order_end ( unsigned  i) const
inline

◆ vertices_begin()

T_Directed_acyclic_graph_with_layers< T_Shelling_diagram_vertex_property< Cell, std::less< Cell > > , Directed_acyclic_graph_default_property >::Vertices_iterator vertices_begin ( void  ) const
inlineinherited

Starts the set of vertices of the graph.

◆ vertices_end()

T_Directed_acyclic_graph_with_layers< T_Shelling_diagram_vertex_property< Cell, std::less< Cell > > , Directed_acyclic_graph_default_property >::Vertices_iterator vertices_end ( void  ) const
inlineinherited

Ends the set of vertices of the graph.