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_type &	label (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:

• S is LessThanComparable,
• A is any Assignable and Default Constructible,
• Comp is a binary predicate such that Comp(S a, S b) == true if and only if a < b.

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.

{
  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:

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

Definition at line 671 of file graph.tpp.

{
  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:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

{
  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]

The content of the graph (edges and vertices.

Definition at line 262 of file graph.hpp.

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.

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.

---

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

• graph.hpp
• impl/graph.tpp