A graph represented as an adjacency list. More...

#include <adjacency_list.h>

Public Types
using	vertex_type = VertexT

using	edge_type = typename VertexT::edge_type

Public Member Functions
	adjacency_list (EdgeOrientation edge_orientation=EdgeOrientation::Undirected)
	create a graph with the given edge_orientation

	adjacency_list (size_t vertex_count, EdgeOrientation edge_orientation=EdgeOrientation::Undirected)
	create a graph with the given edge_orientation and vertex_count default-initialized vertices and zero edges

void	resize (size_t vertex_count)
	resize number of vertices, all edge data is removed

bool	is_directed () const
	return true if the graph is directed

void	clear ()
	clear graph

bool	empty () const
	return true if the graph does not contain any vertices

size_t	vertex_count () const
	return the number of vertices, i.e. the order of the graph

size_t	edge_count () const
	return the number of edges, i.e. the size of the graph

void	remove_all_edges ()
	removes all edges

vertex_type &	vertex (size_t i)
	access to vertex i

const vertex_type &	vertex (size_t i) const
	const access to vertex i

const std::vector< edge_type >	to_edge_list () const
	return a list of all edges in no particular order

size_t	add_vertex (const vertex_type &vertex)
	add a new vertex to graph and return its index

bool	add_edge (const edge_type &edge)
	add an edge to the list; return false if the edge already exists, true otherwise

bool	add_edge (size_t start, size_t end)
	add a default-initialized edge definded by the start and end vertex to the list; return false if the edge already exists, true otherwise

bool	edge_exists (size_t start, size_t end) const
	check if edge is already in list

bool	is_cyclic () const
	return true if the graph contains at least one cycle

std::vector< size_t >	topological_sort () const

Detailed Description

template<typename VertexT>
class cgv::math::adjacency_list< VertexT >

A graph represented as an adjacency list.

To create a basic graph without extra information stored per vertex or edge use the predefined type cgv::math::graph: cgv::math::graph g;

To create a basic weighted graph with an additional weight attribute per edge use the predefined template cgv::math::weighted_graph and specify the weight type; cgv::math::weighted_graph<weight_type> wg;

To create a graph with user-defined attributes per edge and vertex:

struct my_edge: public cgv::math::edge { double my_extra_edge_attr; };

struct my_vertex : public cgv::math::vertex<my_edge> { int my_extra_vertex_attr; };

using my_graph = cgv::math::adjacency_list< my_vertex >; my_graph g; ...

Definition at line 77 of file adjacency_list.h.

Member Typedef Documentation

◆ edge_type

template<typename VertexT >

using cgv::math::adjacency_list< VertexT >::edge_type = typename VertexT::edge_type

Definition at line 80 of file adjacency_list.h.

◆ vertex_type

template<typename VertexT >

using cgv::math::adjacency_list< VertexT >::vertex_type = VertexT

Definition at line 79 of file adjacency_list.h.

Constructor & Destructor Documentation

◆ adjacency_list() [1/2]

template<typename VertexT >

cgv::math::adjacency_list< VertexT >::adjacency_list ( EdgeOrientation edge_orientation = EdgeOrientation::Undirected )

inline

create a graph with the given edge_orientation

Definition at line 83 of file adjacency_list.h.

◆ adjacency_list() [2/2]

template<typename VertexT >

cgv::math::adjacency_list< VertexT >::adjacency_list	(	size_t	vertex_count,
		EdgeOrientation	edge_orientation = `EdgeOrientation::Undirected`
	)

inline

create a graph with the given edge_orientation and vertex_count default-initialized vertices and zero edges

Definition at line 86 of file adjacency_list.h.

References cgv::math::adjacency_list< VertexT >::vertex_count().

Member Function Documentation

◆ add_edge() [1/2]

template<typename VertexT >

bool cgv::math::adjacency_list< VertexT >::add_edge ( const edge_type & edge )

inline

add an edge to the list; return false if the edge already exists, true otherwise

Definition at line 155 of file adjacency_list.h.

References cgv::math::adjacency_list< VertexT >::edge_exists(), cgv::math::vertex< EdgeT >::edges, cgv::math::edge::end, cgv::math::adjacency_list< VertexT >::is_directed(), cgv::math::edge::start, and cgv::math::adjacency_list< VertexT >::vertex_count().

Referenced by cgv::math::adjacency_list< VertexT >::add_edge().

◆ add_edge() [2/2]

template<typename VertexT >

bool cgv::math::adjacency_list< VertexT >::add_edge	(	size_t	start,
		size_t	end
	)

inline

add a default-initialized edge definded by the start and end vertex to the list; return false if the edge already exists, true otherwise

Definition at line 173 of file adjacency_list.h.

References cgv::math::adjacency_list< VertexT >::add_edge().

◆ add_vertex()

template<typename VertexT >

size_t cgv::math::adjacency_list< VertexT >::add_vertex ( const vertex_type & vertex )

inline

add a new vertex to graph and return its index

Definition at line 149 of file adjacency_list.h.

◆ clear()

template<typename VertexT >

void cgv::math::adjacency_list< VertexT >::clear ( )

inline

clear graph

Definition at line 102 of file adjacency_list.h.

◆ edge_count()

template<typename VertexT >

size_t cgv::math::adjacency_list< VertexT >::edge_count ( ) const

inline

return the number of edges, i.e. the size of the graph

Definition at line 117 of file adjacency_list.h.

References cgv::math::adjacency_list< VertexT >::is_directed().

◆ edge_exists()

template<typename VertexT >

bool cgv::math::adjacency_list< VertexT >::edge_exists	(	size_t	start,
		size_t	end
	)		const

inline

check if edge is already in list

Definition at line 178 of file adjacency_list.h.

References cgv::math::vertex< EdgeT >::edges, and cgv::math::edge::end.

Referenced by cgv::math::adjacency_list< VertexT >::add_edge().

template<typename VertexT >

std::vector< size_t > cgv::math::adjacency_list< VertexT >::topological_sort ( ) const

inline

Definition at line 210 of file adjacency_list.h.

◆ vertex() [1/2]

template<typename VertexT >

vertex_type & cgv::math::adjacency_list< VertexT >::vertex ( size_t i )

inline

access to vertex i

Definition at line 131 of file adjacency_list.h.

◆ vertex() [2/2]

template<typename VertexT >

const vertex_type & cgv::math::adjacency_list< VertexT >::vertex ( size_t i ) const

inline

const access to vertex i

Definition at line 136 of file adjacency_list.h.

◆ vertex_count()

template<typename VertexT >

size_t cgv::math::adjacency_list< VertexT >::vertex_count ( ) const

inline

return the number of vertices, i.e. the order of the graph

Definition at line 112 of file adjacency_list.h.

Referenced by cgv::math::adjacency_list< VertexT >::add_edge(), cgv::math::adjacency_list< VertexT >::adjacency_list(), cgv::math::adjacency_list< VertexT >::is_cyclic(), and cgv::math::adjacency_list< VertexT >::resize().

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

cgv/math/adjacency_list.h

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ edge_type

◆ vertex_type

Constructor & Destructor Documentation

◆ adjacency_list() [1/2]

◆ adjacency_list() [2/2]

Member Function Documentation

◆ add_edge() [1/2]

◆ add_edge() [2/2]

◆ add_vertex()

◆ clear()

◆ edge_count()

◆ edge_exists()

◆ empty()

◆ is_cyclic()

◆ is_directed()

◆ remove_all_edges()

◆ resize()

◆ to_edge_list()

◆ topological_sort()

◆ vertex() [1/2]

◆ vertex() [2/2]

◆ vertex_count()