graph_components_example.C

Go to the documentation of this file.

 
/*
                          Aleph_w
 
  Data structures & Algorithms
  version 2.0.0b
  https://github.com/lrleon/Aleph-w
 
  This file is part of Aleph-w library
 
  Copyright (c) 2002-2026 Leandro Rabindranath Leon
 
  Permission is hereby granted, free of charge, to any person obtaining a copy
  of this software and associated documentation files (the "Software"), to deal
  in the Software without restriction, including without limitation the rights
  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  copies of the Software, and to permit persons to whom the Software is
  furnished to do so, subject to the following conditions:
 
  The above copyright notice and this permission notice shall be included in all
  copies or substantial portions of the Software.
 
  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  SOFTWARE.
*/
 
 
#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>
 
using namespace std;
using namespace Aleph;
 
static bool has_flag(int argc, char* argv[], const char* flag)
{
  for (int i = 1; i < argc; ++i)
    if (std::strcmp(argv[i], flag) == 0)
      return true;
  return false;
}
 
static void usage(const char* prog)
{
  cout << "Usage: " << prog
       << " [--components] [--scc] [--spanning-tree] [--network-analysis] [--all] [--help]\n";
  cout << "\nIf no flags are given, all demos are executed.\n";
}
 
// Graph types
using UGraph = List_Graph<Graph_Node<string>, Graph_Arc<int>>;
using DGraph = List_Digraph<Graph_Node<string>, Graph_Arc<int>>;
 
// =============================================================================
// Helper functions
// =============================================================================
 
template <class GT>
typename GT::Node* find_or_create(GT& g, const string& name)
{
  for (auto it = g.get_node_it(); it.has_curr(); it.next_ne())
    if (it.get_curr()->get_info() == name)
      return it.get_curr();
  return g.insert_node(name);
}
 
template <class GT>
void add_edge(GT& g, const string& src, const string& tgt, int weight = 1)
{
  auto s = find_or_create(g, src);
  auto t = find_or_create(g, tgt);
  g.insert_arc(s, t, weight);
}
 
template <class GT>
void print_graph(GT& g, const string& title)
{
  cout << title << ":\n";
  cout << "  Vertices: ";
  for (auto it = g.get_node_it(); it.has_curr(); it.next_ne())
    cout << it.get_curr()->get_info() << " ";
  cout << "\n  Edges:\n";
  for (auto it = g.get_arc_it(); it.has_curr(); it.next_ne()) {
    auto arc = it.get_curr();
    cout << "    " << g.get_src_node(arc)->get_info() 
         << " → " << g.get_tgt_node(arc)->get_info() << "\n";
  }
  cout << "\n";
}
 
// =============================================================================
// Example 1: Connected Components (Undirected Graph)
// =============================================================================
 
void demo_connected_components()
{
  cout << "\n";
  cout << "╔══════════════════════════════════════════════════════════════════╗\n";
  cout << "║      EXAMPLE 1: Connected Components (Undirected)                ║\n";
  cout << "╚══════════════════════════════════════════════════════════════════╝\n\n";
 
  cout << "A connected component is a maximal set of vertices where\n";
  cout << "every pair of vertices is connected by a path.\n\n";
 
  UGraph g;
 
  // Component 1: A-B-C
  add_edge(g, "A", "B");
  add_edge(g, "B", "C");
  add_edge(g, "A", "C");
 
  // Component 2: D-E
  add_edge(g, "D", "E");
 
  // Component 3: F (isolated)
  find_or_create(g, "F");
 
  // Component 4: G-H-I
  add_edge(g, "G", "H");
  add_edge(g, "H", "I");
 
  print_graph(g, "Graph with 4 components");
 
  // Find connected components using Unconnected_Components
  DynList<UGraph> components;
  Unconnected_Components<UGraph> uc;
  uc(g, components);
 
  cout << "Found " << components.size() << " connected components:\n\n";
 
  int i = 1;
  for (auto& comp : components) {
    cout << "  Component " << i++ << ": ";
    for (auto it = comp.get_node_it(); it.has_curr(); it.next_ne())
      cout << it.get_curr()->get_info() << " ";
    cout << "(size: " << comp.get_num_nodes() << ")\n";
  }
 
  cout << "\n--- Testing connectivity ---\n\n";
 
  // Test connectivity using test_connectivity function
  Test_Connectivity<UGraph> test_conn;
  bool is_connected = test_conn(g);
  
  cout << "  Graph is fully connected: " << (is_connected ? "YES" : "NO") << "\n";
  cout << "  Number of components: " << components.size() << "\n";
}
 
