tpl_graph_utils.H File Reference

Utility algorithms and operations for graphs. More...

#include <ah-graph-concepts.H>
#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<AlephGraph 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<AlephGraph 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<AlephGraph GT>
size_t	Aleph::depth_first_traversal (const GT &g, bool(*visit)(const GT &, typename GT::Node *, typename GT::Arc *))
template<AlephGraph 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<AlephGraph GT>
size_t	Aleph::breadth_first_traversal (GT &g, bool(*visit)(const GT &, typename GT::Node *, typename GT::Arc *))
template<AlephGraph 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<AlephGraph GT>
bool	Aleph::test_connectivity (const GT &g)
	Connectivity test for undirected graphs.
template<AlephGraph GT>
static bool	Aleph::__test_cycle (const GT &g, typename GT::Node *, typename GT::Node *)
	Internal helper used by test_for_cycle().
template<AlephGraph GT>
bool	Aleph::test_for_cycle (const GT &g, typename GT::Node *src)
	Search for a cycle reachable from a given node.
template<AlephGraph GT>
static bool	Aleph::__is_graph_acyclique (const GT &g, typename GT::Node *curr_node)
	Internal DFS used by is_graph_acyclique().
template<AlephGraph GT>
bool	Aleph::is_graph_acyclique (const GT &g, typename GT::Node *start_node)
	Return true if an undirected graph is acyclic.
template<AlephGraph GT>
bool	Aleph::is_graph_acyclique (const GT &g)
	Return true if an undirected graph is acyclic.
template<AlephGraph GT>
bool	Aleph::has_cycle (const GT &g)
	Return true if an undirected graph has at least one cycle.
template<AlephGraph 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<AlephGraph 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<AlephGraph GT>
DynList< GT >	Aleph::inconnected_components (const GT &g)
	Forward declaration for inconnected_components().
template<AlephGraph 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<AlephGraph 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<AlephGraph 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<AlephGraph GT>
GT	Aleph::find_depth_first_spanning_tree (const GT &g)
template<AlephGraph 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<AlephGraph 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<AlephGraph GT>
static long &	Aleph::df (typename GT::Node *p)
	Internal helper: DFS discovery time stored in NODE_COUNTER(p).
template<AlephGraph GT>
static long &	Aleph::low (typename GT::Node *p)
	Internal helper: low-link value stored directly in NODE_COOKIE(p).
template<AlephGraph 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<AlephGraph 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<AlephGraph GT>
DynList< typename GT::Node * >	Aleph::compute_cut_nodes (const GT &g)
template<AlephGraph 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<AlephGraph GT>
static bool	Aleph::is_a_cut_node (typename GT::Node *p)
	Return true if the node is marked as an articulation point.
template<AlephGraph 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<AlephGraph GT>
static bool	Aleph::is_node_painted (typename GT::Node *p)
	Return true if the node has a positive color.
template<AlephGraph GT>
static bool	Aleph::is_arc_painted (typename GT::Arc *arc)
	Return true if the arc has a positive color.
template<AlephGraph GT>
static void	Aleph::paint_node (typename GT::Node *p, const long &color)
	Set the node color (stored in NODE_COUNTER).
template<AlephGraph GT>
static void	Aleph::paint_arc (typename GT::Arc *a, const long &color)
	Set the arc color (stored in ARC_COUNTER).
template<AlephGraph GT>
static const long &	Aleph::get_color (typename GT::Node *p)
	Return the node color (stored in NODE_COUNTER).
template<AlephGraph GT>
static const long &	Aleph::get_color (typename GT::Arc *a)
	Return the arc color (stored in ARC_COUNTER).
template<AlephGraph 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<AlephGraph 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<AlephGraph GT>
long	Aleph::paint_subgraphs (const GT &g, const DynList< typename GT::Node * > &cut_node_list)
	Paint connected blocks around articulation points.
template<AlephGraph 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<AlephGraph GT>
GT	Aleph::map_subgraph (const GT &g, const long color)
	Extract a mapped subgraph containing a given color.
template<AlephGraph 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<AlephGraph GT>
GT	Aleph::invert_digraph (const GT &g)
	Compute the transpose (arc-reversed) digraph.
template<AlephGraph GT, ArcFilter< GT > 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<AlephGraph GT, ArcDistance< GT > 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.