Graphs

Collaboration diagram for Graphs:

Modules
	C++20 Concepts for Graph Iterators
	These concepts define the interface contracts for Aleph-w graph iterators.

Files
file	aleph-graph.H
	Simplified graph interface for common use cases.
file	archeap.H
	Arc heap for graph algorithms.
file	AStar.H
	A* shortest path algorithm.
file	Bellman_Ford.H
	Bellman-Ford algorithm for single-source shortest paths.
file	cookie_guard.H
	RAII guards for graph node/arc cookies.
file	Dijkstra.H
	Dijkstra's shortest path algorithm.
file	euclidian-graph-common.H
	Common utilities for Euclidean graphs.
file	eulerian.H
	Eulerian graph detection and path/cycle finding.
file	Floyd_Warshall.H
	Floyd-Warshall algorithm for all-pairs shortest paths.
file	generate_df_tree.H
	Depth-first tree visualization with DFS numbering.
file	generate_graph.H
	Graph visualization and output generation utilities.
file	generate_spanning_tree_picture.H
	Spanning tree visualization with highlighted tree/non-tree edges.
file	graph-dry.H
	Graph base classes and common utilities via CRTP.
file	graph-traverse.H
	Graph traversal algorithms (DFS, BFS).
file	graph_to_tree.H
	Convert spanning tree graphs to Tree_Node structures.
file	grid.H
	2D grid graph generation with 8-connectivity.
file	hamiltonian.H
	Hamiltonian sufficiency testing for graphs.
file	io_graph.H
	Graph serialization and deserialization utilities.
file	Johnson.H
	Johnson's algorithm for all-pairs shortest paths.
file	Karger.H
	Karger's randomized min-cut algorithm.
file	Karger_Stein.H
	Karger-Stein randomized min-cut algorithm (alias for Karger.H fast method).
file	kosaraju.H
	Kosaraju's algorithm for finding strongly connected components.
file	Kruskal.H
	Kruskal's minimum spanning tree algorithm.
file	latex_floyd.H
	Floyd-Warshall algorithm with LaTeX output generation.
file	load_digraph.H
	Utilities for loading directed graphs from pipe-separated files.
file	mat_path.H
	Path reconstruction from Floyd-Warshall path matrices.
file	net_apps.H
	Network flow applications.
file	net_utils.H
	Network flow utilities: generators, visualization, serialization.
file	Prim.H
	Prim's algorithm for minimum spanning trees.
file	random_graph.H
	Random graph generation utilities.
file	random_net.H
	Random network flow graph generation.
file	shortest_path_common.H
	Common utilities and base class for shortest path algorithms.
file	single_graph.H
	Single graph utilities.
file	Stoer_Wagner.H
	Stoer-Wagner deterministic min-cut algorithm.
file	Tarjan.H
	Tarjan's algorithm for strongly connected components.
file	topological_sort.H
	Topological sorting algorithms for directed acyclic graphs (DAGs).
file	tpl_agraph.H
	Array-based graph implementation.
file	tpl_bipartite.H
	Bipartite graph detection and 2-coloring.
file	tpl_components.H
	Graph connectivity and connected components.
file	tpl_cut_nodes.H
	Articulation points (cut nodes) and bridges.
file	tpl_euclidian_graph.H
	Euclidean graph with 2D coordinates.
file	tpl_find_path.H
	Path finding algorithms in graphs.
file	tpl_graph.H
	Generic graph and digraph implementations.
file	tpl_graph_indexes.H
	Graph node and arc indexing.
file	tpl_graph_utils.H
	Utility algorithms and operations for graphs.
file	tpl_indexArc.H
	Arc indexing for fast lookup by endpoint nodes.
file	tpl_indexGraph.H
	Graph indexing utilities for O(log n) node/arc lookup.
file	tpl_indexNode.H
	Node indexing for fast O(log n) lookup by key.
file	tpl_kgraph.H
	K-connected graph structures and connectivity algorithms.
file	tpl_matgraph.H
	Adjacency matrix representations for graphs.
file	tpl_maxflow.H
	Advanced maximum flow algorithms.
file	tpl_mincost.H
	Advanced minimum cost flow algorithms.
file	tpl_net.H
	Network flow graph structures.
file	tpl_net_sup_dem.H
	Supply-demand network flow algorithms.
file	tpl_netcapgraph.H
	Network flow graph with capacities.
file	tpl_sgraph.H
	Simple graph implementation with adjacency lists.
file	tpl_spanning_tree.H
	Spanning tree generation algorithms.
file	tpl_test_acyclique.H
	DAG (acyclic) graph testing.
file	tpl_test_connectivity.H
	Graph connectivity testing.
file	tpl_test_cycle.H
	Cycle detection in graphs.
file	tpl_test_path.H
	Path existence testing.
file	warshall.H
	Warshall's algorithm for transitive closure.
file	xml_graph.H
	XML serialization for graphs.

Classes
class	Aleph::Bit_Fields
	Bit fields for nodes and arcs used for marking visit state during processing. More...
struct	Aleph::Graph_Attr
	General attributes for nodes and arc of graphs. More...
struct	Aleph::Zero_Heuristic< GT, Distance >
	Default heuristic for A* (zero heuristic, degrades to Dijkstra). More...
class	Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >
	A* algorithm for finding the shortest path between two nodes. More...
struct	Aleph::Euclidean_Heuristic< GT, Distance >
	Euclidean distance heuristic for A* in 2D grids. More...
struct	Aleph::Manhattan_Heuristic< GT, Distance >
	Manhattan distance heuristic for A* in grid graphs. More...
class	Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >
	Bellman-Ford algorithm for shortest paths with negative weights. More...
struct	Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::Sni
struct	Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::Ni
struct	Aleph::Bellman_Ford_Negative_Cycle< GT, Distance, Ait, NAit, SA >
	Detects if a negative cycle exists and eventually computes it. More...
class	Aleph::Cookie_Guard< GT >
	RAII guard that clears graph cookies on destruction. More...
class	Aleph::Cookie_Saver< GT >
	RAII guard that saves and restores graph cookies. More...
class	Aleph::Scope_Guard< GT, Cleanup >
	Generic RAII scope guard for cleanup operations on graphs. More...
class	Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >
	Spanning tree calculation of all shortest paths from a given node according to Dijkstra's algorithm. More...
class	Aleph::Test_Eulerian< GT, SN, SA >
	Tests whether a graph or digraph is Eulerian. More...
class	Aleph::Find_Eulerian_Path< GT, SN, SA >
	Finds and constructs an Eulerian path or cycle using Hierholzer's algorithm. More...
struct	Aleph::Find_Eulerian_Path< GT, SN, SA >::Result
	Result type: path and its classification. More...
class	Aleph::Floyd_All_Shortest_Paths< GT, Distance, SA >
	Compute the all-pairs shortest path distance matrix and the path reconstruction matrix for a graph g using the Floyd-Warshall algorithm. More...
struct	Aleph::To_Graphviz< GT, Node_Attr, Arc_Attr, SN, SA >
	Functor class for generating Graphviz DOT specifications. More...
struct	Aleph::Generate_Graphviz< GT, Write_Node, Write_Arc, Shade_Node, Shade_Arc, Dashed_Node, Dashed_Arc, SA, SN >
	Functor for generating Graphviz specifications. More...
struct	GTNodeIterator< GT >
	Common node iterator for graph having its node derived from Dlink class. More...
struct	GTArcIterator< GT >
	Common arc iterator for graph having its arcs derived from Dlink class. More...
struct	Cmp_Dlink_Node< GT, Cmp >
	Used internally for some graphs for compare their nodes. More...
struct	Cmp_Dlink_Arc< GT, Cmp >
	Used internally for some graphs for compare their arcs. More...
class	GTNodeCommon< NodeInfo >
	Common attributes and methods for nodes (vertexes) belonging to graphs. More...
class	GTArcCommon< ArcInfo >
	Common methods for the arc of a graph. More...
class	GraphCommon< GT, Node, Arc >
	Common methods to the Aleph-w ( \(\aleph_\omega\)) graph classes. More...
struct	GraphCommon< GT, Node, Arc >::In_Filt
	Filter for input arcs of a node. More...
struct	GraphCommon< GT, Node, Arc >::Out_Filt
	Filter for output arcs of a node. More...
class	GraphCommon< GT, Node, Arc >::Digraph_Iterator< Filter >
	Special iterator for distinguishing input arcs of output ones. More...
struct	GraphCommon< GT, Node, Arc >::In_Iterator
	Alias for Digraph_Iterator More...
struct	GraphCommon< GT, Node, Arc >::Out_Iterator
class	Aleph::Digraph< BaseGraph >
	Generic directed graph (digraph) wrapper template. More...
class	Graph_Traverse< GT, Itor, Q, Show_Arc >
	Traverse a graph depth-first or breadth-first and execute a visit function. More...
class	Aleph::Graph_To_Tree_Node< GT, Key, Convert, SA >
	Functor class to convert a tree graph to Tree_Node structure. More...
class	Aleph::Build_Grid< GT, Operation_On_Node, Operation_On_Arc >
	Functor to build a 2D grid graph with 8-connectivity. More...
class	Aleph::Test_Hamiltonian_Sufficiency< GT, SN, SA >
	Tests Ore's sufficient condition for Hamiltonian graphs. More...
class	Aleph::Test_Dirac_Condition< GT, SN, SA >
	Tests Dirac's sufficient condition for Hamiltonian graphs. More...
struct	Aleph::Dft_Store_Node< GT >
	Default node storage functor for binary and text modes. More...
struct	Aleph::Dft_Store_Arc< GT >
	Default arc storage functor for binary and text modes. More...
struct	Aleph::Dft_Load_Node< GT >
	Default node loading functor for binary and text modes. More...
struct	Aleph::Dft_Load_Arc< GT >
	Default arc loading functor for binary and text modes. More...
class	Aleph::IO_Graph< GT, Load_Node, Store_Node, Load_Arc, Store_Arc, NF, AF >
	Graph serialization and deserialization class. More...
class	Aleph::Johnson< GT, Distance, Ait, NAit, SA >
	Johnson's algorithm for all-pairs shortest paths. More...
struct	Aleph::Johnson< GT, Distance, Ait, NAit, SA >::Reweighted_Dist
class	Aleph::Karger_Min_Cut< GT, SA >
	Karger's randomized minimum cut algorithm. More...
class	Aleph::Karger_Min_Cut< GT, SA >::ArcIndex
	Arc index with O(1) operations and deterministic ordering. More...
struct	Aleph::Kosaraju_Connected_Components< GT >
	Functor wrapper for Kosaraju's algorithm. More...
class	Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >
	Computes the minimum spanning tree of a graph using Kruskal's algorithm. More...
struct	Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::Init_Node
	Helper struct for initializing node counters during DFS. More...
struct	Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::Paint_Filt< G, GT_SA >
	Filter for arcs painted by Kruskal's algorithm. More...
struct	Aleph::Equal_Node
	Functor to compare nodes by their ID. More...
class	Aleph::Find_Min_Path< Mat >
	Functor wrapper for find_min_path. More...
class	Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >
	Calcula el árbol abarcador mínimo de un grafo según el algoritmo de Prim. More...
struct	Aleph::Dft_Init_Rand_Node< GT >
	Default node initializer for random graph generation. More...
struct	Aleph::Dft_Init_Rand_Arc< GT >
	Default arc initializer for random graph generation. More...
class	Aleph::Random_Graph< GT, Init_Node, Init_Arc >
	Random undirected graph generator. More...
class	Aleph::Random_Digraph< GT, Init_Node, Init_Arc >
	Random directed graph (digraph) generator. More...
class	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >
	Base class providing common infrastructure for shortest path algorithms. More...
struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Arc_Info
	Information stored in arc cookies for painting version. More...
struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Tree_Arc_Info
	Extended arc info with tree arc mapping. More...
struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Node_Info
	Information stored in node cookies for painting version. More...
struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Tree_Node_Info
	Extended node info with tree node mapping. More...
struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Heap_Info
	Functor to access heap node handle from node cookie. More...
struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Get_Potential_Arc
	Functor to get arc potential for heap ordering. More...
struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Initialize_Node
	Node initialization for painting version. More...
struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Initialize_Arc
	Arc initialization for painting version. More...
struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Initialize_Tree_Node
	Node initialization for tree-building version. More...
struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Initialize_Tree_Arc
	Arc initialization for tree-building version. More...
struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Destroy_Node
	Node cleanup for painting version. More...
struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Destroy_Arc
	Arc cleanup for painting version. More...
struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Destroy_Tree_Node
	Node cleanup and mapping for tree-building version. More...
struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Destroy_Tree_Arc
	Arc cleanup and mapping for tree-building version. More...
struct	Aleph::Shortest_Path_Base< GT, Distance, Itor, SA, HeapT >::Total
	Distance totalizer class for path copying. More...
class	Aleph::Test_Single_Graph< GT, SN, SA >
	Determina si un grafo o digrafo es simple. More...
class	Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >
	Stoer-Wagner deterministic minimum cut algorithm. More...
struct	Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::SWNode
struct	Aleph::Stoer_Wagner_Min_Cut< GT, Distance, SA >::PQEntry
class	Aleph::Compute_Cycle_In_Digraph< GT, Itor, SA >
	Determines if a digraph contains a cycle and constructs it. More...
class	Aleph::Topological_Sort< GT, Itor, SA >
	Computes topological ordering using depth-first search. More...
