Namespaces
namespace	BFS

namespace	DFS

namespace	MST

Classes
class	AdjacencyContainerDecorator
	A decorator for adjacency containers that adds additional functionality. More...

class	AdjacencyMap
	Implementation of an Adjacency Map. Implements AdjacencyContainer. More...

class	BinaryAdjacency

class	BinaryFileAdjacency

class	ConcurrentConnectedComponents
	Concurrent specialization for computing connected components. More...

class	ConnectedComponents
	Search Result for Connected Components. More...

struct	DegreeCentrality
	Degree Centrality functor Returns a vector of pairs, with each pair storing the node and the degree centrality value. More...

class	DirectedAcyclicGraph

class	GraphDecorator
	Abstract Graph Decorator using CRTP. More...

class	GraphFactory

class	JSONFileAdjacency

class	Neighborhood

class	SearchPath
	Search Path implementation. More...

class	SearchResult
	CRTP Abstraction of Search Results. More...

class	Subgraphs

Concepts
concept	AdjacencyContainer
	Interface for an AdjacencyContainer.

concept	WeightedGraph
	Interface for a weighted graph.

concept	Node

concept	UniversalNodeRef

concept	Edge
	Interface for an Edge.

concept	Annotation

concept	WeightFunction

concept	WeightedEdge
	Interface for a weighted Edge.

concept	Graph
	Interface for graph types. Every graph type has to inherit from AbstractGraph.

Typedefs
template<Node N, util::HashFunction< N > Hash = std::hash<N>, util::BiPredicate< N > Equal = std::equal_to<N>, AdjacencyContainer< N > AdjContainer = AdjacencyMap<N,Hash,Equal>>
using	UndirectedGraph = graph::__impl::BaseGraph< UndirectedEdge< N, Hash, Equal >, AdjContainer >
	Simple Undirected Graph type.

template<Node N, util::HashFunction< N > Hash = std::hash<N>, util::BiPredicate< N > Equal = std::equal_to<N>, AdjacencyContainer< N > AdjContainer = AdjacencyMap<N,Hash,Equal>>
using	DirectedGraph = graph::__impl::BaseGraph< DirectedEdge< N, Hash, Equal >, AdjContainer >
	Simple Directed Graph type.

template<Graph G, Annotation A, WeightFunction< typename G::node_type, A > W>
using	Weighted = __impl::WeightedGraphDecorator< G, A, W >
	Weighted Graph Decorator type.

template<Node N, fishnet::util::HashFunction< N > Hash = std::hash<N>, fishnet::util::BiPredicate< N > Equal = std::equal_to<N>>
using	UndirectedEdge = __impl::BaseEdge< N, false, Hash, Equal >

template<Node N, fishnet::util::HashFunction< N > Hash = std::hash<N>, fishnet::util::BiPredicate< N > Equal = std::equal_to<N>>
using	DirectedEdge = __impl::BaseEdge< N, true, Hash, Equal >

template<Edge E, Annotation A, WeightFunction< typename E::node_type, A > W>
using	WeightEdge = __impl::WeightedEdgeDecorator< E, A, W >

Enumerations
enum class	NodeStatus { UNKNOWN , OPEN , CLOSED }

Functions
template<Graph SourceGraphType, Graph TargetGraphType>
void	contract (const SourceGraphType &source, util::BiPredicate< typename SourceGraphType::node_type > auto const &contractBiPredicate, util::BiFunction< typename SourceGraphType::node_type, typename SourceGraphType::node_type, typename TargetGraphType::node_type > auto const &mergeFunction, util::UnaryFunction< typename SourceGraphType::node_type, typename TargetGraphType::node_type > auto const &mapper, TargetGraphType &output, u_int8_t workers=1)
	Performs edge contraction algorithm. Edges between nodes fulfilling the contractBiPredicate get contracted. The incident nodes get merged by first mapping to the node type of the result graph and combining them using the mergeFunction Source graph is not changed, target graph is cleared before inserting the contraction result.

