mln::util::graph Class Reference
[Graphes]

Undirected graph. More...

#include <graph.hh>

Inherits graph_base< graph >.

List of all members.

Public Types
typedef std::set< edge_data_t >	edges_set_t
	A set to test the presence of a given edge.
typedef std::vector< edge_data_t >	edges_t
	The type of the set of edges.
typedef std::vector < vertex_data_t >	vertices_t
	The type of the set of vertices.
typedef mln::internal::edge_fwd_iterator < graph >	edge_fwd_iter
	Edge iterators.
typedef mln::internal::edge_nbh_edge_fwd_iterator < graph >	edge_nbh_edge_fwd_iter
	Edge centered edge iterators.
typedef mln::internal::vertex_fwd_iterator < graph >	vertex_fwd_iter
	Iterator types Vertex iterators.
typedef mln::internal::vertex_nbh_edge_fwd_iterator < graph >	vertex_nbh_edge_fwd_iter
	Vertex centered edge iterators.
typedef mln::internal::vertex_nbh_vertex_fwd_iterator < graph >	vertex_nbh_vertex_fwd_iter
	Vertex centered vertex iterators.
Public Member Functions
	graph (unsigned nvertices)
	Construct a graph with nvertices vertices.
	graph ()
bool	has_v (const vertex_id_t &id_v) const
	Check whether a vertex id id_v exists in the graph.
void	invalidate ()
	Invalidate the graph.
bool	is_valid () const
	Return true if this graph is valid.
edge_id_t	v_ith_nbh_edge (const vertex_id_t &id_v, unsigned i) const
	Returns the i th edge adjacent to the vertex id_v.
vertex_id_t	v_ith_nbh_vertex (const vertex_id_t &id_v, unsigned i) const
	Returns the i th vertex adjacent to the vertex id_v.
size_t	v_nmax () const
	Return the number of vertices in the graph.
size_t	v_nmax_nbh_edges (const vertex_id_t &id_v) const
	Return the number of adjacent edges of vertex id_v.
size_t	v_nmax_nbh_vertices (const vertex_id_t &id_v) const
	Return the number of adjacent vertices of vertex id_v.
edge_id_t	add_edge (const vertex_id_t &id_v1, const vertex_id_t &id_v2)
	Edge oriented.
edge_id_t	e_ith_nbh_edge (const edge_id_t &id_e, unsigned i) const
	Return the i th edge adjacent to the edge id_e.
size_t	e_nmax () const
	Return the number of edges in the graph.
size_t	e_nmax_nbh_edges (const edge_id_t &id_e) const
	Return the number max of adjacent edge, given an edge id_e.
edge_t	edge (const vertex_t &v1, const vertex_t &v2) const
	@}
edge_t	edge (const edge_id_t &e) const
	Return the edge whose id is e.
const std::vector < util::ord_pair< vertex_id_t > > &	edges () const
	Return the list of all edges.
bool	has_e (const edge_id_t &id_e) const
	Return whether id_e is in the graph.
template<typename G2 >
bool	is_subgraph_of (const G2 &g) const
	Return whether this graph is a subgraph Return true if g and *this have the same graph_id.
vertex_id_t	v1 (const edge_id_t &id_e) const
	Return the first vertex associated to the edge id_e.
vertex_id_t	v2 (const edge_id_t &id_e) const
	Return the second vertex associated to edge id_e.
unsigned	add_vertex ()
	Vertex oriented.
std::pair< vertex_id_t, vertex_id_t >	add_vertices (unsigned n)
	Add n vertices to the graph.
vertex_t	vertex (vertex_id_t id_v) const
	Return the vertex whose id is v.

---

Detailed Description

Undirected graph.

---

Member Typedef Documentation

typedef mln::internal::edge_fwd_iterator<graph> mln::util::graph::edge_fwd_iter

Edge iterators.

typedef mln::internal::edge_nbh_edge_fwd_iterator<graph> mln::util::graph::edge_nbh_edge_fwd_iter

Edge centered edge iterators.

typedef std::set<edge_data_t> mln::util::graph::edges_set_t

A set to test the presence of a given edge.

typedef std::vector<edge_data_t> mln::util::graph::edges_t

The type of the set of edges.

typedef mln::internal::vertex_fwd_iterator<graph> mln::util::graph::vertex_fwd_iter

Iterator types

Vertex iterators.

typedef mln::internal::vertex_nbh_edge_fwd_iterator<graph> mln::util::graph::vertex_nbh_edge_fwd_iter

Vertex centered edge iterators.

typedef mln::internal::vertex_nbh_vertex_fwd_iterator<graph> mln::util::graph::vertex_nbh_vertex_fwd_iter

Vertex centered vertex iterators.

typedef std::vector<vertex_data_t> mln::util::graph::vertices_t

The type of the set of vertices.

---

Constructor & Destructor Documentation

mln::util::graph::graph

(

)

[inline]

Constructor.

mln::util::graph::graph

(

unsigned

nvertices

)

[inline]

Construct a graph with nvertices vertices.

---

Member Function Documentation

