tpl_graph.H File Reference

Generic graph and digraph implementations. More...

#include <memory>
#include <cassert>
#include <tuple>
#include <utility>
#include <functional>
#include <bitArray.H>
#include <tpl_dynArray.H>
#include <tpl_sort_utils.H>
#include <tpl_dynMapTree.H>
#include <tpl_dynDlist.H>
#include <tpl_treapRk.H>
#include <filter_iterator.H>
#include <aleph-graph.H>
#include <graph-dry.H>
#include <ah-errors.H>

Include dependency graph for tpl_graph.H:

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

Go to the source code of this file.

Classes
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::Arc_Node
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...

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

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

Functions
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 >
size_t	Aleph::in_degree (typename GT::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 >
size_t	Aleph::out_degree (typename GT::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::all_in_arc (typename GT::Node *p, Op op=Op())
	Test if the incoming arcs meet a condition.
template<class GT , class Op >
bool	Aleph::exists_in_arc (typename GT::Node *p, Op op=Op())
	Test if it exists an incoming arc satisfying an operation.
template<class GT , class Op >
auto	Aleph::search_in_arc (typename GT::Node *p, Op op=Op())
	Search an incoming arc to a node satisfying a condition op.
template<class GT , typename T >
auto	Aleph::map_in_arcs (typename GT::Node *p, std::function< T(typename GT::Arc *)> op)
	Map the incoming arcs to a transformation,.
template<class GT , typename T >
T	Aleph::foldl_in_arcs (typename GT::Node *p, const T &init, std::function< T(const T &, typename GT::Arc *)> op)
	Fold the incoming arcs of a node.
template<class GT , class Op >
DynList< typename GT::Arc * >	Aleph::filter_in_arcs (typename GT::Node *p, Op cond)
	Filter the incoming arcs meeting an condition.
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 Op >
bool	Aleph::all_out_arc (typename GT::Node *p, Op op=Op())
	Test if the outcoming arcs meet a condition.
template<class GT , class Op >
bool	Aleph::exists_out_arc (typename GT::Node *p, Op op=Op())
	Test if it exists an outcoming arc satisfying an operation.
template<class GT , class Op >
auto	Aleph::search_out_arc (typename GT::Node *p, Op op=Op())
	Search an outcoming arc to a node satisfying a condition op.
template<class GT , typename T >
auto	Aleph::map_out_arcs (typename GT::Node *p, std::function< T(typename GT::Arc *)> op)
	Map the outcoming arcs to a transformation,.
template<class GT , typename T >
T	Aleph::foldl_out_arcs (typename GT::Node *p, const T &init, std::function< T(const T &, typename GT::Arc *)> op)
	Fold the outcoming arcs of a node.
template<class GT , class Op >
DynList< typename GT::Arc * >	Aleph::filter_out_arcs (typename GT::Node *p, Op cond)
	Filter the outcoming arcs meeting an condition.
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 >
GT::Arc *	Aleph::mapped_arc (typename GT::Arc *a) noexcept
	Return the mapped arc through the cookie of p
template<class GTSRC , class GTTGT >
GTTGT::Node *	Aleph::mapped_node (typename GTSRC::Node *p) noexcept
template<class GTSRC , class GTTGT >
GTTGT::Arc *	Aleph::mapped_arc (typename GTSRC::Arc *a) noexcept
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 GT >
static bool	Aleph::__find_path_depth_first (const GT &g, typename GT::Node *curr_node, typename GT::Arc *curr_arc, typename GT::Node *end_node, Path< GT > &path)
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 >
bool	Aleph::are_equal (const GT &g1, const GT &g2)
	Fast graph comparison.

Detailed Description

Generic graph and digraph implementations.

This file provides the core graph data structures for Aleph-w, including List_Graph (undirected graphs) and List_Digraph (directed graphs). These templates support customizable node and arc information types, and provide efficient adjacency list representations with iterators.

Author

Leandro Rabindranath León

Definition in file tpl_graph.H.