Cut nodes (articulation points) and biconnected components in Aleph-w. More...

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <tpl_graph.H>
#include <tpl_cut_nodes.H>
#include <tclap/CmdLine.h>

Include dependency graph for cut_nodes_example.C:

Typedefs
using	Node = Graph_Node< string >

using	Arc = Graph_Arc< int >

using	Graph = List_Graph< Node, Arc >

Functions
Graph	build_network_graph ()
	Build a network with clear cut nodes.

Graph	build_cyclic_graph ()
	Build a cyclic graph with fewer cut nodes.

Graph	build_computer_network ()
	Build a graph representing a computer network.

Graph::Node *	find_node (Graph &g, const string &name)
	Find a node by name.

void	print_graph (Graph &g, const string &title)
	Print graph structure.

void	demo_cut_nodes (Graph &g, const string &description)
	Demonstrate finding cut nodes.

void	demo_network_vulnerability ()
	Practical example: Network vulnerability analysis.

void	demo_biconnected_components ()
	Demonstrate biconnected components.

void	demo_resilience_comparison ()
	Compare resilient vs fragile networks.

void	demo_fixing_vulnerabilities ()
	Demonstrate fixing network vulnerabilities.

int	main (int argc, char *argv[])

Detailed Description

Cut nodes (articulation points) and biconnected components in Aleph-w.

Overview

This example demonstrates algorithms for analyzing connectivity in undirected graphs:

cut nodes (articulation points): vertices whose removal disconnects the graph
biconnected components: maximal edge blocks not separable by removing one vertex

The implementation uses a DFS-based approach with discovery/low-link values (Tarjan-style).

Data model used by this example

Graph type: Graph = List_Graph<Graph_Node<string>, Graph_Arc<int>>
Node info: label (string)
Arc info: integer value (int) used by the demo

Usage / CLI

This example uses TCLAP. Options:

--basic / -b: basic cut nodes demo.
--network / -n: network vulnerability analysis.
--biconnected / -c: biconnected components demo.
--resilience / -r: resilience comparison demo.
--fix / -f: show how adding edges can remove articulation points.
--all / -a: run all demos.
--help: show help.

Behavior:

If no demo-selection flags are provided, the program defaults to running all demos.

./cut_nodes_example
./cut_nodes_example --basic
./cut_nodes_example --network
./cut_nodes_example --biconnected
./cut_nodes_example --resilience
./cut_nodes_example --fix
./cut_nodes_example --help

Algorithms

The core idea is DFS with:

df[v]: discovery time
low[v]: smallest discovery time reachable from v via tree edges + at most one back edge

A vertex u is an articulation point if:

root case: u is DFS root and has ≥ 2 children
non-root case: there exists a child v with low[v] >= df[u]

This example focuses on cut nodes and biconnected blocks (bridges are discussed conceptually but not printed as a primary output).

Complexity

Let V be the number of vertices and E the number of edges.

Time: O(V + E)
Extra space: O(V)

Pitfalls and edge cases

Disconnected graphs require running DFS from each unvisited node.
DFS recursion depth may be large on deep graphs.

References / see also

tpl_cut_nodes.H
graph_components_example.C (components)
tarjan_example.C (DFS-based decomposition)

Author: Leandro Rabindranath León

Definition in file cut_nodes_example.C.

Typedef Documentation

◆ Arc

using Arc = Graph_Arc<int>

Definition at line 129 of file cut_nodes_example.C.

◆ Graph

using Graph = List_Graph<Node, Arc>

Definition at line 130 of file cut_nodes_example.C.

◆ Node

using Node = Graph_Node<string>

Definition at line 128 of file cut_nodes_example.C.

Function Documentation

◆ build_computer_network()

Graph build_computer_network ( )

Build a graph representing a computer network.

Definition at line 223 of file cut_nodes_example.C.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

Referenced by demo_network_vulnerability().

◆ build_cyclic_graph()

Graph build_cyclic_graph ( )

Build a cyclic graph with fewer cut nodes.

A --- B

/| |\ / | | \ E | | C \ | | / | |/ D — F — G

Only F is a cut node (the cycle A-B-C-F-D-E makes others resilient)

