Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Private Member Functions | Private Attributes | Static Private Attributes | List of all members
Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA > Class Template Reference
Graphs

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

#include <Bidirectional_BFS.H>

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

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<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > 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:

  1. GT: graph type.
  2. Fwd_Itor: arc iterator for forward expansion (from start).
  3. Bck_Itor: arc iterator for backward expansion (from end).
  4. 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 118 of file Bidirectional_BFS.H.

Member Typedef Documentation

◆ Arc

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

Definition at line 122 of file Bidirectional_BFS.H.

◆ Node

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

Definition at line 121 of file Bidirectional_BFS.H.

Constructor & Destructor Documentation

◆ Bidirectional_BFS() [1/2]

template<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::Bidirectional_BFS ( SA  __sa = SA())
inline

Constructor.

Parameters
[in]__saArc filter for iterators.

Definition at line 344 of file Bidirectional_BFS.H.

◆ Bidirectional_BFS() [2/2]

template<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > 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]__saArc filter for iterators.

Definition at line 350 of file Bidirectional_BFS.H.

Member Function Documentation

◆ build_path()

template<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > 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 301 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::blossom_maximum_cardinality_matching(), 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<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
void Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::cleanup ( const GT &  g)
inlineprivate

Definition at line 206 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<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > 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 254 of file Bidirectional_BFS.H.

References Aleph::and, Aleph::blossom_maximum_cardinality_matching(), Aleph::DynListQueue< T >::get(), GraphCommon< GT, Node, Arc >::get_connected_node(), Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::get_dist(), Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::INF_DIST, Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::is_seen(), Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::mark_seen(), Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::parent_arc_ref(), Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::parent_ref(), Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::sa, and Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::set_dist().

◆ find_path()

template<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > 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]gThe graph.
[in]startThe starting node.
[in]endThe destination node.
[out]pathThe shortest path (empty if no path exists).
Returns
true if a path was found, false otherwise.
Exceptions
domain_errorIf start or end is nullptr, or g is empty.
bad_allocIf 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 371 of file Bidirectional_BFS.H.

References ah_domain_error_if, Aleph::and, Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::BACKWARD, Aleph::blossom_maximum_cardinality_matching(), Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::build_path(), 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<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > 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 226 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<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
void Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::init ( const GT &  g)
inlineprivate

Definition at line 186 of file Bidirectional_BFS.H.

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

◆ is_seen()

template<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > 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 216 of file Bidirectional_BFS.H.

References BIBFS_DIR.

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

◆ mark_seen()

template<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > 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 221 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<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > 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]gThe graph.
[in]startThe starting node.
[in]endThe destination node.
Returns
The shortest path (empty if no path exists).

Definition at line 459 of file Bidirectional_BFS.H.

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

◆ operator()() [2/2]

template<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > 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]gThe graph.
[in]startThe starting node.
[in]endThe destination node.
[out]pathThe shortest path.
Returns
true if a path was found, false otherwise.

Definition at line 447 of file Bidirectional_BFS.H.

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

◆ parent_arc_ref()

template<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > 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 246 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<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > 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 239 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<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > 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 231 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<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
constexpr int Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::BACKWARD = 2
staticconstexprprivate

Definition at line 130 of file Bidirectional_BFS.H.

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

◆ FORWARD

template<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
constexpr int Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::FORWARD = 1
staticconstexprprivate

Definition at line 129 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<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > 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 131 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<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
SA Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::sa
private

Definition at line 125 of file Bidirectional_BFS.H.

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

◆ UNSEEN

template<AlephGraph GT, template< typename, class > class Fwd_Itor = Node_Arc_Iterator, template< typename, class > class Bck_Itor = Node_Arc_Iterator, ArcFilter< GT > SA = Dft_Show_Arc<GT>>
constexpr int Aleph::Bidirectional_BFS< GT, Fwd_Itor, Bck_Itor, SA >::UNSEEN = 0
staticconstexprprivate

Definition at line 128 of file Bidirectional_BFS.H.

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