Structural Bioinformatics Library
Template C++ / Python API for developping structural bioinformatics applications.
T_Directed_acyclic_graph< VertexProperty, EdgeProperty > Class Template Reference

Generic representation of a directed acyclic graph. More...

#include <Directed_acyclic_graph.hpp>

Classes

class  Get_child_from_edge
 
class  Get_parent_from_edge
 
class  Is_maximal_element
 
class  Is_minimal_element
 

Public Types

enum  Orientation_type { MAXIMAL_ROOT_ORIENTATION , MINIMAL_ROOT_ORIENTATION }
 Orientation of the edges in the Directed Acyclic Graph. More...
 
typedef T_Directed_acyclic_graph< VertexProperty, EdgeProperty > Self
 
typedef boost::adjacency_list< boost::listS, boost::listS, boost::bidirectionalS, VertexProperty, EdgeProperty > Graph
 Representation of the Directed Acyclic Graph as a adjacency_list of the Boost Graph Library. More...
 
typedef Graph_traits::vertex_descriptor Vertex
 Representation of a Vertex of the Directed Acyclic Graph. More...
 
typedef Graph_traits::edge_descriptor Edge
 Representation of an Edge of the Directed Acyclic Graph. More...
 
typedef Graph_traits::vertex_iterator Vertices_iterator
 Iterator over all the vertices of the Directed Acyclic Graph. More...
 
typedef Graph_traits::edge_iterator Edges_iterator
 Iterator over all the edges of the Directed Acyclic Graph. More...
 
typedef boost::transform_iterator< Get_parent_from_edge, In_edges_iterator > Parents_iterator
 Iterator over all the parents of a given Vertex. More...
 
typedef boost::transform_iterator< Get_child_from_edge, Out_edges_iterator > Children_iterator
 Iterator over all the children of a given Vertex. 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...
 

Constructors

 T_Directed_acyclic_graph (Orientation_type orientation=MAXIMAL_ROOT_ORIENTATION)
 Default constructor creating an empty Directed Acyclic Graph. More...
 

Graph

const Graphget_graph (void) const
 Const Access to the BGL graph. More...
 
Graphget_graph (void)
 Acces to the BGL graph. More...
 
void clear (void)
 

Vertices

unsigned get_number_of_vertices (void) const
 Access to the number of vertices in the graph. More...
 
VertexProperty & operator[] (Vertex v)
 Access to the property associated to a vertex. More...
 
const VertexProperty & 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...
 
template<class Comparator , class DataType , class OutputIterator >
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...
 
template<class Comparator , class DataType >
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...
 
Vertex add_vertex (void)
 Add a vertex with no property to the graph. More...
 
Vertex add_vertex (const VertexProperty &p)
 Add a vertex with the property p to the graph. More...
 
void remove_vertex (Vertex v)
 Remove the vertex v from the graph. 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...
 

Edges

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
 
EdgeProperty & operator[] (Edge e)
 Access to the property attached to e. More...
 
const EdgeProperty & 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 EdgeProperty &p)
 Add an edge from u to v, with the property p. More...
 
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

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...
 
bool is_ancestor (Vertex u, Vertex v) const
 Check that u is an ancestor 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...
 

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

Partial Order Set Builder

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

Subgraph Manipulators

template<class InputIterator , class OutputIterator >
OutputIterator get_induced_subgraph (InputIterator begin, InputIterator end, OutputIterator out) const
 Construct the induced subgraph from the range of vertices in [begin, end). More...
 
template<class OutputIterator >
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...
 
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

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

Detailed Description

template<class VertexProperty = Directed_acyclic_graph_default_property, class EdgeProperty = Directed_acyclic_graph_default_property>
class SBL::CADS::T_Directed_acyclic_graph< VertexProperty, EdgeProperty >

Generic representation of a directed acyclic graph.

It implements a bidirectional adjacency_list from the Boost Graph Library that uses lists for storing the vertices and the out-going edges. The T_Directed_acyclic_graph class provides:

  • manipulators for the vertices,
  • manipulators for the edges,
  • manipulators for the children or parents of given vertices,
  • manipulators for the minimal and maximal elements,
  • constructions for partially ordered set,
  • subgraphs manipulators.
