Bidirectional BFS for finding shortest unweighted paths. More...

#include <Bidirectional_BFS.H>

Collaboration diagram for Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >:

Classes
struct	BFS_Info

class	BiBFS_Init_Guard
	RAII guard for BiBFS initialization and cleanup. More...

Public Types
using	Node = typename GT::Node

using	Arc = typename GT::Arc

Public Member Functions
	Bidirectional_BFS (SA __sa=SA())
	Constructor.

	Bidirectional_BFS (SA &__sa)
	Constructor with lvalue arc filter.

bool	find_path (const GT &g, Node start, Node end, Path< GT > &path)
	Finds the shortest unweighted path between start and end.

bool	operator() (const GT &g, Node start, Node end, Path< GT > &path)
	Finds shortest path (operator interface with path output).

Path< GT >	operator() (const GT &g, Node start, Node end)
	Finds shortest path (operator interface returning path).

Private Member Functions
void	init (const GT &g)

void	cleanup (const GT &g)

bool	is_seen (Node *p, const int dir) const noexcept

void	mark_seen (Node *p, const int dir) noexcept

size_t	get_dist (Node *p, const int dir) const noexcept

void	set_dist (Node *p, const int dir, const size_t d) noexcept

Node *&	parent_ref (Node *p, const int dir) noexcept

Arc *&	parent_arc_ref (Node *p, const int dir) noexcept

template<template< typename, class > class Itor>
void	expand_frontier (const GT &g, DynListQueue< Node * > &frontier, const int my_dir, const int other_dir, size_t &best_len, Node *&best_meeting)

void	build_path (const GT &g, Node start, Node meeting, Node *end, Path< GT > &path)

Private Attributes
SA	sa

Static Private Attributes
static constexpr int	UNSEEN = 0

static constexpr int	FORWARD = 1

static constexpr int	BACKWARD = 2

static constexpr size_t	INF_DIST = std::numeric_limits<size_t>::max()

Detailed Description

template<class GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>
class Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >

Bidirectional BFS for finding shortest unweighted paths.

This class finds the shortest path (in terms of number of edges) between two nodes by simultaneously running BFS from both the source and the target. The search terminates when the two frontiers meet.

For undirected graphs, both iterators default to Node_Arc_Iterator. For directed graphs, use Out_Iterator for forward and In_Iterator for backward traversal.

The class receives the following template parameters:

GT: graph type.
Fwd_Itor: arc iterator for forward expansion (from start).
Bck_Itor: arc iterator for backward expansion (from end).
SA: arc filter for internal iterators.

Note: This algorithm finds shortest paths in terms of edge count (unweighted). For weighted shortest paths, use Dijkstra or A*.

Warning: This class is not thread-safe.

See also: Find_Path_Breadth_First For standard (unidirectional) BFS.; Dijkstra_Min_Paths For weighted shortest paths.

Definition at line 116 of file Bidirectional_BFS.H.

Member Typedef Documentation

◆ Arc

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

using Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::Arc = typename GT::Arc

Definition at line 120 of file Bidirectional_BFS.H.

◆ Node

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

using Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::Node = typename GT::Node

Definition at line 119 of file Bidirectional_BFS.H.

Constructor & Destructor Documentation

◆ Bidirectional_BFS() [1/2]

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::Bidirectional_BFS ( SA __sa = SA() )

inline

Constructor.

Parameters

[in] __sa Arc filter for iterators.

Definition at line 342 of file Bidirectional_BFS.H.

◆ Bidirectional_BFS() [2/2]

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::Bidirectional_BFS ( SA & __sa )

inline

Constructor with lvalue arc filter.

Parameters

[in] __sa Arc filter for iterators.

Definition at line 348 of file Bidirectional_BFS.H.

Member Function Documentation

◆ build_path()

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::build_path	(	const GT &	g,
		Node *	start,
		Node *	meeting,
		Node *	end,
		Path< GT > &	path
	)

inlineprivate

Definition at line 299 of file Bidirectional_BFS.H.

References ah_runtime_error_if, Aleph::Path< GT >::append(), BIBFS_BCK_PARC, BIBFS_BCK_PARENT, BIBFS_FWD_PARC, BIBFS_FWD_PARENT, Aleph::divide_and_conquer_partition_dp(), Aleph::Path< GT >::empty(), Aleph::DynList< T >::insert(), and Aleph::Path< GT >::set_graph().

Referenced by Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::find_path().

◆ cleanup()

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::cleanup ( const GT & g )

inlineprivate

Definition at line 204 of file Bidirectional_BFS.H.

References BIBFS_INFO, and NODE_COOKIE.

Referenced by Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::BiBFS_Init_Guard::~BiBFS_Init_Guard(), and Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::init().

◆ expand_frontier()

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

template<template< typename, class > class Itor>

void Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::expand_frontier	(	const GT &	g,
		DynListQueue< Node * > &	frontier,
		const int	my_dir,
		const int	other_dir,
		size_t &	best_len,
		Node *&	best_meeting
	)

inlineprivate

Definition at line 252 of file Bidirectional_BFS.H.

◆ find_path()

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

bool Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::find_path	(	const GT &	g,
		Node *	start,
		Node *	end,
		Path< GT > &	path
	)

inline

Finds the shortest unweighted path between start and end.

Performs bidirectional BFS by expanding one complete frontier level at a time. At each iteration the smaller frontier is expanded (Fwd_Itor from start or Bck_Itor from end). Meeting detection uses forward/backward distance maps and stops only when no shorter meeting point can still exist.

Parameters

