Description

Types and functionality of paths in graphs.

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 Paths in graphs:

Classes
struct	elementa::adts::graphs::GPathKindType< KIND >
	A type corresponding to each constant value of the kind of a path. More...

class	elementa::adts::graphs::GPath< Vertex, Edge, KIND >
	A path in a graph whose vertices are of type Vertex and edges of type Edge. More...

Typedefs
template<class Vertex , class Edge , GPathKind KIND>
using	elementa::adts::graphs::GPathElement = typename std::conditional< KIND==GPathKind::kVertexPath, typename Graph< Vertex, Edge >::viterator, typename Graph< Vertex, Edge >::eiterator >::type
	Type of the elements of a path, according to its kind. More...

template<class Vertex , class Edge , class Weight = double>
using	elementa::adts::graphs::EdgeWeightFunction = std::function< Weight(const typename Graph< Vertex, Edge >::eiterator &) >
	A family of functions that return the weight of an edge. More...

Functions
	elementa::adts::graphs::ELE_CLASS_ENUM (GPathKind, kVertexPath, kEdgePath)
	Kinds of paths.

constexpr GPathKind	elementa::adts::graphs::kOtherGPathKind (GPathKind kid)
	The kind opposite to a given one. More...

template<class Vertex , class Edge >
constexpr double	elementa::adts::graphs::trivial_edge_weight (const typename Graph< Vertex, Edge >::eiterator &) noexcept
	A family of functions that return 1.0 as the weight of any edge. More...

template<class Vertex , class Edge >
constexpr double	elementa::adts::graphs::value_edge_weight (const typename Graph< Vertex, Edge >::eiterator &eit) noexcept
	A family of functions that return the edge value as the weight. More...

Class Documentation

◆ elementa::adts::graphs::GPathKindType

struct elementa::adts::graphs::GPathKindType

template<GPathKind KIND>
struct elementa::adts::graphs::GPathKindType< KIND >

A type corresponding to each constant value of the kind of a path.

Definition at line 62 of file graph_paths.h.

◆ elementa::adts::graphs::GPath

class elementa::adts::graphs::GPath

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

A path in a graph whose vertices are of type Vertex and edges of type Edge.

Definition at line 78 of file graph_paths.h.

Inheritance diagram for elementa::adts::graphs::GPath< Vertex, Edge, KIND >:

[legend]

Collaboration diagram for elementa::adts::graphs::GPath< Vertex, Edge, KIND >:

[legend]

Public Attributes
T	elements
	STL member.

Public Member Functions
Methods
GPath< Vertex, Edge, kOtherGPathKind(KIND) >	other (const BaseGraph &g, const typename BaseGraph::EPred &epred=BaseGraph::trivial_epred) const
	Construct a path of the other kind equivalent to this one. More...

std::string	to_string (const BaseGraph &g, const std::function< std::string(const Vertex &vd)> &vtostr=[](const Vertex &vd) ->std::string { return(std::to_string(vd));}, const std::function< std::string(const Edge &ed)> &etostr=[](const Edge &ed) ->std::string { return(std::to_string(ed));}) const
	Return a text version of the path. More...

Types, consts., etc.
using	VectorElem = GPathElement< Vertex, Edge, KIND >
	The type of the elements of the vector. More...

using	BasePath = std::vector< VectorElem >
	Base type of the path. More...

using	BaseGraph = Graph< Vertex, Edge >
	The graph class on which the path is defined. More...

using	Collection = std::vector< GPath >
	A collection of paths. More...

static const GPathKind	kKind = KIND
	The kind of the path. More...

Member Typedef Documentation

◆ VectorElem

template<class Vertex , class Edge , GPathKind KIND>

using elementa::adts::graphs::GPath< Vertex, Edge, KIND >::VectorElem = GPathElement<Vertex,Edge,KIND>

The type of the elements of the vector.

Definition at line 89 of file graph_paths.h.

◆ BasePath

template<class Vertex , class Edge , GPathKind KIND>

using elementa::adts::graphs::GPath< Vertex, Edge, KIND >::BasePath = std::vector<VectorElem>

Base type of the path.

Definition at line 92 of file graph_paths.h.

◆ BaseGraph

template<class Vertex , class Edge , GPathKind KIND>

using elementa::adts::graphs::GPath< Vertex, Edge, KIND >::BaseGraph = Graph<Vertex,Edge>

The graph class on which the path is defined.