template<Graph SourceGraphType, Graph TargetGraphType>
void	contract (const SourceGraphType &source, util::BiPredicate< typename SourceGraphType::node_type > auto const &contractBiPredicate, util::ReduceFunction< std::vector< typename SourceGraphType::node_type >, typename TargetGraphType::node_type > auto const &reduceFunction, TargetGraphType &output, u_int8_t workers=1)
	Performs edge contraction algorithm. Edges between nodes fulfilling the contractBiPredicate get contracted. The incident nodes get merge by reducing a vector of nodes from the source graph to a single node of the target graph. Source graph is not changed, target graph is cleared before inserting the contraction result.

template<Graph SourceGraphType, Graph TargetGraphType>
void	contractInPlace (SourceGraphType &source, util::BiPredicate< typename SourceGraphType::node_type > auto const &contractBiPredicate, util::ReduceFunction< std::vector< typename SourceGraphType::node_type >, typename TargetGraphType::node_type > auto const &reduceFunction, TargetGraphType &output, u_int8_t workers=1)
	Performs edge contraction algorithm. Edges between nodes fulfilling the contractBiPredicate get contracted. The incident nodes get merge by reducing a vector of nodes from the source graph to a single node of the target graph. Source graph is not changed, target graph is cleared before inserting the contraction result.

template<Graph SourceGraphType>
void	contractInPlace (SourceGraphType &graph, util::BiPredicate< typename SourceGraphType::node_type > auto const &contractBiPredicate, util::ReduceFunction< std::vector< typename SourceGraphType::node_type >, typename SourceGraphType::node_type > auto const &reduceFunction, u_int8_t workers=1)
	In place edge contraction implementation. Edges between nodes fulfilling the contractBiPredicate get contracted. The incident nodes get merged by reducing a vector of nodes from the source graph to a single node of the target graph. Source graph is cleared and filled with the contraction result.

template<Graph G> requires std::is_constructible_v<G>
G	contract (const G &source, fishnet::util::BiPredicate< typename G::node_type > auto const &contractBiPredicate, fishnet::util::BiOperator< typename G::node_type > auto const &mergeFunction, u_int8_t workers=1)
	Contract the graph depending on the contraction predicate, applying the merge function on the nodes of contracted edges.

template<Graph G> requires std::is_constructible_v<G>
G	contract (const G &source, fishnet::util::BiPredicate< typename G::node_type > auto const &contractBiPredicate, fishnet::util::ReduceFunction< std::vector< typename G::node_type > > auto const &reduceFunction, u_int8_t workers=1)
	Contract the graph depending on the contraction predicate, applying the reduce function to merge clustered nodes.

Typedef Documentation

◆ DirectedEdge

template<Node N, fishnet::util::HashFunction< N > Hash = std::hash<N>, fishnet::util::BiPredicate< N > Equal = std::equal_to<N>>

using fishnet::graph::DirectedEdge = typedef __impl::BaseEdge<N,true,Hash,Equal>

◆ DirectedGraph

template<Node N, util::HashFunction< N > Hash = std::hash<N>, util::BiPredicate< N > Equal = std::equal_to<N>, AdjacencyContainer< N > AdjContainer = AdjacencyMap<N,Hash,Equal>>

using fishnet::graph::DirectedGraph = typedef graph::__impl::BaseGraph<DirectedEdge<N,Hash,Equal>,AdjContainer>

Simple Directed Graph type.

Template Parameters

N	node type
Hash	hasher on node type
Equal	comparator on node type
AdjContainer	Adjacency container used for the graph

◆ UndirectedEdge

template<Node N, fishnet::util::HashFunction< N > Hash = std::hash<N>, fishnet::util::BiPredicate< N > Equal = std::equal_to<N>>

using fishnet::graph::UndirectedEdge = typedef __impl::BaseEdge<N,false,Hash,Equal>

◆ UndirectedGraph

template<Node N, util::HashFunction< N > Hash = std::hash<N>, util::BiPredicate< N > Equal = std::equal_to<N>, AdjacencyContainer< N > AdjContainer = AdjacencyMap<N,Hash,Equal>>

