Claw  1.7.0
Classes | Public Types | Public Member Functions
claw::graph< S, A, Comp > Class Template Reference

A class to represent a graph. More...

#include <graph.hpp>

List of all members.

Classes

class  graph_edge_iterator
 Iterator on the graph's edges. More...
class  graph_vertex_iterator
 Iterator on the graph's vertices. More...

Public Types

typedef S vertex_type
 Type of the vertices.
typedef A edge_type
 Type of the edges.
typedef Comp vertex_compare
 Binary predicate to compare vertices.
typedef std::map< vertex_type,
edge_type, vertex_compare
neighbours_list
 The adjacency list of a vertex. vertex_type is the target vertex, edge_type is the label on the edge.
typedef std::map< vertex_type,
neighbours_list,
vertex_compare
graph_content
 The whole graph: an adjacency list for each vertex.
typedef claw::graph
< vertex_type, edge_type,
vertex_compare
self_type
 Type of the current structure.
typedef graph_vertex_iterator vertex_iterator
typedef graph_edge_iterator edge_iterator
typedef std::reverse_iterator
< vertex_iterator
reverse_vertex_iterator
typedef std::reverse_iterator
< edge_iterator
reverse_edge_iterator

Public Member Functions

 graph ()
 Constructor.
void add_edge (const vertex_type &s1, const vertex_type &s2, const edge_type &e=edge_type())
 Add an edge in the graph.
void add_vertex (const vertex_type &s)
 Add a vertex.
bool edge_exists (const vertex_type &s, const vertex_type &r) const
 Check if there is an edge linking to vertices.
void neighbours (const vertex_type &s, std::vector< vertex_type > &v) const
 Get the neighbors of a vertex.
void vertices (std::vector< vertex_type > &v) const
 Get all the vertices.
vertex_iterator vertex_begin () const
 Get a node iterator on the first node.
vertex_iterator vertex_end () const
 Get a node iterator past the last node.
vertex_iterator vertex_begin (const vertex_type &s) const
 Get a node iterator on a particular node.
reverse_vertex_iterator vertex_rbegin () const
 Get a reverse node iterator on the first node.
reverse_vertex_iterator vertex_rend () const
 Get a reverse node iterator past the last node.
reverse_vertex_iterator vertex_rbegin (const vertex_type &s) const
 Get a reverse node iterator just after a particular node.
edge_iterator edge_begin () const
 Get an edge iterator on the first edge.
edge_iterator edge_end () const
 Get an edge iterator after the last edge.
edge_iterator edge_begin (const vertex_type &s1, const vertex_type &s2) const
 Get en iterator on a particular edge .
reverse_edge_iterator edge_rbegin () const
 Get a reverse edge iterator on the first edge.
reverse_edge_iterator edge_rend () const
 Get a reverse edge iterator after the last edge.
reverse_edge_iterator edge_rbegin (const vertex_type &s1, const vertex_type &s2) const
 Get a reverse edge iterator on a particular edge.
const edge_typelabel (const vertex_type &s, const vertex_type &r) const
 Get the label of an edge.
std::size_t outer_degree (const vertex_type &s) const
 Get the outter degree of a vertex.
std::size_t inner_degree (const vertex_type &s) const
 Get the inner degree of a vertex.
std::size_t vertices_count () const
 Get the number of vertices.
std::size_t edges_count () const
 Get the number of edges.

Detailed Description

template<class S, class A = meta::no_type, class Comp = std::less<S>>
class claw::graph< S, A, Comp >

A class to represent a graph.

Constraints on the template parameters:

Author:
Julien Jorge

Definition at line 77 of file graph.hpp.


Member Function Documentation

template<class S , class A , class Comp >
void claw::graph< S, A, Comp >::add_edge ( const vertex_type s1,
const vertex_type s2,
const edge_type e = edge_type() 
)

Add an edge in the graph.

Parameters:
s1Tail of the edge.
s2Head of the edgre.
eThe label on the edge.

Definition at line 499 of file graph.tpp.

template<class S , class A , class Comp >
void claw::graph< S, A, Comp >::add_vertex ( const vertex_type s)

Add a vertex.

Parameters:
sThe vertex to add.

Definition at line 522 of file graph.tpp.