Definition at line 95 of file graph_paths.h.

◆ Collection

template<class Vertex , class Edge , GPathKind KIND>

using elementa::adts::graphs::GPath< Vertex, Edge, KIND >::Collection = std::vector<GPath>

A collection of paths.

Definition at line 98 of file graph_paths.h.

Member Function Documentation

◆ other()

template<class Vertex , class Edge , GPathKind KIND>

GPath< Vertex, Edge, kOtherGPathKind(KIND) > elementa::adts::graphs::GPath< Vertex, Edge, KIND >::other	(	const BaseGraph &	g,
		const typename BaseGraph::EPred &	epred = `BaseGraph::trivial_epred`
	)		const

inline

Construct a path of the other kind equivalent to this one.

If the conversion is from vertex to edge path, this is O(M * L), where M is the maximum fanout of any vertex involved in the path and L the length of the path (as long as iterating on leaving edges of a vertex is O(1)). If the conversion is from edge to vertex path, it is O(L) (as long as getting the vertices of an edge is O(1)).

Parameters

epred is only used if we are getting an edge path from a vertex path, in order to select which edges to use from the possibly several that join two given vertices.

Definition at line 124 of file graph_paths.h.

◆ to_string()

template<class Vertex , class Edge , GPathKind KIND>

std::string elementa::adts::graphs::GPath< Vertex, Edge, KIND >::to_string	(	const BaseGraph &	g,
		const std::function< std::string(const Vertex &vd)> &	vtostr = `[](const Vertex & vd)->std::string { return(std::to_string(vd)); }`,
		const std::function< std::string(const Edge &ed)> &	etostr = `[](const Edge & ed)->std::string { return(std::to_string(ed)); }`
	)		const

inline

Return a text version of the path.

Parameters

g	is the graph on which the path has been defined.
vtostr	is a converter from vertex data to string.
etostr	is a converter from edge data to string.

Definition at line 133 of file graph_paths.h.

Member Data Documentation

◆ kKind

template<class Vertex , class Edge , GPathKind KIND>

const GPathKind elementa::adts::graphs::GPath< Vertex, Edge, KIND >::kKind = KIND

static

The kind of the path.

Definition at line 86 of file graph_paths.h.

Typedef Documentation

◆ GPathElement

template<class Vertex , class Edge , GPathKind KIND>

using elementa::adts::graphs::GPathElement = typedef typename std::conditional< KIND == GPathKind::kVertexPath, typename Graph<Vertex,Edge>::viterator, typename Graph<Vertex,Edge>::eiterator >::type

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

Type of the elements of a path, according to its kind.

Definition at line 71 of file graph_paths.h.

◆ EdgeWeightFunction

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

using elementa::adts::graphs::EdgeWeightFunction = typedef std::function< Weight(const typename Graph<Vertex,Edge>::eiterator &) >

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

A family of functions that return the weight of an edge.

Definition at line 187 of file graph_paths.h.

Function Documentation

◆ kOtherGPathKind()

constexpr GPathKind elementa::adts::graphs::kOtherGPathKind ( GPathKind kid )

constexpr

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

The kind opposite to a given one.

Definition at line 65 of file graph_paths.h.

◆ trivial_edge_weight()

template<class Vertex , class Edge >

constexpr double elementa::adts::graphs::trivial_edge_weight ( const typename Graph< Vertex, Edge >::eiterator & )

constexprnoexcept

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

A family of functions that return 1.0 as the weight of any edge.

Definition at line 192 of file graph_paths.h.

◆ value_edge_weight()

template<class Vertex , class Edge >

constexpr double elementa::adts::graphs::value_edge_weight ( const typename Graph< Vertex, Edge >::eiterator & eit )

constexprnoexcept

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

A family of functions that return the edge value as the weight.

Definition at line 199 of file graph_paths.h.

Description

Classes

Typedefs

Functions

Class Documentation

◆ elementa::adts::graphs::GPathKindType

◆ elementa::adts::graphs::GPath

Public Attributes

Public Member Functions

Types, consts., etc.

Member Typedef Documentation

◆ VectorElem

◆ BasePath

◆ BaseGraph

◆ Collection

Member Function Documentation

◆ other()

◆ to_string()

Member Data Documentation

◆ kKind

Typedef Documentation

◆ GPathElement

◆ EdgeWeightFunction

Function Documentation

◆ kOtherGPathKind()

◆ trivial_edge_weight()

◆ value_edge_weight()