Bidirectional BFS for shortest unweighted path. More...

#include <limits>
#include <tpl_dynListQueue.H>
#include <tpl_graph_utils.H>
#include <ah-errors.H>

Include dependency graph for Bidirectional_BFS.H:

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

Classes
class	Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >
	Bidirectional BFS for finding shortest unweighted paths. More...

struct	Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::BFS_Info

class	Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::BiBFS_Init_Guard
	RAII guard for BiBFS initialization and cleanup. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Macros
#define	BIBFS_INFO(p) (static_cast<BFS_Info *>(NODE_COOKIE(p)))

#define	BIBFS_DIR(p) (BIBFS_INFO(p)->dir)

#define	BIBFS_FWD_PARENT(p) (BIBFS_INFO(p)->fwd_parent)

#define	BIBFS_BCK_PARENT(p) (BIBFS_INFO(p)->bck_parent)

#define	BIBFS_FWD_PARC(p) (BIBFS_INFO(p)->fwd_parent_arc)

#define	BIBFS_BCK_PARC(p) (BIBFS_INFO(p)->bck_parent_arc)

#define	BIBFS_FWD_DIST(p) (BIBFS_INFO(p)->fwd_dist)

#define	BIBFS_BCK_DIST(p) (BIBFS_INFO(p)->bck_dist)

Detailed Description

Bidirectional BFS for shortest unweighted path.

Implements bidirectional breadth-first search, which explores simultaneously from both the source and the target, meeting in the middle. This can be dramatically faster than standard BFS for large graphs, reducing the search space from O(b^d) to O(b^(d/2)).

How it works

Two BFS frontiers are maintained: one expanding from the start node (forward) and one expanding from the end node (backward). At each step, the smaller frontier is expanded. When a node is reached by both frontiers, the search terminates and the path is reconstructed by concatenating the forward path (start to meeting point) with the backward path (meeting point to end).

Complexity

Operation	Time	Space
Find path	O(b^(d/2))	O(b^(d/2))

where b is the branching factor and d is the path depth.

Directed graph support

For directed graphs, use Out_Iterator for forward search and In_Iterator for backward search:

Bidirectional_BFS<DGT, Out_Iterator, In_Iterator> bibfs;

See also: tpl_find_path.H For standard BFS/DFS path finding; Dijkstra.H For weighted shortest paths

Author: Leandro Rabindranath Leon

Definition in file Bidirectional_BFS.H.

Macro Definition Documentation

◆ BIBFS_BCK_DIST

#define BIBFS_BCK_DIST ( p ) (BIBFS_INFO(p)->bck_dist)

Definition at line 149 of file Bidirectional_BFS.H.

◆ BIBFS_BCK_PARC

#define BIBFS_BCK_PARC ( p ) (BIBFS_INFO(p)->bck_parent_arc)

Definition at line 147 of file Bidirectional_BFS.H.

◆ BIBFS_BCK_PARENT

#define BIBFS_BCK_PARENT ( p ) (BIBFS_INFO(p)->bck_parent)

Definition at line 145 of file Bidirectional_BFS.H.

◆ BIBFS_DIR

#define BIBFS_DIR ( p ) (BIBFS_INFO(p)->dir)

Definition at line 143 of file Bidirectional_BFS.H.

◆ BIBFS_FWD_DIST

#define BIBFS_FWD_DIST ( p ) (BIBFS_INFO(p)->fwd_dist)

Definition at line 148 of file Bidirectional_BFS.H.

◆ BIBFS_FWD_PARC

#define BIBFS_FWD_PARC ( p ) (BIBFS_INFO(p)->fwd_parent_arc)

Definition at line 146 of file Bidirectional_BFS.H.

◆ BIBFS_FWD_PARENT

#define BIBFS_FWD_PARENT ( p ) (BIBFS_INFO(p)->fwd_parent)

Definition at line 144 of file Bidirectional_BFS.H.

◆ BIBFS_INFO

#define BIBFS_INFO ( p ) (static_cast<BFS_Info *>(NODE_COOKIE(p)))

Definition at line 142 of file Bidirectional_BFS.H.

Classes

Namespaces

Macros