STAPL API Reference          
Overview   Containers   Algorithms   Views   Skeletons   Run-Time System
Modules     Classes    
List of all members | Public Member Functions | Public Types
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
TraitsA 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
edThe 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
edThe 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
edThe descriptor of the edge to be found.
viThe output vertex iterator pointing to the source-vertex of the edge.
eiThe 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
edThe descriptor of the edge to be found.
viThe output vertex iterator pointing to the source-vertex of the edge.
eiThe 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: