topological_sort_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 <iomanip>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <tpl_graph.H>
#include <topological_sort.H>
#include <tclap/CmdLine.h>
 
using namespace std;
using namespace Aleph;
 
// Task node
using TaskNode = Graph_Node<string>;
using DependencyArc = Graph_Arc<int>;  // Weight could be time/cost
using TaskGraph = List_Digraph<TaskNode, DependencyArc>;
 
namespace
{
bool verify_topological_order(const TaskGraph & g,
                              const DynDlist<TaskGraph::Node*> & order,
                              std::vector<TaskGraph::Node*> * missing_nodes = nullptr)
{
  std::unordered_map<TaskGraph::Node*, size_t> pos;
  pos.reserve(order.size());
 
  size_t i = 0;
  for (auto it = order.get_it(); it.has_curr(); it.next(), ++i)
    pos.emplace(it.get_curr(), i);
 
  if (missing_nodes != nullptr)
    {
      missing_nodes->clear();
      missing_nodes->reserve(g.get_num_nodes());
      for (auto nit = g.get_node_it(); nit.has_curr(); nit.next_ne())
        {
          auto * n = nit.get_curr();
          if (pos.find(n) == pos.end())
            missing_nodes->push_back(n);
        }
    }
 
  for (auto ait = g.get_arc_it(); ait.has_curr(); ait.next_ne())
    {
      auto * a = ait.get_curr();
      auto * u = g.get_src_node(a);
      auto * v = g.get_tgt_node(a);
 
      const auto it_u = pos.find(u);
      const auto it_v = pos.find(v);
      if (it_u == pos.end() || it_v == pos.end())
        return false; // ordering incomplete
 
      if (it_u->second >= it_v->second)
        return false; // violates u -> v
    }
 
  return true;
}
 
void print_missing_nodes(const std::vector<TaskGraph::Node*> & missing)
{
  if (missing.empty())
    return;
 
  cout << "Missing nodes (not produced by the algorithm): ";
  bool first = true;
  for (auto * n : missing)
    {
      if (!first) cout << ", ";
      cout << n->get_info();
      first = false;
    }
  cout << endl;
}
} // namespace
 
TaskGraph build_project_graph()
{
  TaskGraph g;
  
  // Header files
  auto config_h = g.insert_node("config.h");
  auto utils_h = g.insert_node("utils.h");
  
  // Object files
  auto utils_o = g.insert_node("utils.o");
  auto parser_o = g.insert_node("parser.o");
  auto lexer_o = g.insert_node("lexer.o");
  auto main_o = g.insert_node("main.o");
  auto test_o = g.insert_node("test.o");
  
  // Executables
  auto program = g.insert_node("program");
  auto test_suite = g.insert_node("test_suite");
  
  // Dependencies (edges go from dependency to dependent)
  g.insert_arc(config_h, utils_h);
  g.insert_arc(config_h, parser_o);
  g.insert_arc(utils_h, utils_o);
  g.insert_arc(utils_h, lexer_o);
  g.insert_arc(utils_o, main_o);
  g.insert_arc(utils_o, test_o);
  g.insert_arc(parser_o, main_o);
  g.insert_arc(lexer_o, parser_o);
  g.insert_arc(lexer_o, test_o);
  g.insert_arc(main_o, program);
  g.insert_arc(test_o, test_suite);
  
  return g;
}
 
TaskGraph build_courses_graph()
{
  TaskGraph g;
  
  // Math courses
  auto math101 = g.insert_node("Math101");
  auto math201 = g.insert_node("Math201");
  auto math301 = g.insert_node("Math301");
  
  // CS courses
  auto cs101 = g.insert_node("CS101");
  auto cs102 = g.insert_node("CS102");
  auto cs201 = g.insert_node("CS201");
  auto cs301 = g.insert_node("CS301");
  auto cs302 = g.insert_node("CS302");
  
  // Prerequisites
  g.insert_arc(math101, math201);
  g.insert_arc(math201, math301);
  g.insert_arc(math101, cs101);
  g.insert_arc(cs101, cs102);
  g.insert_arc(cs101, cs201);
  g.insert_arc(math201, cs201);
  g.insert_arc(cs201, cs301);
  g.insert_arc(cs301, cs302);
  g.insert_arc(cs102, cs302);
  
  return g;
}
 