using fishnet::graph::UndirectedGraph = typedef graph::__impl::BaseGraph<UndirectedEdge<N,Hash,Equal>,AdjContainer>

Simple Undirected Graph type.

Template Parameters

N	node type
Hash	hasher on node type
Equal	comparator on node type
AdjContainer	Adjacency container used for the graph

◆ Weighted

template<Graph G, Annotation A, WeightFunction< typename G::node_type, A > W>

using fishnet::graph::Weighted = typedef __impl::WeightedGraphDecorator<G,A,W>

Weighted Graph Decorator type.

Template Parameters

G	graph type
A	annotation type
W	weight function type

◆ WeightEdge

template<Edge E, Annotation A, WeightFunction< typename E::node_type, A > W>

using fishnet::graph::WeightEdge = typedef __impl::WeightedEdgeDecorator<E,A,W>

Enumeration Type Documentation

◆ NodeStatus

enum class fishnet::graph::NodeStatus

strong

Enumerator
UNKNOWN
OPEN
CLOSED

Function Documentation

◆ contract() [1/4]

template<Graph G>
requires std::is_constructible_v<G>

G fishnet::graph::contract	(	const G &	source,
		fishnet::util::BiPredicate< typename G::node_type > auto const &	contractBiPredicate,
		fishnet::util::BiOperator< typename G::node_type > auto const &	mergeFunction,
		u_int8_t	workers = `1`
	)

Contract the graph depending on the contraction predicate, applying the merge function on the nodes of contracted edges.

Template Parameters

G	graph type

Parameters

source	graph
contractBiPredicate	BiPredicate, deciding whether an edge between two nodes should be contracted
mergeFunction	BiOperator, defining how two nodes should be merge into a single node
workers	amount of worker threads

Returns: G contracted graph

◆ contract() [2/4]

template<Graph G>
requires std::is_constructible_v<G>

G fishnet::graph::contract	(	const G &	source,
		fishnet::util::BiPredicate< typename G::node_type > auto const &	contractBiPredicate,
		fishnet::util::ReduceFunction< std::vector< typename G::node_type > > auto const &	reduceFunction,
		u_int8_t	workers = `1`
	)

Contract the graph depending on the contraction predicate, applying the reduce function to merge clustered nodes.

Template Parameters

G	graph type

Parameters

source	graph
contractBiPredicate	BiPredicate, deciding whether an edge between two nodes should be contracted
reduceFunction	Reduce function, defining how a range of nodes should be reduced to a single node
workers	amount of worker threads

Returns: G contracted graph

◆ contract() [3/4]

template<Graph SourceGraphType, Graph TargetGraphType>

void fishnet::graph::contract	(	const SourceGraphType &	source,
		util::BiPredicate< typename SourceGraphType::node_type > auto const &	contractBiPredicate,
		util::BiFunction< typename SourceGraphType::node_type, typename SourceGraphType::node_type, typename TargetGraphType::node_type > auto const &	mergeFunction,
		util::UnaryFunction< typename SourceGraphType::node_type, typename TargetGraphType::node_type > auto const &	mapper,
		TargetGraphType &	output,
		u_int8_t	workers = `1`
	)

Performs edge contraction algorithm. Edges between nodes fulfilling the contractBiPredicate get contracted. The incident nodes get merged by first mapping to the node type of the result graph and combining them using the mergeFunction Source graph is not changed, target graph is cleared before inserting the contraction result.

Template Parameters

SourceGraphType	source graph type
TargetGraphType	target graph type

Parameters

source	source graph (not changed)
contractBiPredicate	specifies when an edge between two nodes from source graph shall be contracted
mergeFunction	specifies how nodes of the target graph will be merged
mapper	maps nodes from the source graph to the node type of the target graph
output	mutable reference to the target graph
workers	amount of concurrent works

Returns: TargetGraphType resulting graph after contracting edges and merging nodes using the target graph node type

◆ contract() [4/4]

