tpl_kgraph.H File Reference

K-connected graph structures and connectivity algorithms. More...

#include <limits>
#include <tpl_dynSetTree.H>
#include <tpl_net.H>
#include <cookie_guard.H>

Include dependency graph for tpl_kgraph.H:

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

Go to the source code of this file.

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

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

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

Detailed Description

K-connected graph structures and connectivity algorithms.

Example: Computing edge connectivity

using GT = List_Graph<Graph_Node<int>, Graph_Arc<int>>;
GT network;
 
// Create nodes
auto a = network.insert_node(1);
auto b = network.insert_node(2);
auto c = network.insert_node(3);
auto d = network.insert_node(4);
 
// 2-connected: requires removing 2 edges to disconnect
network.insert_arc(a, b);
network.insert_arc(b, c);
network.insert_arc(c, d);
network.insert_arc(d, a);
network.insert_arc(a, c); // diagonal
 
long k = edge_connectivity(network);
cout << "Edge connectivity: " << k << endl; // k = 2

Example: Network reliability

// Higher k = more fault-tolerant network
// k=1: single point of failure (bridge exists)
// k=2: can survive one edge failure
// k=3: can survive two edge failures

Author

Leandro Rabindranath León

Definition in file tpl_kgraph.H.