dsac::graph::Graph< V, E > Class Template Reference

#include <graph.h>

Collaboration diagram for dsac::graph::Graph< V, E >:

Data Structures
class	Edge
	Edge instance serves as a token for an underlying edge. More...
struct	EdgeHash
	Hash functor that allows use of Edge as an unordered set/map key. More...
class	Vertex
	Vertex instance serves as a token for an underlying vertex. More...
struct	VertexHash
	Hash functor that allows use of Vertex as an unordered set/map key. More...

Public Member Functions
	Graph (bool is_directed)
	Creates a new graph (directed or undirected, as specified by argument)
bool	is_directed () const
	Returns true if graph is directed, false otherwise.
int	num_vertices () const
	Returns the number of vertices in the graph.
int	num_edges () const
	Returns the number of edges in the graph.
std::list< Vertex >	vertices () const
	Returns a list of Vertex tokens.
std::list< Edge >	edges () const
	Returns a list of Edge tokens.
bool	has_edge (Vertex u, Vertex v) const
	Return true if there exists an edge from u to v, false otherwise.
Edge	get_edge (Vertex u, Vertex v) const
	Return the edge from u to v; undefined behavior if no such edge exists.
int	degree (Vertex v, bool outgoing=true) const
	Returns the number of outgoing (or incoming) edges for Vertex v.
std::list< Vertex >	neighbors (Vertex v, bool outgoing=true) const
	Returns a list of outgoing (or incoming) Vertex tokens for neighbors of Vertex v.
std::list< Edge >	incident_edges (Vertex v, bool outgoing=true) const
	Returns a list of outgoing (or incoming) Edge tokens for Vertex v.
std::pair< Vertex, Vertex >	endpoints (Edge e) const
	Returns the (origin,destination) pair for Edge e.
Vertex	opposite (Edge e, Vertex v) const
	Returns the opposite endpoint to Vertex v for Edge e.
Vertex	insert_vertex (V elem)
	Create a new vertex storing given element, and return Vertex token.
Edge	insert_edge (Vertex u, Vertex v, int weight=1, E elem=E())
void	erase (Edge e)
void	erase (Vertex v)
	Graph (const Graph &other)
	Copy constructor.
Graph &	operator= (const Graph &other)
	Copy assignment.
	Graph (Graph &&)=default
	Move constructor.
Graph &	operator= (Graph &&)=default
	Move assignment.
	~Graph ()=default
	Destructs a graph.

Constructor & Destructor Documentation

Graph() [1/3]

template<typename V , typename E >

dsac::graph::Graph< V, E >::Graph ( bool  is_directed )

inline

Creates a new graph (directed or undirected, as specified by argument)

Graph() [2/3]

template<typename V , typename E >

dsac::graph::Graph< V, E >::Graph ( const Graph< V, E > &  other )

inline

Copy constructor.

Graph() [3/3]

template<typename V , typename E >

dsac::graph::Graph< V, E >::Graph ( Graph< V, E > &&  )

default

Move constructor.

~Graph()

template<typename V , typename E >

dsac::graph::Graph< V, E >::~Graph ( )

default

Destructs a graph.

Member Function Documentation

degree()

template<typename V , typename E >

int dsac::graph::Graph< V, E >::degree ( Vertex  v, bool  outgoing = true  ) const

inline

Returns the number of outgoing (or incoming) edges for Vertex v.

edges()

template<typename V , typename E >

std::list< Edge > dsac::graph::Graph< V, E >::edges ( ) const

inline

Returns a list of Edge tokens.

endpoints()

template<typename V , typename E >

std::pair< Vertex, Vertex > dsac::graph::Graph< V, E >::endpoints ( Edge  e ) const

inline

Returns the (origin,destination) pair for Edge e.

erase() [1/2]

template<typename V , typename E >

void dsac::graph::Graph< V, E >::erase ( Edge  e )

inline

erase() [2/2]

template<typename V , typename E >

void dsac::graph::Graph< V, E >::erase ( Vertex  v )

inline

get_edge()

template<typename V , typename E >

Edge dsac::graph::Graph< V, E >::get_edge ( Vertex  u, Vertex  v  ) const

inline

Return the edge from u to v; undefined behavior if no such edge exists.

has_edge()

template<typename V , typename E >

bool dsac::graph::Graph< V, E >::has_edge ( Vertex  u, Vertex  v  ) const

inline

Return true if there exists an edge from u to v, false otherwise.

incident_edges()

template<typename V , typename E >

std::list< Edge > dsac::graph::Graph< V, E >::incident_edges ( Vertex  v, bool  outgoing = true  ) const

inline

Returns a list of outgoing (or incoming) Edge tokens for Vertex v.

insert_edge()

template<typename V , typename E >

Edge dsac::graph::Graph< V, E >::insert_edge ( Vertex  u, Vertex  v, int  weight = 1, E  elem = E()  )

inline

Inserts new edge from u to v, storing given element, and given weight (default 1) If edge already exists, updates weight and element for that existing edge. Returns Edge token

Here is the call graph for this function:

insert_vertex()

template<typename V , typename E >

Vertex dsac::graph::Graph< V, E >::insert_vertex ( V  elem )

inline

Create a new vertex storing given element, and return Vertex token.

is_directed()

template<typename V , typename E >

bool dsac::graph::Graph< V, E >::is_directed ( ) const

inline

Returns true if graph is directed, false otherwise.

neighbors()

template<typename V , typename E >

std::list< Vertex > dsac::graph::Graph< V, E >::neighbors ( Vertex  v, bool  outgoing = true  ) const

inline

Returns a list of outgoing (or incoming) Vertex tokens for neighbors of Vertex v.

num_edges()

template<typename V , typename E >

int dsac::graph::Graph< V, E >::num_edges ( ) const

inline

Returns the number of edges in the graph.

num_vertices()

template<typename V , typename E >

int dsac::graph::Graph< V, E >::num_vertices ( ) const

inline

Returns the number of vertices in the graph.

operator=() [1/2]

template<typename V , typename E >

Graph & dsac::graph::Graph< V, E >::operator= ( const Graph< V, E > &  other )

inline

Copy assignment.

operator=() [2/2]

template<typename V , typename E >

Graph & dsac::graph::Graph< V, E >::operator= ( Graph< V, E > &&  )

default

Move assignment.

opposite()

template<typename V , typename E >

Vertex dsac::graph::Graph< V, E >::opposite ( Edge  e, Vertex  v  ) const

inline

Returns the opposite endpoint to Vertex v for Edge e.

vertices()

template<typename V , typename E >

std::list< Vertex > dsac::graph::Graph< V, E >::vertices ( ) const

inline

Returns a list of Vertex tokens.

---

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

• dsac/graph/graph.h