[in]	g	The graph.
[in]	start	The starting node.
[in]	end	The destination node.
[out]	path	The shortest path (empty if no path exists).

Returns: true if a path was found, false otherwise.

Exceptions

domain_error	If start or end is nullptr, or g is empty.
bad_alloc	If there is not enough memory.

Note: Time complexity: O(b^(d/2)) where b is branching factor, d is the shortest path length.

Definition at line 369 of file Bidirectional_BFS.H.

References ah_domain_error_if, Aleph::and, Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::BACKWARD, Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::build_path(), Aleph::divide_and_conquer_partition_dp(), Aleph::Path< GT >::empty(), Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::FORWARD, GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::INF_DIST, Aleph::init, Aleph::lower_bound(), Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::mark_seen(), Aleph::DynListQueue< T >::put(), Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::set_dist(), and Aleph::Path< GT >::set_graph().

Referenced by Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::operator()(), and Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::operator()().

◆ get_dist()

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

size_t Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::get_dist	(	Node *	p,
		const int	dir
	)		const

inlineprivatenoexcept

Definition at line 224 of file Bidirectional_BFS.H.

References BIBFS_BCK_DIST, BIBFS_FWD_DIST, and Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::FORWARD.

Referenced by Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::expand_frontier().

◆ init()

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::init ( const GT & g )

inlineprivate

Definition at line 184 of file Bidirectional_BFS.H.

References Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::cleanup(), and NODE_COOKIE.

◆ is_seen()

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

bool Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::is_seen	(	Node *	p,
		const int	dir
	)		const

inlineprivatenoexcept

Definition at line 214 of file Bidirectional_BFS.H.

References BIBFS_DIR.

Referenced by Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::expand_frontier().

◆ mark_seen()

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::mark_seen	(	Node *	p,
		const int	dir
	)

inlineprivatenoexcept

Definition at line 219 of file Bidirectional_BFS.H.

References BIBFS_DIR.

Referenced by Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::expand_frontier(), and Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::find_path().

◆ operator()() [1/2]

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Path< GT > Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::operator()	(	const GT &	g,
		Node *	start,
		Node *	end
	)

inline

Finds shortest path (operator interface returning path).

Parameters

[in]	g	The graph.
[in]	start	The starting node.
[in]	end	The destination node.

Returns: The shortest path (empty if no path exists).

Definition at line 457 of file Bidirectional_BFS.H.

References Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::find_path().

◆ operator()() [2/2]

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

bool Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::operator()	(	const GT &	g,
		Node *	start,
		Node *	end,
		Path< GT > &	path
	)

inline

Finds shortest path (operator interface with path output).

Parameters

[in]	g	The graph.
[in]	start	The starting node.
[in]	end	The destination node.
[out]	path	The shortest path.

Returns: true if a path was found, false otherwise.

Definition at line 445 of file Bidirectional_BFS.H.

References Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::find_path().

◆ parent_arc_ref()

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Arc *& Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::parent_arc_ref	(	Node *	p,
		const int	dir
	)

inlineprivatenoexcept

Definition at line 244 of file Bidirectional_BFS.H.

References BIBFS_BCK_PARC, BIBFS_FWD_PARC, and Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::FORWARD.

Referenced by Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::expand_frontier().

◆ parent_ref()

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Node *& Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::parent_ref	(	Node *	p,
		const int	dir
	)

inlineprivatenoexcept

Definition at line 237 of file Bidirectional_BFS.H.

References BIBFS_BCK_PARENT, BIBFS_FWD_PARENT, and Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::FORWARD.

Referenced by Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::expand_frontier().

◆ set_dist()

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::set_dist	(	Node *	p,
		const int	dir,
		const size_t	d
	)

inlineprivatenoexcept

Definition at line 229 of file Bidirectional_BFS.H.

References BIBFS_BCK_DIST, BIBFS_FWD_DIST, and Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::FORWARD.

Referenced by Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::expand_frontier(), and Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::find_path().

Member Data Documentation

◆ BACKWARD

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

constexpr int Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::BACKWARD = 2

staticconstexprprivate

Definition at line 128 of file Bidirectional_BFS.H.

Referenced by Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::find_path().

◆ FORWARD

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

constexpr int Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::FORWARD = 1

staticconstexprprivate

Definition at line 127 of file Bidirectional_BFS.H.

Referenced by Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::find_path(), Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::get_dist(), Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::parent_arc_ref(), Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::parent_ref(), and Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::set_dist().

◆ INF_DIST

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

constexpr size_t Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::INF_DIST = std::numeric_limits<size_t>::max()

staticconstexprprivate

Definition at line 129 of file Bidirectional_BFS.H.

Referenced by Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::expand_frontier(), and Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::find_path().

◆ sa

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

SA Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::sa

private

Definition at line 123 of file Bidirectional_BFS.H.

Referenced by Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::expand_frontier().

◆ UNSEEN

template<class GT , template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

constexpr int Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::UNSEEN = 0

staticconstexprprivate

Definition at line 126 of file Bidirectional_BFS.H.

The documentation for this class was generated from the following file:

Bidirectional_BFS.H

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ Arc

◆ Node

Constructor & Destructor Documentation

◆ Bidirectional_BFS() [1/2]

◆ Bidirectional_BFS() [2/2]

Member Function Documentation

◆ build_path()

◆ cleanup()

◆ expand_frontier()

◆ find_path()

◆ get_dist()

◆ init()

◆ is_seen()

◆ mark_seen()

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ parent_arc_ref()

◆ parent_ref()

◆ set_dist()

Member Data Documentation

◆ BACKWARD

◆ FORWARD

◆ INF_DIST

◆ sa

◆ UNSEEN