Definition at line 182 of file cut_nodes_example.C.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

Referenced by demo_resilience_comparison().

◆ build_network_graph()

Graph build_network_graph ( )

Build a network with clear cut nodes.

  A --- B --- C
  |     |
  D --- E --- F --- G
              |     |
              +--H--+

Cut nodes: B, E, F (removing any disconnects the graph)

Definition at line 143 of file cut_nodes_example.C.

References h, Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_node(), and Aleph::maps().

Referenced by demo_biconnected_components(), demo_fixing_vulnerabilities(), demo_resilience_comparison(), and main().

◆ demo_biconnected_components()

void demo_biconnected_components ( )

Demonstrate biconnected components.

Definition at line 376 of file cut_nodes_example.C.

References build_network_graph(), Aleph::color(), GraphCommon< GT, Node, Arc >::get_counter(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_node(), LocateFunctions< Container, Type >::get_it(), GraphCommon< GT, Node, Arc >::get_node_it(), Aleph::maps(), Aleph::Compute_Cut_Nodes< GT, SA >::paint_subgraphs(), and print_graph().

Referenced by main().

◆ demo_cut_nodes()

void demo_cut_nodes	(	Graph &	g,
		const string &	description
	)

Demonstrate finding cut nodes.

Definition at line 294 of file cut_nodes_example.C.

References Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_node(), LocateFunctions< Container, Type >::get_it(), Aleph::Dlink::is_empty(), Aleph::maps(), and Aleph::DynDlist< T >::size().

Referenced by main().

◆ demo_fixing_vulnerabilities()

void demo_fixing_vulnerabilities ( )

Demonstrate fixing network vulnerabilities.

Definition at line 473 of file cut_nodes_example.C.

References build_network_graph(), find_node(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_node(), LocateFunctions< Container, Type >::get_it(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::insert_arc(), Aleph::Dlink::is_empty(), and Aleph::maps().

Referenced by main().

◆ demo_network_vulnerability()

void demo_network_vulnerability ( )

Practical example: Network vulnerability analysis.

Definition at line 329 of file cut_nodes_example.C.

References build_computer_network(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_node(), LocateFunctions< Container, Type >::get_it(), Aleph::Dlink::is_empty(), Aleph::maps(), and print_graph().

Referenced by main().

◆ demo_resilience_comparison()

void demo_resilience_comparison ( )

Compare resilient vs fragile networks.

Definition at line 427 of file cut_nodes_example.C.

References build_cyclic_graph(), build_network_graph(), Aleph::maps(), print_graph(), and Aleph::DynDlist< T >::size().

Referenced by main().

◆ find_node()

Graph::Node * find_node	(	Graph &	g,
		const string &	name
	)

Find a node by name.

Definition at line 255 of file cut_nodes_example.C.

References GraphCommon< GT, Node, Arc >::get_node_it().

Referenced by demo_fixing_vulnerabilities().

◆ main()

int main	(	int	argc,
		char *	argv[]
	)

Definition at line 531 of file cut_nodes_example.C.

References build_network_graph(), demo_biconnected_components(), demo_cut_nodes(), demo_fixing_vulnerabilities(), demo_network_vulnerability(), demo_resilience_comparison(), Aleph::maps(), and print_graph().

◆ print_graph()

void print_graph	(	Graph &	g,
		const string &	title
	)

Print graph structure.

Definition at line 266 of file cut_nodes_example.C.

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

Referenced by demo_biconnected_components(), demo_network_vulnerability(), demo_resilience_comparison(), and main().

Typedefs

Functions

Detailed Description

Overview

Data model used by this example

Usage / CLI

Algorithms

Complexity

Pitfalls and edge cases

References / see also

Typedef Documentation

◆ Arc

◆ Graph

◆ Node

Function Documentation

◆ build_computer_network()

◆ build_cyclic_graph()

◆ build_network_graph()

◆ demo_biconnected_components()

◆ demo_cut_nodes()

◆ demo_fixing_vulnerabilities()

◆ demo_network_vulnerability()

◆ demo_resilience_comparison()

◆ find_node()

◆ main()

◆ print_graph()