fishnet::graph::BFS Namespace Reference

Functions
template<Graph G>
auto	connectedComponents (const G &graph, fishnet::util::BiPredicate< typename G::node_type > auto const &inRelation)
	Compute connected components of the graph.
template<Graph G>
auto	connectedComponents (const G &graph)
	Compute connected components of the graph\ Uses DefaultBiPredicate which is always true, when two nodes share an edge.
template<Graph G>
auto	connectedComponents (const G &graph, std::shared_ptr< fishnet::util::BlockingQueue< std::pair< int, std::vector< typename G::node_type > > > > queue, fishnet::util::BiPredicate< typename G::node_type > auto const &inRelation)
	Compute connected components of the graph concurrently.
template<Graph G>
auto	connectedComponents (const G &graph, std::shared_ptr< fishnet::util::BlockingQueue< std::pair< int, std::vector< typename G::node_type > > > > queue)
	Compute connected components of the graph concurrently.
template<Graph G>
auto	findPath (const G &graph, const typename G::node_type &start, const typename G::node_type &goal)
	Find breadth-first search between between start and goal node.
template<Graph G>
util::input_range_of< typename G::edge_type > auto	getPath (const G &graph, const typename G::node_type &start, const typename G::node_type &goal)
	Find breadth-first search between between start and goal node.
template<Graph G, Graph O> requires std::same_as<typename G::node_type, typename O::node_type>
G	neighborhood (const G &graph, const typename G::node_type &node, size_t order, O &&outputGraph)
template<Graph G> requires std::is_default_constructible_v<G>
G	neighborhood (const G &graph, const typename G::node_type &node, size_t order)
template<Graph G> requires (!std::is_default_constructible_v<G> && std::is_copy_constructible_v<G>)
G	neighborhood (const G &graph, const typename G::node_type &node, size_t order)
template<Graph G, typename P , typename R = std::invoke_result_t<std::decay_t<P>>> requires std::same_as<typename G::node_type, typename R::node_type>
fishnet::util::forward_range_of< R > auto	subgraphs (const G &graph, P &&emptyGraphProducer)
	Find all subgraphs in the given graph.
template<Graph G> requires std::is_default_constructible_v<G>
fishnet::util::forward_range_of< G > auto	subgraphs (const G &graph)
	Find all subgraphs in the given graph.

Function Documentation

connectedComponents() [1/4]

template<Graph G>

auto fishnet::graph::BFS::connectedComponents

(

const G &

graph

)

Compute connected components of the graph\ Uses DefaultBiPredicate which is always true, when two nodes share an edge.

Template Parameters

G	graph type

Parameters

graph

graph

Returns

ConnectedComponents search result

connectedComponents() [2/4]

template<Graph G>

auto fishnet::graph::BFS::connectedComponents	(	const G &	graph,
		fishnet::util::BiPredicate< typename G::node_type > auto const &	inRelation
	)

Compute connected components of the graph.

Template Parameters

G	graph type

Parameters

graph	graph
inRelation	BiPredicate indicating whether two nodes are in relation

Returns

ConnectedComponents search result

connectedComponents() [3/4]

template<Graph G>

auto fishnet::graph::BFS::connectedComponents	(	const G &	graph,
		std::shared_ptr< fishnet::util::BlockingQueue< std::pair< int, std::vector< typename G::node_type > > > >	queue
	)

Compute connected components of the graph concurrently.

Template Parameters

G	graph type

Parameters

graph	graph
queue	shared pointer to blocking queue, storing pairs of component-ids and vectors of nodes

Returns

ConcurrentConnectedComponents search result

connectedComponents() [4/4]

template<Graph G>

auto fishnet::graph::BFS::connectedComponents	(	const G &	graph,
		std::shared_ptr< fishnet::util::BlockingQueue< std::pair< int, std::vector< typename G::node_type > > > >	queue,
		fishnet::util::BiPredicate< typename G::node_type > auto const &	inRelation
	)

Compute connected components of the graph concurrently.

Template Parameters

G	graph type

Parameters

graph	graph
queue	shared pointer to blocking queue, storing pairs of component-ids and vectors of nodes
inRelation	BiPredicate indicating whether two nodes are in relation

Returns

ConcurrentConnectedComponents search result

findPath()

template<Graph G>

auto fishnet::graph::BFS::findPath	(	const G &	graph,
		const typename G::node_type &	start,
		const typename G::node_type &	goal
	)

Find breadth-first search between between start and goal node.

Template Parameters

G	graph type

Parameters

graph	graph
start	start node
goal	target node

Returns

util::input_range_of<typename G::edge_type> vector of edges from start to target

getPath()

template<Graph G>

util::input_range_of< typename G::edge_type > auto fishnet::graph::BFS::getPath	(	const G &	graph,
		const typename G::node_type &	start,
		const typename G::node_type &	goal
	)

Find breadth-first search between between start and goal node.

Template Parameters

G	graph type

Parameters

graph	graph
start	start node
goal	target node

Returns

util::input_range_of<typename G::edge_type> vector of edges from start to target

neighborhood() [1/3]

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

G fishnet::graph::BFS::neighborhood	(	const G &	graph,
		const typename G::node_type &	node,
		size_t	order
	)

neighborhood() [2/3]

template<Graph G>
requires (!std::is_default_constructible_v<G> && std::is_copy_constructible_v<G>)

G fishnet::graph::BFS::neighborhood	(	const G &	graph,
		const typename G::node_type &	node,
		size_t	order
	)

neighborhood() [3/3]

template<Graph G, Graph O>
requires std::same_as<typename G::node_type, typename O::node_type>

G fishnet::graph::BFS::neighborhood	(	const G &	graph,
		const typename G::node_type &	node,
		size_t	order,
		O &&	outputGraph
	)

subgraphs() [1/2]

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

fishnet::util::forward_range_of< G > auto fishnet::graph::BFS::subgraphs

(

const G &

graph

)

Find all subgraphs in the given graph.

Template Parameters

G

Parameters

graph

input graph

Returns

fishnet::util::forward_range_of<G> range of subgraphs of type G

subgraphs() [2/2]

template<Graph G, typename P , typename R = std::invoke_result_t<std::decay_t<P>>>
requires std::same_as<typename G::node_type, typename R::node_type>

fishnet::util::forward_range_of< R > auto fishnet::graph::BFS::subgraphs	(	const G &	graph,
		P &&	emptyGraphProducer
	)

Find all subgraphs in the given graph.

Template Parameters

G

Parameters

graph	input graph
emptyGraphProducer	producer function to create an empty graph of type G

Returns

fishnet::util::forward_range_of<G> range of subgraphs of type G