template<class S , class A , class Comp >
claw::graph< S, A, Comp >::edge_iterator claw::graph< S, A, Comp >::edge_begin ( ) const

Get an edge iterator on the first edge.

Remarks:
Returns edge_end() if there's no edge in the graph.

Definition at line 671 of file graph.tpp.

template<class S , class A , class Comp >
claw::graph< S, A, Comp >::edge_iterator claw::graph< S, A, Comp >::edge_begin ( const vertex_type s1,
const vertex_type s2 
) const

Get en iterator on a particular edge .

Remarks:
Returns edge_end() if edge (s1,s2) is not found.

Definition at line 711 of file graph.tpp.

template<class S , class A , class Comp >
bool claw::graph< S, A, Comp >::edge_exists ( const vertex_type s,
const vertex_type r 
) const

Check if there is an edge linking to vertices.

Parameters:
sVertex at the tail of the edge.
rVertex at the head of the edge.

Definition at line 543 of file graph.tpp.

template<class S , class A , class Comp >
claw::graph< S, A, Comp >::reverse_edge_iterator claw::graph< S, A, Comp >::edge_rbegin ( ) const

Get a reverse edge iterator on the first edge.

Remarks:
Returns redge_end() if there's no edge in the graph.

Definition at line 732 of file graph.tpp.

template<class S , class A , class Comp >
claw::graph< S, A, Comp >::reverse_edge_iterator claw::graph< S, A, Comp >::edge_rbegin ( const vertex_type s1,
const vertex_type s2 
) const

Get a reverse edge iterator on a particular edge.

Remarks:
Returns redge_end() if edge (s1,s2) is not found.

Definition at line 756 of file graph.tpp.

template<class S , class A , class Comp >
std::size_t claw::graph< S, A, Comp >::inner_degree ( const vertex_type s) const

Get the inner degree of a vertex.

Parameters:
sThe vertex

Definition at line 816 of file graph.tpp.

template<class S , class A , class Comp >
const claw::graph< S, A, Comp >::edge_type & claw::graph< S, A, Comp >::label ( const vertex_type s,
const vertex_type r 
) const

Get the label of an edge.

Parameters:
sThe vertex at the tail of the edge.
rThe vertex at the head of the edge.

Definition at line 775 of file graph.tpp.

template<class S , class A , class Comp >
void claw::graph< S, A, Comp >::neighbours ( const vertex_type s,
std::vector< vertex_type > &  v 
) const

Get the neighbors of a vertex.

Parameters:
sThe vertex.
v(out) The neighbors.

Definition at line 561 of file graph.tpp.

template<class S , class A , class Comp >
std::size_t claw::graph< S, A, Comp >::outer_degree ( const vertex_type s) const

Get the outter degree of a vertex.

Parameters:
sThe vertex.

Definition at line 800 of file graph.tpp.

template<class S , class A , class Comp >
claw::graph< S, A, Comp >::vertex_iterator claw::graph< S, A, Comp >::vertex_begin ( ) const

Get a node iterator on the first node.

Remarks:
Returns vertex_end() if graph is empty.

Definition at line 596 of file graph.tpp.

template<class S , class A , class Comp >
claw::graph< S, A, Comp >::vertex_iterator claw::graph< S, A, Comp >::vertex_begin ( const vertex_type s) const

Get a node iterator on a particular node.

Remarks:
Returns vertex_end() if S is not found.

Definition at line 619 of file graph.tpp.

template<class S , class A , class Comp >
claw::graph< S, A, Comp >::reverse_vertex_iterator claw::graph< S, A, Comp >::vertex_rbegin ( ) const

Get a reverse node iterator on the first node.

Remarks:
Returns vertex_rend() if graph is empty.

Definition at line 631 of file graph.tpp.

template<class S , class A , class Comp >
claw::graph< S, A, Comp >::reverse_vertex_iterator claw::graph< S, A, Comp >::vertex_rbegin ( const vertex_type s) const

Get a reverse node iterator just after a particular node.

Remarks:
Returns vertex_rend() if s is not found.

Definition at line 654 of file graph.tpp.

template<class S , class A , class Comp >
void claw::graph< S, A, Comp >::vertices ( std::vector< vertex_type > &  v) const

Get all the vertices.

Parameters:
v(out) The vertices.

Definition at line 580 of file graph.tpp.


The documentation for this class was generated from the following files: