Undirected graph. More...

#include <graph.hh>

Inheritance diagram for mln::util::graph:

Public Types
typedef Graph< void >	category
typedef util::edge< graph >	edge_t
	The type of an edge.
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 graph	exact_t
typedef util::vertex< graph >	vertex_t
	The type of a vertex.
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_bkd_iterator < graph >	vertex_bkd_iter
typedef vertex_fwd_iter	vertex_iter


typedef mln::internal::vertex_nbh_edge_fwd_iterator < graph >	vertex_nbh_edge_fwd_iter
	Vertex centered edge iterators.
typedef mln::internal::vertex_nbh_edge_bkd_iterator < graph >	vertex_nbh_edge_bkd_iter
typedef vertex_nbh_edge_fwd_iter	vertex_nbh_edge_iter


typedef mln::internal::vertex_nbh_vertex_fwd_iterator < graph >	vertex_nbh_vertex_fwd_iter
	Vertex centered vertex iterators.
typedef mln::internal::vertex_nbh_vertex_bkd_iterator < graph >	vertex_nbh_vertex_bkd_iter
typedef vertex_nbh_vertex_fwd_iter	vertex_nbh_vertex_iter


typedef mln::internal::edge_fwd_iterator < graph >	edge_fwd_iter
	Edge iterators.
typedef mln::internal::edge_bkd_iterator < graph >	edge_bkd_iter
typedef edge_fwd_iter	edge_iter


typedef mln::internal::edge_nbh_edge_fwd_iterator < graph >	edge_nbh_edge_fwd_iter
	Edge centered edge iterators.
typedef mln::internal::edge_nbh_edge_bkd_iterator < graph >	edge_nbh_edge_bkd_iter
typedef edge_nbh_edge_fwd_iter	edge_nbh_edge_iter
Public Member Functions
const util::tracked_ptr < mln::internal::data< graph > > &	data_hook_ () const
	Hook to data; for debugging purpose.
	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.
void	print_debug (std::ostream &ostr) const
	Print on `ostr` 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.


const void *	id () const
	Misc.


bool	has (const util::vertex< graph > &v) const
	Vertex oriented methodsCheck whether a vertex `v` exists in the graph.


bool	has (const util::edge< graph > &e) const
	Edge oriented methodsCheck whether an edge `e` exists in the graph.


vertex_id_t	v_other (const edge_id_t &id_e, const vertex_id_t &id_v) const
	Vertex and edge oriented methods.
bool	is_valid () const
	Return true if this graph is valid.
void	invalidate ()
	Invalidate the graph.
Protected Attributes
util::tracked_ptr < mln::internal::data< graph > >	data_
	Internal data, sharable by several graphs.
Private Types
typedef super::edge_data_t	edge_data_t
	Internal edge data type.
typedef internal::graph_base < graph >	super
	The super class.
typedef super::vertex_data_t	vertex_data_t
	Internal vertex data type.

Detailed Description

Undirected graph.

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

Member Typedef Documentation

typedef Graph<void> mln::Graph< graph >::category [inherited]

Reimplemented from mln::Object< graph >.

Definition at line 59 of file mln/core/concept/graph.hh.

typedef mln::internal::edge_bkd_iterator<graph> mln::util::graph::edge_bkd_iter

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

typedef super::edge_data_t mln::util::graph::edge_data_t [private]

Internal edge data type.

Reimplemented from mln::util::internal::graph_base< graph >.

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

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 edge_fwd_iter mln::util::graph::edge_iter

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

typedef mln::internal::edge_nbh_edge_bkd_iterator<graph> mln::util::graph::edge_nbh_edge_bkd_iter

Definition at line 137 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 edge_nbh_edge_fwd_iter mln::util::graph::edge_nbh_edge_iter

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

typedef util::edge<graph > mln::util::internal::graph_base< graph >::edge_t [inherited]

The type of an edge.

Definition at line 72 of file graph_base.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 graph mln::Object< graph >::exact_t [inherited]

Definition at line 173 of file object.hh.

typedef internal::graph_base<graph> mln::util::graph::super [private]

The super class.

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

typedef mln::internal::vertex_bkd_iterator<graph> mln::util::graph::vertex_bkd_iter

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

typedef super::vertex_data_t mln::util::graph::vertex_data_t [private]

Internal vertex data type.

Reimplemented from mln::util::internal::graph_base< graph >.

Definition at line 92 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 vertex_fwd_iter mln::util::graph::vertex_iter

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

