Classes | Public Types | Public Member Functions | Private Attributes

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 78 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 220 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 85 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 97 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 93 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 222 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 221 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 100 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 88 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 219 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 82 of file graph.hpp.


Constructor & Destructor Documentation

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

Constructor.

Definition at line 484 of file graph.tpp.

  : m_edges_count(0)
{

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

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.

{
  if ( !edge_exists(s1, s2) )
    {
      // s2 is not a neighbor of s1
      ++m_edges_count;

      add_vertex(s1);
      add_vertex(s2); 

      // in all cases, s2 as one more inner edge
      ++m_inner_degrees[s2]; 
    }

  m_edges[s1][s2] = e;
} // graph::add_edge()

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

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.

{
  std::pair<S, neighbours_list> p;

  if (m_edges.find(s) == m_edges.end())
    {
      // Add the vertex in the adjacency list.
      p.first = s;
      m_edges.insert(p);
      m_inner_degrees[s] = 0;
    }
} // 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

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

{
  bool ok = false;
  typename graph_content::const_iterator it_s;
  it_s = m_edges.begin();

  while ( (it_s != m_edges.end()) && !ok )
    if ( it_s->second.empty() )
      ++it_s;
    else
      ok = true;

  if (ok)
    return edge_iterator( m_edges.begin(), m_edges.end(), it_s, 
                          it_s->second.begin() );
  else
    return edge_end();
                                                 
} // graph::edge_begin()

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:
Return edge_end() if edge (s1,s2) is not found.

Definition at line 711 of file graph.tpp.

{
  if ( edge_exists(s1, s2) )
    {
      typename graph_content::const_iterator it_s1;

      it_s1 = m_edges.find(s1);
      return edge_iterator( m_edges.begin(), m_edges.end(), it_s1, 
                            it_s1->second.find(s2) );
    }
  else
    return edge_end();
} // graph::edge_()

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

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

{
  return edge_iterator( m_edges.begin(), m_edges.end(), m_edges.end(),
                        typename neighbours_list::const_iterator() );
} // 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

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.

{ 
  typename graph_content::const_iterator it = m_edges.find(s);

  if ( it == m_edges.end() )
    return false;
  else
    return it->second.find(r) != it->second.end(); 
} // 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

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.

{
  reverse_edge_iterator it = edge_begin(s1, s2);

  if ( it != edge_end() )
    ++it;

  return reverse_edge_iterator( it );
} // 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

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

{
  return reverse_edge_iterator( edge_end() );
} // 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

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

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

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

Get the number of edges.

Definition at line 843 of file graph.tpp.

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

{
  return m_edges_count; 
} // 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

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.

{ 
  typename std::map<S, std::size_t, Comp>::const_iterator it;
  it = m_inner_degrees.find(s);
  
  if (it == m_inner_degrees.end())
    throw graph_exception
      ("claw::graph::inner_degree(): unkown vertex.");
  else
    return it->second; 
} // 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

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.

{ 
  typename graph_content::const_iterator it_s = m_edges.find(s);

  if ( it_s == m_edges.end() )
    throw graph_exception
      ("claw::graph::label(): unkonwn source vertex.");
  else 
    {
      typename neighbours_list::const_iterator it_r = it_s->second.find(r);

      if ( it_r == it_s->second.end() )
        throw graph_exception
          ("claw::graph::label(): destination is not a neighbor.");
      else
        return it_r->second; 
    }
} // 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

Get the neighbors of a vertex.

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

Definition at line 561 of file graph.tpp.

{ 
  typename graph_content::const_iterator it_s = m_edges.find(s);
  v.clear();

  if ( it_s != m_edges.end() )
    {
      v.resize( it_s->second.size() );
      std::transform( it_s->second.begin(), it_s->second.end(), v.begin(),
                      const_first<S,A>() );
    }
} // graph::neighbours()

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:
s The vertex.

Definition at line 800 of file graph.tpp.

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

{ 
  typename graph_content::const_iterator it = m_edges.find(s);
  
  if (it == m_edges.end())
    throw graph_exception("claw::graph::outer_degree(): unknown vertex.");
  else
    return it->second.size(); 
} // 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

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

{
  return vertex_iterator( m_edges.begin() );
} // 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 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.

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

{
  return vertex_iterator( m_edges.find(s) );
} // 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

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

{
  return vertex_iterator( m_edges.end() );
} // 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

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

{
  return reverse_vertex_iterator( vertex_end() );
} // 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 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.

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

{
  vertex_iterator it = vertex_begin(s);

  if (it != vertex_end())
    ++it;

  return reverse_vertex_iterator( it );
} // 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

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

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

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.

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

{ 
  v.clear();
  v.resize(m_edges.size());

  std::transform( m_edges.begin(), m_edges.end(), v.begin(), 
                  const_first<S,neighbours_list>() );
} // graph::vertices()

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

Get the number of vertices.

Definition at line 833 of file graph.tpp.

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

{
  return m_edges.size(); 
} // 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 268 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 265 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: