tpl_graph_utils.H File Reference

Utility algorithms and operations for graphs. More...

#include <cassert>
#include <cstddef>
#include <limits>
#include <memory>
#include <tuple>
#include <utility>
#include <vector>
#include <tpl_agraph.H>
#include <tpl_dynListQueue.H>
#include <ah-errors.H>

Include dependency graph for tpl_graph_utils.H:

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

Go to the source code of this file.

Classes
struct	Aleph::Default_Visit_Op< GT >
	Default visit operation for traversals (never stops). More...
class	Aleph::Depth_First_Traversal< GT, Operation, SA >
	Stateful depth-first traversal functor. More...
class	Aleph::Breadth_First_Traversal< GT, Operation, SA >
	Stateful breadth-first traversal functor. More...
struct	Aleph::Distance_Compare< GT, Distance >
	Comparison functor for arc weights/distances. More...
class	Aleph::Invert_Digraph< GT, SA >
	Functor for computing the transposed digraph, filtering arcs. More...
class	Aleph::Dft_Dist< GT >
	Default distance accessor for arc weights. More...
class	Aleph::Total_Cost< GT, Distance, SA >
	Compute the total cost (sum of arc weights) of a graph. More...

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

Functions
template<class GT >
static bool	Aleph::__depth_first_traversal (const GT &g, typename GT::Node *node, typename GT::Arc *arc, bool(*visit)(const GT &g, typename GT::Node *, typename GT::Arc *), size_t &count)
	Internal recursive DFS used by depth_first_traversal().
template<class GT >
size_t	Aleph::depth_first_traversal (const GT &g, typename GT::Node *start_node, bool(*visit)(const GT &g, typename GT::Node *, typename GT::Arc *))
	Depth-first traversal starting from a given node.
template<class GT >
size_t	Aleph::depth_first_traversal (const GT &g, bool(*visit)(const GT &, typename GT::Node *, typename GT::Arc *))
template<class GT >
size_t	Aleph::breadth_first_traversal (const GT &g, typename GT::Node *start, bool(*visit)(const GT &, typename GT::Node *, typename GT::Arc *))
	Breadth-first traversal starting from a given node.
template<class GT >
size_t	Aleph::breadth_first_traversal (GT &g, bool(*visit)(const GT &, typename GT::Node *, typename GT::Arc *))
template<class GT >
Path< GT >	Aleph::find_path_breadth_first (const GT &g, typename GT::Node *start, typename GT::Node *end)
	Breadth-first search of a (shortest-by-edges) path between two nodes.
template<class GT >
bool	Aleph::test_connectivity (const GT &g)
	Connectivity test for undirected graphs.
template<class GT >
static bool	Aleph::__test_cycle (const GT &g, typename GT::Node *, typename GT::Node *)
	Internal helper used by test_for_cycle().
template<class GT >
bool	Aleph::test_for_cycle (const GT &g, typename GT::Node *src)
	Search for a cycle reachable from a given node.
template<class GT >
static bool	Aleph::__is_graph_acyclique (const GT &g, typename GT::Node *curr_node)
	Internal DFS used by is_graph_acyclique().
template<class GT >
bool	Aleph::is_graph_acyclique (const GT &g, typename GT::Node *start_node)
	Return true if an undirected graph is acyclic.
template<class GT >
bool	Aleph::is_graph_acyclique (const GT &g)
	Return true if an undirected graph is acyclic.
template<class GT >
bool	Aleph::has_cycle (const GT &g)
	Return true if an undirected graph has at least one cycle.
template<class GT >
bool	Aleph::test_for_path (const GT &g, typename GT::Node *start_node, typename GT::Node *end_node)
	Return true if there is a path between two nodes.
template<class GT >
static bool	Aleph::__test_for_path (const GT &g, typename GT::Node *curr_node, typename GT::Node *end_node)
	Internal recursive DFS used by test_for_path().
template<class GT >
DynList< GT >	Aleph::inconnected_components (const GT &g)
	Forward declaration for inconnected_components().
template<class GT >
void	Aleph::build_subgraph (const GT &g, GT &sg, typename GT::Node *g_src, size_t &node_count)
	Forward declaration for build_subgraph().
template<class GT >
static bool	Aleph::__find_depth_first_spanning_tree (const GT &g, typename GT::Node *gnode, typename GT::Arc *garc, GT &tree, typename GT::Node *tnode)
	Internal recursive DFS used by find_depth_first_spanning_tree().
template<class GT >
GT	Aleph::find_depth_first_spanning_tree (const GT &g, typename GT::Node *gnode)
	Build a depth-first spanning tree (mapped to the original graph).