class	Aleph::Q_Topological_Sort< GT, Itor, SA >
	Computes topological ordering using breadth-first search (Kahn's algorithm). More...
class	Aleph::Graph_Anode< Node_Info >
	Node of Array_Graph More...
class	Aleph::Compute_Bipartite< GT, SA >
	Class that takes a bipartite graph and computes the partition sets. More...
class	Aleph::Compute_Maximum_Cardinality_Bipartite_Matching< GT, Max_Flow, SA >
	Class for computing the maximum cardinality matching of a bipartite graph. More...
class	Aleph::Hopcroft_Karp_Matching< GT, SA >
	Functor wrapper for hopcroft_karp_matching. More...
class	Aleph::Build_Subgraph< GT, SA >
	Build a mapped subgraph from a graph starting at a given node. More...
class	Aleph::Unconnected_Components< GT, SA >
	Compute the connected components of a graph. More...
class	Aleph::Euclidian_Node< Node_Info >
class	Aleph::Find_Path_Depth_First< GT, Itor, SA >
	Busca en profundidad un camino entre un par de nodos. More...
class	Aleph::Find_Path_Breadth_First< GT, Itor, SA >
	Busca en amplitud un camino entre un par de nodos. More...
class	Aleph::Directed_Find_Path< GT, Itor, SA >
	Búsqueda de caminos sobre grafos dirigidos definidos mediante una clase grafo (no digrafo). More...
struct	Aleph::Graph_Node< __Node_Info >
	Node belonging to a graph implemented with a double linked adjacency list. More...
struct	Aleph::Graph_Arc< _Arc_Info >
	Arc of graph implemented with double-linked adjacency lists. More...
class	Aleph::List_Graph< _Graph_Node, _Graph_Arc >
	Graph implemented with double-linked adjacency lists. More...
struct	Aleph::List_Graph< _Graph_Node, _Graph_Arc >::Node_Iterator
	Node iterator. More...
class	Aleph::List_Graph< _Graph_Node, _Graph_Arc >::Node_Arc_Iterator
	Iterator on the arcs of a graph. More...
struct	Aleph::List_Graph< _Graph_Node, _Graph_Arc >::Arc_Iterator
	Iterator on all arcs of a graph. More...
struct	Aleph::Dft_Show_Arc< GT >
	Default filter for filtered iterators on arcs. More...
struct	Aleph::Node_Arc_Iterator< GT, Show_Arc >
	Filtered iterator of adjacent arcs of a node. More...
struct	Aleph::Arc_Iterator< GT, Show_Arc >
	Filtered iterator on all the arcs of a graph. More...
struct	Aleph::Dft_Show_Node< GT >
	Default filter for the graph nodes. More...
class	Aleph::Node_Iterator< GT, Show_Node >
	Filtered iterator on the nodes of a graph. More...
class	Aleph::__Out_Filt< GT >
	Filter the outcoming arcs. More...
class	Aleph::__In_Filt< GT >
	Filter the incoming arcs. More...
class	Aleph::Digraph_Iterator< GT, Filter >
	Filtered iterator on directed graphs. More...
class	Aleph::Out_Iterator< GT, Show_Arc >
	Filtered iterator for outcoming arcs of a node. More...
class	Aleph::In_Iterator< GT, SA >
	Filtered iterator for incoming arcs of a node. More...
class	Aleph::Operate_On_Nodes< GT, Operation, SN >
	Functor that traverses the nodes of a graph and performs an operation. More...
class	Aleph::Operate_On_Arcs< GT, Operation, SA >
	Functor that traverses the arcs of a graph and performs an operation. More...
class	Aleph::Path< GT >
	Path on a graph. More...
struct	Aleph::Path< GT >::Path_Desc
class	Aleph::Path< GT >::Iterator
	Iterator on nodes and arcs of a path. More...
struct	Aleph::Dft_Copy_Node< GTT, GTS >
	Default copy node functor. More...
struct	Aleph::Dft_Copy_Arc< GTT, GTS >
	Default copy arc functor. More...
class	Aleph::Copy_Graph< GT, SN, SA >
	Filtered copy of graphs. More...
struct	Aleph::Painted_Min_Spanning_Tree< GT, Distance >
	Filter of painter arcs with that are set the Spanning_Tree control bit. More...
class	Aleph::GraphCopyWithMapping< GT, Tree >
	Graph copy with explicit node mapping. More...
class	Aleph::Nodes_Index< GT, Compare, Tree, SN >
	Builds a node index for fast lookup and retrieval. More...
class	Aleph::Arcs_Index< GT, Compare, Tree, SA >
	Builds an arc index for fast lookup by source/target nodes. More...
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...
class	Aleph::IndexArc< GT, Tree, SA >
	Index for fast arc lookup by its endpoint nodes. More...
struct	Aleph::IndexArc< GT, Tree, SA >::Cmp_Arc
class	Aleph::Index_Graph< GT, Compare, Tree >
	Construye índices de nodos y arcos para su rápida búsqueda y recuperación. More...
class	Aleph::Edge_Connectivity< GT, Max_Flow >
	Functor wrapper for edge_connectivity(). More...
class	Aleph::Compute_Min_Cut< GT, Max_Flow, SA >
	Functor wrapper for compute_min_cut(). More...
class	Aleph::Map_Matrix_Graph< GT, SA >
	Adjacency matrix mapped to an adjacency list graph. More...
struct	Aleph::Map_Matrix_Graph< GT, SA >::Mat_Entry
class	Aleph::Matrix_Graph< GT, SA >
	Adjacency matrix storing copies of graph attributes. More...
class	Aleph::Ady_Mat< GT, __Entry_Type, SA >
	Auxiliary adjacency matrix with custom entry type. More...
class	Aleph::Bit_Mat_Graph< GT, SA >
	Bit matrix for graph connectivity. More...
struct	Aleph::Bit_Mat_Graph< GT, SA >::Proxy
	Proxy for bit access. More...
class	Aleph::Net_Sup_Dem_Node< Node_Info, F_Type >
	Node with supply/demand flow value. More...
class	Aleph::Net_Sup_Dem_Graph< NodeT, ArcT >
	Network graph with supply and demand nodes. More...
struct	Aleph::Graph_Snode< Node_Info >
	Node for graphs implemented with simple adjacency lists. More...
class	Aleph::Graph_Sarc< Arc_Info >
	Arc for graphs implemented with simple adjacency lists. More...
class	Aleph::List_SGraph< __Graph_Node, __Graph_Arc >
	Graph class implemented with singly-linked adjacency lists. More...
class	Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::Node_Iterator
	Node iterator for a graph. More...
class	Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::Node_Arc_Iterator
	Arc iterator for a graph node. More...
class	Aleph::List_SGraph< __Graph_Node, __Graph_Arc >::Arc_Iterator
	Iterator over arcs of a graph. More...
class	Aleph::Find_Depth_First_Spanning_Tree< GT, SA >
	Compute a depth-first spanning tree of a graph. More...
class	Aleph::Find_Breadth_First_Spanning_Tree< GT, SA >
	Compute a breadth-first spanning tree of a graph. More...
class	Aleph::Build_Spanning_Tree< GT >
	Build a spanning tree from an array of arcs. More...
class	Aleph::Is_Graph_Acyclique< GT, SA >
	Determines whether a graph is acyclic (contains no cycles). More...
class	Aleph::Has_Cycle< GT, SA >
	Determines whether a graph contains cycles. More...
class	Test_Connectivity< GT, SA >
	Determines if a graph g is connected. More...
class	Aleph::Test_For_Cycle< GT, SA >
	Test whether a cycle is reachable from a given node. More...
class	Aleph::Test_For_Path< GT, SA >
	verfica si existe un camino entre dos nodos. More...
class	Fixed_Relation
	Binary relation between a set of integers. More...
class	Relation
	Binary relation between a set of integers. More...
class	Relation_T< T, Compare >
	Binary relation between a set of items. More...
struct	Relation_T< T, Compare >::Pair
struct	Relation_T< T, Compare >::Cmp
class	Aleph::Warshall_Compute_Transitive_Clausure< GT, SA >
	Computes the transitive closure of a graph using Warshall's algorithm. More...
class	Aleph::Tarjan_Connected_Components< GT, Itor, SA >
	Computes strongly connected components (SCCs) in a directed graph using Tarjan's algorithm. More...
class	Aleph::IndexNode< GT, Compare, Tree, SN >
	Builds an index of nodes for fast search and retrieval. More...

Macros
#define	NODE_BITS(p)   ((p)->attrs.control_bits)
	Get the control bits of a node.
#define	NODE_COUNTER(p)   ((p)->attrs.counter)
	Get the counter of a node.
#define	NODE_COLOR(p)   ((p)->attrs.counter)
	Synonymous of NODE_COUNTER.
#define	IS_NODE_VISITED(p, bit)   (NODE_BITS(p).get_bit(bit))
	Determine whether the control bit is set or not to one.
#define	NODE_COOKIE(p)   ((p)->attrs.cookie)
	Return the node cookie
#define	ARC_COUNTER(p)   ((p)->attrs.counter)
	Return the counter of arc p.
#define	ARC_COLOR(p)   ((p)->attrs.counter)
	Return the color of arc p.
#define	ARC_BITS(p)   ((p)->attrs.control_bits)
	Return the control bits of arc p.
#define	IS_ARC_VISITED(p, bit)   (ARC_BITS(p).get_bit(bit))
	Determine whether the bit field is or not set to one.
#define	ARC_COOKIE(p)   ((p)->attrs.cookie)
	Return the arc cookie
#define	ALEPH_GRAPH_COPY_MOVE_CTORS(GraphClass)
	Macro to generate copy/move constructors and assignment operators.

Typedefs
template<typename __Graph_Node = Graph_Anode<int>, typename __Graph_Arc = Graph_Aarc<int>>
using	Aleph::Array_Digraph = Digraph< Array_Graph< __Graph_Node, __Graph_Arc > >
	Directed graph (digraph) implemented with array-based adjacency lists.
template<typename __Graph_Node = Graph_Node<int>, typename __Graph_Arc = Graph_Arc<int>>
using	Aleph::List_Digraph = Digraph< List_Graph< __Graph_Node, __Graph_Arc > >
	Directed graph (digraph) implemented with double-linked adjacency lists.
template<class GT >
using	Aleph::ArcPair = std::tuple< typename GT::Arc *, typename GT::Node * >
	Alias used for encapsulating a pair of arc and node (related between them).
template<class GT >
using	Aleph::_Out_Iterator = Digraph_Iterator< GT, __Out_Filt< GT > >
	Basic iterator for outcoming arcs of a node.
template<class GT >
using	Aleph::_In_Iterator = Digraph_Iterator< GT, __In_Filt< GT > >
	Basic iterator for incoming arcs of a node.
template<typename __Graph_Node = Graph_Snode<int>, typename __Graph_Arc = Graph_Sarc<int>>
using	Aleph::List_SDigraph = Digraph< List_SGraph< __Graph_Node, __Graph_Arc > >
	Directed graph (digraph) implemented with simple adjacency lists.

Enumerations
enum	Aleph::Graph_Bits {   Aleph::Depth_First , Aleph::Breadth_First , Aleph::Test_Cycle , Aleph::Find_Path ,   Aleph::Euler , Aleph::Maximum_Flow , Aleph::Spanning_Tree , Aleph::Build_Subtree ,   Aleph::Convert_Tree , Aleph::Cut , Aleph::Min , Aleph::Num_Bits_Graph }
	Bit numbers of nodes or arcs. More...

Functions
template<class GT , class Func >
auto	Aleph::with_clean_cookies (GT &g, Func &&func) -> decltype(func())
	Convenience function to run an algorithm with automatic cookie cleanup.
template<class GT , class Func >
auto	Aleph::with_saved_cookies (GT &g, Func &&func) -> decltype(func())
	Convenience function to run an algorithm preserving existing cookies.
template<class GT , class Key >
void	write_df_low_tree (GT &g, typename GT::Node *src, std::ofstream &f)
	Generate a DFS tree picture with low-link values.
template<class GT , class Write_Node , class Write_Arc , class Shade_Node , class Shade_Arc , class SA >
void	Aleph::generate_graphpic (const GT &g, const double &xdist, const double &ydist, std::ostream &output)
	Generate a graphpic specification for graph visualization.
template<class GT , class Write_Node , class Write_Arc , class Shade_Node , class Shade_Arc , class Dashed_Node , class Dashed_Arc , class SA , class SN >
void	Aleph::generate_graphviz (const GT &g, std::ostream &output, const std::string &rankdir="TB", float ranksep=0.2, float nodesep=0.2)
	Generate a Graphviz DOT specification for graph visualization.
template<class GT , class Node_Attr , class Arc_Attr , class SN , class SA >
void	Aleph::generate_graphviz (const GT &g, std::ostream &out, Node_Attr node_attr=Node_Attr(), Arc_Attr arc_attr=Arc_Attr(), const std::string &rankdir="TB")
	Generate Graphviz DOT output with custom attribute functors.
template<class GT , class Node_Attr , class Arc_Attr , class SN , class SA >
void	Aleph::digraph_graphviz (const GT &g, std::ostream &out, Node_Attr node_attr=Node_Attr(), Arc_Attr arc_attr=Arc_Attr(), const std::string &rankdir="LR")
	Generate Graphviz DOT output specifically for digraphs.
template<class GT , class Node_Attr , class Arc_Attr , class SN , class SA >
size_t	Aleph::rank_graphviz (const GT &g, std::ostream &out, Node_Attr node_attr=Node_Attr(), Arc_Attr arc_attr=Arc_Attr(), const std::string &rankdir="LR")
	Generate Graphviz DOT output with topological ranking.
template<class GT , class Write_Node , class Write_Arc , class Shade_Node , class Shade_Arc , class SA >
void	Aleph::generate_cross_graph (GT &g, const size_t &nodes_by_level, const double &xdist, const double &ydist, std::ostream &out)
	Generate a cross-graph layout specification for graphpic.
template<class GT , class Write_Node , class Write_Arc , class Shade_Node , class Shade_Arc , class SA >
void	Aleph::generate_net_graph (GT &g, const size_t &nodes_by_level, const double &xdist, const double &ydist, std::ostream &out)
	Generate a net-graph layout specification for graphpic.
template<typename GT , class Write_Node , class Write_Arc , class SA >
void	generate_cross_spanning_tree (GT &g, const size_t &nodes_by_level, const double &xdist, const double &ydist, std::ofstream &output)
	Generate a cross-layout visualization of a spanning tree.
template<typename GT , class Write_Node , class Write_Arc , class SA >
void	generate_net_spanning_tree (GT &g, const size_t &nodes_by_level, const double &xdist, const double &ydist, std::ofstream &output)
	Generate a net-layout visualization of a spanning tree.
template<class GT , typename Key , class Convert , class SA = Dft_Show_Arc<GT>>
Tree_Node< Key > *	Aleph::graph_to_tree_node (GT &g, typename GT::Node *groot)
	Convert a tree graph to a Tree_Node structure.
template<class GT >
void	Aleph::kosaraju_connected_components (const GT &g, DynList< GT > &blk_list, DynList< typename GT::Arc * > &arc_list)
	Compute strongly connected components using Kosaraju's algorithm.
template<class GT >
DynList< DynList< typename GT::Node * > >	Aleph::kosaraju_connected_components (const GT &g)
	Compute strongly connected components as lists of nodes.
template<class GT >
size_t	Aleph::kosaraju_scc_count (const GT &g)
	Count the number of strongly connected components.
template<class GT >
bool	Aleph::is_strongly_connected (const GT &g)
	Check if a directed graph is strongly connected.
template<class GT , class Compare , class Plus >
void	Aleph::floyd_all_shortest_paths (GT &g, Ady_Mat< GT, typename GT::Arc_Type::Distance_Type > &dist, Ady_Mat< GT, long > &path)
	Compute all-pairs shortest paths using Floyd-Warshall algorithm.
template<class Mat >
void	Aleph::find_min_path (Mat &p, const long src_index, const long tgt_index, Path< typename Mat::Graph_Type > &path)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Variant that accepts const indices.
template<class Mat >
void	Aleph::find_min_path (Mat &p, typename Mat::Node *src_node, typename Mat::Node *tgt_node, Path< typename Mat::Graph_Type > &path)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Reconstruct shortest path from path matrix using node pointers.
template<class GT , class Compare , class Plus , template< class > class P_i, template< class > class P_ij, template< class > class D_ij>
void	Aleph::floyd_all_shortest_paths_latex (GT &g, Ady_Mat< GT, typename GT::Arc_Type::Distance_Type > &dist, Ady_Mat< GT, long > &path, std::ofstream &output)
	Floyd-Warshall algorithm with LaTeX step-by-step output.
void	Aleph::split (const std::string &text, const std::string &separators, DynDlist< std::string > &words)
	Split a text into tokens using a separator set.
Digrafo::Node *	Aleph::search_node (Digrafo &g, const std::string &s)
	Find or create a node by ID.
void	Aleph::load_digraph (Digrafo &g, std::istream &nodes_input, std::istream &arcs_input)
	Load nodes and arcs from streams into the directed graph.
void	Aleph::generate_dot_file (Digrafo &g, std::ostream &output)
	Generate a DOT representation of the digraph.
GT	Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::sufficient_hamiltonian (const size_t &__num_nodes, const double &p=0.5)
	Create a random Hamiltonian graph.
GT	Aleph::Random_Graph< GT, Init_Node, Init_Arc >::sufficient_hamiltonian (const size_t &__num_nodes, const double &p=0.5)
	Create a random Hamiltonian graph.
template<class GT , class SA = Dft_Show_Arc<GT>>
void	Aleph::compute_bipartite (const GT &g, DynDlist< typename GT::Node * > &l, DynDlist< typename GT::Node * > &r)
	Computes the partition sets of a bipartite graph.
template<class GT , template< class > class Max_Flow = Ford_Fulkerson_Maximum_Flow, class SA = Dft_Show_Arc<GT>>
void	Aleph::compute_maximum_cardinality_bipartite_matching (const GT &g, DynDlist< typename GT::Arc * > &matching)
	Computes the maximum cardinality matching of a bipartite graph.
template<class GT , class SA = Dft_Show_Arc<GT>>
bool	Aleph::compute_bipartite_all_components (const GT &g, DynDlist< typename GT::Node * > &l, DynDlist< typename GT::Node * > &r)
	Computes the partition sets of a bipartite graph handling all connected components.
template<class GT , class SA = Dft_Show_Arc<GT>>
void	Aleph::hopcroft_karp_matching (const GT &g, DynDlist< typename GT::Arc * > &matching)
	Computes a maximum cardinality matching on a bipartite graph using the Hopcroft-Karp algorithm.
template<class GT , class SN = Dft_Show_Node<GT>>
void	Aleph::for_each_node (const GT &g, std::function< void(typename GT::Node *)> operation, SN sn=SN())
	Traverse all the nodes of graph filtering some ones according to a condition and executing an operation on them.
template<class GT , class SA = Dft_Show_Arc<GT>>
void	Aleph::for_each_arc (const GT &g, std::function< void(typename GT::Arc *)> operation, SA sa=SA())
	Traverse all the arcs of graph filtering some ones according to a condition and executing an operation on them.
template<class GT , class SA = Dft_Show_Arc<GT>>
void	Aleph::for_each_arc (const GT &g, typename GT::Node *p, std::function< void(typename GT::Arc *)> operation, SA sa=SA())
	Traverse all the arcs adjacent to a node filtering some ones according to a condition and executing an operation on them.
template<class GT , class SN = Dft_Show_Node<GT>>
bool	Aleph::forall_node (const GT &g, std::function< bool(typename GT::Node *)> cond, SN sn=SN())
	Return true if condition cond is met on every filtered node of the graph.
template<class GT , class SA = Dft_Show_Arc<GT>>
bool	Aleph::forall_arc (const GT &g, std::function< bool(typename GT::Arc *)> cond, SA sa=SA())
	Return true if condition cond is met on every filtered arc of the graph.
template<class GT , class SA = Dft_Show_Arc<GT>>
bool	Aleph::forall_arc (typename GT::Node *p, std::function< bool(typename GT::Arc *)> cond, SA sa=SA())
	Return true if the condition cond is met on every filtered arc of a node.
template<class GT , typename T , template< typename > class Container = DynList, class SN = Dft_Show_Node<GT>>
Container< T >	Aleph::nodes_map (GT &g, std::function< T(typename GT::Node *)> transformation, SN sn=SN())
	Map the filtered nodes of a graph to a transformed type.
template<class GT , typename T , template< typename > class Container = DynList, class SA = Dft_Show_Arc<GT>>
Container< T >	Aleph::arcs_map (GT &g, std::function< T(typename GT::Arc *)> transformation, SA sa=SA())
	Map the filtered arcs of a graph to a transformed type.
template<class GT , typename T , template< typename > class Container = DynList, class SA = Dft_Show_Arc<GT>>
Container< T >	Aleph::arcs_map (GT &g, typename GT::Node *p, std::function< T(typename GT::Arc *)> transformation, SA sa=SA())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Map the filtered arcs of a specific node in a graph to a transformed type.
template<class GT , typename T , class SN = Dft_Show_Node<GT>>
T	Aleph::foldl_nodes (GT &g, const T &init, std::function< T(const T &, typename GT::Node *)> operation, SN sn=SN())
	Fold the filtered nodes of a graph.
template<class GT , typename T , class SA = Dft_Show_Arc<GT>>
T	Aleph::foldl_arcs (GT &g, const T &init, std::function< T(const T &, typename GT::Arc *)> operation, SA sa=SA())
	Fold the filtered arcs of a graph.
template<class GT , typename T , class SA = Dft_Show_Arc<GT>>
T	Aleph::foldl_arcs (GT &g, typename GT::Node *p, const T &init, std::function< T(const T &, typename GT::Arc *)> operation, SA sa=SA())
	Fold the filtered adjacent arcs of a node.
template<class GT , class SA = Dft_Show_Arc<GT>>
DynList< typename GT::Node * >	Aleph::out_nodes (typename GT::Node *p, SA sa=SA())
	Return the nodes connected to the filtered outcoming arcs of p.
template<class GT , class SA = Dft_Show_Arc<GT>>
DynList< typename GT::Node * >	Aleph::in_nodes (typename GT::Node *p, SA sa=SA())
	Return the nodes connected to the filtered incoming arcs to p.
template<class GT , class SA = Dft_Show_Arc<GT>>
DynList< typename GT::Arc * >	Aleph::out_arcs (typename GT::Node *p, SA sa=SA())
	Return the filtered incoming arcs of p.
template<class GT , class SA = Dft_Show_Arc<GT>>
DynList< typename GT::Arc * >	Aleph::in_arcs (typename GT::Node *p, SA sa=SA())
	Return the filtered incoming arcs of p.
template<class GT , class SA = Dft_Show_Arc<GT>>
DynList< typename GT::Arc * >	Aleph::arcs (typename GT::Node *p, SA sa=SA())
	Return all the filtered arcs related to p
template<class GT , class SA = Dft_Show_Arc<GT>>
DynList< ArcPair< GT > >	Aleph::in_pairs (typename GT::Node *p, SA sa=SA())
	Return the filtered incoming pairs of (arc,node) related to node p
template<class GT , class SA = Dft_Show_Arc<GT>>
DynList< ArcPair< GT > >	Aleph::out_pairs (typename GT::Node *p, SA sa=SA())
	Return the filtered outcoming pairs of (arc,node) related to node p
template<class GT , class SA = Dft_Show_Arc<GT>>
size_t	Aleph::in_degree (typename GT::Node *p, SA sa=SA())
	Compute the filtered in degree of node p.
template<class GT , class SA = Dft_Show_Arc<GT>>
size_t	Aleph::out_degree (typename GT::Node *p, SA sa=SA())
	Compute the filtered out degree of node p
template<class GT , class Itor , class Operation >
bool	Aleph::traverse_arcs (typename GT::Node *p, Operation op=Operation())
	Generic arcs traverse of a node.
template<class GT , class Itor , class Operation >
void	Aleph::for_each_arc (typename GT::Node *p, Operation op=Operation())
	Execute an operation on each arc of a node.
template<class GT , class Op >
bool	Aleph::traverse_in_arcs (typename GT::Node *p, Op op=Op())
	Conditioned traversal of incoming arcs of a node.
template<class GT , class Op >
void	Aleph::for_each_in_arc (typename GT::Node *p, Op op=Op())
	Traverse the incoming arcs of a node and executes an operation.
template<class GT , class Op >
bool	Aleph::traverse_out_arcs (typename GT::Node *p, Op op=Op())
	Conditioned traversal of outcoming arcs of a node.
template<class GT , class Op >
void	Aleph::for_each_out_arc (typename GT::Node *p, Op op=Op())
	Traverse the outcoming arcs of a node and executes an operation.
template<class GT , class SA = Dft_Show_Arc<GT>>
GT::Arc *	Aleph::search_arc (const GT &g, typename GT::Node *src, typename GT::Node *tgt, SA sa=SA()) noexcept
	Arc filtered searching given two nodes.
template<class GT , class SA = Dft_Show_Arc<GT>>
GT::Arc *	Aleph::search_directed_arc (const GT &g, typename GT::Node *src, typename GT::Node *tgt, SA sa=SA()) noexcept
	Searching of directed arc linking two nodes.
template<class GT >
GT::Node *	Aleph::mapped_node (typename GT::Node *p) noexcept
	Return the mapped node through the cookie of p
template<class GT >
void	Aleph::copy_graph (GT &gtgt, const GT &gsrc, bool cookie_map=false)
	Explicit copy of graph.
template<class GT >
void	Aleph::clear_graph (GT &g) noexcept
	Clean a graph: all its nodes and arcs are removed and freed.
template<class GT >
Path< GT >	Aleph::find_path_depth_first (const GT &g, typename GT::Node *start_node, typename GT::Node *end_node)
	Depth-first search of a path between two nodes.
template<class GTS , class GTT >
void	Aleph::map_nodes (typename GTS::Node *p, typename GTT::Node *q) noexcept
	Map two nodes of different types of graphs through their cookies.
template<class GTS , class GTT >
void	Aleph::map_arcs (typename GTS::Arc *p, typename GTT::Arc *q) noexcept
	Map two arcs of different types of graphs through their cookies.
template<class GTT , class GTS , class Copy_Node = Dft_Copy_Node<GTT, GTS>, class Copy_Arc = Dft_Copy_Arc<GTT, GTS>>
void	Aleph::inter_copy_graph (GTT &gtgt, const GTS &gsrc, const bool cookie_map=false)
	Copy between different types of graphs.
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::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 >
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 >
bool	Aleph::test_for_cycle (const GT &g, typename GT::Node *src)
	Search for a cycle reachable from a given node.
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 >
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 >
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_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 >
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 >
long	Aleph::paint_subgraphs (const GT &g, const DynList< typename GT::Node * > &cut_node_list)
	Paint connected blocks around articulation points.
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 , template< class > class Max_Flow = Random_Preflow_Maximum_Flow, class SA = Dft_Show_Arc<GT>>
long	Aleph::edge_connectivity (GT &g)
	Compute edge connectivity (arc connectivity) of an undirected graph.
template<class GT , template< class > class Max_Flow = Heap_Preflow_Maximum_Flow, class SA = Dft_Show_Arc<GT>>
long	Aleph::compute_min_cut (GT &g, DynSetTree< typename GT::Node * > &l, DynSetTree< typename GT::Node * > &r, DynDlist< typename GT::Arc * > &cut)
	Compute a minimum edge cut of an undirected graph.
template<class GT , template< class > class Max_Flow = Random_Preflow_Maximum_Flow, class SA = Dft_Show_Arc<GT>>
long	Aleph::vertex_connectivity (GT &g)
	Compute vertex connectivity of an undirected graph.
template<class GT , class SA = Dft_Show_Arc<GT>>
void	Aleph::warshall_compute_transitive_clausure (GT &g, Bit_Mat_Graph< GT, SA > &mat)
	Computes the transitive closure of a graph using Warshall's algorithm.

Variables
const unsigned char	Aleph::Processed = 2
	The node or arc has already been processed.
const unsigned char	Aleph::Processing = 1
	The node are being processed; probably it is inside a queue, stack or heap.
const unsigned char	Aleph::Unprocessed = 0
	The node have not bees processed.
bool	Aleph::with_power = false
	Configuration options for DOT file generation.
bool	Aleph::with_nes = false
	If true, include NES percentage in node labels.
bool	Aleph::only_num = false
	If true, show only the node number, not the full label.
bool	Aleph::with_class = false
	If true, set node shapes based on class field.
size_t	Aleph::font_size = 6
	Font size for the DOT output.
bool	Aleph::vertical = true
	If true, use vertical layout (default).

Detailed Description

Filtered iterators

The graph classes export several iterators: Node_Iterator, Arc_Iterator, Node_Arc_Iterator, Out_Iterator and In_Iterator. These iterators are exported as subclasses of the graph class. Suppose, for example, that you are using a class Map based on Array_Graph class (but it could have perfectly been base on any other graph class) and the graph is named g. Then, you could iterate on all the arcs through some such as:

for (auto it = g.get_arc_it(); it.has_cur(); it.next()) auto arc = it.get_curr(); // each arc of the graph is seen

Now, there are several, perhaps many, situations where not all the arcs must be processed, but a subset of them satisfying a particular condition. In these cases, the filtered iterator come for us.

As seen in the class Filter_Iterator, a filtered iterator is almost exactly the same thing as a normal iterator. The subtle difference is that on it operates a filter condition that filters all the items satisfying a special condition. Let's show a brief but constructive example.

A brief example

Suppose that your graph represents pathways of automotive transportation. Nodes are the cities and arcs are the pathways. Now suppose that your pathways are classified in Highway, Road and Trail. Now suppose that you wish to solve a problem that only involves highways; for example, you want to find the shortest path between two cities connected by only highways. Then you could specify a filter that catches highways:

struct Only_Highway { bool operator () (GT::Arc * a) { return a->get_info().type == Highway; } };

Now, if your shortest path algorithm receives this filter, this will only see highways and its results will only contain highways.

Convention about filtered iterators

For each subclass iterator on a graph, it is exported a filtered iterator with the same name of subclassed one. Thus, for the subclass GT::Arc_Iterator exists a filtered version named Arc_Iterator and so on for the remainder iterator subclasses on the graphs.

The filtered iterators have a great importance in Aleph-w ( \(\aleph_\omega\)) algorithms on graphs, since almost every algorithm operates with filtered iterator.

When to use then?

The short answer is: almost always!

Filtered iterators have of course a light but constant impact on performance. For each seen graph object a boolean predicate is tested. So, if you know that your algorithm does not require to filter, the use the subclass iterator. But if, in pursuit of generalization your algorithm could profit the filtered version, then design your algorithm on filtered iterator. In this way you will provide generality, which allows to reuse algorithms in a transparent way.

A very good and concrete example of intensive use of filtered iterator is for solving the problem of maximizing a network flow at minimum cost. First, in order to manage the residual net, the arcs are filtered according to source node. Second, the residual cut arcs are also filtered according to flow value; if the flow is equal to the capacity then the arc is filtered. Third, in order to detect negative cycles the Bellman-Ford algorithm is used with a filter that only sees the arcs cost.

Macro Definition Documentation

ALEPH_GRAPH_COPY_MOVE_CTORS

#define ALEPH_GRAPH_COPY_MOVE_CTORS

(

GraphClass

)

Value:

                 \
  GraphClass(const GraphClass & g)                                           \
  {                                                                          \
    copy_graph(*this, g);                                                    \
  }                                                                          \
                                                                             \
  GraphClass(GraphClass && g) noexcept                                       \
  {                                                                          \
    swap(g);                                                                 \
  }                                                                          \
                                                                             \
  GraphClass & operator=(const GraphClass & g)                               \
  {                                                                          \
    if (this == &g)                                                          \
      return *this;                                                          \
    copy_graph(*this, g);                                                    \
    return *this;                                                            \
  }                                                                          \
                                                                             \
  GraphClass & operator=(GraphClass && g) noexcept                           \
  {                                                                          \
    swap(g);                                                                 \
    return *this;                                                            \
  }

Macro to generate copy/move constructors and assignment operators.

This macro generates the standard copy constructor, move constructor, copy assignment operator, and move assignment operator for graph classes.

Requirements for the graph class:

• Must have a swap(GraphClass&) method
• Must work with the free function copy_graph(dest, src)

Parameters

GraphClass

The name of the graph class

Usage example:

class List_Graph : public GraphCommon<...> {
  // ... other members ...
 
  void swap(List_Graph & g) noexcept { ... }
 
  ALEPH_GRAPH_COPY_MOVE_CTORS(List_Graph)
 
  virtual ~List_Graph() { clear_graph(*this); }
};

Note

This macro does NOT generate the destructor, as destruction logic varies between graph implementations.

Definition at line 3786 of file graph-dry.H.

ARC_BITS

#define ARC_BITS

(

p

)

((p)->attrs.control_bits)

Return the control bits of arc p.

Definition at line 379 of file aleph-graph.H.

ARC_COLOR

#define ARC_COLOR

(

p

)

((p)->attrs.counter)

Return the color of arc p.

Definition at line 373 of file aleph-graph.H.

ARC_COOKIE

#define ARC_COOKIE

(

p

)

((p)->attrs.cookie)

Return the arc cookie

Definition at line 394 of file aleph-graph.H.

ARC_COUNTER

#define ARC_COUNTER

(

p

)

((p)->attrs.counter)

Return the counter of arc p.

Definition at line 367 of file aleph-graph.H.

IS_ARC_VISITED

#define IS_ARC_VISITED	(		p,
			bit
	)		(ARC_BITS(p).get_bit(bit))

