Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
random_graph.cc File Reference

Tests for Random Graph. More...

#include <cassert>
#include <iostream>
#include <random_graph.H>
#include <tpl_graph.H>
#include <tpl_graph_utils.H>
Include dependency graph for random_graph.cc:

Go to the source code of this file.

Classes

struct  NodeInitializer
 
struct  ArcInitializer
 

Typedefs

using Graph = List_Graph< Graph_Node< int >, Graph_Arc< int > >
 

Functions

template<class GT >
bool is_simple_graph (const GT &g)
 Verify that a graph has no parallel arcs (simple graph)
 
template<class GT >
bool all_nodes_have_even_degree (const GT &g)
 Verify that all nodes have even degree (necessary for Eulerian)
 
template<class GT >
bool satisfies_ore_condition (const GT &g)
 Verify Ore's theorem condition for Hamiltonian graphs: For all non-adjacent pairs u, v: deg(u) + deg(v) >= n.
 
void test_random_graph_sparse_basic ()
 
void test_random_graph_sparse_connected ()
 
void test_random_graph_sparse_disconnected ()
 
void test_random_graph_probability ()
 
void test_random_graph_probability_dense ()
 
void test_random_graph_invalid_probability ()
 
void test_random_graph_eulerian_sparse ()
 
void test_random_graph_eulerian_probability ()
 
void test_random_graph_hamiltonian ()
 
void test_random_graph_deterministic_seed ()
 
void test_random_graph_different_seeds ()
 
void test_single_node_graph ()
 
void test_zero_nodes_rejected ()
 
void test_two_node_graph ()
 
void test_complete_graph_limit ()
 
void test_custom_initializers ()
 
int main ()
 

Detailed Description

Tests for Random Graph.

Definition in file random_graph.cc.

Typedef Documentation

◆ Graph

using Graph = List_Graph<Graph_Node<int>, Graph_Arc<int> >

Definition at line 48 of file random_graph.cc.

Function Documentation

◆ all_nodes_have_even_degree()

template<class GT >
bool all_nodes_have_even_degree ( const GT g)

Verify that all nodes have even degree (necessary for Eulerian)

Definition at line 82 of file random_graph.cc.

References GraphCommon< GT, Node, Arc >::get_node_it(), and GraphCommon< GT, Node, Arc >::get_num_arcs().

Referenced by test_random_graph_eulerian_probability(), and test_random_graph_eulerian_sparse().

◆ is_simple_graph()

◆ main()

◆ satisfies_ore_condition()

template<class GT >
bool satisfies_ore_condition ( const GT g)

◆ test_complete_graph_limit()

void test_complete_graph_limit ( )

Definition at line 396 of file random_graph.cc.

References Aleph::maps().

Referenced by main().

◆ test_custom_initializers()

void test_custom_initializers ( )

Definition at line 434 of file random_graph.cc.

References Aleph::maps().

Referenced by main().

◆ test_random_graph_deterministic_seed()

void test_random_graph_deterministic_seed ( )

Definition at line 302 of file random_graph.cc.

References Aleph::maps().

Referenced by main().

◆ test_random_graph_different_seeds()

void test_random_graph_different_seeds ( )

Definition at line 318 of file random_graph.cc.

References Aleph::maps().

Referenced by main().

◆ test_random_graph_eulerian_probability()

void test_random_graph_eulerian_probability ( )

◆ test_random_graph_eulerian_sparse()

void test_random_graph_eulerian_sparse ( )

Definition at line 257 of file random_graph.cc.

References all_nodes_have_even_degree(), Aleph::maps(), and Aleph::test_connectivity().

Referenced by main().

◆ test_random_graph_hamiltonian()

void test_random_graph_hamiltonian ( )

◆ test_random_graph_invalid_probability()

void test_random_graph_invalid_probability ( )

Definition at line 221 of file random_graph.cc.

References Aleph::maps().

Referenced by main().

◆ test_random_graph_probability()

void test_random_graph_probability ( )

Definition at line 184 of file random_graph.cc.

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

Referenced by main().

◆ test_random_graph_probability_dense()

void test_random_graph_probability_dense ( )

Definition at line 202 of file random_graph.cc.

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

Referenced by main().

◆ test_random_graph_sparse_basic()

void test_random_graph_sparse_basic ( )

Definition at line 137 of file random_graph.cc.

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

Referenced by main().

◆ test_random_graph_sparse_connected()

void test_random_graph_sparse_connected ( )

Definition at line 153 of file random_graph.cc.

References is_simple_graph(), Aleph::maps(), and Aleph::test_connectivity().

Referenced by main().

◆ test_random_graph_sparse_disconnected()

void test_random_graph_sparse_disconnected ( )

Definition at line 168 of file random_graph.cc.

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

Referenced by main().

◆ test_single_node_graph()

void test_single_node_graph ( )

Definition at line 349 of file random_graph.cc.

References Aleph::maps().

Referenced by main().

◆ test_two_node_graph()

void test_two_node_graph ( )

Definition at line 381 of file random_graph.cc.

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

Referenced by main().

◆ test_zero_nodes_rejected()

void test_zero_nodes_rejected ( )

Definition at line 363 of file random_graph.cc.

References Aleph::maps().

Referenced by main().