Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
Classes | Typedefs | Functions
johnson_example.cc File Reference

Johnson all-pairs shortest paths in Aleph-w (negative weights, Floyd comparison, benchmark flags). More...

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <limits>
#include <chrono>
#include <cmath>
#include <random>
#include <unordered_set>
#include <cstring>
#include <tpl_graph.H>
#include <Johnson.H>
#include <Floyd_Warshall.H>
Include dependency graph for johnson_example.cc:

Go to the source code of this file.

Classes

struct  Distance
 Distance accessor. More...
 

Typedefs

using WeightedDigraph = List_Digraph< Graph_Node< string >, Graph_Arc< double > >
 
using Node = WeightedDigraph::Node
 
using Arc = WeightedDigraph::Arc
 

Functions

template<typename Func >
double measure_ms (Func &&f)
 
static void usage (const char *prog)
 
static WeightedDigraph build_random_graph (int n, int e, unsigned seed)
 
static void compare_with_floyd (WeightedDigraph &g)
 
Node * find_node (WeightedDigraph &g, const string &name)
 
void print_graph (WeightedDigraph &g)
 
void example_basic_all_pairs ()
 
void example_negative_cycle ()
 
void example_reweighting ()
 
void example_complexity_comparison ()
 
void example_currency_arbitrage ()
 
int main (int argc, char *argv[])
 

Detailed Description

Johnson all-pairs shortest paths in Aleph-w (negative weights, Floyd comparison, benchmark flags).

Overview

This example demonstrates Johnson's algorithm for all-pairs shortest paths (APSP) on a weighted directed graph.

Johnson is especially useful when:

  • the graph can contain negative edge weights, but
  • there are no negative cycles, and
  • the graph is sparse (E is closer to V than to V²).

Johnson combines Bellman-Ford (for reweighting) and Dijkstra (for efficient shortest paths once all weights are non-negative).

Data model used by this example

  • Graph type: WeightedDigraph = List_Digraph<Graph_Node<string>, Graph_Arc<double>>
  • Node info: label/name (string)
  • Arc info: weight/cost (double)

Usage / CLI

# Run built-in demos
./johnson_example
# Compare Johnson vs Floyd-Warshall on a small demo graph
./johnson_example --compare
# Random graph benchmark (non-negative weights)
./johnson_example -n 1000 -e 5000
# Benchmark + compare (Floyd only runs automatically for n <= 200)
./johnson_example --compare -n 150 -e 1000
# Show help
./johnson_example --help
./johnson_example -h

Notes:

  • If you pass -n without -e, the program uses e = 5*n.
  • The generated benchmark graph uses positive weights in [1, 10].

Algorithm (Johnson)

  1. Add a dummy source q and connect q -> v with weight 0 for all vertices v.
  2. Run Bellman-Ford from q to compute potentials h(v).
    • If a negative cycle is detected, APSP is undefined.
  3. Reweight edges:
  4. Run Dijkstra as needed on the reweighted graph.
  5. Convert distances back: -d(u,v) = d'(u,v) - h(u) + h(v)`

In Aleph-w, constructing Johnson<...> performs the Bellman-Ford step and reweighting internally.

Complexity

Let V be the number of nodes and E the number of arcs.

  • Classic Johnson (one Dijkstra per source):
    • O(V*E + V*(E+V) log V) with a binary heap.
  • This example's Floyd comparison computes a full distance table by repeatedly calling johnson.get_distance(src,tgt) for every pair, which is significantly more expensive if each get_distance() triggers a Dijkstra run.
  • **Benchmark mode (-n/-e)** intentionally performs only a single sample query to avoid an O(V^2) all-pairs loop.

Pitfalls and edge cases

  • Negative cycles: if a negative cycle exists, shortest paths are undefined. In this example, Johnson<...> construction throws std::domain_error.
  • Dense graphs: for E ≈ V², Floyd-Warshall (O(V^3)) can be competitive or simpler to reason about.
  • Benchmarking: avoid computing a full V×V matrix by naïvely calling get_distance(src,tgt) for all pairs on large graphs.

References / see also

Author
Leandro Rabindranath León

Definition in file johnson_example.cc.

Typedef Documentation

◆ Arc

using Arc = WeightedDigraph::Arc

Definition at line 152 of file johnson_example.cc.

◆ Node

using Node = WeightedDigraph::Node

Definition at line 151 of file johnson_example.cc.

◆ WeightedDigraph

using WeightedDigraph = List_Digraph<Graph_Node<string>, Graph_Arc<double> >

Definition at line 150 of file johnson_example.cc.

Function Documentation

◆ build_random_graph()

static WeightedDigraph build_random_graph ( int  n,
int  e,
unsigned  seed 
)
static

Definition at line 174 of file johnson_example.cc.

References StlAlephIterator< SetName >::end(), Aleph::DynList< T >::insert(), Aleph::maps(), nodes, rng, and Aleph::to_string().

◆ compare_with_floyd()

static void compare_with_floyd ( WeightedDigraph &  g)
static

Definition at line 216 of file johnson_example.cc.

References Aleph::maps(), measure_ms(), and nodes.

◆ example_basic_all_pairs()

void example_basic_all_pairs ( )

Definition at line 323 of file johnson_example.cc.

References h, Aleph::maps(), nodes, and print_graph().

◆ example_complexity_comparison()

void example_complexity_comparison ( )

Definition at line 510 of file johnson_example.cc.

◆ example_currency_arbitrage()

void example_currency_arbitrage ( )

Definition at line 523 of file johnson_example.cc.

◆ example_negative_cycle()

void example_negative_cycle ( )

Definition at line 415 of file johnson_example.cc.

References Aleph::maps(), and print_graph().

◆ example_reweighting()

void example_reweighting ( )

Definition at line 466 of file johnson_example.cc.

References Aleph::maps().

◆ find_node()

Node * find_node ( WeightedDigraph &  g,
const string &  name 
)

Definition at line 279 of file johnson_example.cc.

◆ main()

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

Definition at line 568 of file johnson_example.cc.

◆ measure_ms()

template<typename Func >
double measure_ms ( Func &&  f)

Definition at line 311 of file johnson_example.cc.

Referenced by compare_with_floyd().

◆ print_graph()

void print_graph ( WeightedDigraph &  g)

Definition at line 287 of file johnson_example.cc.

References Aleph::maps().

Referenced by example_basic_all_pairs(), and example_negative_cycle().

◆ usage()

static void usage ( const char *  prog)
static

Definition at line 166 of file johnson_example.cc.

References Aleph::maps().