Description

Graph search functionality.

See also: Basic graphs support

Author: Juan-Antonio Fernandez-Madrigal. http://jafma.net

Date: 2019

Copyright: Copyright (c), Individual contributors, see AUTHORS file. This program is free for non-commercial uses. For the rest, contact the AUTHORS. Please include a mention in your programs to the main developer and the web page of the library.

Collaboration diagram for Graph search algorithms:

Classes
class	elementa::adts::graphs::AllPathsVertices< Vertex, Edge, KIND >
	A class that search for all paths connecting a given pair of vertices. More...

class	elementa::adts::graphs::FloydWarshall< Vertex, Edge, Weight >
	Floyd-Warshall data and algorithm to find all shortest paths in a graph. More...

Functions
	elementa::adts::graphs::FloydWarshall< Vertex, Edge, Weight >::FloydWarshall (const Gr &g, const EdgeWeightFunction< Vertex, Edge, Weight > &w=trivial_edge_weight< Vertex, Edge >, const typename Gr::MapOfVItPos *mpos=nullptr, const typename Gr::EPred &epred=Gr::trivial_epred)
	Constructor: prepare data and perform the search. More...

	elementa::adts::graphs::FloydWarshall< Vertex, Edge, Weight >::FloydWarshall (FloydWarshall &&)
	Move constructor. More...

bool	elementa::adts::graphs::FloydWarshall< Vertex, Edge, Weight >::shortest (const typename Gr::viterator vit0, const typename Gr::viterator vit1, Weight &d) const
	Get the shortest distance (sum of weights) from vit0 to vit1. More...

bool	elementa::adts::graphs::FloydWarshall< Vertex, Edge, Weight >::shortest (const typename Gr::viterator vit0, const typename Gr::viterator vit1, Weight &d, GPath< Vertex, Edge, GPathKind::kVertexPath > &path) const
	Return the shortest distance and the shortest vertex path from 0 to 1. More...

Constructors
	elementa::adts::graphs::AllPathsVertices< Vertex, Edge, KIND >::AllPathsVertices (const GraphType &gr, const typename GraphType::viterator &vit0, const typename GraphType::viterator &vit1, bool detectcycles=true, const typename GraphType::EPred &epred=GraphType::trivial_epred)
	Constructor for two given vertices. More...

	elementa::adts::graphs::AllPathsVertices< Vertex, Edge, KIND >::AllPathsVertices (const AllPathsVertices &)=delete

	elementa::adts::graphs::AllPathsVertices< Vertex, Edge, KIND >::AllPathsVertices (AllPathsVertices &&)=delete

AllPathsVertices &	elementa::adts::graphs::AllPathsVertices< Vertex, Edge, KIND >::operator= (const AllPathsVertices &)=delete

AllPathsVertices &	elementa::adts::graphs::AllPathsVertices< Vertex, Edge, KIND >::operator= (AllPathsVertices &&)=delete

Class Documentation

◆ elementa::adts::graphs::AllPathsVertices

class elementa::adts::graphs::AllPathsVertices

template<class Vertex, class Edge, GPathKind KIND>
class elementa::adts::graphs::AllPathsVertices< Vertex, Edge, KIND >

A class that search for all paths connecting a given pair of vertices.

This class uses internally a depth-first edge iterator to scan the graph.

Template Parameters

Vertex	is the type of the vertex data.
Edge	is the type of the edge data.
KIND	is the kind of paths to generate.

Definition at line 67 of file graph_search.h.

Public Types
Types, consts., etc.
using	GraphType = Graph< Vertex, Edge >
	Shortcut for graph type. More...

using	PathType = GPath< Vertex, Edge, KIND >
	Shortcut for the path type. More...

Public Member Functions
Constructors
	AllPathsVertices (const GraphType &gr, const typename GraphType::viterator &vit0, const typename GraphType::viterator &vit1, bool detectcycles=true, const typename GraphType::EPred &epred=GraphType::trivial_epred)
	Constructor for two given vertices. More...

	AllPathsVertices (const AllPathsVertices &)=delete

	AllPathsVertices (AllPathsVertices &&)=delete

AllPathsVertices &	operator= (const AllPathsVertices &)=delete

AllPathsVertices &	operator= (AllPathsVertices &&)=delete

Methods
bool	found (void) const noexcept
	Return TRUE if there is some current path already found. More...

bool	next (void)
	Search for another path and return TRUE if any is found. More...

const PathType &	current (void) const
	Return a reference to the last path found. More...

Member Typedef Documentation

◆ GraphType

template<class Vertex , class Edge , GPathKind KIND>

using elementa::adts::graphs::AllPathsVertices< Vertex, Edge, KIND >::GraphType = Graph<Vertex,Edge>

Shortcut for graph type.

Definition at line 75 of file graph_search.h.

◆ PathType

template<class Vertex , class Edge , GPathKind KIND>