// =============================================================================
// Example 2: Strongly Connected Components (Directed Graph)
// =============================================================================
 
void demo_strongly_connected()
{
  cout << "\n";
  cout << "╔══════════════════════════════════════════════════════════════════╗\n";
  cout << "║      EXAMPLE 2: Strongly Connected Components (Directed)         ║\n";
  cout << "╚══════════════════════════════════════════════════════════════════╝\n\n";
 
  cout << "A strongly connected component (SCC) is a maximal set where\n";
  cout << "every vertex can reach every other vertex (bidirectional paths).\n\n";
 
  DGraph g;
 
  // SCC 1: A ↔ B ↔ C (cycle)
  add_edge(g, "A", "B");
  add_edge(g, "B", "C");
  add_edge(g, "C", "A");
 
  // SCC 2: D ↔ E (cycle)
  add_edge(g, "D", "E");
  add_edge(g, "E", "D");
 
  // SCC 3: F (single node)
  find_or_create(g, "F");
 
  // Cross-component edges
  add_edge(g, "C", "D");
  add_edge(g, "E", "F");
 
  print_graph(g, "Directed graph");
 
  // Using Tarjan's algorithm
  Tarjan_Connected_Components<DGraph> tarjan;
  auto sccs = tarjan(g);  // Returns DynList<DynList<Node*>>
 
  cout << "Tarjan's Algorithm found " << sccs.size() << " SCCs:\n\n";
 
  int i = 1;
  for (auto& scc : sccs) {
    cout << "  SCC " << i++ << ": ";
    for (auto node : scc)
      cout << node->get_info() << " ";
    cout << "\n";
  }
 
  // Check if graph has cycles
  cout << "\n--- Cycle analysis ---\n\n";
  cout << "  Graph has cycles: " << (tarjan.has_cycle(g) ? "YES" : "NO") << "\n";
  cout << "  Graph is a DAG: " << (tarjan.is_dag(g) ? "YES" : "NO") << "\n";
 
  cout << "\n--- Why SCCs matter ---\n\n";
  cout << "  • Compiler optimization: basic blocks\n";
  cout << "  • Web crawling: identify tightly connected pages\n";
  cout << "  • Social networks: find communities\n";
  cout << "  • 2-SAT problem solving\n";
}
 
// =============================================================================
// Example 3: Spanning Tree
// =============================================================================
 
void demo_spanning_tree()
{
  cout << "\n";
  cout << "╔══════════════════════════════════════════════════════════════════╗\n";
  cout << "║      EXAMPLE 3: Spanning Tree                                    ║\n";
  cout << "╚══════════════════════════════════════════════════════════════════╝\n\n";
 
  cout << "A spanning tree connects all vertices using exactly V-1 edges.\n";
  cout << "It contains no cycles and forms a tree structure.\n\n";
 
  UGraph g;
 
  // Create a connected graph
  add_edge(g, "A", "B");
  add_edge(g, "A", "C");
  add_edge(g, "B", "C");
  add_edge(g, "B", "D");
  add_edge(g, "C", "D");
  add_edge(g, "C", "E");
  add_edge(g, "D", "E");
 
  cout << "Original graph:\n";
  cout << "  Vertices: " << g.get_num_nodes() << "\n";
  cout << "  Edges: " << g.get_num_arcs() << "\n\n";
 
  // Build spanning tree using DFS
  UGraph tree;
  Find_Depth_First_Spanning_Tree<UGraph> dfs_tree;
  
  auto start = find_or_create(g, "A");
  dfs_tree(g, start, tree);
 
  cout << "DFS Spanning Tree:\n";
  cout << "  Vertices: " << tree.get_num_nodes() << "\n";
  cout << "  Edges: " << tree.get_num_arcs() << "\n";
  cout << "  Tree edges:\n";
  for (auto it = tree.get_arc_it(); it.has_curr(); it.next_ne()) {
    auto arc = it.get_curr();
    cout << "    " << tree.get_src_node(arc)->get_info() 
         << " — " << tree.get_tgt_node(arc)->get_info() << "\n";
  }
 
  cout << "\n--- Properties of spanning tree ---\n\n";
  cout << "  • Connects all " << tree.get_num_nodes() << " vertices\n";
  cout << "  • Uses exactly " << tree.get_num_arcs() << " edges (V-1)\n";
  cout << "  • Contains no cycles\n";
  cout << "  • Unique path between any two vertices\n";
}
 