Template Parameters
VertexPropertyInformation attached to the vertices (default is Directed_acyclic_graph_default_property).
EdgePropertyInformation attached to the edges (default is Directed_acyclic_graph_default_property).

Member Typedef Documentation

◆ Children_iterator

typedef boost::transform_iterator<Get_child_from_edge, Out_edges_iterator> Children_iterator

Iterator over all the children of a given Vertex.

◆ Edge

typedef Graph_traits::edge_descriptor Edge

Representation of an Edge of the Directed Acyclic Graph.

◆ Edges_iterator

typedef Graph_traits::edge_iterator Edges_iterator

Iterator over all the edges of the Directed Acyclic Graph.

◆ Graph

typedef boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, VertexProperty, EdgeProperty> Graph

Representation of the Directed Acyclic Graph as a adjacency_list of the Boost Graph Library.

Note that the containers for vertices and out edges are both lists for supoprting the removal.

◆ Maximal_elements_iterator

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

◆ Minimal_elements_iterator

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

◆ Parents_iterator

typedef boost::transform_iterator<Get_parent_from_edge, In_edges_iterator> Parents_iterator

Iterator over all the parents of a given Vertex.

◆ Self

typedef T_Directed_acyclic_graph<VertexProperty, EdgeProperty> Self

◆ Vertex

typedef Graph_traits::vertex_descriptor Vertex

Representation of a Vertex of the Directed Acyclic Graph.

◆ Vertices_iterator

typedef Graph_traits::vertex_iterator Vertices_iterator

Iterator over all the vertices of the Directed Acyclic Graph.

Member Enumeration Documentation

◆ 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.
Enumerator
MAXIMAL_ROOT_ORIENTATION 
MINIMAL_ROOT_ORIENTATION 

Constructor & Destructor Documentation

◆ T_Directed_acyclic_graph()

Default constructor creating an empty Directed Acyclic Graph.

Parameters
orientationdefines the orientation of the edges.

Member Function Documentation

◆ add_edge() [1/2]

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Edge add_edge ( Vertex  u,
Vertex  v 
)
inline

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

Precondition
The edge (u,v) does not exist.
Adding the edge (u,v) do not make any cycle in the graph.

◆ add_edge() [2/2]

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Edge add_edge ( Vertex  u,
Vertex  v,
const EdgeProperty &  p 
)
inline

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

Precondition
The edge (u,v) does not exist.
Adding the edge (u,v) do not make any cycle in the graph.

◆ add_vertex() [1/2]

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

Add a vertex with the property p to the graph.

◆ add_vertex() [2/2]

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Vertex add_vertex ( void  )
inline

Add a vertex with no property to the graph.

◆ build_from_partially_ordered_set()

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

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

The input order predicate is used as a partial order. Each element of the set is represented by a vertex in the Directed Acyclic Graph. There is an edge from a vertex u to a vertex v if v is compared less than u with the partial order, and if there is no other vertex w such that v is less than w and w is less than u. Note that each element has to be unique (i.e multiplicity is not allowed).

Parameters
beginStarts the set of elements of the partially ordered set.
endEnds the set of elements of the partially ordered set.
orderFunctor representing a partial ordering over the elements in [begin, end).

◆ children_begin()

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Children_iterator children_begin ( Vertex  v) const
inline

Starts the set of children of v.

◆ children_end()

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Children_iterator children_end ( Vertex  v) const
inline

Ends the set of children of v.

◆ clear()

void clear ( void  )
inline

◆ clear_children()

void clear_children ( Vertex  v)
inline

Remove all out-going edges incident to v.

◆ clear_parents()

void clear_parents ( Vertex  v)
inline

Remove all in-going edges incident to v.

◆ clear_vertex()

void clear_vertex ( Vertex  v)
inline

Remove all edges incident to v.

◆ edges_begin()

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Edges_iterator edges_begin ( void  ) const
inline

Starts the set of edges.

◆ edges_end()

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Edges_iterator edges_end ( void  ) const
inline

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
inline

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
inline

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()

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Vertex get_child ( Edge  e) const
inline

Access to the target of e.