TaskGraph::Node* find_task(TaskGraph& g, const string& name)
{
  for (auto it = g.get_node_it(); it.has_curr(); it.next())
    if (it.get_curr()->get_info() == name)
      return it.get_curr();
  return nullptr;
}
 
void print_graph(TaskGraph& g, const string& title)
{
  cout << "\n=== " << title << " ===" << endl;
  cout << "Tasks: " << g.get_num_nodes() << endl;
  cout << "Dependencies: " << g.get_num_arcs() << endl;
  
  cout << "\nDependency structure:" << endl;
  for (auto nit = g.get_node_it(); nit.has_curr(); nit.next())
  {
    auto* node = nit.get_curr();
    cout << "  " << node->get_info() << " depends on: ";
    
    // Count incoming edges (dependencies)
    bool first = true;
    for (auto ait = g.get_arc_it(); ait.has_curr(); ait.next())
    {
      auto* arc = ait.get_curr();
      if (g.get_tgt_node(arc) == node)
      {
        if (not first) cout << ", ";
        cout << g.get_src_node(arc)->get_info();
        first = false;
      }
    }
    if (first) cout << "(none - root task)";
    cout << endl;
  }
}
 
void demo_dfs_topological_sort(TaskGraph& g, bool verbose)
{
  cout << "\n--- DFS-based Topological Sort ---" << endl;
  cout << "Algorithm: Post-order DFS traversal" << endl;
  
  Topological_Sort<TaskGraph> sorter;
  DynDlist<TaskGraph::Node*> sorted;
  
  sorter(g, sorted);
  
  cout << "\nExecution order:" << endl;
  int step = 1;
  for (auto it = sorted.get_it(); it.has_curr(); it.next(), ++step)
  {
    auto* node = it.get_curr();
    cout << "  " << setw(2) << step << ". " << node->get_info() << endl;
  }
  
  std::vector<TaskGraph::Node*> missing;
  const bool ok = verify_topological_order(g, sorted, &missing);
  if (!ok)
    {
      cout << "\n[Warning] The produced order is not a valid topological ordering.\n";
      cout << "This usually means the input graph is not a DAG (has a cycle) or the order is incomplete.\n";
      print_missing_nodes(missing);
    }
 
  if (verbose)
  {
    if (ok)
      cout << "\nVerification: Each task appears after all its dependencies." << endl;
  }
}
 
void demo_bfs_topological_sort(TaskGraph& g, bool verbose)
{
  cout << "\n--- BFS-based Topological Sort (Kahn's Algorithm) ---" << endl;
  cout << "Algorithm: Iteratively remove source nodes (in-degree 0)" << endl;
  
  Q_Topological_Sort<TaskGraph> sorter;
  DynDlist<TaskGraph::Node*> sorted;
  
  sorter(g, sorted);
  
  cout << "\nExecution order:" << endl;
  int step = 1;
  for (auto it = sorted.get_it(); it.has_curr(); it.next(), ++step)
  {
    auto* node = it.get_curr();
    cout << "  " << setw(2) << step << ". " << node->get_info() << endl;
  }
  
  std::vector<TaskGraph::Node*> missing;
  const bool ok = verify_topological_order(g, sorted, &missing);
  if (!ok)
    {
      cout << "\n[Warning] Kahn's algorithm did not produce a complete valid ordering.\n";
      cout << "If output size < V, the graph contains a cycle (not a DAG).\n";
      print_missing_nodes(missing);
    }
 
  if (verbose)
  {
    // Show ranks (parallel execution levels)
    cout << "\nParallel execution ranks:" << endl;
    Q_Topological_Sort<TaskGraph> rank_sorter;
    auto ranks = rank_sorter.ranks(g);
 
    // Validate rank output by flattening ranks into a single ordering
    DynDlist<TaskGraph::Node*> flat;
    std::unordered_set<TaskGraph::Node*> seen;
    seen.reserve(g.get_num_nodes());
    for (auto rit = ranks.get_it(); rit.has_curr(); rit.next_ne())
      for (auto nit = rit.get_curr().get_it(); nit.has_curr(); nit.next_ne())
        {
          auto * n = nit.get_curr();
          if (seen.insert(n).second)
            flat.append(n);
        }
    std::vector<TaskGraph::Node*> missing_ranks;
    const bool ok_ranks = verify_topological_order(g, flat, &missing_ranks);
    if (!ok_ranks)
      {
        cout << "\n[Warning] Rank-based output is incomplete/invalid (cycle or missing nodes).\n";
        print_missing_nodes(missing_ranks);
      }
    
    int rank_num = 0;
    for (auto rit = ranks.get_it(); rit.has_curr(); rit.next(), ++rank_num)
    {
      cout << "  Level " << rank_num << " (can run in parallel): ";
      auto& rank = rit.get_curr();
      bool first = true;
      for (auto nit = rank.get_it(); nit.has_curr(); nit.next())
      {
        if (not first) cout << ", ";
        cout << nit.get_curr()->get_info();
        first = false;
      }
      cout << endl;
    }
  }
}
 
