pathFinding.h File Reference

Generic BFS-based path-finding algorithms for aGrUM graphs. More...

#include <optional>
#include <vector>
#include <agrum/agrum.h>
#include <agrum/base/graphs/graphConcepts.h>
#include <agrum/base/graphs/algorithms/generic/pathFinding_tpl.h>

Include dependency graph for pathFinding.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces
namespace	gum
	gum is the global namespace for all aGrUM entities
namespace	gum::graph
namespace	gum::graph::detail

Functions
std::vector< NodeId >	gum::graph::detail::reconstructPath (const NodeProperty< NodeId > &mark, NodeId n1, NodeId n2)
	Reconstruct the BFS path [n1 … n2] from the predecessor mark table.
template<GUM_DiGraphable G>
std::optional< std::vector< NodeId > >	gum::graph::directedPath (const G &g, NodeId n1, NodeId n2)
	Shortest directed path from n1 to n2 (BFS, arc direction).
template<GUM_DiGraphable G>
std::optional< std::vector< NodeId > >	gum::graph::directedUnorientedPath (const G &g, NodeId n1, NodeId n2)
	Shortest path from n1 to n2 ignoring arc orientation (BFS).
template<GUM_DiGraphable G>
bool	gum::graph::hasDirectedPath (const G &g, NodeId from, NodeId to)
	Returns true if there is a directed path from from to to.
template<GUM_UndiGraphable G>
std::optional< std::vector< NodeId > >	gum::graph::undirectedPath (const G &g, NodeId n1, NodeId n2)
	Shortest undirected path from n1 to n2 (BFS).
template<GUM_UndiGraphable G>
bool	gum::graph::hasUndirectedPath (const G &g, NodeId n1, NodeId n2)
	Returns true if an undirected path exists between n1 and n2.
template<GUM_UndiGraphable G>
bool	gum::graph::hasUndirectedPath (const G &g, NodeId n1, NodeId n2, const NodeSet &except)
	Returns true if an undirected path from n1 to n2 exists that avoids all nodes in except.
template<GUM_UndiGraphable G>
bool	gum::graph::hasUndirectedPath (const G &g, const NodeSet &n1, const NodeSet &n2, const NodeSet &except)
	Returns true if an undirected path exists from any node in n1 to any node in n2, avoiding nodes in except.
template<GUM_MixedGraphable G>
std::optional< std::vector< NodeId > >	gum::graph::mixedOrientedPath (const G &g, NodeId n1, NodeId n2)
	Shortest mixed-oriented path from n1 to n2.
template<GUM_MixedGraphable G>
bool	gum::graph::hasMixedOrientedPath (const G &g, NodeId n1, NodeId n2)
	Returns true if a mixed-oriented path from n1 to n2 exists.
template<GUM_MixedGraphable G>
std::optional< std::vector< NodeId > >	gum::graph::mixedUnorientedPath (const G &g, NodeId n1, NodeId n2)
	Shortest path ignoring all orientations in a mixed graph.

Detailed Description

Generic BFS-based path-finding algorithms for aGrUM graphs.

All functions live in namespace gum::graph and are constrained by the concepts defined in graphConcepts.h :

GUM_DiGraphable — directed graphs (DiGraph, DAG, …) GUM_UndiGraphable — undirected graphs (UndiGraph, …) GUM_MixedGraphable — mixed graphs (MixedGraph, PDAG)

Class methods in DiGraph / UndiGraph / MixedGraph delegate to these free functions wherever the class satisfies the required concept.

Author

Pierre-Henri WUILLEMIN(_at_LIP6) and Christophe GONZALES(_at_AMU)

Definition in file pathFinding.h.