0-1 BFS algorithm for shortest paths in graphs with 0/1 weights. More...

#include <Zero_One_BFS.H>

Collaboration diagram for Aleph::Zero_One_BFS< GT, Distance, Itor, SA >:

Classes
struct	Node_Info

struct	Painted_Info
	Stores parent and distance after painting for O(1) access. More...

class	ZOB_Init_Guard
	RAII guard for Zero_One_BFS initialization and cleanup. More...

Public Types
using	Distance_Type = typename Distance::Distance_Type

using	Node = typename GT::Node

using	Arc = typename GT::Arc

Public Member Functions
	Zero_One_BFS (Distance dist=Distance(), SA __sa=SA())
	Constructor.

	~Zero_One_BFS () noexcept
	Destructor.

bool	is_painted () const noexcept
	Check if a computation has been performed.

Node *	get_start_node () const noexcept
	Get the start node of the last computation.

GT *	get_graph () const noexcept
	Get the graph of the last computation.

void	paint_min_paths_tree (const GT &g, Node *start)
	Paints the shortest paths tree on the graph from start.

Distance_Type	get_distance (Node *node)
	Gets the accumulated distance to a node after painting.

Distance_Type	get_min_path (Node *end, Path< GT > &path)
	Extracts a shortest path from a previously painted graph.

Distance_Type	find_min_path (const GT &g, Node start, Node end, Path< GT > &path)
	Computes the shortest path from start to end.

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

Private Member Functions
void	release_owned_node_infos () noexcept

void	release_owned_painted_infos () noexcept

void	reset_state_after_failure () noexcept

void	init (const GT &g)

void	uninit_paint ()

void	uninit_discard ()

void	run_bfs (const GT &g, Node start, Node end=nullptr)

Private Attributes
SA	sa

Distance	distance

bool	painted = false

GT *	ptr_g = nullptr

Node *	s = nullptr

DynList< std::pair< Node , Node_Info > >	owned_node_infos

DynList< std::pair< Node , Painted_Info > >	owned_painted_infos

Static Private Attributes
static constexpr Distance_Type	Inf

Detailed Description

template<class GT, class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>
class Aleph::Zero_One_BFS< GT, Distance, Itor, SA >

0-1 BFS algorithm for shortest paths in graphs with 0/1 weights.

This class computes shortest paths in graphs where every edge weight is either 0 or 1. It uses a deque-based BFS that runs in O(V + E) time, which is asymptotically faster than Dijkstra's O((V + E) log V) for this special case.

The algorithm works by maintaining a deque of nodes. When relaxing an edge with weight 0, the target is pushed to the front of the deque; when relaxing an edge with weight 1, the target is pushed to the back. This ensures nodes are always processed in non-decreasing order of distance.

The class receives the following template parameters:

GT: graph type (List_Graph, List_SGraph, Array_Graph, etc.).
Distance: class reading the weight from an arc. Must export Distance_Type and operator()(Arc*).
Itor: arc iterator template (defaults to Node_Arc_Iterator).
SA: arc filter for internal iterators.

Warning: All arc weights must be exactly 0 or 1. A domain_error is thrown if any other weight is encountered.

Note: This algorithm works for both directed and undirected graphs.

See also: Dijkstra_Min_Paths For general non-negative weights.; Dial_Min_Paths For small integer weights.

Definition at line 129 of file Zero_One_BFS.H.

Member Typedef Documentation

◆ Arc

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

using Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::Arc = typename GT::Arc

Definition at line 134 of file Zero_One_BFS.H.

◆ Distance_Type

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

using Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::Distance_Type = typename Distance::Distance_Type

Definition at line 132 of file Zero_One_BFS.H.

◆ Node

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

using Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::Node = typename GT::Node

Definition at line 133 of file Zero_One_BFS.H.

Constructor & Destructor Documentation

◆ Zero_One_BFS()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::Zero_One_BFS	(	Distance	dist = `Distance()`,
		SA	__sa = `SA()`
	)

inline

Constructor.

Parameters

[in]	dist	Distance functor for arc weights.
[in]	__sa	Arc filter for iterators.

Definition at line 398 of file Zero_One_BFS.H.

◆ ~Zero_One_BFS()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::~Zero_One_BFS ( )

inlinenoexcept

Destructor.

Releases any per-node data left in NODE_COOKIE by the last computation so sanitizers do not report leaks.

Definition at line 409 of file Zero_One_BFS.H.

References Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::reset_state_after_failure(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::uninit_discard().

Member Function Documentation

◆ find_min_path()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance_Type Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::find_min_path	(	const GT &	g,
		Node *	start,
		Node *	end,
		Path< GT > &	path
	)

inline

Computes the shortest path from start to end.

Paints the graph (stopping early when end is found) and extracts the path. This is the recommended entry point for single-target queries.

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: The total cost, or max value if no path exists.

Exceptions

domain_error	If start or end is nullptr, g is empty, or any arc weight is not 0 or 1.
bad_alloc	If there is not enough memory.

Note: Time complexity: O(V + E)

Definition at line 589 of file Zero_One_BFS.H.

Referenced by Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::operator()().

◆ get_distance()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance_Type Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_distance ( Node * node )

inline

Gets the accumulated distance to a node after painting.

Parameters

[in] node The destination node.

Returns: The shortest distance from start to node.

Exceptions

domain_error If the graph has not been painted, node is null, or node is not reachable from the start.

Note: Time complexity: O(path_length)

Definition at line 473 of file Zero_One_BFS.H.

References ah_domain_error_if, Aleph::and, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::distance, Aleph::divide_and_conquer_partition_dp(), GraphCommon< GT, Node, Arc >::get_connected_node(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::Inf, IS_ARC_VISITED, IS_NODE_VISITED, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::painted, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::ptr_g, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::s, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::sa, Aleph::Spanning_Tree, and ZOB_PNTD.

Referenced by TEST(), TEST(), TEST(), TEST(), and TEST().

◆ get_graph()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

GT * Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_graph ( ) const

inlinenoexcept

Get the graph of the last computation.

Returns: Pointer to the graph, or nullptr if no computation done.

Definition at line 428 of file Zero_One_BFS.H.

References Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::ptr_g.

Referenced by TEST().

◆ get_min_path()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance_Type Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_min_path	(	Node *	end,
		Path< GT > &	path
	)

inline

Extracts a shortest path from a previously painted graph.

Parameters

[in]	end	Destination node of the path.
[out]	path	Path where the shortest path will be stored.

Returns: The total cost of the path.

Exceptions

domain_error If the graph has not been painted.

Note: Time complexity: O(path_length)

Definition at line 523 of file Zero_One_BFS.H.

References ah_domain_error_if, Aleph::and, Aleph::Path< GT >::append(), arcs, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::distance, Aleph::divide_and_conquer_partition_dp(), Aleph::Path< GT >::empty(), GraphCommon< GT, Node, Arc >::get_connected_node(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::Inf, Aleph::DynList< T >::insert(), IS_ARC_VISITED, IS_NODE_VISITED, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::painted, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::ptr_g, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::s, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::sa, Aleph::Path< GT >::set_graph(), Aleph::Spanning_Tree, and ZOB_PNTD.

Referenced by Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::find_min_path(), and TEST().

◆ get_start_node()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Node * Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_start_node ( ) const

inlinenoexcept

Get the start node of the last computation.

Returns: Pointer to the start node, or nullptr if no computation done.

Definition at line 423 of file Zero_One_BFS.H.

References Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::s.

Referenced by TEST(), and TEST().

◆ init()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::init ( const GT & g )

inlineprivate

Definition at line 249 of file Zero_One_BFS.H.

References Aleph::divide_and_conquer_partition_dp(), NODE_COOKIE, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::owned_node_infos, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::ptr_g, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::release_owned_node_infos(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::release_owned_painted_infos(), GraphCommon< GT, Node, Arc >::reset_bit(), and Aleph::Spanning_Tree.

◆ is_painted()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

bool Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::is_painted ( ) const

inlinenoexcept

Check if a computation has been performed.

Returns: true if a graph has been painted, false otherwise.

Definition at line 418 of file Zero_One_BFS.H.

References Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::painted.

Referenced by TEST(), and TEST().

◆ operator()()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance_Type Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::operator()	(	const GT &	g,
		Node *	start,
		Node *	end,
		Path< GT > &	path
	)

inline

Computes shortest path (operator interface).

Parameters

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

Returns: The total cost, or max value if no path exists.

Definition at line 626 of file Zero_One_BFS.H.

References Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::find_min_path().

◆ paint_min_paths_tree()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::paint_min_paths_tree	(	const GT &	g,
		Node *	start
	)

inline

Paints the shortest paths tree on the graph from start.

After calling this method, NODE_COOKIE(p) stores the parent node in the shortest path tree, and the Spanning_Tree bit is set on nodes and arcs that belong to the tree.

Parameters

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

Exceptions

domain_error	If start is nullptr, g is empty, or any arc weight is not 0 or 1.
bad_alloc	If there is not enough memory.

Note: Time complexity: O(V + E)

Definition at line 444 of file Zero_One_BFS.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::init, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::painted, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::ptr_g, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::run_bfs(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::s, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::uninit_discard(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::uninit_paint().

Referenced by main(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ release_owned_node_infos()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::release_owned_node_infos ( )

inlineprivatenoexcept

Definition at line 171 of file Zero_One_BFS.H.

References Aleph::divide_and_conquer_partition_dp(), NODE_COOKIE, and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::owned_node_infos.

Referenced by Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::init(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::uninit_discard(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::uninit_paint().

◆ release_owned_painted_infos()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::release_owned_painted_infos ( )

inlineprivatenoexcept

Definition at line 186 of file Zero_One_BFS.H.

References Aleph::divide_and_conquer_partition_dp(), NODE_COOKIE, and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::owned_painted_infos.

Referenced by Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::init(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::uninit_discard().

◆ reset_state_after_failure()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::reset_state_after_failure ( )

inlineprivatenoexcept

Definition at line 201 of file Zero_One_BFS.H.

References Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::painted, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::ptr_g, and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::s.

Referenced by Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::~Zero_One_BFS(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::ZOB_Init_Guard::~ZOB_Init_Guard().

◆ run_bfs()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::run_bfs	(	const GT &	g,
		Node *	start,
		Node *	end = `nullptr`
	)

inlineprivate

Definition at line 342 of file Zero_One_BFS.H.

References ah_domain_error_if, Aleph::and, ARC_BITS, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::distance, Aleph::divide_and_conquer_partition_dp(), GraphCommon< GT, Node, Arc >::get_connected_node(), NODE_BITS, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::sa, Aleph::Spanning_Tree, w, ZOB_DIST, ZOB_PARENT, and ZOB_PARENT_ARC.

Referenced by Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::find_min_path(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::paint_min_paths_tree().

◆ uninit_discard()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::uninit_discard ( )

inlineprivate

Definition at line 324 of file Zero_One_BFS.H.

References Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::ptr_g, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::release_owned_node_infos(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::release_owned_painted_infos(), GraphCommon< GT, Node, Arc >::reset_bit(), and Aleph::Spanning_Tree.

Referenced by Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::~Zero_One_BFS(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::ZOB_Init_Guard::~ZOB_Init_Guard(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::find_min_path(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::paint_min_paths_tree().

◆ uninit_paint()

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

void Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::uninit_paint ( )

inlineprivate

Definition at line 290 of file Zero_One_BFS.H.

References Aleph::DynList< T >::append(), Aleph::divide_and_conquer_partition_dp(), LocateFunctions< Container, Type >::get_it(), NODE_COOKIE, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::owned_painted_infos, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::Painted_Info::parent, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::ptr_g, Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::release_owned_node_infos(), and ZOB_INFO.

Referenced by Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::find_min_path(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::paint_min_paths_tree().

Member Data Documentation

◆ distance

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Distance Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::distance

private

Definition at line 138 of file Zero_One_BFS.H.

Referenced by Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_distance(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_min_path(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::run_bfs().

◆ Inf

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

constexpr Distance_Type Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::Inf

staticconstexprprivate

Initial value:

=

std::numeric_limits<Distance_Type>::max()

Definition at line 143 of file Zero_One_BFS.H.

Referenced by Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::find_min_path(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_distance(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_min_path().

◆ owned_node_infos

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

DynList<std::pair<Node *, Node_Info *> > Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::owned_node_infos

private

Definition at line 162 of file Zero_One_BFS.H.

Referenced by Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::init(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::release_owned_node_infos().

◆ owned_painted_infos

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

DynList<std::pair<Node *, Painted_Info *> > Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::owned_painted_infos

private

Definition at line 163 of file Zero_One_BFS.H.

Referenced by Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::release_owned_painted_infos(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::uninit_paint().

◆ painted

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

bool Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::painted = false

private

Definition at line 139 of file Zero_One_BFS.H.

Referenced by Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::find_min_path(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_distance(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_min_path(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::is_painted(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::paint_min_paths_tree(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::reset_state_after_failure().

◆ ptr_g

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

GT* Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::ptr_g = nullptr

private

Definition at line 140 of file Zero_One_BFS.H.

◆ s

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

Node* Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::s = nullptr

private

Definition at line 141 of file Zero_One_BFS.H.

Referenced by Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::find_min_path(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_distance(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_min_path(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_start_node(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::paint_min_paths_tree(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::reset_state_after_failure().

◆ sa

template<class GT , class Distance = Dft_Dist<GT>, template< typename, class > class Itor = Node_Arc_Iterator, class SA = Dft_Show_Arc<GT>>

SA Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::sa

private

Definition at line 137 of file Zero_One_BFS.H.

Referenced by Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_distance(), Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::get_min_path(), and Aleph::Zero_One_BFS< GT, Distance, Itor, SA >::run_bfs().

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

Zero_One_BFS.H

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Member Typedef Documentation

◆ Arc

◆ Distance_Type

◆ Node

Constructor & Destructor Documentation

◆ Zero_One_BFS()

◆ ~Zero_One_BFS()

Member Function Documentation

◆ find_min_path()

◆ get_distance()

◆ get_graph()

◆ get_min_path()

◆ get_start_node()

◆ init()

◆ is_painted()

◆ operator()()

◆ paint_min_paths_tree()

◆ release_owned_node_infos()

◆ release_owned_painted_infos()

◆ reset_state_after_failure()

◆ run_bfs()

◆ uninit_discard()

◆ uninit_paint()

Member Data Documentation

◆ distance

◆ Inf

◆ owned_node_infos

◆ owned_painted_infos

◆ painted

◆ ptr_g

◆ s

◆ sa