claw::graph< S, A, Comp > Class Template Reference

A class to represent a graph. More...

#include <graph.hpp>

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.

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

s1	Tail of the edge.
s2	Head of the edgre.
e	The 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

s	The 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

s	Vertex at the tail of the edge.
r	Vertex 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

s	The 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

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.

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.

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.

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:

• graph.hpp
• impl/graph.tpp