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.

Private Attributes

graph_content m_edges
 The content of the graph (edges and vertices.
std::map< vertex_type,
std::size_t, vertex_compare
m_inner_degrees
 Inner degree of the vertices.
std::size_t m_edges_count
 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 Typedef Documentation

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

Definition at line 219 of file graph.hpp.

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

Type of the edges.

Definition at line 84 of file graph.hpp.

template<class S, class A = meta::no_type, class Comp = std::less<S>>
typedef std::map<vertex_type, neighbours_list, vertex_compare> claw::graph< S, A, Comp >::graph_content

The whole graph: an adjacency list for each vertex.

Definition at line 96 of file graph.hpp.

template<class S, class A = meta::no_type, class Comp = std::less<S>>
typedef std::map<vertex_type, edge_type, vertex_compare> claw::graph< S, A, Comp >::neighbours_list

The adjacency list of a vertex. vertex_type is the target vertex, edge_type is the label on the edge.

Definition at line 92 of file graph.hpp.

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

Definition at line 221 of file graph.hpp.

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

Definition at line 220 of file graph.hpp.

template<class S, class A = meta::no_type, class Comp = std::less<S>>
typedef claw::graph<vertex_type, edge_type, vertex_compare> claw::graph< S, A, Comp >::self_type

Type of the current structure.

Definition at line 99 of file graph.hpp.

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

Binary predicate to compare vertices.

Definition at line 87 of file graph.hpp.

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

Definition at line 218 of file graph.hpp.

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

Type of the vertices.

Definition at line 81 of file graph.hpp.


Constructor & Destructor Documentation

template<class S , class A , class Comp >
claw::graph< S, A, Comp >::graph (  )  [inline]

Constructor.

Definition at line 484 of file graph.tpp.

00485   : m_edges_count(0)
00486 {
00487 
00488 } // graph::graph() [constructor]


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() 
) [inline]

Add an edge in the graph.

Parameters:
s1 Tail of the edge.
s2 Head of the edgre.
e The label on the edge.

Definition at line 499 of file graph.tpp.

00500 {
00501   if ( !edge_exists(s1, s2) )
00502     {
00503       // s2 is not a neighbor of s1
00504       ++m_edges_count;
00505 
00506       add_vertex(s1);
00507       add_vertex(s2); 
00508 
00509       // in all cases, s2 as one more inner edge
00510       ++m_inner_degrees[s2]; 
00511     }
00512 
00513   m_edges[s1][s2] = e;
00514 } // graph::add_edge()

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

Add a vertex.

Parameters:
s The vertex to add.

Definition at line 522 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges, and claw::graph< S, A, Comp >::m_inner_degrees.

00523 {
00524   std::pair<S, neighbours_list> p;
00525 
00526   if (m_edges.find(s) == m_edges.end())
00527     {
00528       // Add the vertex in the adjacency list.
00529       p.first = s;
00530       m_edges.insert(p);
00531       m_inner_degrees[s] = 0;
00532     }
00533 } // graph::add_vertex()

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 [inline]

Get en iterator on a particular edge .

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

Definition at line 711 of file graph.tpp.

00712 {
00713   if ( edge_exists(s1, s2) )
00714     {
00715       typename graph_content::const_iterator it_s1;
00716 
00717       it_s1 = m_edges.find(s1);
00718       return edge_iterator( m_edges.begin(), m_edges.end(), it_s1, 
00719                             it_s1->second.find(s2) );
00720     }
00721   else
00722     return edge_end();
00723 } // graph::edge_()

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

Get an edge iterator on the first edge.

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

Definition at line 671 of file graph.tpp.

References claw::graph< S, A, Comp >::edge_end(), and claw::graph< S, A, Comp >::m_edges.

Referenced by claw::graph< S, A, Comp >::edge_rend().

00672 {
00673   bool ok = false;
00674   typename graph_content::const_iterator it_s;
00675   it_s = m_edges.begin();
00676 
00677   while ( (it_s != m_edges.end()) && !ok )
00678     if ( it_s->second.empty() )
00679       ++it_s;
00680     else
00681       ok = true;
00682 
00683   if (ok)
00684     return edge_iterator( m_edges.begin(), m_edges.end(), it_s, 
00685                           it_s->second.begin() );
00686   else
00687     return edge_end();
00688                                                  
00689 } // graph::edge_begin()

