Undirected simple graph stored as adjacency sets. More...

#include <graph.hpp>

Classes
class	Iterator
	Forward iterator over the vertices of a graph. More...
class	EdgeIterator
	Forward iterator over the undirected edges of a graph. More...

Public Types
using	VertexType = Vertex
using	NeighborSet = std::unordered_set<Vertex>
using	EdgeType = std::array<Vertex, 2>
using	iterator = Iterator
using	const_iterator = Iterator

Public Member Functions
	Graph ()=default
	Creates an empty graph.
	Graph (const std::vector< std::array< Vertex, 2 > > &edges)
	Creates a graph from a list of undirected edges.
void	addVertex (const Vertex &vertex)
	Adds a vertex if it is not already present.
void	addEdge (const Vertex &u, const Vertex &v)
	Adds an undirected edge and its endpoints.
bool	containsVertex (const Vertex &vertex) const
	Tests whether a vertex is present.
bool	containsEdge (const Vertex &u, const Vertex &v) const
	Tests whether an undirected edge is present.
int	degree (const Vertex &vertex) const
	Returns the degree of a vertex.
int	maxDegree () const
	Returns the largest vertex degree.
int	vertexCount () const
	Returns the number of vertices.
int	edgeCount () const
	Returns the number of undirected edges.
void	removeEdge (const Vertex &u, const Vertex &v)
	Removes an undirected edge if it is present.
void	removeVertex (const Vertex &vertex)
	Removes a vertex and every incident edge.
void	clear ()
	Removes every vertex and edge.
auto	vertices () const
	Returns a lazy view over the vertices.
auto	edges () const
	Returns a lazy view over the undirected edges.
const NeighborSet &	neighbors (const Vertex &vertex) const
	Returns the neighbors of a vertex.
NeighborSet	closedNeighbors (const Vertex &vertex) const
	Returns a vertex together with all of its neighbors.
std::vector< Vertex >	bfs (const Vertex &vertex, int maxVertices=0) const
	Traverses a connected component in breadth-first order.
std::vector< std::vector< Vertex > >	components () const
	Returns the graph's connected components.
std::vector< std::vector< Vertex > >	biconnectedComponents () const
	Returns the vertex-biconnected blocks of the graph.
std::vector< std::vector< Vertex > >	cliqueCover () const
	Computes a vertex clique cover using the DSATUR heuristic.
std::vector< Vertex >	independentSet () const
	Computes a maximal independent set greedily from low-degree vertices.
template<class WeightFunction>
Graph	spanningTree (WeightFunction weight) const
	Computes a minimum spanning forest using Prim's algorithm.
template<class WeightFunction>
std::vector< Vertex >	shortestPath (const Vertex &source, const Vertex &target, WeightFunction weight) const
	Computes a shortest path between two vertices using Dijkstra's algorithm.
template<class WeightFunction, class LowerBoundFunction>
std::vector< Vertex >	shortestPath (const Vertex &source, const Vertex &target, WeightFunction weight, LowerBoundFunction lowerBound) const
	Computes a shortest path between two vertices using the A* algorithm.
iterator	begin ()
	Returns an iterator to the first vertex.
iterator	end ()
	Returns the end iterator.
const_iterator	begin () const
	Returns a const iterator to the first vertex.
const_iterator	end () const
	Returns the const end iterator.
const_iterator	cbegin () const
	Returns a const iterator to the first vertex.
const_iterator	cend () const
	Returns the const end iterator.

Detailed Description

template<class Vertex>
class pgl::Graph< Vertex >

Undirected simple graph stored as adjacency sets.

Undirected simple graph with hashable vertices.

Adding an edge also adds both of its endpoints. Self-loops are ignored and repeated edges are coalesced. Vertex and traversal order are unspecified because the graph uses unordered containers.

Template Parameters

Vertex Hashable, equality-comparable vertex type.

Member Typedef Documentation

◆ const_iterator

template<class Vertex>

using pgl::Graph< Vertex >::const_iterator = Iterator

◆ EdgeType

template<class Vertex>

using pgl::Graph< Vertex >::EdgeType = std::array<Vertex, 2>

Undirected edge, listing its two endpoints in increasing order.

◆ iterator

template<class Vertex>

using pgl::Graph< Vertex >::iterator = Iterator

◆ NeighborSet

template<class Vertex>

using pgl::Graph< Vertex >::NeighborSet = std::unordered_set<Vertex>

Set containing the neighbors of a vertex.

◆ VertexType

template<class Vertex>

using pgl::Graph< Vertex >::VertexType = Vertex

Type used to represent a vertex.