Determine whether the bit field is or not set to one.

Parameters

p	pointer to arc
bit	number of bit to be read

Returns

true if bit is 1; false otherwise (bit is set to 0)

Definition at line 388 of file aleph-graph.H.

IS_NODE_VISITED

#define IS_NODE_VISITED	(		p,
			bit
	)		(NODE_BITS(p).get_bit(bit))

Determine whether the control bit is set or not to one.

Parameters

p	pointer to the node
bit	number of bit to read

Returns

true if the bit is 1; false if 0

Definition at line 355 of file aleph-graph.H.

NODE_BITS

#define NODE_BITS

(

p

)

((p)->attrs.control_bits)

Get the control bits of a node.

Definition at line 333 of file aleph-graph.H.

NODE_COLOR

#define NODE_COLOR

(

p

)

((p)->attrs.counter)

Synonymous of NODE_COUNTER.

Definition at line 345 of file aleph-graph.H.

NODE_COOKIE

#define NODE_COOKIE

(

p

)

((p)->attrs.cookie)

Return the node cookie

Definition at line 361 of file aleph-graph.H.

NODE_COUNTER

#define NODE_COUNTER

(

p

)

((p)->attrs.counter)

Get the counter of a node.

Definition at line 339 of file aleph-graph.H.

Typedef Documentation

_In_Iterator

template<class GT >

using Aleph::_In_Iterator = typedef Digraph_Iterator<GT, __In_Filt<GT> >

Basic iterator for incoming arcs of a node.

Definition at line 1737 of file tpl_graph.H.

_Out_Iterator

template<class GT >

using Aleph::_Out_Iterator = typedef Digraph_Iterator<GT, __Out_Filt<GT> >

Basic iterator for outcoming arcs of a node.

Definition at line 1729 of file tpl_graph.H.

ArcPair

template<class GT >

using Aleph::ArcPair = typedef std::tuple<typename GT::Arc *, typename GT::Node *>

Alias used for encapsulating a pair of arc and node (related between them).

Definition at line 1541 of file tpl_graph.H.

Array_Digraph

template<typename __Graph_Node = Graph_Anode<int>, typename __Graph_Arc = Graph_Aarc<int>>

using Aleph::Array_Digraph = typedef Digraph<Array_Graph<__Graph_Node, __Graph_Arc> >

Directed graph (digraph) implemented with array-based adjacency lists.

This class models a directed graph. Functionally it is equivalent to the Array_Graph class, except that this one handles directed graphs.

This is a type alias for Digraph<Array_Graph<...>>, which provides all the directed graph functionality through the generic Digraph template wrapper defined in graph-dry.H.

Template Parameters

__Graph_Node	The node type. Must be defined from the Graph_Anode class, either by attribute inclusion, by derivation, or by a combination of both.
__Graph_Arc	The arc type. Must be defined from the Graph_Aarc class, either by attribute inclusion, by derivation, or by a combination of both.

See also

Graph_Anode Graph_Aarc Digraph

Array_Graph

Definition at line 617 of file tpl_agraph.H.

List_Digraph

template<typename __Graph_Node = Graph_Node<int>, typename __Graph_Arc = Graph_Arc<int>>

using Aleph::List_Digraph = typedef Digraph<List_Graph<__Graph_Node, __Graph_Arc> >

Directed graph (digraph) implemented with double-linked adjacency lists.

This class models a directed graph. Functionally, it is equivalent to the List_Graph class, except that this one handles directed graphs.

This is a type alias for Digraph<List_Graph<...>>, which provides all the directed graph functionality through the generic Digraph template wrapper defined in graph-dry.H.

Template Parameters

__Graph_Node	The node type. Must be defined from the Graph_Node class, either by attribute inclusion, by derivation, or by a combination of both.
__Graph_Arc	The arc type. Must be defined from the Graph_Arc class, either by attribute inclusion, by derivation, or by a combination of both.

See also

Graph_Node Graph_Arc Digraph

List_Graph

Definition at line 1532 of file tpl_graph.H.

List_SDigraph

template<typename __Graph_Node = Graph_Snode<int>, typename __Graph_Arc = Graph_Sarc<int>>

using Aleph::List_SDigraph = typedef Digraph<List_SGraph<__Graph_Node, __Graph_Arc> >

Directed graph (digraph) implemented with simple adjacency lists.

This class models a directed graph. Functionally it is equivalent to the List_SGraph class, except that this one handles directed graphs.

This is a type alias for Digraph<List_SGraph<...>>, which provides all the directed graph functionality through the generic Digraph template wrapper defined in graph-dry.H.

Template Parameters

__Graph_Node	The node type. Must be defined from the Graph_Snode class, either by attribute inclusion, by derivation, or by a combination of both.
__Graph_Arc	The arc type. Must be defined from the Graph_Sarc class, either by attribute inclusion, by derivation, or by a combination of both.

See also

Graph_Snode Graph_Sarc Digraph

List_SGraph

Definition at line 656 of file tpl_sgraph.H.

Enumeration Type Documentation

Graph_Bits

enum Aleph::Graph_Bits

Bit numbers of nodes or arcs.

Nodes y arcs of graph have as control attributes (internal representation of state), a set of bits. These are their numbers named according to their use by the library.

You can use then for purposes other than the suggested name. However, be careful.

See also

Bit_Fields

Enumerator
Depth_First
Breadth_First
Test_Cycle
Find_Path
Euler
Maximum_Flow
Spanning_Tree
Build_Subtree
Convert_Tree
Cut
Min
Num_Bits_Graph

Definition at line 71 of file aleph-graph.H.

Function Documentation

arcs()

template<class GT , class SA = Dft_Show_Arc<GT>>

DynList< typename GT::Arc * > Aleph::arcs	(	typename GT::Node *	p,
		SA	sa = SA()
	)

Return all the filtered arcs related to p

Parameters

[in]	p	node pointer
[in]	sa	arc filter

Definition at line 1903 of file tpl_graph.H.

References Aleph::DynList< T >::append(), Aleph::maps(), and Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne().

arcs_map() [1/2]

template<class GT , typename T , template< typename > class Container = DynList, class SA = Dft_Show_Arc<GT>>

Container< T > Aleph::arcs_map	(	GT &	g,
		std::function< T(typename GT::Arc *)>	transformation,
		SA	sa = SA()
	)

Map the filtered arcs of a graph to a transformed type.

Template Parameters

GT	Graph type
T	Result type
Container	Container type (default: DynList)
SA	Arc filter type (default: Dft_Show_Arc<GT>)

Parameters

g	the graph
transformation	function Arc* -> T that transforms each arc
sa	arc filter functor (default: Dft_Show_Arc<GT>)

Returns

a Container<T> object with all the arcs mapped through the transformation

Definition at line 1393 of file tpl_graph.H.

References Aleph::DynList< T >::append(), and Aleph::maps().

Referenced by Aleph::max_flow_min_cost_by_cycle_canceling().

arcs_map() [2/2]

template<class GT , typename T , template< typename > class Container = DynList, class SA = Dft_Show_Arc<GT>>

Container< T > Aleph::arcs_map	(	GT &	g,
		typename GT::Node *	p,
		std::function< T(typename GT::Arc *)>	transformation,
		SA	sa = SA()
	)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Map the filtered arcs of a specific node in a graph to a transformed type.

This overload filters arcs connected to a specific node p.

Template Parameters

GT	Graph type
T	Result type
Container	Container type (default: DynList)
SA	Arc filter type (default: Dft_Show_Arc<GT>)

Parameters

g	the graph
p	node pointer (arcs connected to this node are filtered)
transformation	function Arc* -> T that transforms each arc
sa	arc filter functor (default: Dft_Show_Arc<GT>)

Returns

a Container<T> object with all the arcs mapped through the transformation

See also

arcs_map(GT &, std::function<T (typename GT::Arc *)>, SA) For the version that maps all arcs in the graph.

Definition at line 1428 of file tpl_graph.H.

References Aleph::DynList< T >::append(), and Aleph::maps().

breadth_first_traversal()

template<class GT >

size_t Aleph::breadth_first_traversal ( const GT &  g, typename GT::Node *  start, bool(*)(const GT &, typename GT::Node *, typename GT::Arc *)  visit  )

inline

Breadth-first traversal starting from a given node.

Traverses the connected component reachable from start in breadth-first order.

