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::vertex_fwd_iterator < graph >	vertex_fwd_iter
	Iterator typesVertex 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.
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.
Public Member Functions
	graph ()
	graph (unsigned nvertices)
	Construct a graph with nvertices vertices.
bool	has_v (const vertex_id_t &id_v) const
	Check whether a vertex id id_v exists in the graph.
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.
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.
edge_id_t	add_edge (const vertex_id_t &id_v1, const vertex_id_t &id_v2)
	Edge oriented.
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.
size_t	e_nmax () const
	Return the number of edges in the graph.
bool	has_e (const edge_id_t &id_e) const
	Return whether id_e is in the graph.
edge_t	edge (const vertex_t &v1, const vertex_t &v2) const
	Return the corresponding edge id if exists.
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.
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_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.
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.

---

Detailed Description

Undirected graph.

Definition at line 87 of file mln/util/graph.hh.

---

Member Typedef Documentation

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

Edge iterators.

Definition at line 129 of file mln/util/graph.hh.

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

Edge centered edge iterators.

Definition at line 136 of file mln/util/graph.hh.

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

A set to test the presence of a given edge.

Definition at line 102 of file mln/util/graph.hh.

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

The type of the set of edges.

Definition at line 100 of file mln/util/graph.hh.

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

Iterator typesVertex iterators.

Definition at line 108 of file mln/util/graph.hh.

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

Vertex centered edge iterators.

Definition at line 115 of file mln/util/graph.hh.

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

Vertex centered vertex iterators.

Definition at line 122 of file mln/util/graph.hh.

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

The type of the set of vertices.

Definition at line 97 of file mln/util/graph.hh.

---

Constructor & Destructor Documentation

mln::util::graph::graph

(

)

[inline]

Constructor.

Definition at line 282 of file mln/util/graph.hh.

mln::util::graph::graph

(

unsigned

nvertices

)

[inline]

Construct a graph with nvertices vertices.

Definition at line 288 of file mln/util/graph.hh.

---

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

Definition at line 386 of file mln/util/graph.hh.

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.

Definition at line 299 of file mln/util/graph.hh.

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.

Definition at line 310 of file mln/util/graph.hh.

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.

Definition at line 503 of file mln/util/graph.hh.

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.

Definition at line 443 of file mln/util/graph.hh.

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.

Definition at line 495 of file mln/util/graph.hh.

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

Referenced by e_ith_nbh_edge().

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

(

const edge_id_t &

e

)

const [inline]

Return the edge whose id is e.

Definition at line 435 of file mln/util/graph.hh.

References e_nmax().

Referenced by add_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.

Definition at line 457 of file mln/util/graph.hh.

References has_v().

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

(

)

const [inline]

Return the list of all edges.

Definition at line 428 of file mln/util/graph.hh.

bool mln::util::graph::has_e

(

const edge_id_t &

id_e

)

const [inline]

Return whether id_e is in the graph.

Definition at line 450 of file mln/util/graph.hh.

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.

Definition at line 338 of file mln/util/graph.hh.

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

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.

Definition at line 519 of file mln/util/graph.hh.

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.

Definition at line 479 of file mln/util/graph.hh.

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.

Definition at line 487 of file mln/util/graph.hh.

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.

Definition at line 353 of file mln/util/graph.hh.

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.

Definition at line 371 of file mln/util/graph.hh.

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.

Definition at line 331 of file mln/util/graph.hh.

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.

Definition at line 345 of file mln/util/graph.hh.

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.

Definition at line 363 of file mln/util/graph.hh.

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.

Definition at line 322 of file mln/util/graph.hh.

References has_v().