void demo_build_order()
{
  cout << "\n" << string(60, '=') << endl;
  cout << "Example: Build System Dependencies" << endl;
  cout << string(60, '=') << endl;
  
  TaskGraph g = build_project_graph();
  print_graph(g, "Project Build Graph");
  
  cout << "\n--- Computing Build Order ---" << endl;
  
  Topological_Sort<TaskGraph> sorter;
  DynDlist<TaskGraph::Node*> build_order;
  
  sorter(g, build_order);
  
  cout << "\nBuild order (satisfies all dependencies):" << endl;
  cout << "  make ";
  bool first = true;
  for (auto it = build_order.get_it(); it.has_curr(); it.next())
  {
    if (not first) cout << " && make ";
    cout << it.get_curr()->get_info();
    first = false;
  }
  cout << endl;
}
 
void demo_course_scheduling()
{
  cout << "\n" << string(60, '=') << endl;
  cout << "Example: University Course Prerequisites" << endl;
  cout << string(60, '=') << endl;
  
  TaskGraph g = build_courses_graph();
  print_graph(g, "Course Prerequisites Graph");
  
  cout << "\n--- Computing Course Order ---" << endl;
  
  Q_Topological_Sort<TaskGraph> sorter;
  auto semesters = sorter.ranks(g);
  
  cout << "\nSuggested course schedule:" << endl;
  int semester = 1;
  for (auto sit = semesters.get_it(); sit.has_curr(); sit.next(), ++semester)
  {
    cout << "  Semester " << semester << ": ";
    auto& courses = sit.get_curr();
    bool first = true;
    for (auto cit = courses.get_it(); cit.has_curr(); cit.next())
    {
      if (not first) cout << ", ";
      cout << cit.get_curr()->get_info();
      first = false;
    }
    cout << endl;
  }
  
  cout << "\nTotal semesters needed: " << (semester - 1) << endl;
}
 
int main(int argc, char* argv[])
{
  try
  {
    TCLAP::CmdLine cmd("Topological Sort Example", ' ', "1.0");
    
    TCLAP::SwitchArg buildArg("b", "build",
      "Show build system example", false);
    TCLAP::SwitchArg courseArg("c", "courses",
      "Show course scheduling example", false);
    TCLAP::SwitchArg allArg("a", "all",
      "Run all demos", false);
    TCLAP::SwitchArg verboseArg("v", "verbose",
      "Show detailed output", false);
    
    cmd.add(buildArg);
    cmd.add(courseArg);
    cmd.add(allArg);
    cmd.add(verboseArg);
    
    cmd.parse(argc, argv);
    
    bool runBuild = buildArg.getValue();
    bool runCourse = courseArg.getValue();
    bool runAll = allArg.getValue();
    bool verbose = verboseArg.getValue();
    
    if (not runBuild and not runCourse)
      runAll = true;
    
    cout << "=== Topological Sort: Task Ordering with Dependencies ===" << endl;
    
    if (runAll or runBuild)
    {
      demo_build_order();
      
      // Also show both algorithms
      TaskGraph g = build_project_graph();
      demo_dfs_topological_sort(g, verbose);
      demo_bfs_topological_sort(g, verbose);
    }
    
    if (runAll or runCourse)
      demo_course_scheduling();
    
    cout << "\n=== Algorithm Summary ===" << endl;
    cout << "DFS-based:  O(V + E), post-order traversal" << endl;
    cout << "BFS-based:  O(V + E), Kahn's algorithm (removes sources)" << endl;
    cout << "Requirement: Input must be a DAG (no cycles)" << endl;
    
    return 0;
  }
  catch (TCLAP::ArgException& e)
  {
    cerr << "Error: " << e.error() << " for arg " << e.argId() << endl;
    return 1;
  }
}