stapl::sequential::UG< Traits > Class Template Reference

Class implementing an undirected graph. More...

Public Member Functions
	UG (size_t sz)
	Create an undirected graph with the specified number of vertices.
	UG (UG const &other)
bool	is_directed () const
	Method used to check if the graph is directed or not. This class always returns false;.
edge_iterator	edges_begin ()
	Returns an iterator over all the edges of the graph, pointing to the starting edge in the graph. Skips sibling edges (where target < source), to avoid duplicating edges in undirected graph.
const_edge_iterator	edges_begin () const
	Returns an iterator over all the edges of the graph, pointing to the starting edge in the graph. Skips sibling edges (where target < source), to avoid duplicating edges in undirected graph.
edge_iterator	edges_end ()
	Returns an iterator over all the edges of the graph, pointing to one past the ending edge in the graph. Skips sibling edges (where target < source), to avoid duplicating edges in undirected graph.
const_edge_iterator	edges_end () const
	Returns an iterator over all the edges of the graph, pointing to one past the ending edge in the graph. Skips sibling edges (where target < source), to avoid duplicating edges in undirected graph.
edge_descriptor	add_edge (edge_descriptor const &ed)
	Adds the specified edge in both directions. More...
edge_descriptor	add_edge (edge_descriptor const &ed, edge_property const &p)
	Adds the specified edge in both directions, with the given property. More...
size_t	get_num_edges (void) const
	Returns the number of undirected edges in the graph. The number of edges is half the number of directed edges in the graph.
bool	delete_edge (edge_descriptor const &ed)
	Deletes the specified undirected edge (removes the directed edge and its sibling edge). More...
bool	find_edge (edge_descriptor const &ed, vertex_iterator &vi, adj_edge_iterator &ei)
	Finds one of the two edges defining an undirected edge. More...
bool	find_edge (edge_descriptor const &ed, const_vertex_iterator &vi, const_adj_edge_iterator &ei) const
	Finds one of the two edges defining an undirected edge. More...
void	clear ()
	Erase all vertices and edges in the graph, and any associated properties.
bool	delete_vertex (vertex_descriptor const &vd)
	Deletes the specified vertex and all edges pointing to it and from it. More...

Public Types
typedef base_type::vertex_descriptor	vertex_descriptor
typedef base_type::edge_descriptor	edge_descriptor
typedef base_type::vertex_property	vertex_property
typedef base_type::edge_property	edge_property
typedef base_type::vertex_iterator	vertex_iterator
typedef base_type::const_vertex_iterator	const_vertex_iterator
typedef base_type::adj_edge_iterator	adj_edge_iterator
typedef base_type::const_adj_edge_iterator	const_adj_edge_iterator
typedef base_type::edge_iterator	edge_iterator
typedef base_type::const_edge_iterator	const_edge_iterator

Detailed Description

template<class Traits>
class stapl::sequential::UG< Traits >

Class implementing an undirected graph.

Template Parameters

Traits

A traits class that defines customizable components of graph, such as the descriptor, model, storage, etc.

Member Function Documentation

add_edge() [1/2]

template<class Traits >

edge_descriptor stapl::sequential::UG< Traits >::add_edge

(

edge_descriptor const &

ed

)

Adds the specified edge in both directions.

Undirected graph doesn't allow for self loops; this is consistent with other graph libraries like BGL, LEDA.

Parameters

ed	The descriptor of the edge to be added.

Returns

The edge descriptor of the added edge. If successful, the id() of the descriptor is populated with the actual edge's id, otherwise set to std::numeric_limits<size_t>::max().

add_edge() [2/2]

template<class Traits >

edge_descriptor stapl::sequential::UG< Traits >::add_edge	(	edge_descriptor const &	ed,
		edge_property const &	p
	)

Adds the specified edge in both directions, with the given property.

Undirected graph doesn't allow for self loops; this is consistent with other graph libraries like BGL, LEDA.

Parameters

ed	The descriptor of the edge to be added.

Returns

The edge descriptor of the added edge. If successful, the id() of the descriptor is populated with the actual edge's id, otherwise set to std::numeric_limits<size_t>::max().

delete_edge()

template<class Traits >

bool stapl::sequential::UG< Traits >::delete_edge

(

edge_descriptor const &

ed

)

Deletes the specified undirected edge (removes the directed edge and its sibling edge).

Returns

True if the delete was successful, or false otherwise.

find_edge() [1/2]

template<class Traits >

bool stapl::sequential::UG< Traits >::find_edge	(	edge_descriptor const &	ed,
		vertex_iterator &	vi,
		adj_edge_iterator &	ei
	)

Finds one of the two edges defining an undirected edge.

As a rule, we report the edge where source is smaller than the destination.

Parameters

ed	The descriptor of the edge to be found.
vi	The output vertex iterator pointing to the source-vertex of the edge.
ei	The output edge iterator pointing to the specified edge.

Returns

True if the edge was found, or false otherwise.

find_edge() [2/2]

template<class Traits >

bool stapl::sequential::UG< Traits >::find_edge	(	edge_descriptor const &	ed,
		const_vertex_iterator &	vi,
		const_adj_edge_iterator &	ei
	)		const

Finds one of the two edges defining an undirected edge.

As a rule, we report the edge where source is smaller than the destination.

Parameters

ed	The descriptor of the edge to be found.
vi	The output vertex iterator pointing to the source-vertex of the edge.
ei	The output edge iterator pointing to the specified edge.

Returns

True if the edge was found, or false otherwise.

delete_vertex()

template<class Traits >

bool stapl::sequential::UG< Traits >::delete_vertex

(

vertex_descriptor const &

vd

)

Deletes the specified vertex and all edges pointing to it and from it.

Returns

True if vertex was deleted, or false otherwise.

---

The documentation for this class was generated from the following file:

• graph.h