Constructor & Destructor Documentation

◆ Graph() [1/2]

template<class Vertex>

pgl::Graph< Vertex >::Graph ( )

default

Creates an empty graph.

◆ Graph() [2/2]

template<class Vertex>

pgl::Graph< Vertex >::Graph ( const std::vector< std::array< Vertex, 2 > > & edges )

inlineexplicit

Creates a graph from a list of undirected edges.

Parameters

edges Endpoint pairs. Self-loops are ignored.

Member Function Documentation

◆ addEdge()

template<class Vertex>

void pgl::Graph< Vertex >::addEdge	(	const Vertex &	u,
		const Vertex &	v )

inline

Adds an undirected edge and its endpoints.

A self-loop is ignored, including its endpoint.

Parameters

u	First endpoint.
v	Second endpoint.

◆ addVertex()

template<class Vertex>

void pgl::Graph< Vertex >::addVertex ( const Vertex & vertex )

inline

Adds a vertex if it is not already present.

Parameters

vertex Vertex to add.

◆ begin() [1/2]

template<class Vertex>

iterator pgl::Graph< Vertex >::begin ( )

inlinenodiscard

Returns an iterator to the first vertex.

◆ begin() [2/2]

template<class Vertex>

const_iterator pgl::Graph< Vertex >::begin ( ) const

inlinenodiscard

Returns a const iterator to the first vertex.

◆ bfs()

template<class Vertex>

std::vector< Vertex > pgl::Graph< Vertex >::bfs	(	const Vertex &	vertex,
		int	maxVertices = 0 ) const

inlinenodiscard

Traverses a connected component in breadth-first order.

Parameters

vertex	Starting vertex.
maxVertices	Maximum number of vertices to return; 0 means no limit.

Returns: Visited vertices in breadth-first order, or an empty vector if vertex is absent.

◆ biconnectedComponents()

template<class Vertex>

std::vector< std::vector< Vertex > > pgl::Graph< Vertex >::biconnectedComponents ( ) const

inlinenodiscard

Returns the vertex-biconnected blocks of the graph.

A bridge is returned as a two-vertex block. Isolated vertices do not belong to an edge-defined block and are omitted. Articulation vertices consequently appear in more than one result. Blocks are sorted by decreasing size; their order among equal-size blocks and the order of vertices within each block are unspecified.

The implementation is an iterative form of Tarjan's depth-first search, avoiding recursion depth proportional to the graph size.

Returns: Vertex sets of the biconnected blocks, largest first.

◆ cbegin()

template<class Vertex>

const_iterator pgl::Graph< Vertex >::cbegin ( ) const

inlinenodiscard

Returns a const iterator to the first vertex.

◆ cend()

template<class Vertex>

const_iterator pgl::Graph< Vertex >::cend ( ) const

inlinenodiscard

Returns the const end iterator.

◆ clear()

template<class Vertex>

void pgl::Graph< Vertex >::clear ( )

inline

Removes every vertex and edge.

◆ cliqueCover()

template<class Vertex>

std::vector< std::vector< Vertex > > pgl::Graph< Vertex >::cliqueCover ( ) const

inlinenodiscard

Computes a vertex clique cover using the DSATUR heuristic.

DSATUR colors the complement graph: vertices receiving the same color are pairwise adjacent in this graph and therefore form a clique. Every graph vertex appears in exactly one returned clique. The heuristic does not guarantee a minimum-cardinality cover.

At each step, the algorithm selects an uncolored vertex adjacent in the complement to the largest number of distinct colors. Ties are broken by complement degree, then by the graph's unspecified iteration order. Returned cliques are sorted by decreasing size.

Returns: A partition of the vertices into cliques, largest first.

◆ closedNeighbors()

template<class Vertex>

NeighborSet pgl::Graph< Vertex >::closedNeighbors ( const Vertex & vertex ) const

inlinenodiscard

Returns a vertex together with all of its neighbors.

Parameters

vertex Vertex whose closed neighborhood to return.

Returns: Closed neighborhood in unspecified order.

Exceptions

std::out_of_range if vertex is absent.

◆ components()

template<class Vertex>

std::vector< std::vector< Vertex > > pgl::Graph< Vertex >::components ( ) const

inlinenodiscard

Returns the graph's connected components.

Isolated vertices form one-vertex components. Components are sorted by decreasing size; their order among equal-size components and the order of vertices within each component are unspecified.

Returns: Connected components, largest first.

◆ containsEdge()

template<class Vertex>

bool pgl::Graph< Vertex >::containsEdge	(	const Vertex &	u,
		const Vertex &	v ) const