using elementa::adts::graphs::AllPathsVertices< Vertex, Edge, KIND >::PathType = GPath<Vertex,Edge,KIND>

Shortcut for the path type.

Definition at line 78 of file graph_search.h.

Member Function Documentation

◆ found()

template<class Vertex , class Edge , GPathKind KIND>

bool elementa::adts::graphs::AllPathsVertices< Vertex, Edge, KIND >::found ( void ) const

inlinenoexcept

Return TRUE if there is some current path already found.

Definition at line 114 of file graph_search.h.

◆ next()

template<class Vertex , class Edge , GPathKind KIND>

bool elementa::adts::graphs::AllPathsVertices< Vertex, Edge, KIND >::next ( void )

inline

Search for another path and return TRUE if any is found.

Definition at line 117 of file graph_search.h.

◆ current()

template<class Vertex , class Edge , GPathKind KIND>

const PathType & elementa::adts::graphs::AllPathsVertices< Vertex, Edge, KIND >::current ( void ) const

inline

Return a reference to the last path found.

Throw if no path has been found.

Definition at line 122 of file graph_search.h.

References ELE_CODE_PLACE.

◆ elementa::adts::graphs::FloydWarshall

class elementa::adts::graphs::FloydWarshall

template<class Vertex, class Edge, class Weight = double>
class elementa::adts::graphs::FloydWarshall< Vertex, Edge, Weight >

Floyd-Warshall data and algorithm to find all shortest paths in a graph.

This algorithms cannot deal with negative weighted cycles, and only finds one path between any pair of vertices even when several paths are equally shortest. It creates internally three matrices, one of V * V weight values, another of V * V vertex iterators, and another one of V * V booleans, that are automatically freed when the object is destroyed. It also creates, if the user requests it, a map of vertices and iterators.

Template Parameters

Weight is the data type to hold weights of edges.

Note: - The algorithm is recommended in densely connected graphs, where it is O(V^3). If the graph is sparsely connected, it is better to call repeatedly Dijstra's, which becomes in that case O(V^2 * log(V)).

Definition at line 182 of file graph_search.h.

Public Types
using	Gr = Graph< Vertex, Edge >
	The base graph on which the algorithm works. More...

Public Member Functions
	FloydWarshall (const Gr &g, const EdgeWeightFunction< Vertex, Edge, Weight > &w=trivial_edge_weight< Vertex, Edge >, const typename Gr::MapOfVItPos *mpos=nullptr, const typename Gr::EPred &epred=Gr::trivial_epred)
	Constructor: prepare data and perform the search. More...

	FloydWarshall (FloydWarshall &&)
	Move constructor. More...

FloydWarshall &	operator= (FloydWarshall &&)=delete

	FloydWarshall (const FloydWarshall &)=delete

FloydWarshall &	operator= (const FloydWarshall &)=delete

	~FloydWarshall (void)
	Destructor. More...

const Gr::MapOfVItPos &	mapOfVPoses (void) const
	Return the vertex mapping used by the object. More...

bool	filled (void) const noexcept
	Return TRUE if there is some previous calculation in the object. More...

bool	shortest (const typename Gr::viterator vit0, const typename Gr::viterator vit1, Weight &d) const
	Get the shortest distance (sum of weights) from vit0 to vit1. More...

bool	shortest (const typename Gr::viterator vit0, const typename Gr::viterator vit1, Weight &d, GPath< Vertex, Edge, GPathKind::kVertexPath > &path) const
	Return the shortest distance and the shortest vertex path from 0 to 1. More...

Member Typedef Documentation

◆ Gr

template<class Vertex , class Edge , class Weight = double>

using elementa::adts::graphs::FloydWarshall< Vertex, Edge, Weight >::Gr = Graph<Vertex,Edge>

The base graph on which the algorithm works.

Definition at line 187 of file graph_search.h.

Constructor & Destructor Documentation

◆ ~FloydWarshall()

template<class Vertex , class Edge , class Weight = double>

elementa::adts::graphs::FloydWarshall< Vertex, Edge, Weight >::~FloydWarshall ( void )

inline

Destructor.

Definition at line 211 of file graph_search.h.

Member Function Documentation

◆ mapOfVPoses()

template<class Vertex , class Edge , class Weight = double>

const Gr::MapOfVItPos & elementa::adts::graphs::FloydWarshall< Vertex, Edge, Weight >::mapOfVPoses ( void ) const

inline

Return the vertex mapping used by the object.

Definition at line 215 of file graph_search.h.

◆ filled()

template<class Vertex , class Edge , class Weight = double>

bool elementa::adts::graphs::FloydWarshall< Vertex, Edge, Weight >::filled ( void ) const

inlinenoexcept

Return TRUE if there is some previous calculation in the object.

Definition at line 218 of file graph_search.h.

Function Documentation

◆ AllPathsVertices()

template<class Vertex , class Edge , GPathKind KIND>