typedef mln::internal::vertex_nbh_edge_bkd_iterator<graph> mln::util::graph::vertex_nbh_edge_bkd_iter

Definition at line 116 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 vertex_nbh_edge_fwd_iter mln::util::graph::vertex_nbh_edge_iter

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

typedef mln::internal::vertex_nbh_vertex_bkd_iterator<graph> mln::util::graph::vertex_nbh_vertex_bkd_iter

Definition at line 123 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 vertex_nbh_vertex_fwd_iter mln::util::graph::vertex_nbh_vertex_iter

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

typedef util::vertex<graph > mln::util::internal::graph_base< graph >::vertex_t [inherited]

The type of a vertex.

Definition at line 70 of file graph_base.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.

References mln::util::internal::graph_base< graph >::data_.

mln::util::graph::graph ( unsigned nvertices ) [inline]

Construct a graph with nvertices vertices.

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

References mln::util::internal::graph_base< graph >::data_.

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 mln::util::internal::graph_base< graph >::data_, edge(), mln::util::ord_pair< T >::first(), has_v(), and mln::util::ord_pair< T >::second().

Referenced by mln::make::impl::generic::influence_zone_adjacency_graph(), mln::make::impl::generic::rag_and_labeled_wsl(), mln::make::impl::generic::region_adjacency_graph(), and 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 mln::util::internal::graph_base< graph >::data_, and 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 mln::util::internal::graph_base< graph >::data_, and v_nmax().

Referenced by mln::make::impl::generic::influence_zone_adjacency_graph(), mln::make::impl::generic::rag_and_labeled_wsl(), and mln::make::impl::generic::region_adjacency_graph().

const util::tracked_ptr< mln::internal::data<graph > >& mln::util::internal::graph_base< graph >::data_hook_ ( ) const [inherited]

Hook to data; for debugging purpose.

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.

References mln::util::internal::graph_base< graph >::data_.

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 mln::util::internal::graph_base< graph >::data_, has_v(), and mln::util::vertex< G >::id().

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.

References mln::util::internal::graph_base< graph >::data_.

bool mln::util::internal::graph_base< graph >::has ( const util::edge< graph > & e ) const [inherited]

Edge oriented methodsCheck whether an edge e exists in the graph.

bool mln::util::internal::graph_base< graph >::has ( const util::vertex< graph > & v ) const [inherited]

Vertex oriented methodsCheck whether a vertex v exists in the graph.

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.

References mln::util::internal::graph_base< graph >::data_.

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.

References mln::util::internal::graph_base< graph >::data_.

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

const void* mln::util::internal::graph_base< graph >::id ( ) const [inherited]

Misc.

methods

Returns the graph id, the "this" pointer.

Referenced by is_subgraph_of().

void mln::util::internal::graph_base< graph >::invalidate ( ) [inherited]

Invalidate the graph.

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.

References mln::util::internal::graph_base< graph >::id().

bool mln::util::internal::graph_base< graph >::is_valid ( ) const [inherited]

Return true if this graph is valid.

void mln::util::internal::graph_base< graph >::print_debug ( std::ostream & ostr ) const [inherited]

Print on ostr the graph.

Parameters:

[in] ostr The output stream.

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 mln::util::internal::graph_base< graph >::data_, and 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 mln::util::internal::graph_base< graph >::data_, and 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 mln::util::internal::graph_base< graph >::data_, 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(), v_ith_nbh_edge(), and mln::util::internal::graph_base< graph >::v_other().

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.

References mln::util::internal::graph_base< graph >::data_.

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 mln::util::internal::graph_base< graph >::data_, and 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().

vertex_id_t mln::util::internal::graph_base< graph >::v_other	(	const edge_id_t &	id_e,
		const vertex_id_t &	id_v
	)			const `[inherited]`

Vertex and edge oriented methods.

Returns the other adjacent vertex id of a given edge id id_e.

Referenced by v_ith_nbh_vertex().

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

Member Data Documentation

util::tracked_ptr< mln::internal::data<graph > > mln::util::internal::graph_base< graph >::data_ [protected, inherited]

Internal data, sharable by several graphs.

Definition at line 126 of file graph_base.hh.

Referenced by add_edge(), add_vertex(), add_vertices(), e_nmax(), edge(), edges(), graph(), has_e(), has_v(), v1(), v2(), v_ith_nbh_edge(), v_nmax(), and v_nmax_nbh_edges().

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

Public Types

Public Member Functions

Protected Attributes

Private Types

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

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