// =============================================================================
// Example 4: Practical Application - Network Analysis
// =============================================================================
 
void demo_network_analysis()
{
  cout << "\n";
  cout << "╔══════════════════════════════════════════════════════════════════╗\n";
  cout << "║      EXAMPLE 4: Network Analysis Application                     ║\n";
  cout << "╚══════════════════════════════════════════════════════════════════╝\n\n";
 
  cout << "Scenario: Analyzing a computer network for redundancy.\n\n";
 
  UGraph network;
 
  // Core network (highly connected)
  add_edge(network, "Server1", "Server2");
  add_edge(network, "Server2", "Server3");
  add_edge(network, "Server3", "Server1");
  add_edge(network, "Server1", "Router");
  add_edge(network, "Server2", "Router");
 
  // Branch office (separate component)
  add_edge(network, "Branch1", "Branch2");
 
  // Remote worker (isolated)
  find_or_create(network, "Remote");
 
  // Analyze components
  DynList<UGraph> components;
  Unconnected_Components<UGraph> uc;
  uc(network, components);
 
  cout << "Network analysis results:\n\n";
  cout << "  Total devices: " << network.get_num_nodes() << "\n";
  cout << "  Network segments: " << components.size() << "\n\n";
 
  int segment = 1;
  for (auto& comp : components) {
    cout << "  Segment " << segment++ << ":\n";
    cout << "    Devices: ";
    for (auto it = comp.get_node_it(); it.has_curr(); it.next_ne())
      cout << it.get_curr()->get_info() << " ";
    cout << "\n";
    cout << "    Connections: " << comp.get_num_arcs() << "\n";
 
    // Check if segment is a single point of failure
    if (comp.get_num_nodes() > 1 && comp.get_num_arcs() == comp.get_num_nodes() - 1)
      cout << "    ⚠️  No redundancy (tree structure)\n";
    else if (comp.get_num_arcs() > comp.get_num_nodes() - 1)
      cout << "    ✓ Has redundancy (multiple paths)\n";
    else
      cout << "    • Single device\n";
    cout << "\n";
  }
 
  cout << "Recommendation: Connect segments for full network connectivity.\n";
}
 
// =============================================================================
// Main
// =============================================================================
 
int main(int argc, char* argv[])
{
  if (has_flag(argc, argv, "--help"))
    {
      usage(argv[0]);
      return 0;
    }
 
  const bool run_all = has_flag(argc, argv, "--all") || argc == 1;
  const bool run_components = run_all || has_flag(argc, argv, "--components");
  const bool run_scc = run_all || has_flag(argc, argv, "--scc");
  const bool run_spanning = run_all || has_flag(argc, argv, "--spanning-tree");
  const bool run_network = run_all || has_flag(argc, argv, "--network-analysis");
 
  cout << "\n";
  cout << "╔══════════════════════════════════════════════════════════════════╗\n";
  cout << "║        Graph Connectivity Analysis in Aleph-w Library            ║\n";
  cout << "║                                                                  ║\n";
  cout << "║     Aleph-w Library - https://github.com/lrleon/Aleph-w          ║\n";
  cout << "╚══════════════════════════════════════════════════════════════════╝\n";
 
  if (run_components)
    demo_connected_components();
  if (run_scc)
    demo_strongly_connected();
  if (run_spanning)
    demo_spanning_tree();
  if (run_network)
    demo_network_analysis();
 
  if (!(run_components || run_scc || run_spanning || run_network))
    {
      usage(argv[0]);
      return 1;
    }
 
  cout << "\n";
  cout << "╔══════════════════════════════════════════════════════════════════╗\n";
  cout << "║                         Summary                                  ║\n";
  cout << "╠══════════════════════════════════════════════════════════════════╣\n";
  cout << "║  Unconnected_Components: Find connected components (undirected) ║\n";
  cout << "║  Tarjan_Connected:       Find SCCs (directed) - O(V+E)          ║\n";
  cout << "║  Find_DFS_Spanning_Tree: Build spanning tree via DFS            ║\n";
  cout << "║  Find_BFS_Spanning_Tree: Build spanning tree via BFS            ║\n";
  cout << "║  Test_Connectivity:      Check if graph is connected            ║\n";
  cout << "║                                                                  ║\n";
  cout << "║  All algorithms run in O(V + E) time complexity.                ║\n";
  cout << "╚══════════════════════════════════════════════════════════════════╝\n\n";
 
  return 0;
}