30 #ifndef __CLAW_GRAPH_HPP__
31 #define __CLAW_GRAPH_HPP__
59 virtual const char*
what()
const throw();
63 const std::string m_msg;
78 template <
class S,
class A = meta::no_type,
class Comp = std::less<S> >
97 typedef std::map<vertex_type, neighbours_list, vertex_compare>
108 friend class graph<vertex_type, edge_type, vertex_compare>;
111 typedef const vertex_type value_type;
112 typedef const vertex_type& reference;
113 typedef const vertex_type*
const pointer;
114 typedef ptrdiff_t difference_type;
116 typedef std::bidirectional_iterator_tag iterator_category;
136 typename graph_content::const_iterator m_iterator;
146 friend class graph<vertex_type, edge_type, vertex_compare>;
159 const edge_type&
label()
const;
160 const vertex_type&
source()
const;
161 const vertex_type&
target()
const;
164 void set(
const edge_type& l,
const vertex_type& s,
165 const vertex_type& t );
168 edge_type
const* m_label;
169 vertex_type
const* m_source;
170 vertex_type
const* m_target;
176 typedef const edge*
const pointer;
177 typedef ptrdiff_t difference_type;
179 typedef std::bidirectional_iterator_tag iterator_category;
196 typename graph_content::const_iterator it_end,
197 typename graph_content::const_iterator it_s,
198 typename neighbours_list::const_iterator it_d );
202 typename graph_content::const_iterator m_vertex_begin;
205 typename graph_content::const_iterator m_vertex_end;
208 typename graph_content::const_iterator m_vertex_iterator;
211 typename neighbours_list::const_iterator m_neighbours_iterator;
222 typedef std::reverse_iterator<vertex_iterator> reverse_vertex_iterator;
223 typedef std::reverse_iterator<edge_iterator> reverse_edge_iterator;
234 void vertices( std::vector<vertex_type>& v )
const;
266 std::map<vertex_type, std::size_t, vertex_compare> m_inner_degrees;
269 std::size_t m_edges_count;
277 #endif // __CLAW_GRAPH_HPP__
virtual ~graph_exception()
Destructor.
bool operator==(const graph_vertex_iterator &it) const
Equality.
pointer operator->() const
Pointer.
Iterator on the graph's edges.
S vertex_type
Type of the vertices.
void vertices(std::vector< vertex_type > &v) const
Get all the vertices.
const edge_type & label() const
Gets edge's label.
reverse_vertex_iterator vertex_rend() const
Get a reverse node iterator past the last node.
A edge_type
Type of the edges.
Implementation of the claw::graph class.
Value pointed by the iterator.
void add_vertex(const vertex_type &s)
Add a vertex.
reverse_edge_iterator edge_rend() const
Get a reverse edge iterator after the last edge.
edge_iterator edge_begin() const
Get an edge iterator on the first edge.
reference operator*() const
Reference.
Comp vertex_compare
Binary predicate to compare vertices.
bool edge_exists(const vertex_type &s, const vertex_type &r) const
Check if there is an edge linking to vertices.
Iterator on the graph's vertices.
std::size_t inner_degree(const vertex_type &s) const
Get the inner degree of a vertex.
std::size_t edges_count() const
Get the number of edges.
graph_vertex_iterator & operator++()
Preincrement.
graph_vertex_iterator & operator--()
Predecrement.
std::size_t vertices_count() const
Get the number of vertices.
std::size_t outer_degree(const vertex_type &s) const
Get the outter degree of a vertex.
const vertex_type & target() const
Gets edge's target.
graph_edge_iterator & operator++()
Preincrement.
void neighbours(const vertex_type &s, std::vector< vertex_type > &v) const
Get the neighbors of a vertex.
bool operator==(const graph_edge_iterator &it) const
Equality.
edge_iterator edge_end() const
Get an edge iterator after the last edge.
std::map< vertex_type, neighbours_list, vertex_compare > graph_content
The whole graph: an adjacency list for each vertex.
reverse_vertex_iterator vertex_rbegin() const
Get a reverse node iterator on the first node.
reverse_edge_iterator edge_rbegin() const
Get a reverse edge iterator on the first edge.
pointer operator->() const
Reference.
bool operator!=(const graph_edge_iterator &it) const
Difference.
An empty class not considered as a effective type.
bool operator!=(const graph_vertex_iterator &it) const
Difference.
claw::graph< vertex_type, edge_type, vertex_compare > self_type
Type of the current structure.
The exceptions thrown by the graphs.
graph_edge_iterator & operator--()
Predecrement.
graph_vertex_iterator()
Constructor of the graph_vertex_iterator class.
const edge_type & label(const vertex_type &s, const vertex_type &r) const
Get the label of an edge.
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...
A class to represent a graph.
vertex_iterator vertex_begin() const
Get a node iterator on the first node.
const vertex_type & source() const
Gets edge's source.
graph_exception()
Default constructor.
vertex_iterator vertex_end() const
Get a node iterator past the last node.
graph_edge_iterator()
Constructor of the graph_edge_iterator class.
virtual const char * what() const
Get an explanation of the problem.
void add_edge(const vertex_type &s1, const vertex_type &s2, const edge_type &e=edge_type())
Add an edge in the graph.
reference operator*() const
Dereference.