The callback must have the following signature: bool visit(const GT& g, typename GT::Node* curr, typename GT::Arc* from).

from is the arc that discovered curr (nullptr for the start node). If visit returns true, the traversal stops early. If visit is nullptr, no callback is executed.

Template Parameters

GT	Graph type.

Parameters

[in]	g	Graph to traverse.
[in]	start	Starting node (must be non-null and belong to g).
[in]	visit	Optional visit callback (may be nullptr).

Returns

Number of discovered nodes.

Note

Resets the Breadth_First control bit on all nodes and arcs.

Uses the Breadth_First control bit on both nodes and arcs.

See also

breadth_first_traversal(const GT&, bool (*)(...)), depth_first_traversal, Breadth_First_Traversal

Definition at line 326 of file tpl_graph_utils.H.

References ARC_BITS, Aleph::Breadth_First, Aleph::DynListQueue< T >::get(), GraphCommon< GT, Node, Arc >::get_arc_it(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), IS_ARC_VISITED, Aleph::DynListQueue< T >::is_empty(), IS_NODE_VISITED, Aleph::maps(), NODE_BITS, Aleph::DynListQueue< T >::put(), GraphCommon< GT, Node, Arc >::reset_bit_arcs(), and GraphCommon< GT, Node, Arc >::reset_bit_nodes().

Referenced by Aleph::breadth_first_traversal(), TEST(), TEST(), and TEST().

build_spanning_tree()

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).

Builds a new graph ret containing every arc in arcs (skipping null entries). Nodes are created on demand.

Mapping:

• Each node created in ret stores the original node pointer in its cookie.
• Each arc created in ret stores the original arc pointer in its cookie.

Note

This is a one-way mapping (ret → original). The original graph is not modified.

Parameters

[in]

arcs

Dynamic array containing the arcs to insert.

Returns

A graph containing exactly the arcs provided in arcs.

Exceptions

bad_alloc

If there is not enough memory.

Definition at line 1239 of file tpl_graph_utils.H.