elementa::adts::graphs::AllPathsVertices< Vertex, Edge, KIND >::AllPathsVertices	(	const GraphType &	gr,
		const typename GraphType::viterator &	vit0,
		const typename GraphType::viterator &	vit1,
		bool	detectcycles = `true`,
		const typename GraphType::EPred &	epred = `GraphType::trivial_epred`
	)

#include <elementa/adts/graphs/graph_search.h>

Constructor for two given vertices.

The object will detect cycles in the paths (with an additional cost of O(V)*O(E) at each new path) if detectcyles == TRUE; otherwise, if there is any cycle the search will go on and on without end (dangerous). Ownership of the graph and of epred is outside this class; their lifetime must span beyond the lifetime of this object. This constructor already searches for the first possible path between the nodes, thus no need for calling next() until that path is read with currentPath().

Definition at line 284 of file graph_search.h.

References elementa::adts::graphs::Graph< Vertex, Edge >::ERange_DepthFirst::begin(), ELE_CODE_TRACE_OFF, elementa::adts::graphs::Graph< Vertex, Edge >::ERange_DepthFirst::end(), and elementa::adts::graphs::Graph< Vertex, Edge >::erangeDepthFirst().

◆ FloydWarshall() [1/2]

template<class Vertex , class Edge , class Weight >

elementa::adts::graphs::FloydWarshall< Vertex, Edge, Weight >::FloydWarshall	(	const Gr &	g,
		const EdgeWeightFunction< Vertex, Edge, Weight > &	w = `trivial_edge_weight<Vertex,Edge>`,
		const typename Gr::MapOfVItPos *	mpos = `nullptr`,
		const typename Gr::EPred &	epred = `Gr::trivial_epred`
	)

#include <elementa/adts/graphs/graph_search.h>

Constructor: prepare data and perform the search.

Leaves internal data updated with the result of the search.

Parameters

mpos	is a pointer to a previously calculated map of positions in g (see the Graph class), or nullptr if you wish this constructor to calculate it internally. In the former case, it must outlive this object, since an internal reference is held.
epred	is a predicate that must return TRUE for those edges to consider.

Definition at line 531 of file graph_search.h.

◆ FloydWarshall() [2/2]

template<class Vertex , class Edge , class Weight >

elementa::adts::graphs::FloydWarshall< Vertex, Edge, Weight >::FloydWarshall ( FloydWarshall< Vertex, Edge, Weight > && o )

#include <elementa/adts/graphs/graph_search.h>

Move constructor.

Definition at line 636 of file graph_search.h.

◆ shortest() [1/2]

template<class Vertex , class Edge , class Weight >

bool elementa::adts::graphs::FloydWarshall< Vertex, Edge, Weight >::shortest	(	const typename Gr::viterator	vit0,
		const typename Gr::viterator	vit1,
		Weight &	d
	)		const

#include <elementa/adts/graphs/graph_search.h>

Get the shortest distance (sum of weights) from vit0 to vit1.

Return TRUE if there is a finite distance calculated, or FALSE if the distance is infinity. In the former case, fill D with the distance. Throw if there is no such path found previously.

Definition at line 655 of file graph_search.h.

References ELE_CODE_TRACE_OFF, elementa::base::to_number(), and elementa::base::MultIterator< Data, BIDIR >::to_string().

◆ shortest() [2/2]

template<class Vertex , class Edge , class Weight >

bool elementa::adts::graphs::FloydWarshall< Vertex, Edge, Weight >::shortest	(	const typename Gr::viterator	vit0,
		const typename Gr::viterator	vit1,
		Weight &	d,
		GPath< Vertex, Edge, GPathKind::kVertexPath > &	path
	)		const

#include <elementa/adts/graphs/graph_search.h>

Return the shortest distance and the shortest vertex path from 0 to 1.

Return TRUE if there is a finite distance calculated, or FALSE if the distance is infinity. In the former case, fill D with the distance and PATH with the path. Throw if there is no such path found previously.

Definition at line 677 of file graph_search.h.

References ELE_CODE_TRACE_OFF, elementa::base::to_number(), and elementa::base::MultIterator< Data, BIDIR >::to_string().

Description

Classes

Functions

Constructors

Class Documentation

◆ elementa::adts::graphs::AllPathsVertices

Public Types

Public Member Functions

Member Typedef Documentation

◆ GraphType

◆ PathType

Member Function Documentation

◆ found()

◆ next()

◆ current()

◆ elementa::adts::graphs::FloydWarshall

Public Types

Public Member Functions

Member Typedef Documentation

◆ Gr

Constructor & Destructor Documentation

◆ ~FloydWarshall()

Member Function Documentation

◆ mapOfVPoses()

◆ filled()

Function Documentation

◆ AllPathsVertices()

◆ FloydWarshall() [1/2]

◆ FloydWarshall() [2/2]

◆ shortest() [1/2]

◆ shortest() [2/2]