Example demonstrating random graph generation in Aleph-w. More...

#include <iostream>
#include <iomanip>
#include <string>
#include <tclap/CmdLine.h>
#include <tpl_graph.H>
#include <random_graph.H>
#include <tpl_components.H>
#include <eulerian.H>

Include dependency graph for random_graph_example.C:

Typedefs
using	Node = Graph_Node< int >

using	Arc = Graph_Arc< double >

using	UGraph = List_Graph< Node, Arc >

using	DGraph = List_Digraph< Node, Arc >

Functions
void	print_section (const string &title)

void	print_subsection (const string &title)

template<typename G >
void	print_graph_stats (const string &label, G &g)

void	demo_erdos_renyi ()

void	demo_connected ()

void	demo_eulerian ()

void	demo_digraph ()

void	demo_eulerian_digraph ()

void	demo_parameters ()

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

Detailed Description

Example demonstrating random graph generation in Aleph-w.

This program demonstrates random_graph.H which provides various models for generating random graphs. Random graphs are essential for algorithm testing, benchmarking, and research in graph theory.

Why Random Graphs?

Random graphs are useful for:

Algorithm testing: Test algorithms on diverse inputs
Benchmarking: Compare algorithm performance
Research: Study graph properties statistically
Simulation: Model real-world networks

Graph Models

Erdős–Rényi G(n,m)

Model: Random graph with n vertices and m randomly placed edges

Properties:

Each of the C(n,2) possible edges included with probability p = m/C(n,2)
May be disconnected (especially for small m)
Expected number of edges: m

Complexity: O(m) to generate

Applications:

Basic random graph model
Algorithm testing
Theoretical analysis

Connected Random Graph

Model: Random graph guaranteed to be connected

Algorithm:

Generate a random graph
If it is disconnected, add extra edges between components until it becomes connected

Properties:

Always connected
Minimum m = n-1 (spanning tree)
Can have any m ≥ n-1

Complexity: O(m) to generate

Applications:

Testing connectivity algorithms
Network design
Ensuring graph properties

Eulerian Random Graph

Model: Random graph with Eulerian cycle

Properties:

All vertices have even degree
Has an Eulerian cycle (visits every edge once)
Can be generated by pairing odd-degree vertices

Algorithm:

Generate random graph
Identify vertices with odd degree
Pair them and add edges (makes all degrees even)

Complexity: O(m + V) to generate

Applications:

Testing Eulerian path algorithms
Route planning
Network design

Random Directed Graphs (Digraphs)

Model: Directed version of random graphs

Properties:

Edges have direction
May have cycles
Connectivity is asymmetric

Applications:

Testing directed graph algorithms
Modeling directed networks
Dependency analysis

Graph Properties by Model

Model	Connected?	Eulerian?	Cycles?	Degree Distribution
Erdős–Rényi	Maybe	Maybe	Maybe	Binomial
Connected	Always	Maybe	Usually	Varies
Eulerian	Usually	Always	Usually	All even
Digraph	Maybe	Maybe	Maybe	Asymmetric

When to Use Each Model

Use Erdős–Rényi When:

Need simple random graph
Don't care about connectivity
Testing general algorithms

Use Connected When:

Need guaranteed connectivity
Testing connectivity algorithms
Network design problems

Use Eulerian When:

Testing Eulerian path algorithms
Route planning problems
Need even-degree graph

Use Digraph When:

Testing directed algorithms
Modeling directed networks
Dependency problems

Complexity

Operation	Complexity	Notes
Generate G(n,m)	O(m)	Random edge placement
Generate connected	O(m)	Tree + random edges
Generate Eulerian	O(m + V)	Fix odd degrees
Generate digraph	O(m)	Directed edges

Applications

Algorithm Testing

Diverse inputs: Test on various graph structures
Edge cases: Find algorithm weaknesses
Performance: Benchmark on different sizes

Research

Graph theory: Study graph properties
Random processes: Model random phenomena
Statistical analysis: Analyze graph statistics

Simulation

Network modeling: Model real-world networks
Social networks: Generate synthetic networks
Infrastructure: Model transportation networks

Usage

# Run all random graph demos
./random_graph_example
 
# Generate specific model
./random_graph_example -s erdos
./random_graph_example -s connected
./random_graph_example -s eulerian
./random_graph_example -s digraph
./random_graph_example -s eulerian_dig
./random_graph_example -s params