References ARC_COOKIE, arcs, FunctionalMethods< Container, T >::for_each(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::maps(), NODE_COOKIE, and Aleph::DynMapTree< Key, Data, Tree, Compare >::search().

build_subgraph()

template<class GT >

void Aleph::build_subgraph ( const GT &  g, GT &  sg, typename GT::Node *  g_src, size_t &  node_count  )

inline

Forward declaration for build_subgraph().

Build a mapped subgraph from a starting node.

Traverses g in depth-first order starting at g_src, copying every reachable node and arc into sg.

node_count accumulates the number of visited nodes across repeated calls (useful when building all components).

Note

Uses the Build_Subtree control bit on both nodes and arcs.

Uses cookies to map nodes/arcs between g and sg.

Parameters

[in]	g	Original graph.
[out]	sg	Destination graph (expected to be initially empty).
[in]	g_src	Starting node in g (must be non-null and belong to g).
[in,out]	node_count	Visited node counter.

Exceptions

bad_alloc

If there is not enough memory.

See also

inconnected_components(), copy_graph()

Definition at line 997 of file tpl_graph_utils.H.

References ARC_BITS, Aleph::build_subgraph(), Aleph::Build_Subtree, GraphCommon< GT, Node, Arc >::get_arc_it(), GTArcCommon< ArcInfo >::get_info(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), IS_ARC_VISITED, IS_NODE_VISITED, GraphCommon< GT, Node, Arc >::map_arcs(), GraphCommon< GT, Node, Arc >::map_nodes(), Aleph::maps(), and NODE_BITS.

Referenced by Aleph::build_subgraph(), Aleph::inconnected_components(), and TEST().

clear_graph()

template<class GT >

void Aleph::clear_graph ( GT &  g )

inlinenoexcept

Clean a graph: all its nodes and arcs are removed and freed.

Parameters

[in]

g

the graph

Definition at line 3549 of file tpl_graph.H.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_arc(), and Aleph::List_Graph< _Graph_Node, _Graph_Arc >::remove_node().

Referenced by Aleph::Euclidian_Graph< __Euclidian_Node, __Euclidian_Arc >::~Euclidian_Graph(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::~List_Graph(), Aleph::Net_Cap_Graph< NodeT, ArcT >::~Net_Cap_Graph(), Aleph::Karger_Min_Cut< GT, SA >::build_kgraph(), Aleph::Find_Depth_First_Spanning_Tree< GT, SA >::build_tree(), Aleph::Find_Breadth_First_Spanning_Tree< GT, SA >::build_tree(), Aleph::Bellman_Ford< GT, Distance, Ait, NAit, SA >::build_tree(), Aleph::GraphCopyWithMapping< GT, Tree >::clear(), Aleph::IndexNode< GT, Compare, Tree, SN >::clear_graph(), Aleph::Net_Cap_Graph< NodeT, ArcT >::compute_aux_net(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::compute_min_paths_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_partial_min_paths_tree(), Aleph::Dijkstra_Min_Paths< GT, Distance, Itor, SA, HeapT >::compute_partial_min_paths_tree(), Aleph::AStar_Min_Path< GT, Distance, Heuristic, Itor, SA, HeapT >::compute_partial_path(), Aleph::Copy_Graph< GT, SN, SA >::copy(), Aleph::copy_graph(), Aleph::Net_Cap_Graph< NodeT, ArcT >::free_aux_net(), Aleph::inter_copy_graph(), Aleph::Compute_Cut_Nodes< GT, SA >::map_cut_graph(), Aleph::Compute_Cut_Nodes< GT, SA >::map_subgraph(), Aleph::Prim_Min_Spanning_Tree< GT, Distance, SA >::min_spanning_tree(), Aleph::Build_Grid< GT, Operation_On_Node, Operation_On_Arc >::operator()(), Aleph::Kruskal_Min_Spanning_Tree< GT, Distance, SA >::paint_min_spanning_tree(), and TEST_F().

compute_bipartite()

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::compute_bipartite	(	const GT &	g,
		DynDlist< typename GT::Node * > &	l,
		DynDlist< typename GT::Node * > &	r
	)

Computes the partition sets of a bipartite graph.

A graph is bipartite if it can be divided into two subsets l and r such that every node in l only has edges to nodes in r and vice versa.

compute_bipartite(g,l,r) takes a bipartite graph g and computes the bipartition sets named by parameters l and r, respectively.

Parameters

[in]	g	the bipartite graph.
[out]	l	one partition set.
[out]	r	the other partition set.

Exceptions

domain_error	if during computation it is determined that the graph is not bipartite.
bad_alloc	if there is not enough memory.

Definition at line 94 of file tpl_bipartite.H.

References ah_domain_error_if, Aleph::Bp_Blue, Aleph::Bp_Red, Aleph::DynList< T >::get(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_node(), Aleph::HTList::is_empty(), l, Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), Aleph::DynList< T >::put(), Aleph::DynDlist< T >::put(), GraphCommon< GT, Node, Arc >::reset_arcs(), and GraphCommon< GT, Node, Arc >::reset_nodes().

Referenced by Aleph::compute_maximum_cardinality_bipartite_matching(), demo_dating(), demo_definition(), demo_halls_theorem(), demo_matching(), and demo_testing().

compute_bipartite_all_components()

template<class GT , class SA = Dft_Show_Arc<GT>>

bool Aleph::compute_bipartite_all_components	(	const GT &	g,
		DynDlist< typename GT::Node * > &	l,
		DynDlist< typename GT::Node * > &	r
	)

Computes the partition sets of a bipartite graph handling all connected components.

Unlike compute_bipartite(), this function processes disconnected graphs correctly by running BFS from each unvisited node.

Parameters

[in]	g	the graph to test.
[out]	l	one partition set (red nodes).
[out]	r	the other partition set (blue nodes).

Returns

true if the graph is bipartite, false otherwise.

Definition at line 330 of file tpl_bipartite.H.

References Aleph::DynList< T >::append(), Aleph::DynDlist< T >::append(), Aleph::Bp_Blue, Aleph::Bp_Red, Aleph::Bp_White, Aleph::DynListQueue< T >::get(), Aleph::DynListQueue< T >::is_empty(), l, Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), Aleph::DynListQueue< T >::put(), GraphCommon< GT, Node, Arc >::reset_arcs(), and GraphCommon< GT, Node, Arc >::reset_nodes().

compute_cut_nodes()

template<class GT >

Aleph::compute_cut_nodes	(	const GT &	g,
		typename GT::Node *	start
	)

Compute articulation points (cut vertices) of an undirected graph.

Uses a DFS-based algorithm (Tarjan-style) to compute the articulation points reachable from start.

Side effects:

• Resets arc control attributes via g.reset_arcs().
• Resets node counters and control bits (all node bit fields are cleared).
• Uses the Depth_First and Cut control bits on nodes, and Depth_First on arcs.
• Temporarily stores low-link values in node cookies and clears all node cookies to nullptr before returning.

Note

For a disconnected graph, only the connected component reachable from start is analyzed.

Parameters

[in]	g	Graph to analyze (must not be a digraph).
[in]	start	Starting node (must be non-null and belong to g).

Returns

List of articulation nodes (pointers into g).

Exceptions

domain_error	If g is a directed graph.
bad_alloc	If there is not enough memory.

See also

paint_subgraphs(), map_subgraph(), map_cut_graph()

Definition at line 1332 of file tpl_graph_utils.H.

References Aleph::Cookie_Guard< GT >::~Cookie_Guard(), Aleph::__compute_cut_nodes(), ah_domain_error_if, ah_invalid_argument_if, Aleph::DynList< T >::append(), ARC_BITS, Aleph::Cut, Aleph::Depth_First, GraphCommon< GT, Node, Arc >::get_arc_it(), GraphCommon< GT, Node, Arc >::get_node_it(), GraphCommon< GT, Node, Arc >::get_num_nodes(), IS_ARC_VISITED, GraphCommon< GT, Node, Arc >::is_digraph(), IS_NODE_VISITED, Aleph::maps(), NODE_BITS, NODE_COOKIE, NODE_COUNTER, nodes, and GraphCommon< GT, Node, Arc >::reset_arcs().

Referenced by Aleph::compute_cut_nodes(), TEST(), TEST(), TEST(), and write_df_low_tree().

compute_maximum_cardinality_bipartite_matching()

template<class GT , template< class > class Max_Flow = Ford_Fulkerson_Maximum_Flow, class SA = Dft_Show_Arc<GT>>

void Aleph::compute_maximum_cardinality_bipartite_matching	(	const GT &	g,
		DynDlist< typename GT::Arc * > &	matching
	)

Computes the maximum cardinality matching of a bipartite graph.

compute_maximum_cardinality_bipartite_matching(g,matching) takes a bipartite graph g and computes the maximum bipartite matching in the list matching.

The procedure computes the bipartition sets, then constructs an equivalent unit-capacity flow network and invokes a maximum flow algorithm on it.

The routine handles two type parameters:

1. GT the bipartite graph type
2. Max_Flow the maximum flow algorithm to use for the computation

Parameters

[in]	g	the bipartite graph.
[out]	matching	list of arcs that form the matching.

Exceptions

bad_alloc

if there is not enough memory.

Definition at line 208 of file tpl_bipartite.H.

References Aleph::DynList< T >::append(), Aleph::compute_bipartite(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Dlink::Iterator::has_curr(), Aleph::DynList< T >::insert(), l, Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), and NODE_COOKIE.

compute_min_cut()

template<class GT , template< class > class Max_Flow = Heap_Preflow_Maximum_Flow, class SA = Dft_Show_Arc<GT>>

long Aleph::compute_min_cut	(	GT &	g,
		DynSetTree< typename GT::Node * > &	l,
		DynSetTree< typename GT::Node * > &	r,
		DynDlist< typename GT::Arc * > &	cut
	)

Compute a minimum edge cut of an undirected graph.

Builds a unit-capacity auxiliary network and uses successive max-flow computations to obtain a minimum cut. The partition and cut arcs are returned through output parameters.

The arc filter SA is applied when computing degrees, connectivity, and when building the auxiliary network.

Output parameters are cleared on entry.

Note

If the graph is disconnected, returns 0, cut is empty, and the partition l/r corresponds to the component reachable from a minimum-degree node.

If the graph is connected and the minimum filtered degree is <= 1, the cut isolates a minimum-degree node.

Side effects:

• Uses the Depth_First control bit on nodes and arcs to test connectivity.
• Overwrites node cookies to map GT <-> Net nodes when the auxiliary network is built.
• Overwrites arc cookies on the auxiliary network to map back to GT arcs.

Template Parameters

GT	Graph type (undirected).
Max_Flow	Maximum flow functor.
SA	Arc filter functor.

Parameters

[in,out]	g	Graph to analyze.
[out]	l	Set of nodes on the source side of the cut.
[out]	r	Set of nodes on the sink side of the cut.
[out]	cut	List of cut arcs (arcs crossing between l and r).

Returns

Edge connectivity of g (minimum cut size).

Exceptions

std::domain_error	If g is a digraph.
std::bad_alloc	If there is not enough memory.

Definition at line 263 of file tpl_kgraph.H.

References ah_domain_error_if, Aleph::DynList< T >::append(), Aleph::DynDlist< T >::append(), ARC_COOKIE, Aleph::Depth_First, Aleph::DynSetTree< Key, Tree, Compare >::empty(), Aleph::DynList< T >::empty(), Aleph::DynDlist< T >::empty(), GraphCommon< GT, Node, Arc >::get_connected_node(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Dlink::Iterator::has_curr(), Aleph::HTList::Iterator::has_curr(), Aleph::BinNodeInfixIterator< Node >::has_curr(), Aleph::DynSetTree< Key, Tree, Compare >::insert(), Aleph::DynList< T >::insert(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::insert_node(), GraphCommon< GT, Node, Arc >::is_digraph(), IS_NODE_VISITED, l, GraphCommon< GT, Node, Arc >::map_nodes(), Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_COOKIE, num_nodes, Aleph::Net_Graph< NodeT, ArcT >::remove_node(), Aleph::Net_Graph< NodeT, ArcT >::reset(), and Aleph::DynList< T >::swap().

copy_graph()

template<class GT >

void Aleph::copy_graph ( GT &  gtgt, const GT &  gsrc, bool  cookie_map = false  )

inline

Explicit copy of graph.

This function takes a source graph gsrc for copying to another target graph gtgt. First the function cleans gtgt; that is all its arc and nodes are removed and freed. Then gsrc is copied to gtgt- The resulting gtgt is isomorphic to gsrc.

Eventually, the copy can be mapped through the cookies. For that, a forth bool parameter is specified-

Parameters

[in]	gsrc	source graph
[in]	gtgt	target graph
[in]	cookie_map	boolean indicating if the result must be mapped through the nodes and arcs cookies.

Exceptions

bad_alloc

if there is no enough memory

Definition at line 3567 of file tpl_graph.H.

References Aleph::clear_graph(), GTNodeCommon< NodeInfo >::get_info(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), GraphCommon< GT, Node, Arc >::map_arcs(), GraphCommon< GT, Node, Arc >::map_nodes(), and Aleph::maps().

Referenced by Aleph::Digraph< BaseGraph >::Digraph(), Aleph::Euclidian_Graph< __Euclidian_Node, __Euclidian_Arc >::Euclidian_Graph(), Aleph::Net_Graph< NodeT, ArcT >::Net_Graph(), Aleph::Digraph< BaseGraph >::operator=(), and Aleph::Euclidian_Graph< __Euclidian_Node, __Euclidian_Arc >::operator=().

depth_first_traversal()

template<class GT >

size_t Aleph::depth_first_traversal ( const GT &  g, typename GT::Node *  start_node, bool(*)(const GT &g, typename GT::Node *, typename GT::Arc *)  visit  )

inline

Depth-first traversal starting from a given node.

Recursively traverses the connected component reachable from start_node.

The callback must have the following signature: bool visit(const GT& g, typename GT::Node* curr, typename GT::Arc* from).

from is the arc that discovered curr (nullptr for the start node). If visit returns true, the traversal stops early. If visit is nullptr, no callback is executed.

Template Parameters

GT	Graph type.

Parameters

[in]	g	Graph to traverse.
[in]	start_node	Starting node (must be non-null and belong to g).
[in]	visit	Optional visit callback (may be nullptr).

Returns

Number of discovered nodes.

Note

Resets the Depth_First control bit on all nodes and arcs.

Uses the Depth_First control bit on both nodes and arcs.

See also

Depth_First_Traversal, breadth_first_traversal, test_connectivity

Definition at line 106 of file tpl_graph_utils.H.

References Aleph::__depth_first_traversal(), Aleph::Depth_First, Aleph::maps(), GraphCommon< GT, Node, Arc >::reset_bit_arcs(), and GraphCommon< GT, Node, Arc >::reset_bit_nodes().

Referenced by Aleph::depth_first_traversal(), TEST(), TEST(), TEST(), and write_df_low_tree().

digraph_graphviz()

template<class GT , class Node_Attr , class Arc_Attr , class SN , class SA >

void Aleph::digraph_graphviz	(	const GT &	g,
		std::ostream &	out,
		Node_Attr	node_attr = Node_Attr(),
		Arc_Attr	arc_attr = Arc_Attr(),
		const std::string &	rankdir = "LR"
	)

Generate Graphviz DOT output specifically for digraphs.

Similar to generate_graphviz() but always outputs "digraph {}" regardless of the graph type. Useful when you want to force directed edge notation.

Template Parameters

GT	Graph type
Node_Attr	Node attribute generator
Arc_Attr	Arc attribute generator
SN	Node filter
SA	Arc filter

Parameters

g	Graph to visualize
out	Output stream
node_attr	Node attribute functor
arc_attr	Arc attribute functor
rankdir	Layout direction (default: "LR" for left-to-right)

See also

generate_graphviz() For automatic graph/digraph detection

Definition at line 448 of file generate_graph.H.

References GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::DynList< T >::insert(), Aleph::maps(), and Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne().

edge_connectivity()

template<class GT , template< class > class Max_Flow = Random_Preflow_Maximum_Flow, class SA = Dft_Show_Arc<GT>>

long Aleph::edge_connectivity

(

GT &

g

)

Compute edge connectivity (arc connectivity) of an undirected graph.

Builds a unit-capacity auxiliary network and computes maximum flow from a fixed source to every other node. The minimum of those flow values equals the edge connectivity.

The arc filter SA is applied when computing degrees and when building the auxiliary network.

Template Parameters

GT	Graph type (undirected).
Max_Flow	Maximum flow functor to use.
SA	Arc filter functor.

Side effects:

• Uses the Depth_First control bit on nodes and arcs to test connectivity.
• Overwrites node cookies to store the GT -> Net mapping when the auxiliary network is built.

Parameters

[in,out]

g

Graph to analyze.

Returns

Edge connectivity of g (0 for empty or disconnected graphs).

Note

For connected graphs with minimum filtered degree <= 1, returns that degree without running max flow.

Exceptions

std::domain_error	If g is a digraph.
std::bad_alloc	If there is not enough memory.

Definition at line 110 of file tpl_kgraph.H.

References ah_domain_error_if, Aleph::DynList< T >::append(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Dlink::Iterator::has_curr(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::insert_node(), GraphCommon< GT, Node, Arc >::is_digraph(), Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_COOKIE, num_nodes, Aleph::Net_Graph< NodeT, ArcT >::remove_node(), and Aleph::Net_Graph< NodeT, ArcT >::reset().

find_breadth_first_spanning_tree()

template<class GT >

GT Aleph::find_breadth_first_spanning_tree ( GT &  g, typename GT::Node *  gp  )

inline

Build a breadth-first spanning tree (mapped to the original graph).

Returns a spanning tree of the connected component reachable from gp, visiting nodes in breadth-first order.

Side effects:

• Resets the Spanning_Tree control bit on all nodes and arcs.
• Uses the Spanning_Tree control bit on both nodes and arcs.
• Maps nodes and arcs between g and the returned tree via cookies.

Parameters

[in,out]	g	Graph to traverse.
[in]	gp	Start node (must be non-null and belong to g).

Returns

A mapped spanning tree of the reachable component.

Exceptions

bad_alloc

If there is not enough memory.

See also

find_depth_first_spanning_tree()

Definition at line 1158 of file tpl_graph_utils.H.

References ARC_BITS, Aleph::DynList< T >::get(), Aleph::DynListQueue< T >::get(), GraphCommon< GT, Node, Arc >::get_arc_it(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), IS_ARC_VISITED, Aleph::DynListQueue< T >::is_empty(), IS_NODE_VISITED, GraphCommon< GT, Node, Arc >::map_arcs(), GraphCommon< GT, Node, Arc >::map_nodes(), Aleph::maps(), NODE_BITS, Aleph::DynListQueue< T >::put(), GraphCommon< GT, Node, Arc >::reset_bit_arcs(), GraphCommon< GT, Node, Arc >::reset_bit_nodes(), and Aleph::Spanning_Tree.

Referenced by TEST().

find_depth_first_spanning_tree()

template<class GT >

GT Aleph::find_depth_first_spanning_tree ( const GT &  g, typename GT::Node *  gnode  )

inline

Build a depth-first spanning tree (mapped to the original graph).

Returns a spanning tree of the connected component reachable from gnode, visiting nodes in depth-first order.

Side effects:

• Resets all node and arc control attributes via g.reset_nodes() and g.reset_arcs().
• Uses the Spanning_Tree control bit on both nodes and arcs.
• Maps nodes and arcs between g and the returned tree via cookies.

Parameters

[in]	g	Graph to traverse.
[in]	gnode	Start node (must be non-null and belong to g).

Returns

A mapped spanning tree of the reachable component.

Exceptions

bad_alloc

If there is not enough memory.

See also

find_breadth_first_spanning_tree()

Definition at line 1065 of file tpl_graph_utils.H.

References Aleph::__find_depth_first_spanning_tree(), GraphCommon< GT, Node, Arc >::get_arc_it(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), IS_ARC_VISITED, IS_NODE_VISITED, GraphCommon< GT, Node, Arc >::map_nodes(), Aleph::maps(), NODE_BITS, GraphCommon< GT, Node, Arc >::reset_arcs(), GraphCommon< GT, Node, Arc >::reset_nodes(), GraphCommon< GT, Node, Arc >::set_bit(), and Aleph::Spanning_Tree.

Referenced by Aleph::find_depth_first_spanning_tree(), TEST(), and write_df_low_tree().

find_min_path() [1/2]

template<class Mat >

void Aleph::find_min_path	(	Mat &	p,
		const long	src_index,
		const long	tgt_index,
		Path< typename Mat::Graph_Type > &	path
	)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Variant that accepts const indices.

Build a minimum path from Floyd-Warshall path matrix using indices.

See mat_path.H for the primary definition and full documentation. This overload is provided for compatibility with const index values.

See also

mat_path.H For the primary definition with non-const indices

Takes a path matrix computed by Floyd-Warshall algorithm and two matrix indices (source and target), then constructs the minimum path in the adjacency list representation.

The path is reconstructed by following the intermediate node indices stored in the path matrix until reaching the target.

Template Parameters

Mat	Matrix type from Map_Matrix_Graph (e.g., Ady_Mat<GT, long, ...>)

Parameters

[in]	p	Path index matrix from Floyd-Warshall. Entry p(i,j) contains the index of the next node after i on the shortest path to j.
[in]	src_index	Source node index in the path matrix (0-based).
[in]	tgt_index	Target node index in the path matrix (0-based).
[out]	path	The reconstructed minimum path in the adjacency list graph. The path is cleared and rebuilt from scratch.

Precondition

The path matrix p must have been computed by floyd_all_shortest_paths().

src_idx and tgt_idx must be valid indices (0 <= idx < n).

A path must exist between src_idx and tgt_idx (no infinite distance).

Warning

Results are undefined if:

• The path matrix is invalid or not properly computed
• There is no path between source and target
• The indices are out of range

Exceptions

std::bad_alloc

If insufficient memory to build the path.

Complexity

• Time: O(k) where k is the number of nodes in the path
• Space: O(k) for storing the path

See also

floyd_all_shortest_paths()

find_min_path(Mat&, typename Mat::Node*, typename Mat::Node*, Path<typename Mat::Graph_Type>&)

latex_floyd.H For variant with const indices

Definition at line 229 of file latex_floyd.H.

References Aleph::Path< GT >::append(), Aleph::find_min_path(), Aleph::maps(), Aleph::next(), and Aleph::Path< GT >::set_graph().

Referenced by Aleph::find_min_path(), Aleph::find_min_path(), TEST_F(), TEST_F(), and TEST_F().

find_min_path() [2/2]

template<class Mat >

void Aleph::find_min_path	(	Mat &	p,
		typename Mat::Node *	src_node,
		typename Mat::Node *	tgt_node,
		Path< typename Mat::Graph_Type > &	path
	)

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.Reconstruct shortest path from path matrix using node pointers.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Build a minimum path using node pointers instead of indices.

Convenience overload that accepts node pointers instead of indices.

Template Parameters

Mat	Path matrix type

Parameters

[in]	p	The path matrix from Floyd-Warshall
[in]	src_node	Source node pointer
[in]	tgt_node	Target node pointer
[out]	path	The reconstructed path

See also

find_min_path(Mat&, const long, const long, Path<GT>&)

Convenience overload that accepts node pointers and converts them to matrix indices before calling the index-based version.

See also

find_min_path(Mat&, long, long, Path<typename Mat::Graph_Type>&)

Definition at line 266 of file latex_floyd.H.

References Aleph::find_min_path(), and Aleph::maps().

find_path_breadth_first()

template<class GT >

Path< GT > Aleph::find_path_breadth_first ( const GT &  g, typename GT::Node *  start, typename GT::Node *  end  )

inline

Breadth-first search of a (shortest-by-edges) path between two nodes.

Searches a path from start to end using breadth-first search (BFS). If a path exists, the returned path has the minimum number of arcs (ties depend on iteration order).

Side effects:

• Resets all node and arc control attributes via g.reset_nodes() and g.reset_arcs().
• Uses the Find_Path control bit on nodes and arcs.
• Stores predecessor pointers in node cookies while searching.

Template Parameters

GT	Graph type.

Parameters

[in]	g	Graph to search.
[in]	start	Start node (must be non-null and belong to g).
[in]	end	End node (must be non-null and belong to g).

Returns

A Path<GT> describing the found path; an empty path if no path exists.

Exceptions

bad_alloc

If there is not enough memory.

See also

find_path_depth_first(), test_for_path()

Definition at line 554 of file tpl_graph_utils.H.

References ah_invalid_argument_if, ARC_BITS, Aleph::DynListQueue< T >::empty(), Aleph::Find_Path, Aleph::DynListQueue< T >::get(), GraphCommon< GT, Node, Arc >::get_arc_it(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Path< GT >::insert(), IS_ARC_VISITED, Aleph::DynListQueue< T >::is_empty(), IS_NODE_VISITED, Aleph::maps(), NODE_BITS, NODE_COOKIE, Aleph::DynListQueue< T >::put(), GraphCommon< GT, Node, Arc >::reset_arcs(), and GraphCommon< GT, Node, Arc >::reset_nodes().

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

find_path_depth_first()

template<class GT >

Path< GT > Aleph::find_path_depth_first ( const GT &  g, typename GT::Node *  start_node, typename GT::Node *  end_node  )

inline

Depth-first search of a path between two nodes.

find_path_depth_first() recursively searches a path between start_node y end_node

Parameters

[in]	g	the graph
[in]	start_node	pointer to the starting node of search
[in]	end_node	pointer to ending node of search

Returns

a Path object containing the path if this was found; an empty path otherwise

Exceptions

bad_alloc

if there is no enough memory

See also

find_path_breadth_first()

Definition at line 3468 of file tpl_graph.H.

References ARC_BITS, Aleph::Path< GT >::empty(), Aleph::Find_Path, GraphCommon< GT, Node, Arc >::get_arc_it(), IS_NODE_VISITED, Aleph::maps(), NODE_BITS, GraphCommon< GT, Node, Arc >::reset_bit_arcs(), and GraphCommon< GT, Node, Arc >::reset_bit_nodes().

Referenced by TEST_F(), and TEST_F().

floyd_all_shortest_paths()

template<class GT , class Compare , class Plus >

void Aleph::floyd_all_shortest_paths	(	GT &	g,
		Ady_Mat< GT, typename GT::Arc_Type::Distance_Type > &	dist,
		Ady_Mat< GT, long > &	path
	)

Compute all-pairs shortest paths using Floyd-Warshall algorithm.

Computes the shortest path between every pair of vertices in the graph. The algorithm runs in O(V³) time and O(V²) space.

Template Parameters

GT	Graph type (must have Arc_Type with Distance_Type, Max_Distance, Zero_Distance)
Compare	Comparison functor (default: less)
Plus	Addition functor for distances (default: plus)

Parameters

	g	The input graph
[out]	dist	Distance matrix - dist(i,j) = shortest distance from i to j
[out]	path	Path matrix - path(i,j) = next node on shortest path from i to j

Note

The path matrix can be used with find_min_path() to reconstruct paths.

Warning

Does not detect negative cycles.

Definition at line 171 of file latex_floyd.H.

References GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::maps(), and max().

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

floyd_all_shortest_paths_latex()

template<class GT , class Compare , class Plus , template< class > class P_i, template< class > class P_ij, template< class > class D_ij>

void Aleph::floyd_all_shortest_paths_latex	(	GT &	g,
		Ady_Mat< GT, typename GT::Arc_Type::Distance_Type > &	dist,
		Ady_Mat< GT, long > &	path,
		std::ofstream &	output
	)

Floyd-Warshall algorithm with LaTeX step-by-step output.

Computes all-pairs shortest paths while generating LaTeX output showing the distance and path matrices at each iteration step. Useful for educational purposes and algorithm visualization.

LaTeX Output Format

Generates figures with side-by-side D_k and P_k matrices for k = 0..n. Requires LaTeX packages: float (for [H] placement).

Template Parameters

GT	Graph type
Compare	Comparison functor
Plus	Addition functor
P_i	Row/column index formatter
P_ij	Path matrix entry formatter
D_ij	Distance matrix entry formatter

Parameters

	g	The input graph
[out]	dist	Distance matrix
[out]	path	Path matrix
[out]	output	Output stream for LaTeX code

See also

floyd_all_shortest_paths() For algorithm without LaTeX output

Definition at line 308 of file latex_floyd.H.

References GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::maps(), max(), and output.

Referenced by TEST_F(), TEST_F(), and TEST_F().

foldl_arcs() [1/2]

template<class GT , typename T , class SA = Dft_Show_Arc<GT>>

T Aleph::foldl_arcs	(	GT &	g,
		const T &	init,
		std::function< T(const T &, typename GT::Arc *)>	operation,
		SA	sa = SA()
	)

Fold the filtered arcs of a graph.

Parameters

[in]	g	the graph
[in]	init	initial value of folded result
[in]	operation	folding operation on the arc
[in]	sa	arc filter

Returns

the final folded result

Definition at line 1474 of file tpl_graph.H.

References Aleph::init, and Aleph::maps().

foldl_arcs() [2/2]

template<class GT , typename T , class SA = Dft_Show_Arc<GT>>

T Aleph::foldl_arcs	(	GT &	g,
		typename GT::Node *	p,
		const T &	init,
		std::function< T(const T &, typename GT::Arc *)>	operation,
		SA	sa = SA()
	)

Fold the filtered adjacent arcs of a node.

Parameters

[in]	g	the graph
[in]	p	node pointer
[in]	init	initial value of folded result
[in]	operation	folding operation on the arc
[in]	sa	arc filter

Returns

the final folded result

Definition at line 1497 of file tpl_graph.H.

References Aleph::init, and Aleph::maps().

foldl_nodes()

template<class GT , typename T , class SN = Dft_Show_Node<GT>>

T Aleph::foldl_nodes	(	GT &	g,
		const T &	init,
		std::function< T(const T &, typename GT::Node *)>	operation,
		SN	sn = SN()
	)

Fold the filtered nodes of a graph.

Parameters

[in]	g	the graph
[in]	init	initial value of folded result
[in]	operation	folding operation on the node
[in]	sn	node filter

Returns

the final folded result

Definition at line 1452 of file tpl_graph.H.

References Aleph::init, and Aleph::maps().

for_each_arc() [1/3]

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::for_each_arc	(	const GT &	g,
		std::function< void(typename GT::Arc *)>	operation,
		SA	sa = SA()
	)

Traverse all the arcs of graph filtering some ones according to a condition and executing an operation on them.

Parameters

[in]	g	the graph
[in]	operation	to be executed on each seen arc
[in]	sa	an arc filter

Definition at line 1256 of file tpl_graph.H.

References Aleph::maps(), and Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne().

for_each_arc() [2/3]

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::for_each_arc	(	const GT &	g,
		typename GT::Node *	p,
		std::function< void(typename GT::Arc *)>	operation,
		SA	sa = SA()
	)

Traverse all the arcs adjacent to a node filtering some ones according to a condition and executing an operation on them.

Parameters

[in]	g	the graph
[in]	p	a node pointer
[in]	operation	to be executed on each seen arc
[in]	sa	an arc filter

Definition at line 1275 of file tpl_graph.H.

References Aleph::maps(), and Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne().

for_each_arc() [3/3]

template<class GT , class Itor , class Operation >

void Aleph::for_each_arc ( typename GT::Node *  p, Operation  op = Operation()  )

inline

Execute an operation on each arc of a node.

This template function receives threes template parameters:

1. GT: the graph type.
2. Itor: the iterator type; it is intended to be _In_Iterator or _Out_Iterator.
3. Operation: an operation to be executed on each arc. This operation must have the following signature:

void operation(typename GT::Arc * arc)

Parameters

[in]	p	node pointer
[in]	op	operation to be performed on each arc

Definition at line 2054 of file tpl_graph.H.

for_each_in_arc()

template<class GT , class Op >

void Aleph::for_each_in_arc ( typename GT::Node *  p, Op  op = Op()  )

inline

Traverse the incoming arcs of a node and executes an operation.

Parameters

[in]	p	node pointer
[in]	op	operation to perform on each node

Definition at line 2087 of file tpl_graph.H.

References Aleph::maps().

Referenced by Aleph::filter_in_arcs(), Aleph::foldl_in_arcs(), and Aleph::map_in_arcs().

for_each_node()

template<class GT , class SN = Dft_Show_Node<GT>>

void Aleph::for_each_node	(	const GT &	g,
		std::function< void(typename GT::Node *)>	operation,
		SN	sn = SN()
	)

Traverse all the nodes of graph filtering some ones according to a condition and executing an operation on them.

Parameters

[in]	g	the graph
[in]	operation	to be executed on each seen node
[in]	sn	a node filter

Definition at line 1238 of file tpl_graph.H.

References Aleph::maps(), and Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne().

for_each_out_arc()

template<class GT , class Op >

void Aleph::for_each_out_arc ( typename GT::Node *  p, Op  op = Op()  )

inline

Traverse the outcoming arcs of a node and executes an operation.

Parameters

[in]	p	node pointer
[in]	op	operation to perform on each node

Definition at line 2260 of file tpl_graph.H.

References Aleph::maps().

Referenced by Aleph::filter_out_arcs(), Aleph::foldl_out_arcs(), and Aleph::map_out_arcs().

forall_arc() [1/2]

template<class GT , class SA = Dft_Show_Arc<GT>>

bool Aleph::forall_arc	(	const GT &	g,
		std::function< bool(typename GT::Arc *)>	cond,
		SA	sa = SA()
	)

Return true if condition cond is met on every filtered arc of the graph.

Parameters

[in]	g	the graph
[in]	cond	condition
[in]	sa	arc filter

Returns

true if all the arcs satisfy the condition; false otherwise

Definition at line 1317 of file tpl_graph.H.

References Aleph::maps(), and Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne().

forall_arc() [2/2]

template<class GT , class SA = Dft_Show_Arc<GT>>

bool Aleph::forall_arc	(	typename GT::Node *	p,
		std::function< bool(typename GT::Arc *)>	cond,
		SA	sa = SA()
	)

Return true if the condition cond is met on every filtered arc of a node.

Parameters

[in]	p	node pointer
[in]	cond	condition
[in]	sa	arc filter

Returns

true if all the arcs satisfy the condition; false otherwise

Definition at line 1338 of file tpl_graph.H.

References Aleph::maps(), and Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne().

forall_node()

template<class GT , class SN = Dft_Show_Node<GT>>

bool Aleph::forall_node	(	const GT &	g,
		std::function< bool(typename GT::Node *)>	cond,
		SN	sn = SN()
	)

Return true if condition cond is met on every filtered node of the graph.

Parameters

[in]	g	the graph
[in]	cond	condition
[in]	sn	node filter

Returns

true if all the nodes satisfy the condition; false otherwise

Definition at line 1296 of file tpl_graph.H.

References Aleph::maps(), and Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne().

generate_cross_graph()

template<class GT , class Write_Node , class Write_Arc , class Shade_Node , class Shade_Arc , class SA >

void Aleph::generate_cross_graph	(	GT &	g,
		const size_t &	nodes_by_level,
		const double &	xdist,
		const double &	ydist,
		std::ostream &	out
	)

Generate a cross-graph layout specification for graphpic.

Creates a graphpic specification with nodes arranged in a cross pattern. In this layout, even levels have (nodes_by_level - 1) nodes and odd levels have nodes_by_level nodes, creating a staggered pattern.

Template Parameters

GT	Graph type
Write_Node	Functor returning node label string
Write_Arc	Functor returning arc label string
Shade_Node	Functor returning shading command (e.g., "SHADOW-NODE")
Shade_Arc	Functor returning shading command (e.g., "SHADOW-ARC")
SA	Arc filter

Parameters

g	Graph to visualize
nodes_by_level	Nodes per level (last level may have fewer)
xdist	Horizontal distance between nodes
ydist	Vertical distance between levels
out	Output stream for graphpic specification

Definition at line 792 of file generate_graph.H.

References GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::is_digraph(), and Aleph::maps().

Referenced by Aleph::generate_cross_graph(), and generate_cross_spanning_tree().

generate_cross_spanning_tree()

template<typename GT , class Write_Node , class Write_Arc , class SA >

void generate_cross_spanning_tree	(	GT &	g,
		const size_t &	nodes_by_level,
		const double &	xdist,
		const double &	ydist,
		std::ofstream &	output
	)

Generate a cross-layout visualization of a spanning tree.

Creates a graphpic specification with nodes arranged in a cross pattern, with spanning tree edges highlighted.

Template Parameters

GT	Graph type
Write_Node	Functor to convert node content to string
Write_Arc	Functor to convert arc content to string
SA	Arc filter class

Parameters

g	The graph containing the spanning tree
nodes_by_level	Number of nodes per level in the layout
xdist	Horizontal distance between nodes
ydist	Vertical distance between levels
output	Output stream for the graphpic specification

See also

generate_cross_graph() For the underlying layout function

Definition at line 122 of file generate_spanning_tree_picture.H.

References Aleph::generate_cross_graph(), Aleph::maps(), and output.

generate_dot_file()

void Aleph::generate_dot_file ( Digrafo &  g, std::ostream &  output  )

inline

Generate a DOT representation of the digraph.

Creates a DOT file suitable for rendering with Graphviz. The output includes:

• Node colors based on the "plazo" field (cp=Green, mp=Yellow, lp=Red)
• Optional labels showing power and NES values
• Optional shapes based on the "class" field
• Cycle detection with warning comments
• Topological ranking for acyclic graphs

The appearance is controlled by the global configuration variables: with_power, with_nes, only_num, with_class, font_size.

Parameters

g	The digraph to export.
output	Output stream for the DOT data.

Definition at line 280 of file load_digraph.H.

References Aleph::font_size, Aleph::generate_dot_file(), LocateFunctions< Container, Type >::get_it(), Aleph::Dlink::Iterator::has_curr(), Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), Aleph::only_num, output, Aleph::ranks(), Aleph::with_class, Aleph::with_nes, and Aleph::with_power.

Referenced by Aleph::generate_dot_file(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

generate_graphpic()

template<class GT , class Write_Node , class Write_Arc , class Shade_Node , class Shade_Arc , class SA >

void Aleph::generate_graphpic	(	const GT &	g,
		const double &	xdist,
		const double &	ydist,
		std::ostream &	output
	)

Generate a graphpic specification for graph visualization.

Creates a text specification for the graphpic drawing program. Handles both graphs and digraphs, with support for curved arcs when bidirectional edges exist.

Template Parameters

• GT: Graph or digraph type
• Write_Node: Functor returning node label as string
• Write_Arc: Functor returning arc label as string
  
• Shade_Node: Functor returning shading command (e.g., "SHADOW-NODE")
• Shade_Arc: Functor returning shading command (e.g., "SHADOW-ARC")
• SA: Arc filter class

Parameters

g	The graph or digraph to visualize
xdist	Horizontal distance between nodes
ydist	Vertical distance between levels (currently unused)
output	Output stream for the graphpic specification

See also

Filter_Iterator For arc filtering

Definition at line 159 of file generate_graph.H.

References GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), nodes, output, Aleph::HTList::size(), and Aleph::size().

generate_graphviz() [1/2]

template<class GT , class Node_Attr , class Arc_Attr , class SN , class SA >

void Aleph::generate_graphviz	(	const GT &	g,
		std::ostream &	out,
		Node_Attr	node_attr = Node_Attr(),
		Arc_Attr	arc_attr = Arc_Attr(),
		const std::string &	rankdir = "TB"
	)

Generate Graphviz DOT output with custom attribute functors.

Creates a DOT specification using custom functors to generate node and arc attributes. This is the most flexible version, allowing complete control over the DOT output.

Attribute Functors

• Node_Attr: Called as node_attr(g, node, out) to write attributes
• Arc_Attr: Called as arc_attr(g, arc, out) to write attributes

Example attribute functor:

struct MyNodeAttr {
  void operator()(const Graph& g, Graph::Node* n, std::ostream& out) {
    out << "label=\"" << n->get_info() << "\" color=blue";
  }
};

Template Parameters

GT	Graph type
Node_Attr	Node attribute generator functor
Arc_Attr	Arc attribute generator functor
SN	Node filter class
SA	Arc filter class

Parameters

g	Graph to visualize
out	Output stream for DOT specification
node_attr	Functor for node attributes
arc_attr	Functor for arc attributes
rankdir	Layout direction: "TB", "BT", "LR", "RL"

See also

Filter_Iterator For filtering

Definition at line 363 of file generate_graph.H.

References GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::DynList< T >::insert(), GraphCommon< GT, Node, Arc >::is_digraph(), Aleph::maps(), and Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne().

generate_graphviz() [2/2]

template<class GT , class Write_Node , class Write_Arc , class Shade_Node , class Shade_Arc , class Dashed_Node , class Dashed_Arc , class SA , class SN >

void Aleph::generate_graphviz	(	const GT &	g,
		std::ostream &	output,
		const std::string &	rankdir = "TB",
		float	ranksep = 0.2,
		float	nodesep = 0.2
	)

Generate a Graphviz DOT specification for graph visualization.

Creates a DOT format specification for the Graphviz system (dot, neato, etc.). Supports both graphs and digraphs with configurable layout direction.

Template Parameters

• GT: Graph or digraph type
• Write_Node: Functor returning node label
• Write_Arc: Functor returning arc label
• Shade_Node: Returns true to apply bold style to node
• Shade_Arc: Returns true to apply bold style to arc
• Dashed_Node: (unused) For dashed node borders
• Dashed_Arc: (unused) For dashed arc lines
• SA: Arc filter class
• SN: Node filter class

Parameters

g	The graph or digraph to visualize
output	Output stream for the DOT specification
rankdir	Layout direction: "TB" (top-bottom), "BT", "LR", "RL"
ranksep	Separation between ranks (topological levels)
nodesep	Separation between nodes in the same rank

See also

Filter_Iterator For node/arc filtering

Definition at line 247 of file generate_graph.H.

References GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), GraphCommon< GT, Node, Arc >::is_digraph(), Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), nodes, output, and Aleph::HTList::size().

Referenced by Aleph::Generate_Graphviz< GT, Write_Node, Write_Arc, Shade_Node, Shade_Arc, Dashed_Node, Dashed_Arc, SA, SN >::operator()().

generate_net_graph()

template<class GT , class Write_Node , class Write_Arc , class Shade_Node , class Shade_Arc , class SA >

void Aleph::generate_net_graph	(	GT &	g,
		const size_t &	nodes_by_level,
		const double &	xdist,
		const double &	ydist,
		std::ostream &	out
	)

Generate a net-graph layout specification for graphpic.

Creates a graphpic specification with nodes arranged in a regular grid (net) pattern. Each level has exactly nodes_by_level nodes.

Template Parameters

GT	Graph type
Write_Node	Functor returning node label string
Write_Arc	Functor returning arc label string
Shade_Node	Functor returning shading command (e.g., "SHADOW-NODE")
Shade_Arc	Functor returning shading command (e.g., "SHADOW-ARC")
SA	Arc filter

Parameters

g	Graph to visualize
nodes_by_level	Nodes per level (last level may have fewer)
xdist	Horizontal distance between nodes
ydist	Vertical distance between levels
out	Output stream for graphpic specification

Definition at line 848 of file generate_graph.H.

References GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::is_digraph(), and Aleph::maps().

Referenced by Aleph::generate_net_graph(), and generate_net_spanning_tree().

generate_net_spanning_tree()

template<typename GT , class Write_Node , class Write_Arc , class SA >

void generate_net_spanning_tree	(	GT &	g,
		const size_t &	nodes_by_level,
		const double &	xdist,
		const double &	ydist,
		std::ofstream &	output
	)

Generate a net-layout visualization of a spanning tree.

Creates a graphpic specification with nodes arranged in a regular grid (net) pattern, with spanning tree edges highlighted.

Template Parameters

GT	Graph type
Write_Node	Functor to convert node content to string
Write_Arc	Functor to convert arc content to string
SA	Arc filter class

Parameters

g	The graph containing the spanning tree
nodes_by_level	Number of nodes per level in the layout
xdist	Horizontal distance between nodes
ydist	Vertical distance between levels
output	Output stream for the graphpic specification

See also

generate_net_graph() For the underlying layout function

Definition at line 168 of file generate_spanning_tree_picture.H.

References Aleph::generate_net_graph(), Aleph::maps(), and output.

graph_to_tree_node()

template<class GT , typename Key , class Convert , class SA = Dft_Show_Arc<GT>>

Tree_Node< Key > * Aleph::graph_to_tree_node ( GT &  g, typename GT::Node *  groot  )

inline

Convert a tree graph to a Tree_Node structure.

Takes a tree represented as an adjacency-list graph and converts it to a Tree_Node<Key> structure rooted at the specified node.

This enables the use of tree-specific algorithms and visualization tools on spanning trees extracted from graphs.

Conversion Process

The Convert class is invoked for each node:

void Convert::operator()(GT::Node* gnode, Tree_Node<Key>* tnode)

It should copy/transform data from the graph node to the tree node.

Limitations

• Tree_Node<Key> cannot store arc data (only node data)
• The Key type may differ from GT::Node's data type
• Requires the input graph to be acyclic (a tree)

Template Parameters

GT	Graph type (derived from List_Graph)
Key	Data type for tree nodes
Convert	Converter class with operator()(gnode, tnode)
SA	Arc filter (default: show all arcs)

Parameters

g	The tree graph to convert
groot	Node to use as the tree root

Returns

Root of the new Tree_Node<Key> tree

Exceptions

std::domain_error	If the graph is not acyclic
std::bad_alloc	If memory allocation fails

Note

Uses the Convert_Tree bit to mark visited arcs.

Performs an acyclicity check which adds O(V+E) overhead.

See also

Tree_Node Target tree structure

is_graph_acyclique() Acyclicity verification

Definition at line 160 of file graph_to_tree.H.

References ah_domain_error_if, and Aleph::maps().

has_cycle()

template<class GT >

bool Aleph::has_cycle ( const GT &  g )

inline

Return true if an undirected graph has at least one cycle.

Parameters

[in]

g

Graph to test.

Returns

true if g contains a cycle; false otherwise.

See also

is_graph_acyclique()

Definition at line 851 of file tpl_graph_utils.H.

References Aleph::is_graph_acyclique(), and Aleph::maps().

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

hopcroft_karp_matching()

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::hopcroft_karp_matching	(	const GT &	g,
		DynDlist< typename GT::Arc * > &	matching
	)

Computes a maximum cardinality matching on a bipartite graph using the Hopcroft-Karp algorithm.

The Hopcroft-Karp algorithm runs in O(E * sqrt(V)) time, which is more efficient than the max-flow based approach for sparse bipartite graphs.

This implementation handles disconnected graphs correctly.

Parameters

[in]	g	the bipartite graph.
[out]	matching	list of arcs forming the maximum matching.

Exceptions

domain_error

if the graph is not bipartite.

Definition at line 436 of file tpl_bipartite.H.

References ah_domain_error_if, Aleph::DynList< T >::append(), Aleph::DynListQueue< T >::get(), GraphCommon< GT, Node, Arc >::get_connected_node(), LocateFunctions< Container, Type >::get_it(), GraphCommon< GT, Node, Arc >::get_num_nodes(), Aleph::DynList< T >::insert(), Aleph::DynListQueue< T >::is_empty(), Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_COOKIE, NODE_COUNTER, and Aleph::DynListQueue< T >::put().

in_arcs()

template<class GT , class SA = Dft_Show_Arc<GT>>

DynList< typename GT::Arc * > Aleph::in_arcs	(	typename GT::Node *	p,
		SA	sa = SA()
	)

Return the filtered incoming arcs of p.

Parameters

[in]	p	node pointer
[in]	sa	arc filter

Definition at line 1888 of file tpl_graph.H.

References Aleph::DynList< T >::append(), Aleph::Digraph_Iterator< GT, Filter >::has_curr(), and Aleph::maps().

in_degree()

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::in_degree	(	typename GT::Node *	p,
		SA	sa = SA()
	)

Compute the filtered in degree of node p.

Note

This function computes the degree, it does not retrieve it.

Parameters

[in]	p	node pointer
[in]	sa	arc filter

Returns

the incoming degree

Definition at line 1958 of file tpl_graph.H.

References Aleph::count(), and Aleph::Digraph_Iterator< GT, Filter >::has_curr().

Referenced by Aleph::Random_Digraph< GT, Init_Node, Init_Arc >::connect().

in_nodes()

template<class GT , class SA = Dft_Show_Arc<GT>>

DynList< typename GT::Node * > Aleph::in_nodes	(	typename GT::Node *	p,
		SA	sa = SA()
	)

Return the nodes connected to the filtered incoming arcs to p.

Parameters

[in]	p	node pointer
[in]	sa	arc filter

Returns

A DynList<typename GT::Node*> with the pointer to the incoming nodes

Definition at line 1856 of file tpl_graph.H.

References Aleph::DynList< T >::append(), Aleph::Digraph_Iterator< GT, Filter >::has_curr(), and Aleph::maps().

Referenced by TEST().

in_pairs()

template<class GT , class SA = Dft_Show_Arc<GT>>

DynList< ArcPair< GT > > Aleph::in_pairs	(	typename GT::Node *	p,
		SA	sa = SA()
	)

Return the filtered incoming pairs of (arc,node) related to node p

Parameters

[in]	p	node pointer
[in]	sa	arc filter

Definition at line 1918 of file tpl_graph.H.

References Aleph::DynList< T >::append(), GTArcCommon< ArcInfo >::get_connected_node(), Aleph::Digraph_Iterator< GT, Filter >::has_curr(), and Aleph::maps().

inconnected_components()

template<class GT >

DynList< GT > Aleph::inconnected_components ( const GT &  g )

inline

Forward declaration for inconnected_components().

Compute the connected components as mapped subgraphs.

Builds a DynList<GT> where each element is a subgraph containing one connected component of g.

Side effects:

• Resets all node and arc control attributes via g.reset_nodes() and g.reset_arcs().
• Uses the Build_Subtree control bit on both nodes and arcs.
• Maps nodes and arcs between each subgraph and g via cookies.

Parameters

[in]

g

Graph to split.

Returns

List of mapped subgraphs, one per connected component.

Exceptions

bad_alloc

If there is not enough memory.

See also

build_subgraph(), copy_graph()

Definition at line 953 of file tpl_graph_utils.H.

References Aleph::DynList< T >::append(), Aleph::build_subgraph(), Aleph::Build_Subtree, Aleph::count(), Aleph::DynList< T >::get_last(), GraphCommon< GT, Node, Arc >::get_node_it(), GraphCommon< GT, Node, Arc >::get_num_nodes(), IS_NODE_VISITED, Aleph::maps(), GraphCommon< GT, Node, Arc >::reset_arcs(), and GraphCommon< GT, Node, Arc >::reset_nodes().

Referenced by TEST().

inter_copy_graph()

template<class GTT , class GTS , class Copy_Node = Dft_Copy_Node<GTT, GTS>, class Copy_Arc = Dft_Copy_Arc<GTT, GTS>>

void Aleph::inter_copy_graph	(	GTT &	gtgt,
		const GTS &	gsrc,
		const bool	cookie_map = false
	)

Copy between different types of graphs.

Parameters

[in]	gtgt	target graph
[in]	gsrc	source graph
[in]	cookie_map	if true ==> a mapping will be done through nodes and arcs cookies

Definition at line 3654 of file tpl_graph.H.

References Aleph::clear_graph(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), and Aleph::maps().

invert_digraph()

template<class GT >

GT Aleph::invert_digraph

(

const GT &

g

)

Compute the transpose (arc-reversed) digraph.

Builds a new digraph containing the same nodes as g and every arc reversed.

Side effects:

• Resets all node and arc control attributes via g.reset_nodes() and g.reset_arcs().
• Maps nodes and arcs between g and the returned digraph via cookies.

Parameters

[in]

g

Input digraph.

Returns

The transposed digraph, mapped to g.

Exceptions

domain_error	If g is not a digraph.
bad_alloc	If there is not enough memory.

Definition at line 1832 of file tpl_graph_utils.H.

References ah_domain_error_unless, GraphCommon< GT, Node, Arc >::get_arc_it(), GTArcCommon< ArcInfo >::get_info(), GraphCommon< GT, Node, Arc >::get_node_it(), GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), GraphCommon< GT, Node, Arc >::is_digraph(), GraphCommon< GT, Node, Arc >::map_arcs(), GraphCommon< GT, Node, Arc >::map_nodes(), Aleph::maps(), GraphCommon< GT, Node, Arc >::reset_arcs(), and GraphCommon< GT, Node, Arc >::reset_nodes().

Referenced by Aleph::kosaraju_connected_components(), Aleph::kosaraju_connected_components(), TEST(), and TEST().

is_graph_acyclique() [1/2]

template<class GT >

bool Aleph::is_graph_acyclique ( const GT &  g )

inline

Return true if an undirected graph is acyclic.

Equivalent to calling is_graph_acyclique(g, node) for every connected component of g.

Note

Uses the Test_Cycle control bit on both nodes and arcs.

Returns true for empty graphs.

Parameters

[in]

g

Graph to test.

Returns

true if g is acyclic; false otherwise.

Exceptions

domain_error

If g is a directed graph.

See also

has_cycle(), is_graph_acyclique(const GT&, typename GT::Node*)

Definition at line 810 of file tpl_graph_utils.H.

References Aleph::__is_graph_acyclique(), ah_domain_error_if, GraphCommon< GT, Node, Arc >::get_node_it(), GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::is_digraph(), IS_NODE_VISITED, Aleph::maps(), num_nodes, GraphCommon< GT, Node, Arc >::reset_bit_arcs(), GraphCommon< GT, Node, Arc >::reset_bit_nodes(), and Aleph::Test_Cycle.

is_graph_acyclique() [2/2]

template<class GT >

bool Aleph::is_graph_acyclique ( const GT &  g, typename GT::Node *  start_node  )

inline

Return true if an undirected graph is acyclic.

This is a cycle-detection routine for undirected graphs. It performs a DFS-like traversal while marking arcs to avoid immediately revisiting the parent edge.

Note

Uses the Test_Cycle control bit on both nodes and arcs.

Returns true for empty graphs.

Parameters

[in]	g	Graph to test.
[in]	start_node	Starting node (must be non-null and belong to g).

Returns

true if the component reachable from start_node is acyclic; false otherwise.

Exceptions

domain_error

If g is a directed graph.

See also

has_cycle(), is_graph_acyclique(const GT&)

Definition at line 770 of file tpl_graph_utils.H.

References Aleph::__is_graph_acyclique(), ah_domain_error_if, ah_invalid_argument_if, GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::is_digraph(), Aleph::maps(), num_nodes, GraphCommon< GT, Node, Arc >::reset_bit_arcs(), GraphCommon< GT, Node, Arc >::reset_bit_nodes(), and Aleph::Test_Cycle.

Referenced by Aleph::has_cycle(), TEST(), TEST(), TEST(), and TEST().

is_strongly_connected()

template<class GT >

bool Aleph::is_strongly_connected ( const GT &  g )

inline

Check if a directed graph is strongly connected.

A directed graph is strongly connected if there is exactly one SCC containing all nodes.

Template Parameters

GT	Graph type (must be a directed graph).

Parameters

[in]

g

The directed graph.

Returns

true if the graph is strongly connected, false otherwise.

Note

An empty graph or a graph with a single node is considered strongly connected.

Author

Leandro Rabindranath León

Definition at line 402 of file kosaraju.H.

References GraphCommon< GT, Node, Arc >::get_num_nodes(), and Aleph::kosaraju_scc_count().

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

kosaraju_connected_components() [1/2]

template<class GT >

DynList< DynList< typename GT::Node * > > Aleph::kosaraju_connected_components ( const GT &  g )

inline

Compute strongly connected components as lists of nodes.

This is a lightweight version of Kosaraju's algorithm that returns the SCCs as lists of node pointers rather than full subgraphs. This is more efficient when you only need to know which nodes belong to which component, without needing the induced subgraphs.

Time complexity: O(V + E) Space complexity: O(V + E) for the transposed graph

Template Parameters

GT	Graph type (must be a directed graph).

Parameters

[in]

g

The directed graph.

Returns

A list of lists, where each inner list contains the nodes belonging to one SCC. The nodes are pointers to the original graph's nodes.

Note

This version is faster than the subgraph version because it doesn't need to build and map subgraphs.

Warning

This function modifies the control bits (Depth_First) on nodes and arcs. The bits are reset at the start.

See also

kosaraju_connected_components(g, blk_list, arc_list) for the version that builds mapped subgraphs

Author

Leandro Rabindranath León

Definition at line 299 of file kosaraju.H.

References Aleph::__dfp_phase1(), Aleph::__dfp_phase2_list(), Aleph::DynList< T >::append(), Aleph::Depth_First, Aleph::df(), GraphCommon< GT, Node, Arc >::get_node_it(), Aleph::invert_digraph(), IS_NODE_VISITED, Aleph::maps(), GraphCommon< GT, Node, Arc >::reset_arcs(), and GraphCommon< GT, Node, Arc >::reset_nodes().

kosaraju_connected_components() [2/2]

template<class GT >

void Aleph::kosaraju_connected_components ( const GT &  g, DynList< GT > &  blk_list, DynList< typename GT::Arc * > &  arc_list  )

inline

Compute strongly connected components using Kosaraju's algorithm.

This function computes the strongly connected components (SCCs) of a directed graph using Kosaraju's algorithm. The algorithm works in two phases:

1. First DFS: Traverse the original graph and compute finish times (nodes are ordered by when they finish, stored in postorder).
2. Second DFS: Create the transposed graph, then process nodes in decreasing order of finish time. Each DFS tree in this phase forms one SCC.

The resulting SCCs are returned as subgraphs, with nodes and arcs mapped to the original graph via cookies. Arcs that cross between different SCCs are collected in a separate list.

Time complexity: O(V + E) Space complexity: O(V + E) for the transposed graph

Template Parameters

GT	Graph type (must be a directed graph).

Parameters

[in]	g	The directed graph. Must not be modified during execution.
[out]	blk_list	List of subgraphs, one per SCC. Each subgraph is mapped to g via node and arc cookies.
[out]	arc_list	List of arcs that cross between different SCCs (inter-component arcs).

Note

If the graph is strongly connected, blk_list will contain a single subgraph with all nodes, and arc_list will be empty.

Warning

This function modifies the control bits (Depth_First) on nodes and arcs. The bits are reset at the start.

See also

tarjan_connected_components() for an alternative algorithm

invert_digraph() used internally to create the transposed graph

Author

Leandro Rabindranath León

Definition at line 210 of file kosaraju.H.

References Aleph::__dfp_phase1(), Aleph::__dfp_phase2_subgraph(), Aleph::DynArray< T >::access(), Aleph::DynList< T >::append(), Aleph::color(), Aleph::Depth_First, Aleph::df(), GraphCommon< GT, Node, Arc >::get_arc_it(), GraphCommon< GT, Node, Arc >::get_node_it(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::invert_digraph(), IS_NODE_VISITED, GraphCommon< GT, Node, Arc >::map_arcs(), Aleph::maps(), NODE_COLOR, GraphCommon< GT, Node, Arc >::reset_arcs(), and GraphCommon< GT, Node, Arc >::reset_nodes().

Referenced by example_basic_sccs(), example_dag(), example_lightweight_version(), example_strongly_connected(), Aleph::kosaraju_scc_count(), Aleph::Kosaraju_Connected_Components< GT >::operator()(), Aleph::Kosaraju_Connected_Components< GT >::operator()(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

kosaraju_scc_count()

template<class GT >

size_t Aleph::kosaraju_scc_count ( const GT &  g )

inline

Count the number of strongly connected components.

Computes the number of SCCs in the graph without building the actual component lists.

Template Parameters

GT	Graph type (must be a directed graph).

Parameters

[in]

g

The directed graph.

Returns

The number of strongly connected components.

Author

Leandro Rabindranath León

Definition at line 381 of file kosaraju.H.

References Aleph::kosaraju_connected_components().

Referenced by Aleph::is_strongly_connected(), and TEST().

load_digraph()

void Aleph::load_digraph ( Digrafo &  g, std::istream &  nodes_input, std::istream &  arcs_input  )

inline

Load nodes and arcs from streams into the directed graph.

Reads nodes from a pipe-separated file and arcs from a space/comma separated file, populating the graph.

The nodes file format:

• First line is a header (ignored)
• Subsequent lines: field1|field2|...|fieldN
• Lines with fewer than MIN_NODE_FIELDS are skipped
• field[0] is used as the node ID

The arcs file format:

• Each line: source_id target_id (or source_id,target_id)
• Lines with fewer than 2 IDs are skipped
• If a referenced node doesn't exist, it's created with empty fields

Parameters

g	The digraph to populate.
nodes_input	Input stream for node data.
arcs_input	Input stream for arc data.

Definition at line 201 of file load_digraph.H.

References Aleph::load_digraph(), Aleph::maps(), Aleph::MIN_NODE_FIELDS, Aleph::search_node(), Aleph::HTList::size(), Aleph::DynDlist< T >::size(), and Aleph::split().

Referenced by Aleph::load_digraph(), main(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

map_arcs()

template<class GTS , class GTT >

void Aleph::map_arcs ( typename GTS::Arc *  p, typename GTT::Arc *  q  )

noexcept

Map two arcs of different types of graphs through their cookies.

Note

It is intended that the mapping be done between at least homomorphic graphs

Parameters

[in]	p	pointer to the source arc
[in]	q	pointer to the target arc

Definition at line 3532 of file tpl_graph.H.

References ARC_COOKIE, and Aleph::maps().

map_cut_graph()

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.

Requires a graph previously processed by:

• compute_cut_nodes(): marks cut nodes with the Cut bit
• paint_subgraphs(): paints blocks and marks cross/cut arcs

The returned cut graph contains:

• all cut nodes
• all cut arcs (arcs between cut nodes; marked with the Cut bit on arcs)

Cross arcs (cut → non-cut) are returned separately in cross_arc_list.

Parameters

[in]	g	Painted graph.
[in]	cut_node_list	Cut nodes list.

Returns

{cut_graph, cross_arc_list}.

Exceptions

bad_alloc

If there is not enough memory.

See also

map_subgraph(), compute_cut_nodes(), paint_subgraphs()

Definition at line 1749 of file tpl_graph_utils.H.

References Aleph::DynList< T >::append(), Aleph::DynList< T >::get(), GraphCommon< GT, Node, Arc >::get_arc_it(), LocateFunctions< Container, Type >::get_it(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), GraphCommon< GT, Node, Arc >::map_arcs(), GraphCommon< GT, Node, Arc >::map_nodes(), and Aleph::maps().

Referenced by TEST(), and TEST().

map_nodes()

template<class GTS , class GTT >

void Aleph::map_nodes ( typename GTS::Node *  p, typename GTT::Node *  q  )

noexcept

Map two nodes of different types of graphs through their cookies.

Note

It is intended that the mapping be done between at least homomorphic graphs

Parameters

[in]	p	pointer to the source node
[in]	q	pointer to the target node

Definition at line 3504 of file tpl_graph.H.

References Aleph::maps(), and NODE_COOKIE.

map_subgraph()

template<class GT >

GT Aleph::map_subgraph	(	const GT &	g,
		const long	color
	)

Extract a mapped subgraph containing a given color.

Assumes g has been painted (e.g., via paint_subgraphs()) and extracts the connected block whose nodes/arcs have the given positive color.

Side effects:

• Resets the Build_Subtree control bit on all nodes and arcs.
• Uses the Build_Subtree control bit during extraction.
• Maps nodes and arcs between g and the returned subgraph via cookies.

Parameters

[in]	g	Painted graph.
[in]	color	Color value to extract.

Returns

A mapped subgraph containing only nodes/arcs with color.

Exceptions

domain_error	If color does not exist in g.
bad_alloc	If there is not enough memory.

See also

paint_subgraphs(), compute_cut_nodes(), map_cut_graph()

Definition at line 1700 of file tpl_graph_utils.H.

References Aleph::__map_subgraph(), ah_domain_error_if, Aleph::Build_Subtree, Aleph::color(), Aleph::DynList< T >::get(), GraphCommon< GT, Node, Arc >::get_node_it(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), GraphCommon< GT, Node, Arc >::map_nodes(), Aleph::maps(), NODE_BITS, GraphCommon< GT, Node, Arc >::reset_bit_arcs(), and GraphCommon< GT, Node, Arc >::reset_bit_nodes().

Referenced by TEST().

mapped_node()

template<class GT >

Aleph::mapped_node ( typename GT::Node *  p )

noexcept

Return the mapped node through the cookie of p

Definition at line 2468 of file tpl_graph.H.

References Aleph::maps(), and NODE_COOKIE.

nodes_map()

template<class GT , typename T , template< typename > class Container = DynList, class SN = Dft_Show_Node<GT>>

Container< T > Aleph::nodes_map	(	GT &	g,
		std::function< T(typename GT::Node *)>	transformation,
		SN	sn = SN()
	)

Map the filtered nodes of a graph to a transformed type.

Template Parameters

GT	Graph type
T	Result type
Container	Container type (default: DynList)
SN	Node filter type (default: Dft_Show_Node<GT>)

Parameters

[in]	g	the graph
[in]	transformation	function Node* -> T that transforms each node
[in]	sn	node filter functor (default: Dft_Show_Node<GT>)

Returns

a Container<T> object with all the nodes mapped through the transformation

Definition at line 1365 of file tpl_graph.H.

References Aleph::DynList< T >::append(), and Aleph::maps().

out_arcs()

template<class GT , class SA = Dft_Show_Arc<GT>>

DynList< typename GT::Arc * > Aleph::out_arcs	(	typename GT::Node *	p,
		SA	sa = SA()
	)

Return the filtered incoming arcs of p.

Parameters

[in]	p	node pointer
[in]	sa	arc filter

Definition at line 1872 of file tpl_graph.H.

References Aleph::DynList< T >::append(), Aleph::Digraph_Iterator< GT, Filter >::has_curr(), and Aleph::maps().

out_degree()

template<class GT , class SA = Dft_Show_Arc<GT>>

size_t Aleph::out_degree	(	typename GT::Node *	p,
		SA	sa = SA()
	)

Compute the filtered out degree of node p

Note

This function computes the degree, it does not retrieve it.

Parameters

[in]	p	node pointer
[in]	sa	arc filter

Returns

the outcoming degree

Definition at line 1986 of file tpl_graph.H.

References Aleph::count(), and Aleph::Digraph_Iterator< GT, Filter >::has_curr().

out_nodes()

template<class GT , class SA = Dft_Show_Arc<GT>>

DynList< typename GT::Node * > Aleph::out_nodes	(	typename GT::Node *	p,
		SA	sa = SA()
	)

Return the nodes connected to the filtered outcoming arcs of p.

Parameters

[in]	p	node pointer
[in]	sa	arc filter

Returns

A DynList<typename GT::Node*> with the pointer to the outcoming nodes

Definition at line 1839 of file tpl_graph.H.

References Aleph::DynList< T >::append(), Aleph::Digraph_Iterator< GT, Filter >::has_curr(), and Aleph::maps().

out_pairs()

template<class GT , class SA = Dft_Show_Arc<GT>>

DynList< ArcPair< GT > > Aleph::out_pairs	(	typename GT::Node *	p,
		SA	sa = SA()
	)

Return the filtered outcoming pairs of (arc,node) related to node p

Parameters

[in]	p	node pointer
[in]	sa	arc filter

Returns

a DynList<ArcPair<GT>> containing the outcoming pairs

Definition at line 1937 of file tpl_graph.H.

References Aleph::DynList< T >::append(), GTArcCommon< ArcInfo >::get_connected_node(), Aleph::Digraph_Iterator< GT, Filter >::has_curr(), and Aleph::maps().

paint_subgraphs()

template<class GT >

long Aleph::paint_subgraphs ( const GT &  g, const DynList< typename GT::Node * > &  cut_node_list  )

inline

Paint connected blocks around articulation points.

Given a list of cut nodes (typically computed with compute_cut_nodes()), paints the graph so that each biconnected block around the cut nodes gets a distinct positive "color".

Color storage:

• Node colors are stored in NODE_COUNTER(node).
• Arc colors are stored in ARC_COUNTER(arc).

Special markers:

• Cut nodes keep color 0.
• Cross arcs (cut → non-cut) are marked with ARC_COUNTER(arc) == Cross_Arc.
• Cut arcs (cut → cut) are marked by setting the Cut control bit on arcs.

Return value:

• The first used color is 1.
• The function returns the next unused color value (so valid colors are in the range [1, return_value - 1]).

Protocol:

• The Cut bit on nodes must already mark cut nodes.
• Do not reset/alter node/arc control bits between computing cut nodes and calling this function.

Side effects:

• Resets all node and arc counters (colors) to 0 before painting.

Parameters

[in]	g	Graph to paint.
[in]	cut_node_list	Cut nodes list (as returned by compute_cut_nodes()).

Returns

Next unused color id (one past the last used color).

See also

compute_cut_nodes(), map_subgraph(), map_cut_graph()

Definition at line 1627 of file tpl_graph_utils.H.

References Aleph::__paint_from_cut_node(), LocateFunctions< Container, Type >::get_it(), Aleph::maps(), GraphCommon< GT, Node, Arc >::reset_counter_arcs(), and GraphCommon< GT, Node, Arc >::reset_counter_nodes().

Referenced by TEST(), and TEST().

rank_graphviz()

template<class GT , class Node_Attr , class Arc_Attr , class SN , class SA >

size_t Aleph::rank_graphviz	(	const GT &	g,
		std::ostream &	out,
		Node_Attr	node_attr = Node_Attr(),
		Arc_Attr	arc_attr = Arc_Attr(),
		const std::string &	rankdir = "LR"
	)

Generate Graphviz DOT output with topological ranking.

Creates a DOT specification that groups nodes by their topological rank (level in DAG). Each rank is placed in a separate subgraph for visual grouping.

This is useful for visualizing DAGs where the vertical position should reflect dependencies.

Template Parameters

GT	Graph type (must be a DAG)
Node_Attr	Node attribute generator
Arc_Attr	Arc attribute generator
SN	Node filter
SA	Arc filter

Parameters

g	Graph to visualize (should be a DAG)
out	Output stream
node_attr	Node attribute functor
arc_attr	Arc attribute functor
rankdir	Layout direction (default: "LR")

Returns

Number of topological ranks

See also

Q_Topological_Sort For rank computation

Definition at line 536 of file generate_graph.H.

References LocateFunctions< Container, Type >::get_it(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::DynList< T >::insert(), Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), and Aleph::ranks().

Referenced by TEST().

search_arc()

template<class GT , class SA = Dft_Show_Arc<GT>>

GT::Arc * Aleph::search_arc ( const GT &  g, typename GT::Node *  src, typename GT::Node *  tgt, SA  sa = SA()  )

noexcept

Arc filtered searching given two nodes.

This function receives two nodes and returns the first arc linking them. The arc sense is irrelevant for this function. Simply, it searches an arc linking the nodes

Parameters

[in]	g	the graph
[in]	src	a node
[in]	tgt	another node
[in]	sa	filtering condition

Returns

pointer to found node; nullptr otherwise

Definition at line 2421 of file tpl_graph.H.

References GraphCommon< GT, Node, Arc >::is_digraph(), Aleph::maps(), and GTNodeCommon< NodeInfo >::num_arcs.

Referenced by Aleph::Path< GT >::append(), Aleph::Path< GT >::insert(), Aleph::Initialize_Dist< AM >::operator()(), parse_arc_definition(), parse_arc_text_definition(), TEST(), TEST(), TEST(), TEST_F(), and TEST_F().

search_directed_arc()

template<class GT , class SA = Dft_Show_Arc<GT>>

GT::Arc * Aleph::search_directed_arc ( const GT &  g, typename GT::Node *  src, typename GT::Node *  tgt, SA  sa = SA()  )

noexcept

Searching of directed arc linking two nodes.

Parameters

[in]	g	the graph
[in]	src	source node pointer
[in]	tgt	target node pointer
[in]	sa	arc filter (default: Dft_Show_Arc)

Returns

a pointer to a directed linking arc if this is found; nullptr otherwise.

Definition at line 2449 of file tpl_graph.H.

References Aleph::maps(), and Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne().

Referenced by Aleph::Path< GT >::append_directed(), Aleph::Path< GT >::insert_directed(), TEST(), TEST(), and TEST_F().

search_node()

Digrafo::Node * Aleph::search_node ( Digrafo &  g, const std::string &  s  )

inline

Find or create a node by ID.

Searches for a node with the given ID in the graph. If not found, creates a new node with empty fields.

Parameters

g	The digraph to search.
s	The node ID to find.

Returns

Pointer to the found or created node.

Note

This performs a linear search. For large graphs, consider using a hash index.

Definition at line 162 of file load_digraph.H.

References Aleph::maps(), and Aleph::search_node().

Referenced by Aleph::load_digraph(), Aleph::search_node(), TEST(), TEST(), TEST(), TEST(), and TEST().

split()

void Aleph::split ( const std::string &  text, const std::string &  separators, DynDlist< std::string > &  words  )

inline

Split a text into tokens using a separator set.

Tokenizes the input text by splitting on any character in the separators set. Empty tokens are not included.

Parameters

text	The text to split.
separators	String containing separator characters.
words	Output list to receive the tokens.

Definition at line 115 of file load_digraph.H.

References Aleph::DynDlist< T >::append(), FunctionalMethods< Container, T >::length(), Aleph::maps(), and Aleph::split().

sufficient_hamiltonian() [1/2]

template<class GT , class Init_Node , class Init_Arc >

GT Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::sufficient_hamiltonian ( const size_t &  __num_nodes, const double &  p = 0.5  )

inline

Create a random Hamiltonian graph.

This version builds a random graph that is guaranteed to satisfy sufficient conditions for being Hamiltonian.

The process first generates a random graph, then examines the result and creates new arcs so that the output satisfies the Ore/Dirac theorems for Hamiltonian graphs.

Warning

The procedure can be extremely slow and memory-intensive as __num_nodes increases.

The graph is ensured to be Hamiltonian by the Ore and Dirac theorems. Note that this is a sufficiency condition, meaning the graph is not necessarily minimal. In fact, the generated graph tends to be dense.

Parameters

[in]	__num_nodes	Number of nodes the graph should have.
[in]	p	Probability of an arc existing between any pair of nodes. Defaults to 0.5, which empirically tends to produce fewer arcs and consume less time.

Returns

The randomly created graph.

Exceptions

bad_alloc	if there is not enough memory.
domain_error	if p is not in the range (0, 1].

Definition at line 310 of file random_graph.H.

References Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::create_p(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::g, and Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::make_hamiltonian().

sufficient_hamiltonian() [2/2]

template<class GT , class Init_Node = Dft_Init_Rand_Node<GT>, class Init_Arc = Dft_Init_Rand_Arc<GT>>

GT Aleph::Random_Graph< GT, Init_Node, Init_Arc >::sufficient_hamiltonian ( const size_t &  __num_nodes, const double &  p = 0.5  )

inline

Create a random Hamiltonian graph.

This version builds a random graph that is guaranteed to satisfy sufficient conditions for being Hamiltonian.

The process first generates a random graph, then examines the result and creates new arcs so that the output satisfies the Ore/Dirac theorems for Hamiltonian graphs.

Warning

The procedure can be extremely slow and memory-intensive as __num_nodes increases.

The graph is ensured to be Hamiltonian by the Ore and Dirac theorems. Note that this is a sufficiency condition, meaning the graph is not necessarily minimal. In fact, the generated graph tends to be dense.

Parameters

[in]	__num_nodes	Number of nodes the graph should have.
[in]	p	Probability of an arc existing between any pair of nodes. Defaults to 0.5, which empirically tends to produce fewer arcs and consume less time.

Returns

The randomly created graph.

Exceptions

bad_alloc	if there is not enough memory.
domain_error	if p is not in the range (0, 1].

Definition at line 707 of file random_graph.H.

References Aleph::Random_Graph< GT, Init_Node, Init_Arc >::create_p(), Aleph::Random_Graph_Base< GT, Init_Node, Init_Arc >::g, and Aleph::Random_Graph< GT, Init_Node, Init_Arc >::make_hamiltonian().

test_connectivity()

template<class GT >

bool Aleph::test_connectivity ( const GT &  g )

inline

Connectivity test for undirected graphs.

Parameters

[in]

g

Graph to test.

Returns

true if g is connected; false otherwise.

Note

Returns false for an empty graph.

This function is not intended for multigraphs.

Exceptions

domain_error

If g is a directed graph.

See also

depth_first_traversal()

Definition at line 641 of file tpl_graph_utils.H.

References ah_domain_error_if, GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::is_digraph(), Aleph::maps(), and num_nodes.

Referenced by TEST(), TEST(), test_random_graph_eulerian_probability(), test_random_graph_eulerian_sparse(), test_random_graph_hamiltonian(), test_random_graph_sparse_connected(), and test_two_node_graph().

test_for_cycle()

template<class GT >

bool Aleph::test_for_cycle ( const GT &  g, typename GT::Node *  src  )

inline

Search for a cycle reachable from a given node.

Performs a depth-first exploration starting at src and returns true if a cycle that returns to src is found.

Note

This is a single-source cycle check. If you only need to know whether the graph has any cycle at all, prefer has_cycle().

Uses the Test_Cycle control bit on both nodes and arcs.

Parameters

[in]	g	Graph to search.
[in]	src	Source node (must be non-null and belong to g).

Returns

true if a cycle returning to src is found; false otherwise.

See also

has_cycle(), is_graph_acyclique()

Definition at line 679 of file tpl_graph_utils.H.

References Aleph::__test_cycle(), ah_invalid_argument_if, ARC_BITS, GraphCommon< GT, Node, Arc >::get_arc_it(), IS_ARC_VISITED, GraphCommon< GT, Node, Arc >::reset_bit_arcs(), GraphCommon< GT, Node, Arc >::reset_bit_nodes(), and Aleph::Test_Cycle.

Referenced by TEST().

test_for_path()

template<class GT >

bool Aleph::test_for_path ( const GT &  g, typename GT::Node *  start_node, typename GT::Node *  end_node  )

inline

Return true if there is a path between two nodes.

Performs a depth-first reachability test from start_node to end_node.

Note

Uses the Find_Path control bit on both nodes and arcs.

Parameters

[in]	g	Graph to test.
[in]	start_node	Start node (must be non-null and belong to g).
[in]	end_node	End node (must be non-null and belong to g).

Returns

true if end_node is reachable from start_node; false otherwise.

See also

find_path_depth_first(), find_path_breadth_first()

Definition at line 873 of file tpl_graph_utils.H.

References Aleph::__test_for_path(), ah_invalid_argument_if, ARC_BITS, Aleph::Find_Path, GraphCommon< GT, Node, Arc >::get_arc_it(), Aleph::maps(), GraphCommon< GT, Node, Arc >::reset_bit_arcs(), and GraphCommon< GT, Node, Arc >::reset_bit_nodes().

Referenced by TEST().

traverse_arcs()

template<class GT , class Itor , class Operation >

bool Aleph::traverse_arcs ( typename GT::Node *  p, Operation  op = Operation()  )

inline

Generic arcs traverse of a node.

This template function receives threes template parameters:

1. GT: the graph type.
2. Itor: the iterator type; it is intended to be _In_Iterator or _Out_Iterator.
3. Operation: an operation to be executed on each arc. This operation must have the following signature:

bool operation(typename GT::Arc * arc)

If operation returns true then the traversal continues to the next arc; otherwise the traversal stops and the result of traverse() is false. If all the arcs are traversed, then the result is true.

Parameters

[in]	p	node pointer
[in]	op	operation to be performed on each arc

Returns

true if all the arcs were traversed: false otherwise

Definition at line 2027 of file tpl_graph.H.

References Aleph::maps().

Referenced by TEST().

traverse_in_arcs()

template<class GT , class Op >

bool Aleph::traverse_in_arcs ( typename GT::Node *  p, Op  op = Op()  )

inline

Conditioned traversal of incoming arcs of a node.

Parameters

[in]	p	node pointer
[in]	op	operation whose result must be bool. Si the result is false, then the traversal stops and the traverse returns false; otherwise, all the ars are traversed and it returns true

Returns

true is all the arcs were traversed: false otherwise

Definition at line 2074 of file tpl_graph.H.

References Aleph::maps().

Referenced by Aleph::all_in_arc(), and Aleph::search_in_arc().

traverse_out_arcs()

template<class GT , class Op >

bool Aleph::traverse_out_arcs ( typename GT::Node *  p, Op  op = Op()  )

inline

Conditioned traversal of outcoming arcs of a node.

Parameters

[in]	p	node pointer
[in]	op	operation whose result must be bool. Si the result is false, then the traversal stops and the traverse returns false; otherwise, all the ars are traversed and it returns true

Returns

true is all the arcs were traversed: false otherwise

Definition at line 2247 of file tpl_graph.H.

References Aleph::maps().

Referenced by Aleph::all_out_arc().

vertex_connectivity()

template<class GT , template< class > class Max_Flow = Random_Preflow_Maximum_Flow, class SA = Dft_Show_Arc<GT>>

long Aleph::vertex_connectivity

(

GT &

g

)

Compute vertex connectivity of an undirected graph.

Uses a max-flow node-splitting reduction to compute the minimum number of vertices whose removal disconnects the graph.

The arc filter SA is applied when computing degrees, connectivity, and when building the auxiliary network.

Side effects:

• Uses the Depth_First control bit on nodes and arcs to test connectivity.
• Overwrites node cookies to store the GT -> Net mapping (and auxiliary mappings during the reduction) when the auxiliary network is built.

Template Parameters

GT	Graph type (undirected).
Max_Flow	Maximum flow functor.
SA	Arc filter functor.

Parameters

[in,out]

g

Graph to analyze.

Returns

Vertex connectivity of g (0 for empty or disconnected graphs).

Note

For connected graphs with minimum filtered degree <= 1, returns that degree without running max flow.

Exceptions

std::domain_error	If g is a digraph.
std::bad_alloc	If there is not enough memory.

Definition at line 497 of file tpl_kgraph.H.

References ah_domain_error_if, Aleph::DynList< T >::append(), Aleph::Net_Graph< NodeT, ArcT >::connect_arc(), Aleph::Net_Graph< NodeT, ArcT >::disconnect_arc(), Aleph::DynMapTree< Key, Data, Tree, Compare >::find(), Aleph::DynList< T >::get(), GraphCommon< GT, Node, Arc >::get_num_nodes(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), Aleph::Dlink::Iterator::has_curr(), Aleph::Digraph_Iterator< GT, Filter >::has_curr(), Aleph::DynMapTree< Key, Data, Tree, Compare >::insert(), Aleph::Net_Graph< NodeT, ArcT >::insert_arc(), Aleph::Net_Graph< NodeT, ArcT >::insert_node(), GraphCommon< GT, Node, Arc >::is_digraph(), Aleph::HTList::is_empty(), Aleph::maps(), Aleph::Filter_Iterator< Container, It, Show_Item >::next(), Aleph::Filter_Iterator< Container, It, Show_Item >::next_ne(), NODE_COOKIE, num_nodes, and Aleph::Net_Graph< NodeT, ArcT >::reset().

warshall_compute_transitive_clausure()

template<class GT , class SA = Dft_Show_Arc<GT>>

void Aleph::warshall_compute_transitive_clausure	(	GT &	g,
		Bit_Mat_Graph< GT, SA > &	mat
	)

Computes the transitive closure of a graph using Warshall's algorithm.

This function computes the transitive closure of graph g by means of Warshall's algorithm. The result is stored in the bit matrix mat.

Each entry mat(i,j) indicates whether there exists a path from the source node with index i to the destination node with index j. A value of 0 indicates there is no path; a value of 1 indicates there exists at least one path.

The procedure uses two bit matrices: an internal temporary one (freed when the procedure ends) and the output matrix mat.

Parameters

[in]	g	The graph represented by a List_Graph variant.
[out]	mat	Bit matrix where the result is stored.

Exceptions

std::bad_alloc

if there is not enough memory.

See also

List_Graph Bit_Mat_Graph

Definition at line 80 of file warshall.H.

References Aleph::Bit_Mat_Graph< GT, SA >::get_list_graph(), Aleph::Bit_Mat_Graph< GT, SA >::get_num_nodes(), Aleph::maps(), and Aleph::Bit_Mat_Graph< GT, SA >::set_list_graph().

Referenced by TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

with_clean_cookies()

template<class GT , class Func >

auto Aleph::with_clean_cookies	(	GT &	g,
		Func &&	func
	)		-> decltype(func())

Convenience function to run an algorithm with automatic cookie cleanup.

Executes the given callable with automatic cookie cleanup on exit (whether normal return or exception).

Template Parameters

GT	Graph type.
Func	Callable type.

Parameters

g	Graph to operate on.
func	Function/lambda to execute.

Returns

Result of func().

Example

auto result = with_clean_cookies(g, [&]() {
  // Algorithm that uses cookies...
  return compute_something(g);
});

Author

Leandro Rabindranath León

Definition at line 492 of file cookie_guard.H.

References Aleph::maps().

Referenced by TEST_F().

with_saved_cookies()

template<class GT , class Func >

auto Aleph::with_saved_cookies	(	GT &	g,
		Func &&	func
	)		-> decltype(func())

Convenience function to run an algorithm preserving existing cookies.

Executes the given callable, automatically saving cookies before and restoring them after (whether normal return or exception).

Template Parameters

GT	Graph type.
Func	Callable type.

Parameters

g	Graph to operate on.
func	Function/lambda to execute.

Returns

Result of func().

Example

// Cookies already contain important data from previous algorithm
auto result = with_saved_cookies(g, [&]() {
  // Temporary algorithm that uses cookies...
  return compute_temporary(g);
});
// Original cookies are restored

Author

Leandro Rabindranath León

Definition at line 524 of file cookie_guard.H.

References Aleph::maps().

Referenced by TEST_F().

write_df_low_tree()

template<class GT , class Key >

void write_df_low_tree	(	GT &	g,
		typename GT::Node *	src,
		std::ofstream &	f
	)

Generate a DFS tree picture with low-link values.

Computes and visualizes a depth-first spanning tree with:

• DFS discovery numbers
• Low-link values (for cut-vertex detection)
• Non-tree arcs (back edges)

The output is suitable for tree visualization tools.

Template Parameters

GT	Graph type (must be derived from List_Graph)
Key	Key type for tree nodes (typically Clave)

Parameters

g	The input graph
src	Starting node for DFS traversal
f	Output stream for the tree specification

Note

This function also computes cut-vertices as a side effect.

Warning

Uses global state (global_counter) - NOT thread-safe.

See also

compute_cut_nodes() For cut-vertex computation

generate_tree() For tree output format

Definition at line 218 of file generate_df_tree.H.

References Aleph::compute_cut_nodes(), Aleph::depth_first_traversal(), Aleph::find_depth_first_spanning_tree(), Aleph::maps(), NODE_COOKIE, visitar_df(), and visitar_low().

Variable Documentation

font_size

size_t Aleph::font_size = 6

inline

Font size for the DOT output.

Definition at line 255 of file load_digraph.H.

Referenced by FlagReset::FlagReset(), FlagReset::~FlagReset(), Aleph::generate_dot_file(), TEST(), TEST(), TEST(), and TEST().

only_num

bool Aleph::only_num = false

inline

If true, show only the node number, not the full label.

Definition at line 249 of file load_digraph.H.

Referenced by FlagReset::FlagReset(), FlagReset::~FlagReset(), Aleph::generate_dot_file(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

Processed

const unsigned char Aleph::Processed = 2

The node or arc has already been processed.

Definition at line 39 of file aleph-graph.C.

Referenced by Aleph::Directed_Find_Path< GT, Itor, SA >::find(), and Aleph::Find_Aumenting_Path< Net, Q >::search().

Processing

const unsigned char Aleph::Processing = 1

The node are being processed; probably it is inside a queue, stack or heap.

Definition at line 38 of file aleph-graph.C.

Referenced by Aleph::Directed_Find_Path< GT, Itor, SA >::find(), and Aleph::Find_Aumenting_Path< Net, Q >::search().

Unprocessed

const unsigned char Aleph::Unprocessed = 0

The node have not bees processed.

This must be the initial state before general processing

Definition at line 37 of file aleph-graph.C.

Referenced by Aleph::min_cut(), and Aleph::Find_Aumenting_Path< Net, Q >::search().

vertical

bool Aleph::vertical = true

inline

If true, use vertical layout (default).

Definition at line 258 of file load_digraph.H.

Referenced by TEST(), and TEST().

with_class

bool Aleph::with_class = false

inline

If true, set node shapes based on class field.

Definition at line 252 of file load_digraph.H.

Referenced by FlagReset::FlagReset(), FlagReset::~FlagReset(), Aleph::generate_dot_file(), TEST(), TEST(), TEST(), and TEST().

with_nes

bool Aleph::with_nes = false

inline

If true, include NES percentage in node labels.

Definition at line 246 of file load_digraph.H.

Referenced by FlagReset::FlagReset(), FlagReset::~FlagReset(), Aleph::generate_dot_file(), TEST(), TEST(), TEST(), and TEST().

with_power

bool Aleph::with_power = false

inline

Configuration options for DOT file generation.

These variables control the appearance of the generated DOT output. They are inline variables to avoid ODR violations while maintaining the original API.

Note

Consider using a configuration struct instead of global variables in new code. If true, include power value in node labels.

Definition at line 243 of file load_digraph.H.

Referenced by FlagReset::FlagReset(), FlagReset::~FlagReset(), Aleph::generate_dot_file(), TEST(), TEST(), TEST(), and TEST().