inlinenodiscard

Tests whether an undirected edge is present.

Parameters

u	First endpoint.
v	Second endpoint.

Returns: true if the graph contains the edge between u and v.

◆ containsVertex()

template<class Vertex>

bool pgl::Graph< Vertex >::containsVertex ( const Vertex & vertex ) const

inlinenodiscard

Tests whether a vertex is present.

Parameters

vertex Vertex to find.

Returns: true if vertex belongs to the graph.

◆ degree()

template<class Vertex>

int pgl::Graph< Vertex >::degree ( const Vertex & vertex ) const

inlinenodiscard

Returns the degree of a vertex.

Parameters

vertex Vertex whose degree to query.

Returns: Number of neighbors, or -1 if vertex is absent.

◆ edgeCount()

template<class Vertex>

int pgl::Graph< Vertex >::edgeCount ( ) const

inlinenodiscard

Returns the number of undirected edges.

◆ edges()

template<class Vertex>

auto pgl::Graph< Vertex >::edges ( ) const

inlinenodiscard

Returns a lazy view over the undirected edges.

Each edge appears exactly once, as an EdgeType holding its two endpoints in increasing order; edges come in unspecified order. Nothing is copied or allocated: the view walks the adjacency sets in place, so it refers to this graph and is invalidated by anything that modifies it.

Iterating the whole view costs $O(n + m)$ for a graph with $n$ vertices and $m$ edges, which is also the cost of reaching the first edge of a graph made of isolated vertices.

Returns: A forward view of the edgeCount() edges.

◆ end() [1/2]

template<class Vertex>

iterator pgl::Graph< Vertex >::end ( )

inlinenodiscard

Returns the end iterator.

◆ end() [2/2]

template<class Vertex>

const_iterator pgl::Graph< Vertex >::end ( ) const

inlinenodiscard

Returns the const end iterator.

◆ independentSet()

template<class Vertex>

std::vector< Vertex > pgl::Graph< Vertex >::independentSet ( ) const

inlinenodiscard

Computes a maximal independent set greedily from low-degree vertices.

Vertices are considered in increasing order of their degree in this graph. A vertex is added when it is not adjacent to any vertex already in the result. Equal-degree vertices are considered in the graph's unspecified iteration order. The returned set is maximal: every vertex outside it is adjacent to at least one vertex in it. It is not generally a maximum-cardinality independent set.

Returns: Pairwise non-adjacent vertices forming a maximal independent set.

◆ maxDegree()

template<class Vertex>

int pgl::Graph< Vertex >::maxDegree ( ) const

inlinenodiscard

Returns the largest vertex degree.

Returns: Maximum degree, or -1 if the graph is empty.

◆ neighbors()

template<class Vertex>

const NeighborSet & pgl::Graph< Vertex >::neighbors ( const Vertex & vertex ) const

inlinenodiscard

Returns the neighbors of a vertex.

Parameters

vertex Vertex whose neighbors to access.

Returns: Const reference to the vertex's adjacency set.

Exceptions

std::out_of_range if vertex is absent.

◆ removeEdge()

template<class Vertex>

void pgl::Graph< Vertex >::removeEdge	(	const Vertex &	u,
		const Vertex &	v )

inline

Removes an undirected edge if it is present.

The endpoints remain in the graph.

Parameters

u	First endpoint.
v	Second endpoint.

◆ removeVertex()

template<class Vertex>

void pgl::Graph< Vertex >::removeVertex ( const Vertex & vertex )

inline

Removes a vertex and every incident edge.

Parameters

vertex Vertex to remove.

◆ shortestPath() [1/2]

template<class Vertex>

template<class WeightFunction>

std::vector< Vertex > pgl::Graph< Vertex >::shortestPath	(	const Vertex &	source,
		const Vertex &	target,
		WeightFunction	weight ) const

inlinenodiscard

Computes a shortest path between two vertices using Dijkstra's algorithm.

The returned path starts at source, ends at target and lists every vertex along the way; the path from a vertex to itself is that vertex alone. An empty result means that no path exists, either because the two vertices lie in different connected components or because one of them is absent. Ties between equally long paths are broken by the graph's unspecified iteration order.

The frontier is a lazy binary heap (std::priority_queue): a vertex is pushed once per incident edge relaxed and discarded when popped if it has already been settled. The search stops as soon as target is settled. Complexity is $O(m \log m)$ weight comparisons and $O(m)$ calls to weight for a graph with $m$ edges.

Template Parameters

WeightFunction Callable taking two vertices and returning a copyable edge weight ordered by < and added by +; the weight type is chosen by the callable.

