Cut nodes (articulation points), bridges, and biconnected components. 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_bridges ()
	Demonstrate bridge finding with Compute_Bridges / find_bridges().

void	demo_fixing_vulnerabilities ()
	Demonstrate fixing network vulnerabilities.

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

Detailed Description

Cut nodes (articulation points), bridges, and biconnected components.

Overview

Demonstrates algorithms for analyzing connectivity vulnerabilities in undirected graphs using Aleph-w:

Cut nodes (articulation points): vertices whose removal disconnects the graph (Compute_Cut_Nodes, compute_cut_nodes()).
Bridges (cut edges / isthmuses): edges whose removal disconnects the graph (Compute_Bridges, find_bridges()).
Biconnected components: maximal 2-edge-connected blocks (Compute_Cut_Nodes::paint_subgraphs()).

Both algorithms use Tarjan's DFS low-link technique.

Key concepts

Given a DFS, let df[v] = discovery time and low[v] = minimum discovery time reachable from v's subtree via back-edges.

Articulation point u: DFS root with ≥ 2 children, OR non-root where low[child] >= df[u].
Bridge (u, v) (tree edge): low[v] > df[u] — strictly greater, meaning no back-edge from v's subtree escapes above u.

Data model

Graph = List_Graph<Graph_Node<string>, Graph_Arc<int>>
Node info: label (string), arc info: int (unused in most demos).

CLI options (TCLAP)

Flag	Long	Description
`-b`	`--basic`	Basic cut nodes demo
`-n`	`--network`	Network vulnerability analysis
`-c`	`--biconnected`	Biconnected components demo
`-r`	`--resilience`	Resilience comparison
`-f`	`--fix`	Fixing vulnerabilities by adding edges
`-d`	`--bridges`	Bridge edges demo
`-a`	`--all`	Run all demos (default if no flag given)

./cut_nodes_example             # all demos
./cut_nodes_example --bridges   # bridge demo only
./cut_nodes_example --basic --bridges

Complexity

Time: O(V + E) — single DFS for both cut nodes and bridges.
Space: O(V) extra.

See also: tpl_cut_nodes.H

Author: Leandro Rabindranath León

Definition in file cut_nodes_example.C.

Typedef Documentation

◆ Arc

using Arc = Graph_Arc<int>

Definition at line 107 of file cut_nodes_example.C.

◆ Graph

using Graph = List_Graph<Node, Arc>

Definition at line 108 of file cut_nodes_example.C.

◆ Node

using Node = Graph_Node<string>

Definition at line 106 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 201 of file cut_nodes_example.C.

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

Referenced by demo_bridges(), and 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 160 of file cut_nodes_example.C.

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

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 121 of file cut_nodes_example.C.

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

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 354 of file cut_nodes_example.C.

References build_network_graph(), Aleph::color(), Aleph::divide_and_conquer_partition_dp(), 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::Compute_Cut_Nodes< GT, SA >::paint_subgraphs(), and print_graph().

Referenced by main().

◆ demo_bridges()

void demo_bridges ( )

Demonstrate bridge finding with Compute_Bridges / find_bridges().

Shows three scenarios:

A graph with several bridges (the computer network).
A fully 2-edge-connected graph (cycle → no bridges).
The relationship between bridges and articulation points.

Definition at line 457 of file cut_nodes_example.C.

References build_computer_network(), Aleph::compute_cut_nodes(), Aleph::divide_and_conquer_partition_dp(), Aleph::find_bridges(), 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(), 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 272 of file cut_nodes_example.C.

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

Referenced by main().

◆ demo_fixing_vulnerabilities()

void demo_fixing_vulnerabilities ( )

Demonstrate fixing network vulnerabilities.

Definition at line 550 of file cut_nodes_example.C.

References build_network_graph(), Aleph::divide_and_conquer_partition_dp(), 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(), and Aleph::Dlink::is_empty().

Referenced by main().

◆ demo_network_vulnerability()

void demo_network_vulnerability ( )

Practical example: Network vulnerability analysis.

Definition at line 307 of file cut_nodes_example.C.

References build_computer_network(), Aleph::divide_and_conquer_partition_dp(), Aleph::List_Graph< _Graph_Node, _Graph_Arc >::get_first_node(), LocateFunctions< Container, Type >::get_it(), Aleph::Dlink::is_empty(), Aleph::Filter_Iterator< Container, It, Show_Item >::next(), and print_graph().

Referenced by main().

◆ demo_resilience_comparison()

void demo_resilience_comparison ( )

Compare resilient vs fragile networks.

Definition at line 406 of file cut_nodes_example.C.

References build_cyclic_graph(), build_network_graph(), Aleph::divide_and_conquer_partition_dp(), 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 233 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 608 of file cut_nodes_example.C.

References Aleph::and, build_network_graph(), cmd, demo_biconnected_components(), demo_bridges(), demo_cut_nodes(), demo_fixing_vulnerabilities(), demo_network_vulnerability(), demo_resilience_comparison(), Aleph::divide_and_conquer_partition_dp(), and print_graph().

◆ print_graph()

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

Print graph structure.

Definition at line 244 of file cut_nodes_example.C.

References Aleph::divide_and_conquer_partition_dp(), 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::Filter_Iterator< Container, It, Show_Item >::next().

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

Typedefs

Functions

Detailed Description

Overview

Key concepts

Data model

CLI options (TCLAP)

Complexity

Typedef Documentation

◆ Arc

◆ Graph

◆ Node

Function Documentation

◆ build_computer_network()

◆ build_cyclic_graph()

◆ build_network_graph()

◆ demo_biconnected_components()

◆ demo_bridges()

◆ demo_cut_nodes()

◆ demo_fixing_vulnerabilities()

◆ demo_network_vulnerability()

◆ demo_resilience_comparison()

◆ find_node()

◆ main()

◆ print_graph()