edge_id_t mln::util::graph::add_edge	(	const vertex_id_t &	id_v1,
		const vertex_id_t &	id_v2
	)			[inline]

Edge oriented.

Add an edge.

Returns:

The id of the new edge if it does not exist yet; otherwise, return mln_max(unsigned).

References edge(), and has_v().

Referenced by mln::make::voronoi().

unsigned mln::util::graph::add_vertex

(

)

[inline]

Vertex oriented.

Shortcuts factoring the insertion of vertices and edges. Add a vertex.

Returns:

The id of the new vertex.

References v_nmax().

Referenced by mln::make::voronoi().

std::pair< vertex_id_t, vertex_id_t > mln::util::graph::add_vertices

(

unsigned

n

)

[inline]

Add n vertices to the graph.

Returns:

A range of vertex ids.

References v_nmax().

edge_id_t mln::util::graph::e_ith_nbh_edge	(	const edge_id_t &	id_e,
		unsigned	i
	)			const [inline]

Return the i th edge adjacent to the edge id_e.

References e_nmax(), e_nmax_nbh_edges(), has_e(), v1(), v2(), v_ith_nbh_edge(), and v_nmax_nbh_edges().

size_t mln::util::graph::e_nmax

(

)

const [inline]

Return the number of edges in the graph.

Referenced by e_ith_nbh_edge(), and edge().

size_t mln::util::graph::e_nmax_nbh_edges

(

const edge_id_t &

id_e

)

const [inline]

Return the number max of adjacent edge, given an edge id_e.

References has_e(), v1(), v2(), and v_nmax_nbh_edges().

Referenced by e_ith_nbh_edge().

graph::edge_t mln::util::graph::edge	(	const vertex_t &	v1,
		const vertex_t &	v2
	)			const [inline]

@}

Return the corresponding edge id if exists. If it is not, returns an invalid edge.

References has_v().

graph::edge_t mln::util::graph::edge

(

const edge_id_t &

e

)

const [inline]

Return the edge whose id is e.

References e_nmax().

Referenced by add_edge().

const std::vector< util::ord_pair< vertex_id_t > > & mln::util::graph::edges

(

)

const [inline]

Return the list of all edges.

bool mln::util::graph::has_e

(

const edge_id_t &

id_e

)

const [inline]

Return whether id_e is in the graph.

@{

Referenced by e_ith_nbh_edge(), e_nmax_nbh_edges(), v1(), and v2().

bool mln::util::graph::has_v

(

const vertex_id_t &

id_v

)

const [inline]

Check whether a vertex id id_v exists in the graph.

Referenced by add_edge(), edge(), v_ith_nbh_edge(), v_ith_nbh_vertex(), v_nmax_nbh_edges(), v_nmax_nbh_vertices(), and vertex().

void mln::Graph< graph >::invalidate

(

)

[inherited]

Invalidate the graph.

FIXME: does nothing!

template<typename G2 >

bool mln::util::graph::is_subgraph_of

(

const G2 &

g

)

const [inline]

Return whether this graph is a subgraph Return true if g and *this have the same graph_id.

bool mln::Graph< graph >::is_valid

(

)

const [inherited]

Return true if this graph is valid.

FIXME: currently it always returns true.

vertex_id_t mln::util::graph::v1

(

const edge_id_t &

id_e

)

const [inline]

Return the first vertex associated to the edge id_e.

References has_e().

Referenced by e_ith_nbh_edge(), and e_nmax_nbh_edges().

vertex_id_t mln::util::graph::v2

(

const edge_id_t &

id_e

)

const [inline]

Return the second vertex associated to edge id_e.

References has_e().

Referenced by e_ith_nbh_edge(), and e_nmax_nbh_edges().

edge_id_t mln::util::graph::v_ith_nbh_edge	(	const vertex_id_t &	id_v,
		unsigned	i
	)			const [inline]

Returns the i th edge adjacent to the vertex id_v.

References has_v(), and v_nmax_nbh_edges().

Referenced by e_ith_nbh_edge(), and v_ith_nbh_vertex().

vertex_id_t mln::util::graph::v_ith_nbh_vertex	(	const vertex_id_t &	id_v,
		unsigned	i
	)			const [inline]

Returns the i th vertex adjacent to the vertex id_v.

References has_v(), and v_ith_nbh_edge().

size_t mln::util::graph::v_nmax

(

)

const [inline]

Return the number of vertices in the graph.

Referenced by add_vertex(), and add_vertices().

size_t mln::util::graph::v_nmax_nbh_edges

(

const vertex_id_t &

id_v

)

const [inline]

Return the number of adjacent edges of vertex id_v.

References has_v().

Referenced by e_ith_nbh_edge(), e_nmax_nbh_edges(), v_ith_nbh_edge(), and v_nmax_nbh_vertices().

size_t mln::util::graph::v_nmax_nbh_vertices

(

const vertex_id_t &

id_v

)

const [inline]

Return the number of adjacent vertices of vertex id_v.

References has_v(), and v_nmax_nbh_edges().

graph::vertex_t mln::util::graph::vertex

(

vertex_id_t

id_v

)

const [inline]

Return the vertex whose id is v.

References has_v().