Parameters

source	First vertex of the path.
target	Last vertex of the path.
weight	Edge weight function. It must be symmetric and must not return a negative weight; neither is checked, and the returned path is unspecified when either fails.

Returns: The vertices of a shortest path from source to target, or an empty vector if there is none.

◆ shortestPath() [2/2]

template<class Vertex>

template<class WeightFunction, class LowerBoundFunction>

std::vector< Vertex > pgl::Graph< Vertex >::shortestPath	(	const Vertex &	source,
		const Vertex &	target,
		WeightFunction	weight,
		LowerBoundFunction	lowerBound ) const

inlinenodiscard

Computes a shortest path between two vertices using the A* algorithm.

This overload has the same result and endpoint behavior as the Dijkstra overload, but uses lowerBound to prioritize vertices that appear closer to target. The lower bound need not be consistent: a vertex is reopened whenever a shorter path to it is found.

The frontier is a lazy binary heap (std::priority_queue) ordered by the sum of the path length so far and the estimated remaining distance. With a consistent lower bound, complexity is $O(m \log m)$ weight comparisons and $O(m)$ calls to weight and lowerBound for a graph with $m$ edges. An inconsistent lower bound can cause vertices to be reopened.

Template Parameters

WeightFunction	Callable taking two vertices and returning a copyable edge weight ordered by < and added by +; the weight type is chosen by the callable.
LowerBoundFunction	Callable taking two vertices and returning a lower bound in the same weight type.

Parameters

source	First vertex of the path.
target	Last vertex of the path.
weight	Edge weight function. It must be symmetric and must not return a negative weight; neither is checked, and the returned path is unspecified when either fails.
lowerBound	Estimate of the distance between two vertices. For every vertex reached by the search, lowerBound(vertex, target) must be nonnegative, must not exceed the shortest distance to `target`, and must be zero when vertex == target. These requirements are not checked.

Returns: The vertices of a shortest path from source to target, or an empty vector if there is none.

◆ spanningTree()

template<class Vertex>

template<class WeightFunction>

Graph pgl::Graph< Vertex >::spanningTree ( WeightFunction weight ) const

inlinenodiscard

Computes a minimum spanning forest using Prim's algorithm.

The tree of a connected graph is a minimum spanning tree. A disconnected graph yields one minimum spanning tree per connected component, so the result always contains every vertex of this graph, isolated ones included. Ties between equally heavy edges are broken by the graph's unspecified iteration order.

The frontier is a lazy binary heap (std::priority_queue): an edge is pushed when one endpoint enters the tree and discarded when popped if its other endpoint has since been reached. Complexity is $O(m \log m)$ weight comparisons and $O(m)$ calls to weight for a graph with $m$ edges.

Template Parameters

WeightFunction Callable taking two vertices and returning a copyable, less-than-comparable edge weight; the weight type is chosen by the callable.

Parameters

weight Edge weight function. It must be symmetric, otherwise which of the two values is used for an edge is unspecified.

Returns: A minimum spanning forest of this graph.

◆ vertexCount()

template<class Vertex>

int pgl::Graph< Vertex >::vertexCount ( ) const

inlinenodiscard

Returns the number of vertices.

◆ vertices()

template<class Vertex>

auto pgl::Graph< Vertex >::vertices ( ) const

inlinenodiscard

Returns a lazy view over the vertices.

The vertices are the keys of the adjacency map, so the view is the graph iteration range itself: it yields every vertex as a const reference, in unspecified order, copying and allocating nothing. It refers to this graph and is invalidated by anything that modifies it.

Returns: A forward view of the vertexCount() vertices.

Classes

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ EdgeType

◆ iterator

◆ NeighborSet

◆ VertexType

Constructor & Destructor Documentation

◆ Graph() [1/2]

◆ Graph() [2/2]

Member Function Documentation

◆ addEdge()

◆ addVertex()

◆ begin() [1/2]

◆ begin() [2/2]

◆ bfs()

◆ biconnectedComponents()

◆ cbegin()

◆ cend()

◆ clear()

◆ cliqueCover()

◆ closedNeighbors()

◆ components()

◆ containsEdge()

◆ containsVertex()

◆ degree()

◆ edgeCount()

◆ edges()

◆ end() [1/2]

◆ end() [2/2]

◆ independentSet()

◆ maxDegree()

◆ neighbors()

◆ removeEdge()

◆ removeVertex()

◆ shortestPath() [1/2]

◆ shortestPath() [2/2]

◆ spanningTree()

◆ vertexCount()

◆ vertices()