random_graph_example.C File Reference

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:

Go to the source code of this file.

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:

1. Generate a random graph
2. 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:

1. Generate random graph
2. Identify vertices with odd degree
3. 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

See also

random_graph.H Random graph generation functions

eulerian_example.C Eulerian graph testing

graph_components_example.C Connected components (related)

Author

Leandro Rabindranath León

Date

2024

Copyright

GNU General Public License

Definition in file random_graph_example.C.

Typedef Documentation

Arc

using Arc = Graph_Arc<double>

Definition at line 187 of file random_graph_example.C.

DGraph

using DGraph = List_Digraph<Node, Arc>

Definition at line 189 of file random_graph_example.C.

Node

using Node = Graph_Node<int>

Definition at line 186 of file random_graph_example.C.

UGraph

using UGraph = List_Graph<Node, Arc>

Definition at line 188 of file random_graph_example.C.

Function Documentation

demo_connected()

void demo_connected

(

)

Definition at line 290 of file random_graph_example.C.

References Aleph::divide_and_conquer_partition_dp(), log(), m, print_graph_stats(), print_section(), and print_subsection().

Referenced by main().

demo_digraph()

void demo_digraph

(

)

Definition at line 374 of file random_graph_example.C.

References Aleph::divide_and_conquer_partition_dp(), m, max(), Aleph::Filter_Iterator< Container, It, Show_Item >::next(), print_section(), and print_subsection().

Referenced by main().

demo_erdos_renyi()

void demo_erdos_renyi

(

)

Definition at line 239 of file random_graph_example.C.

References Aleph::divide_and_conquer_partition_dp(), m, print_graph_stats(), print_section(), print_subsection(), and Aleph::to_string().

Referenced by main().

demo_eulerian()

void demo_eulerian

(

)

Definition at line 328 of file random_graph_example.C.

References Aleph::divide_and_conquer_partition_dp(), GraphCommon< GT, Node, Arc >::get_node_it(), m, Aleph::Filter_Iterator< Container, It, Show_Item >::next(), print_graph_stats(), print_section(), print_subsection(), and test().

Referenced by main().

demo_eulerian_digraph()

void demo_eulerian_digraph

(

)

Definition at line 419 of file random_graph_example.C.

References Aleph::divide_and_conquer_partition_dp(), m, print_section(), print_subsection(), and test().

Referenced by main().

demo_parameters()

void demo_parameters

(

)

Definition at line 452 of file random_graph_example.C.

References Aleph::divide_and_conquer_partition_dp(), log(), m, and print_section().

Referenced by main().

main()

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

Definition at line 504 of file random_graph_example.C.

References cmd, demo_connected(), demo_digraph(), demo_erdos_renyi(), demo_eulerian(), demo_eulerian_digraph(), demo_parameters(), Aleph::divide_and_conquer_partition_dp(), and section().

print_graph_stats()

template<typename G >

void print_graph_stats	(	const string &	label,
		G &	g
	)

Definition at line 208 of file random_graph_example.C.

References Aleph::divide_and_conquer_partition_dp(), GraphCommon< GT, Node, Arc >::get_node_it(), GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), max(), min(), and Aleph::Filter_Iterator< Container, It, Show_Item >::next().

Referenced by demo_connected(), demo_erdos_renyi(), and demo_eulerian().

print_section()

void print_section

(

const string &

title

)

Definition at line 195 of file random_graph_example.C.

Referenced by demo_connected(), demo_digraph(), demo_erdos_renyi(), demo_eulerian(), demo_eulerian_digraph(), and demo_parameters().

print_subsection()

void print_subsection

(

const string &

title

)

Definition at line 202 of file random_graph_example.C.

Referenced by demo_connected(), demo_digraph(), demo_erdos_renyi(), demo_eulerian(), and demo_eulerian_digraph().