|
Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
|
Tests for Random Graph. More...
#include <cassert>#include <iostream>#include <random_graph.H>#include <tpl_graph.H>#include <tpl_graph_utils.H>Go to the source code of this file.
Classes | |
| struct | NodeInitializer |
| struct | ArcInitializer |
Typedefs | |
| using | Graph = List_Graph< Graph_Node< int >, Graph_Arc< int > > |
Tests for Random Graph.
Definition in file random_graph.cc.
| using Graph = List_Graph<Graph_Node<int>, Graph_Arc<int> > |
Definition at line 48 of file random_graph.cc.
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().
Verify that a graph has no parallel arcs (simple graph)
Definition at line 56 of file random_graph.cc.
References Aleph::count(), GraphCommon< GT, Node, Arc >::get_arc_it(), GraphCommon< GT, Node, Arc >::get_src_node(), GraphCommon< GT, Node, Arc >::get_tgt_node(), and Aleph::maps().
Referenced by test_random_graph_probability(), test_random_graph_probability_dense(), test_random_graph_sparse_basic(), test_random_graph_sparse_connected(), and test_random_graph_sparse_disconnected().
| int main | ( | ) |
Definition at line 471 of file random_graph.cc.
References Aleph::maps(), test_complete_graph_limit(), test_custom_initializers(), test_random_graph_deterministic_seed(), test_random_graph_different_seeds(), test_random_graph_eulerian_sparse(), test_random_graph_invalid_probability(), test_random_graph_probability(), test_random_graph_probability_dense(), test_random_graph_sparse_basic(), test_random_graph_sparse_connected(), test_random_graph_sparse_disconnected(), test_single_node_graph(), test_two_node_graph(), and test_zero_nodes_rejected().
Verify Ore's theorem condition for Hamiltonian graphs: For all non-adjacent pairs u, v: deg(u) + deg(v) >= n.
Definition at line 96 of file random_graph.cc.
References GraphCommon< GT, Node, Arc >::get_arc_it(), GraphCommon< GT, Node, Arc >::get_connected_node(), GraphCommon< GT, Node, Arc >::get_node_it(), GraphCommon< GT, Node, Arc >::get_num_arcs(), GraphCommon< GT, Node, Arc >::get_num_nodes(), and Aleph::maps().
Referenced by test_random_graph_hamiltonian().
| void test_complete_graph_limit | ( | ) |
| void test_custom_initializers | ( | ) |
| void test_random_graph_deterministic_seed | ( | ) |
| void test_random_graph_different_seeds | ( | ) |
| void test_random_graph_eulerian_probability | ( | ) |
Definition at line 272 of file random_graph.cc.
References all_nodes_have_even_degree(), Aleph::maps(), and Aleph::test_connectivity().
| 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().
| void test_random_graph_hamiltonian | ( | ) |
Definition at line 287 of file random_graph.cc.
References Aleph::maps(), satisfies_ore_condition(), and Aleph::test_connectivity().
| void test_random_graph_invalid_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().
| 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().
| 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().
| 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().
| 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().
| void test_single_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().
| void test_zero_nodes_rejected | ( | ) |