template<class S , class A , class Comp >
claw::graph< S, A, Comp >::edge_iterator claw::graph< S, A, Comp >::edge_end (  )  const [inline]

Get an edge iterator after the last edge.

Definition at line 697 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges.

Referenced by claw::graph< S, A, Comp >::edge_begin(), and claw::graph< S, A, Comp >::edge_rbegin().

00698 {
00699   return edge_iterator( m_edges.begin(), m_edges.end(), m_edges.end(),
00700                         typename neighbours_list::const_iterator() );
00701 } // graph::edge_end()

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

Check if there is an edge linking to vertices.

Parameters:
s Vertex at the tail of the edge.
r Vertex at the head of the edge.

Definition at line 543 of file graph.tpp.

00544 { 
00545   typename graph_content::const_iterator it = m_edges.find(s);
00546 
00547   if ( it == m_edges.end() )
00548     return false;
00549   else
00550     return it->second.find(r) != it->second.end(); 
00551 } // graph::edge_exists()

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 [inline]

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.

00757 {
00758   reverse_edge_iterator it = edge_begin(s1, s2);
00759 
00760   if ( it != edge_end() )
00761     ++it;
00762 
00763   return reverse_edge_iterator( it );
00764 } // graph::edge_rbegin()

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

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.

References claw::graph< S, A, Comp >::edge_end().

00733 {
00734   return reverse_edge_iterator( edge_end() );
00735 } // graph::edge_rbegin()

template<class S , class A , class Comp >
claw::graph< S, A, Comp >::reverse_edge_iterator claw::graph< S, A, Comp >::edge_rend (  )  const [inline]

Get a reverse edge iterator after the last edge.

Definition at line 743 of file graph.tpp.

References claw::graph< S, A, Comp >::edge_begin().

00744 {
00745   return reverse_edge_iterator( edge_begin() );
00746 } // graph::edge_rend()

template<class S , class A , class Comp >
std::size_t claw::graph< S, A, Comp >::edges_count (  )  const [inline]

Get the number of edges.

Definition at line 843 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges_count.

00844 {
00845   return m_edges_count; 
00846 } // graph::edges_count()

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

Get the inner degree of a vertex.

Parameters:
s The vertex

Definition at line 816 of file graph.tpp.

References claw::graph< S, A, Comp >::m_inner_degrees.

00817 { 
00818   typename std::map<S, std::size_t, Comp>::const_iterator it;
00819   it = m_inner_degrees.find(s);
00820   
00821   if (it == m_inner_degrees.end())
00822     throw graph_exception
00823       ("claw::graph::inner_degree(): unkown vertex.");
00824   else
00825     return it->second; 
00826 } // graph::inner_degree()

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 [inline]

Get the label of an edge.

Parameters:
s The vertex at the tail of the edge.
r The vertex at the head of the edge.

Definition at line 775 of file graph.tpp.

00776 { 
00777   typename graph_content::const_iterator it_s = m_edges.find(s);
00778 
00779   if ( it_s == m_edges.end() )
00780     throw graph_exception
00781       ("claw::graph::label(): unkonwn source vertex.");
00782   else 
00783     {
00784       typename neighbours_list::const_iterator it_r = it_s->second.find(r);
00785 
00786       if ( it_r == it_s->second.end() )
00787         throw graph_exception
00788           ("claw::graph::label(): destination is not a neighbor.");
00789       else
00790         return it_r->second; 
00791     }
00792 } // graph::label()

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

Get the neighbors of a vertex.

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

Definition at line 561 of file graph.tpp.

00562 { 
00563   typename graph_content::const_iterator it_s = m_edges.find(s);
00564   v.clear();
00565 
00566   if ( it_s != m_edges.end() )
00567     {
00568       v.resize( it_s->second.size() );
00569       std::transform( it_s->second.begin(), it_s->second.end(), v.begin(),
00570                       const_first<S,A>() );
00571     }
00572 } // graph::neighbours()

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

