cgv
Loading...
Searching...
No Matches
cgv::math::adjacency_list< VertexT > Class Template Reference

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.

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.

Referenced by cgv::math::adjacency_list< vertex< edge > >::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.

◆ 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.

◆ 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.

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

◆ empty()

template<typename VertexT>
bool cgv::math::adjacency_list< VertexT >::empty ( ) const
inline

return true if the graph does not contain any vertices

Definition at line 107 of file adjacency_list.h.

◆ is_cyclic()

template<typename VertexT>
bool cgv::math::adjacency_list< VertexT >::is_cyclic ( ) const
inline

return true if the graph contains at least one cycle

Definition at line 187 of file adjacency_list.h.

◆ is_directed()

template<typename VertexT>
bool cgv::math::adjacency_list< VertexT >::is_directed ( ) const
inline

◆ remove_all_edges()

template<typename VertexT>
void cgv::math::adjacency_list< VertexT >::remove_all_edges ( )
inline

removes all edges

Definition at line 126 of file adjacency_list.h.

Referenced by cgv::math::adjacency_list< vertex< edge > >::resize().

◆ resize()

template<typename VertexT>
void cgv::math::adjacency_list< VertexT >::resize ( size_t vertex_count)
inline

resize number of vertices, all edge data is removed

Definition at line 91 of file adjacency_list.h.

◆ to_edge_list()

template<typename VertexT>
const std::vector< edge_type > cgv::math::adjacency_list< VertexT >::to_edge_list ( ) const
inline

return a list of all edges in no particular order

Definition at line 141 of file adjacency_list.h.

◆ topological_sort()

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

◆ 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< vertex< edge > >::is_cyclic().


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