template<Graph SourceGraphType, Graph TargetGraphType>

void fishnet::graph::contract	(	const SourceGraphType &	source,
		util::BiPredicate< typename SourceGraphType::node_type > auto const &	contractBiPredicate,
		util::ReduceFunction< std::vector< typename SourceGraphType::node_type >, typename TargetGraphType::node_type > auto const &	reduceFunction,
		TargetGraphType &	output,
		u_int8_t	workers = `1`
	)

Performs edge contraction algorithm. Edges between nodes fulfilling the contractBiPredicate get contracted. The incident nodes get merge by reducing a vector of nodes from the source graph to a single node of the target graph. Source graph is not changed, target graph is cleared before inserting the contraction result.

Template Parameters

SourceGraphType	source graph type
TargetGraphType	target graph type

Parameters

source	source graph (not changed)
contractBiPredicate	specifies when an edge between two nodes from source graph shall be contracted
reduceFunction	specifies how a vector of nodes from the source graph get combined to a single node of the target graph
output	mutable reference to the target graph
workers	amount of concurrent works

Returns: TargetGraphType resulting graph after contracting edges and merging nodes using the target graph node type

◆ contractInPlace() [1/2]

template<Graph SourceGraphType>

void fishnet::graph::contractInPlace	(	SourceGraphType &	graph,
		util::BiPredicate< typename SourceGraphType::node_type > auto const &	contractBiPredicate,
		util::ReduceFunction< std::vector< typename SourceGraphType::node_type >, typename SourceGraphType::node_type > auto const &	reduceFunction,
		u_int8_t	workers = `1`
	)

In place edge contraction implementation. Edges between nodes fulfilling the contractBiPredicate get contracted. The incident nodes get merged by reducing a vector of nodes from the source graph to a single node of the target graph. Source graph is cleared and filled with the contraction result.

Template Parameters

SourceGraphType	source graph type
TargetGraphType	target graph type

Parameters

graph	mutable reference to graph to be contracted
contractBiPredicate	specifies when an edge between two nodes from source graph shall be contracted
reduceFunction	specifies how a vector of nodes from the source graph get combined to a single node of the target graph
workers	amount of concurrent works

Returns: TargetGraphType resulting graph after contracting edges and merging nodes using the target graph node type

◆ contractInPlace() [2/2]

template<Graph SourceGraphType, Graph TargetGraphType>

void fishnet::graph::contractInPlace	(	SourceGraphType &	source,
		util::BiPredicate< typename SourceGraphType::node_type > auto const &	contractBiPredicate,
		util::ReduceFunction< std::vector< typename SourceGraphType::node_type >, typename TargetGraphType::node_type > auto const &	reduceFunction,
		TargetGraphType &	output,
		u_int8_t	workers = `1`
	)

Performs edge contraction algorithm. Edges between nodes fulfilling the contractBiPredicate get contracted. The incident nodes get merge by reducing a vector of nodes from the source graph to a single node of the target graph. Source graph is not changed, target graph is cleared before inserting the contraction result.

Template Parameters

SourceGraphType	source graph type
TargetGraphType	target graph type

Parameters

source	source graph (gets cleared)
contractBiPredicate	specifies when an edge between two nodes from source graph shall be contracted
reduceFunction	specifies how a vector of nodes from the source graph get combined to a single node of the target graph
output	mutable reference to the target graph
workers	amount of concurrent works

Returns: TargetGraphType resulting graph after contracting edges and merging nodes using the target graph node type

Namespaces

Classes

Concepts

Typedefs

Enumerations

Functions

Typedef Documentation

◆ DirectedEdge

◆ DirectedGraph

◆ UndirectedEdge

◆ UndirectedGraph

◆ Weighted

◆ WeightEdge

Enumeration Type Documentation

◆ NodeStatus

Function Documentation

◆ contract() [1/4]

◆ contract() [2/4]

◆ contract() [3/4]

◆ contract() [4/4]

◆ contractInPlace() [1/2]

◆ contractInPlace() [2/2]