Get the outter degree of a vertex.

Parameters:
s The vertex.

Definition at line 800 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges.

00801 { 
00802   typename graph_content::const_iterator it = m_edges.find(s);
00803   
00804   if (it == m_edges.end())
00805     throw graph_exception("claw::graph::outer_degree(): unknown vertex.");
00806   else
00807     return it->second.size(); 
00808 } // graph::outer_degree()

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 [inline]

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.

References claw::graph< S, A, Comp >::m_edges.

00620 {
00621   return vertex_iterator( m_edges.find(s) );
00622 } // graph::vertex_begin()

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

Get a node iterator on the first node.

Remarks:
Returns vertex_end() if graph is empty.

Definition at line 596 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges.

Referenced by claw::graph< S, A, Comp >::vertex_rbegin(), and claw::graph< S, A, Comp >::vertex_rend().

00597 {
00598   return vertex_iterator( m_edges.begin() );
00599 } // graph::vertex_begin()

template<class S , class A , class Comp >
claw::graph< S, A, Comp >::vertex_iterator claw::graph< S, A, Comp >::vertex_end (  )  const [inline]

Get a node iterator past the last node.

Definition at line 607 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges.

Referenced by claw::graph< S, A, Comp >::vertex_rbegin().

00608 {
00609   return vertex_iterator( m_edges.end() );
00610 } // graph::vertex_end()

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 [inline]

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.

References claw::graph< S, A, Comp >::vertex_begin(), and claw::graph< S, A, Comp >::vertex_end().

00655 {
00656   vertex_iterator it = vertex_begin(s);
00657 
00658   if (it != vertex_end())
00659     ++it;
00660 
00661   return reverse_vertex_iterator( it );
00662 } // graph::vertex_rbegin()

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

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.

References claw::graph< S, A, Comp >::vertex_end().

00632 {
00633   return reverse_vertex_iterator( vertex_end() );
00634 } // graph::vertex_rbegin()

template<class S , class A , class Comp >
claw::graph< S, A, Comp >::reverse_vertex_iterator claw::graph< S, A, Comp >::vertex_rend (  )  const [inline]

Get a reverse node iterator past the last node.

Definition at line 642 of file graph.tpp.

References claw::graph< S, A, Comp >::vertex_begin().

00643 {
00644   return reverse_vertex_iterator( vertex_begin() );
00645 } // graph::vertex_rend()

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

Get all the vertices.

Parameters:
v (out) The vertices.

Definition at line 580 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges.

00581 { 
00582   v.clear();
00583   v.resize(m_edges.size());
00584 
00585   std::transform( m_edges.begin(), m_edges.end(), v.begin(), 
00586                   const_first<S,neighbours_list>() );
00587 } // graph::vertices()

template<class S , class A , class Comp >
std::size_t claw::graph< S, A, Comp >::vertices_count (  )  const [inline]

Get the number of vertices.

Definition at line 833 of file graph.tpp.

References claw::graph< S, A, Comp >::m_edges.

00834 {
00835   return m_edges.size(); 
00836 } // graph::vertices_count()


Member Data Documentation

template<class S, class A = meta::no_type, class Comp = std::less<S>>
graph_content claw::graph< S, A, Comp >::m_edges [private]
template<class S, class A = meta::no_type, class Comp = std::less<S>>
std::size_t claw::graph< S, A, Comp >::m_edges_count [private]

Number of edges.

Definition at line 267 of file graph.hpp.

Referenced by claw::graph< S, A, Comp >::edges_count().

template<class S, class A = meta::no_type, class Comp = std::less<S>>
std::map<vertex_type, std::size_t, vertex_compare> claw::graph< S, A, Comp >::m_inner_degrees [private]

Inner degree of the vertices.

Definition at line 264 of file graph.hpp.

Referenced by claw::graph< S, A, Comp >::add_vertex(), and claw::graph< S, A, Comp >::inner_degree().


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

Generated on 9 Nov 2009 for CLAW Library (a C++ Library Absolutely Wonderful) by  doxygen 1.6.1