template<class GT >
GT	Aleph::find_depth_first_spanning_tree (const GT &g)
template<class GT >
GT	Aleph::find_breadth_first_spanning_tree (GT &g, typename GT::Node *gp)
	Build a breadth-first spanning tree (mapped to the original graph).
template<class GT >
GT	Aleph::build_spanning_tree (const DynArray< typename GT::Arc * > &arcs)
	Build a graph from a list of arcs (typically a spanning tree).
template<class GT >
static long &	Aleph::df (typename GT::Node *p)
	Internal helper: DFS discovery time stored in NODE_COUNTER(p).
template<class GT >
static long &	Aleph::low (typename GT::Node *p)
	Internal helper: low-link value stored directly in NODE_COOKIE(p).
template<class GT >
static void	Aleph::__compute_cut_nodes (const GT &g, DynList< typename GT::Node * > &list, typename GT::Node *p, typename GT::Arc *a, long &curr_df)
	Internal DFS step used by compute_cut_nodes().
template<class GT >
DynList< typename GT::Node * >	Aleph::compute_cut_nodes (const GT &g, typename GT::Node *start)
	Compute articulation points (cut vertices) of an undirected graph.
template<class GT >
DynList< typename GT::Node * >	Aleph::compute_cut_nodes (const GT &g)
template<class GT >
static bool	Aleph::is_a_cross_arc (typename GT::Arc *a)
	Return true if the arc is marked as a cross-arc by paint_subgraphs().
template<class GT >
static bool	Aleph::is_a_cut_node (typename GT::Node *p)
	Return true if the node is marked as an articulation point.
template<class GT >
static bool	Aleph::is_an_cut_arc (typename GT::Arc *a)
	Return true if the arc is marked as a cut-arc (between cut nodes).
template<class GT >
static bool	Aleph::is_node_painted (typename GT::Node *p)
	Return true if the node has a positive color.
template<class GT >
static bool	Aleph::is_arc_painted (typename GT::Arc *arc)
	Return true if the arc has a positive color.
template<class GT >
static void	Aleph::paint_node (typename GT::Node *p, const long &color)
	Set the node color (stored in NODE_COUNTER).
template<class GT >
static void	Aleph::paint_arc (typename GT::Arc *a, const long &color)
	Set the arc color (stored in ARC_COUNTER).
template<class GT >
static const long &	Aleph::get_color (typename GT::Node *p)
	Return the node color (stored in NODE_COUNTER).
template<class GT >
static const long &	Aleph::get_color (typename GT::Arc *a)
	Return the arc color (stored in ARC_COUNTER).
template<class GT >
static void	Aleph::__paint_subgraph (const GT &g, typename GT::Node *p, long current_color)
	Internal DFS that paints a non-cut block with current_color.
template<class GT >
static void	Aleph::__paint_from_cut_node (const GT &g, typename GT::Node *p, long &current_color)
	Internal step that paints all blocks adjacent to a cut node.
template<class GT >
long	Aleph::paint_subgraphs (const GT &g, const DynList< typename GT::Node * > &cut_node_list)
	Paint connected blocks around articulation points.
template<class GT >
static void	Aleph::__map_subgraph (const GT &g, GT &sg, typename GT::Node *gsrc, const long color)
	Internal recursive step used by map_subgraph().
template<class GT >
GT	Aleph::map_subgraph (const GT &g, const long color)
	Extract a mapped subgraph containing a given color.
template<class GT >
std::tuple< GT, DynList< typename GT::Arc * > >	Aleph::map_cut_graph (const GT &g, const DynList< typename GT::Node * > &cut_node_list)
	Extract the cut graph and cross-arc list.
template<class GT >
GT	Aleph::invert_digraph (const GT &g)
	Compute the transpose (arc-reversed) digraph.
template<class GT , class SA = Dft_Show_Arc<GT>>
GT::Arc *	Aleph::search_spanning_tree_arc (const GT &g, typename GT::Node *src, typename GT::Node *tgt, SA sa=SA()) noexcept
	Helper to find the spanning tree arc between two nodes in a multigraph.
template<class GT , class Distance = Dft_Dist<GT>>
Distance::Distance_Type	Aleph::get_min_path (typename GT::Node *s, typename GT::Node *end, Path< GT > &path)

Variables
const long	Aleph::Cross_Arc = -1
	Special marker for arcs connecting a cut node to a non-cut block.

Detailed Description

Utility algorithms and operations for graphs.

This file provides a comprehensive collection of graph algorithms including traversals (BFS, DFS), path finding, connectivity tests, spanning trees, graph copying, and various utility functions for working with graphs.

Author

Leandro Rabindranath León

Definition in file tpl_graph_utils.H.