Graph connectivity: components and spanning trees. More...

#include <iostream>
#include <string>
#include <cstring>
#include <tpl_graph.H>
#include <tpl_components.H>
#include <tpl_spanning_tree.H>
#include <tpl_test_connectivity.H>
#include <Tarjan.H>

Include dependency graph for graph_components_example.C:

Typedefs
using	UGraph = List_Graph< Graph_Node< string >, Graph_Arc< int > >

using	DGraph = List_Digraph< Graph_Node< string >, Graph_Arc< int > >

Functions
static bool	has_flag (int argc, char argv[], const char flag)

static void	usage (const char *prog)

template<class GT >
GT::Node *	find_or_create (GT &g, const string &name)

template<class GT >
void	add_edge (GT &g, const string &src, const string &tgt, int weight=1)

template<class GT >
void	print_graph (GT &g, const string &title)

void	demo_connected_components ()

void	demo_strongly_connected ()

void	demo_spanning_tree ()

void	demo_network_analysis ()

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

Detailed Description

Graph connectivity: components and spanning trees.

This example demonstrates fundamental algorithms for analyzing graph connectivity, which is crucial for understanding graph structure and designing efficient algorithms. Connectivity analysis helps identify isolated groups, understand graph structure, and design robust systems.

Connected Components (Undirected Graphs)

Definition

A connected component is a maximal set of vertices where every vertex can reach every other vertex through a path.

Key property: In undirected graphs, connectivity is symmetric: if u can reach v, then v can reach u.

Algorithm

Uses DFS or BFS traversal:

Find_Components(G):
  visited = all false
  components = []
  For each unvisited vertex v:
    component = []
    DFS(v, visited, component)
    components.append(component)
  Return components
 
DFS(v, visited, component):
  visited[v] = true
  component.append(v)
  For each neighbor w of v:
    If not visited[w]:
      DFS(w, visited, component)

Time Complexity: O(V + E) - visits each vertex and edge once

Applications

Social networks: Finding friend groups (connected communities)
Network analysis: Identifying isolated subnetworks
Image processing: Connected pixel regions (blob detection)
Circuit design: Identifying disconnected circuits
Ecology: Habitat connectivity analysis

Strongly Connected Components (Directed Graphs)

Definition

A strongly connected component (SCC) is a maximal set of vertices in a directed graph where every vertex can reach every other vertex through directed paths.

Key difference: In directed graphs, connectivity is NOT symmetric: u → v doesn't imply v → u.

Algorithm: Tarjan's Algorithm

Uses a single DFS pass with:

**index[v]**: Discovery time (order of first visit)
**lowlink[v]**: Lowest index reachable from v's DFS subtree

Key insight: When lowlink[v] == index[v], v is the root of an SCC.

Time Complexity: O(V + E) - single DFS traversal

Applications

Web analysis: Finding communities of mutually linked pages
Compiler optimization: Detecting cyclic dependencies
Social networks: Finding tightly-knit groups
Deadlock detection: Identifying circular wait conditions
2-SAT solving: Reducing to SCC finding

Spanning Tree

Definition

A spanning tree is a subgraph that:

Contains all vertices
Is a tree (connected, acyclic)
Has exactly V-1 edges

Finding a Spanning Tree

Algorithm: Use DFS or BFS to traverse the graph, keeping track of tree edges (edges used in traversal).

Find_Spanning_Tree(G, root):
  visited = all false
  tree_edges = []
  DFS(root, visited, tree_edges)
  Return tree_edges
 
DFS(v, visited, tree_edges):
  visited[v] = true
  For each neighbor w of v:
    If not visited[w]:
      tree_edges.append((v, w))
      DFS(w, visited, tree_edges)

Time Complexity: O(V + E)

Applications

Network design: Minimum cost to connect all nodes (MST)
Broadcast trees: Efficient message distribution
Graph simplification: Reduce graph while maintaining connectivity
Routing: Find paths in networks

Comparison: Components vs SCCs

Aspect	Connected Components	Strongly Connected Components
Graph type	Undirected	Directed
Connectivity	Symmetric	Not symmetric
Algorithm	Simple DFS/BFS	Tarjan/Kosaraju
Complexity	O(V + E)	O(V + E)

Usage

# Analyze graph connectivity
./graph_components_example
 
# Find components
./graph_components_example --components
 
# Find SCCs
./graph_components_example --scc
 
# Find spanning tree
./graph_components_example --spanning-tree
 
# Network analysis demo
./graph_components_example --network-analysis
 
# Show help
./graph_components_example --help