◆ get_descendant_ancestor_subgraph()

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

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< VertexProperty, EdgeProperty >::Edge get_edge ( Vertex  u,
Vertex  v 
) const
inline

Access to the Edge u -> v.

Precondition
u is a parent of v.

◆ get_edge_subgraph()

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

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  )
inline

Acces to the BGL graph.

◆ get_graph() [2/2]

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

Const Access to the BGL graph.

◆ get_induced_subgraph()

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

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
inline

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

◆ get_minimal_elements_from()

OutputIterator get_minimal_elements_from ( Vertex  v,
OutputIterator  out 
) const
inline

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

◆ get_number_of_children()

unsigned get_number_of_children ( Vertex  v) const
inline

Access to the number of children of v.

◆ get_number_of_edges()

unsigned get_number_of_edges ( void  ) const
inline

Access to the number of edges in the graph.

◆ get_number_of_parents()

unsigned get_number_of_parents ( Vertex  v) const
inline

Access to the number of parents of v.

◆ get_number_of_vertices()

unsigned get_number_of_vertices ( void  ) const
inline

Access to the number of vertices in the graph.

◆ get_orientation() [1/2]

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

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
inline

Return the orientation of the DAG.

◆ get_parent()

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Vertex get_parent ( Edge  e) const
inline

Access to the source of e.

◆ get_subgraph()

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

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.

◆ is_ancestor()

bool is_ancestor ( Vertex  u,
Vertex  v 
) const
inline

Check that u is an ancestor of v.

◆ is_empty()

bool is_empty ( void  ) const
inline

Check that the graph has no vertex.

◆ is_lower()

bool is_lower ( Vertex  u,
Vertex  v 
) const
inline

Check that u is lower than v.

◆ is_maximal_element()

bool is_maximal_element ( Vertex  u) const
inline

Check that u is a maximal element.

◆ is_maximal_root_oriented()

bool is_maximal_root_oriented ( void  ) const
inline

Check that maximal elements are the roots of the graph.

◆ is_minimal_element()

bool is_minimal_element ( Vertex  u) const
inline

Check that u is a minimal element.

◆ is_parent()

bool is_parent ( Vertex  u,
Vertex  v 
) const
inline

Check that u is a parent of v.

◆ maximal_elements_begin()

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

Starts the set of maximal elements.

◆ maximal_elements_end()

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

Ends the set of maximal elements.

◆ minimal_elements_begin()

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

Starts the set of minimal elements.

◆ minimal_elements_end()

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

Ends the set of minimal elements.

◆ operator[]() [1/4]

EdgeProperty & operator[] ( Edge  e)
inline

Access to the property attached to e.

◆ operator[]() [2/4]

const EdgeProperty & operator[] ( Edge  e) const
inline

Const access to the property attached to e.

◆ operator[]() [3/4]

VertexProperty & operator[] ( Vertex  v)
inline

Access to the property associated to a vertex.

◆ operator[]() [4/4]

const VertexProperty & operator[] ( Vertex  v) const
inline

Const access to the property associated to a vertex.

◆ parents_begin()

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Parents_iterator parents_begin ( Vertex  v) const
inline

Starts the set of parents of v.

◆ parents_end()

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Parents_iterator parents_end ( Vertex  v) const
inline

Ends the set of parents of v.

◆ print_in_dot_format() [1/2]

void print_in_dot_format ( OutputStream &  out) const

Print in the output stream the graph in DOT format.

◆ print_in_dot_format() [2/2]

void print_in_dot_format ( void  ) const

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

◆ remove_edge() [1/2]

void remove_edge ( Edge  e)
inline

Remove the edge e from the graph.

◆ remove_edge() [2/2]

void remove_edge ( Vertex  u,
Vertex  v 
)
inline

Remove the edge from u to v.

◆ remove_vertex()

void remove_vertex ( Vertex  v)
inline

Remove the vertex v from the graph.

Precondition
There is no incident edge to v.

◆ vertices_begin()

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Vertices_iterator vertices_begin ( void  ) const
inline

Starts the set of vertices of the graph.

◆ vertices_end()

T_Directed_acyclic_graph< VertexProperty, EdgeProperty >::Vertices_iterator vertices_end ( void  ) const
inline

Ends the set of vertices of the graph.