Structural Bioinformatics Library
Template C++ / Python API for developping structural bioinformatics applications.
|
Diagram representing the shelling order of a cell complex. More...
#include <Cell_complex_shelling_diagram.hpp>
Public Types | |
typedef Base::Graph | Graph |
Underlaying graph representing the shellign diagram. More... | |
Public Member Functions | |
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... | |
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< Vertex > | Layer |
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_iterator > | Maximal_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_iterator > | Minimal_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... | |
void | set_dot_graph_vertex_label (std::string vlabel) |
Dot graph vertex label. 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_property & | operator[] (Edge e) |
Access to the property attached to e. More... | |
const Directed_acyclic_graph_default_property & | operator[] (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 | |
Graph & | get_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_type & | get_orientation (void) const |
Return the orientation of the DAG. More... | |
Orientation_type & | get_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... | |
Diagram representing the shelling order of a cell complex.
The CellComplex has some requirements for visiting 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.
|
inherited |
Iterator over all the children of a given Vertex.
|
inherited |
Representation of an Edge of the Directed Acyclic Graph.
|
inherited |
Iterator over all the edges of the Directed Acyclic Graph.
typedef Base::Graph Graph |
Underlaying graph representing the shellign diagram.
|
inherited |
Iterator over all the vertices of a given layer.
|
inherited |
Iterator over the vertices of the Directed Acyclic Graph that are maximal elements of the corresponding partially ordered set.
|
inherited |
Iterator over the vertices of the Directed Acyclic Graph that are minimal elements of the corresponding partially ordered set.
|
inherited |
Orientation of the edges in the Directed Acyclic Graph.
Options are:
|
inherited |
Iterator over all the parents of a given Vertex.
|
inherited |
Representation of a Vertex of the Directed Acyclic Graph.
|
inherited |
Iterator over all the vertices of the Directed Acyclic Graph.
|
inlineinherited |
Add an edge from u to v, with no property.
|
inlineinherited |
Add an edge from u to v, with the property p.
|
inlineinherited |
Add a vertex with a property p in the graph, at a height h.
|
inlineinherited |
Add a vertex with the property p to the graph.
|
inlineinherited |
Add a vertex with no property in the graph, at a height h.
|
inline |
Build this shelling diagram from the input cell-complex.
|
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).
|
inlineinherited |
Starts the set of children of v.
|
inlineinherited |
Ends the set of children of v.
|
inlineinherited |
Remove all out-going edges incident to v.
|
inlineinherited |
Remove all in-going edges incident to v.
|
inlineinherited |
Remove all edges incident to v.
|
inlineinherited |
Starts the set of edges.
|
inlineinherited |
Ends the set of edges.
|
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.
data | Data to be compared with the properties of the vertices. |
v | Vertex with a property that compares equal to data, if any. |
compare | Comparator between the data and the properties of vertices. |
|
inlineinherited |
Find all the vertices in the graph having a property that compares equal to the input data.
data | Data to be compared with the properties of the vertices. |
out | Output iterator over a container of vertices. |
compare | Comparator between the data and the properties of vertices. |
|
inlineinherited |
Access to the target of e.
|
inlineinherited |
Construct the maximal subgraph such that all vertices are ancestors of u and descendants of v.
u | The descendant. |
v | The ancestor. |
out | Output iterator over a set of edges. |
|
inlineinherited |
Access to the Edge u -> v.
|
inlineinherited |
Construct the edge subgraph from the range of edges in [begin, end).
begin | Starts the set of edges. |
end | Ends the set of edges. |
subgraph | The output edge subgraph. |
|
inlineinherited |
Construct the edge subgraph from the range of edges in [begin, end).
begin | Starts the set of edges. |
end | Ends the set of edges. |
subgraph | The output edge subgraph. |
|
inlineinherited |
Acces to the BGL graph.
|
inlineinherited |
Access to the height of a vertex.
|
inlineinherited |
Construct the induced subgraph from the range of vertices in [begin, end).
begin | Starts the set of vertices. |
end | Ends the set of vertices. |
out | Output iterator over a set of edges. |
|
inlineinherited |
Access to the set of maximal elements greater or equal to v.
|
inlineinherited |
Access to the set of minimal elements lower or equal to v.
|
inlineinherited |
Access to the number of children of v.
|
inlineinherited |
Access to the number of edges in the graph.
|
inlineinherited |
Access to the number of layers in the graph.
|
inlineinherited |
Access to the number of parents of v.
|
inlineinherited |
Access to the number of vertices with the input height.
|
inlineinherited |
Access to the number of vertices in the graph.
|
inlineinherited |
Return a reference to the orientation of the DAG.
|
inlineinherited |
Return the orientation of the DAG.
|
inlineinherited |
Access to the source of e.
|
inlineinherited |
Construct the subgraph from the range of vertices [v_begin, v_end) and edges in [e_begin, e_end).
v_begin | Starts the set of vertices. |
v_end | Ends the set of vertices. |
e_begin | Starts the set of edges. |
e_end | Ends the set of edges. |
subgraph | The output subgraph. |
|
inlineinherited |
Construct the subgraph from the range of vertices [v_begin, v_end) and edges in [e_begin, e_end).
v_begin | Starts the set of vertices. |
v_end | Ends the set of vertices. |
e_begin | Starts the set of edges. |
e_end | Ends the set of edges. |
subgraph | The output subgraph. |
|
inlineinherited |
Return true if v is an associated height.
|
inlineinherited |
Increment the maximal height by adding k layers.
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.
|
inlineinherited |
Check that the graph has no vertex.
|
inlineinherited |
Check that u is a maximal element.
|
inlineinherited |
Check that maximal elements are the roots of the graph.
|
inlineinherited |
Check that u is a minimal element.
|
inlineinherited |
Starts the set of vertices (possibly empty) with the input height.
|
inlineinherited |
Ends the set of vertices (possibly empty) with the input height.
|
inlineinherited |
Starts the set of maximal elements.
|
inlineinherited |
Ends the set of maximal elements.
|
inlineinherited |
Starts the set of minimal elements.
|
inlineinherited |
Ends the set of minimal elements.
|
inlineinherited |
Access to the property attached to e.
|
inlineinherited |
Const access to the property attached to e.
|
inlineinherited |
Access to the property associated to a vertex.
|
inlineinherited |
Const access to the property associated to a vertex.
|
inlineinherited |
Starts the set of parents of v.
|
inlineinherited |
Ends the set of parents of v.
|
inlineinherited |
Print in the standard output stream the graph in DOT format.
|
inherited |
Print in the output stream the graph in DOT format.
|
inlineinherited |
Print in the output stream the graph in DOT format.
|
inherited |
Print in the standard output stream the graph in DOT format.
|
inlineinherited |
Remove the edge e from the graph.
|
inlineinherited |
Remove the vertex v from the graph.
It also removes v from its layer.
|
inlineinherited |
Dot graph vertex label.
|
inlineinherited |
Starts the set of vertices of the graph.
|
inlineinherited |
Ends the set of vertices of the graph.