09 May 2025 9:14:40.080 PM graph_adj_test(): FORTRAN90 version Test graph_adj(), which implements graph algorithms. graph_adj_breadth_first_test() graph_adj_breadth_first() sets up a breadth-first traversal of a graph. The graph: 1 0111111100000 2 1000110100000 3 1001001000000 4 1010000000000 5 1100000000000 6 1100000000000 7 1010000000000 8 1100000000000 9 0000000001001 10 0000000010111 11 0000000001010 12 0000000001100 13 0000000011000 I, dad(i), deep(i), order(i) 1 0 1 1 2 1 2 2 3 1 2 3 4 1 2 4 5 1 2 5 6 1 2 6 7 1 2 7 8 1 2 8 9 0 3 9 10 9 4 10 11 10 5 12 12 10 5 13 13 9 4 11 graph_adj_block_test(): graph_adj_block() finds the blocks in a graph. Number of blocks = 3 I, DAD(I), ORDER(I) 1 0 -1 2 1 2 3 4 5 4 1 -4 5 4 6 6 2 3 The graph: 1 010331 2 100001 3 000200 4 302030 5 300300 6 110000 graph_adj_color_next_test(): graph_adj_color_next() produces colorings of a graph The number of colors available is 3 The graph: 1 0101 2 1010 3 0101 4 1010 Possible node colorings: 1 3 2 3 1 3 1 3 1 3 1 2 1 2 3 2 1 2 1 3 1 2 1 2 graph_adj_complement_test(): graph_adj_complement() finds the complement of a graph; The adjacency matrix for G: 1 10011000 2 01000000 3 00100011 4 10011000 5 10011100 6 00001100 7 00100010 8 00100001 Adjacency matrix for the complement of G: 1 01100111 2 10111111 3 11011100 4 01100111 5 01100011 6 11110011 7 11011101 8 11011110 graph_adj_cycle_test(): graph_adj_cycle() searches for cycles in a graph. The graph: 1 0010001001 2 0000100001 3 1000010010 4 0000001100 5 0100000000 6 0010000010 7 1001000000 8 0001000001 9 0010010000 10 1100000100 Node, Dad, Order 1 0 1 2 10 9 3 1 2 4 7 6 5 2 10 6 3 3 7 1 5 8 4 7 9 6 4 10 8 8 Adjacency matrix with cycles marked. 0 0 -2 0 0 0 -2 0 0 -1 0 0 0 0 -2 0 0 0 0 -2 -2 0 0 0 0 -2 0 0 -1 0 0 0 0 0 0 0 -2 -2 0 0 0 -2 0 0 0 0 0 0 0 0 0 0 -2 0 0 0 0 0 -2 0 -2 0 0 -2 0 0 0 0 0 0 0 0 0 -2 0 0 0 0 0 -2 0 0 -1 0 0 -2 0 0 0 0 -1 -2 0 0 0 0 0 -2 0 0 graph_adj_degree_test(): graph_adj_degree() computes the degree of the nodes; The graph: 1 0010001001 2 0000100001 3 1000010010 4 0000001100 5 0100000000 6 0010000010 7 1001000000 8 0001000001 9 0010010000 10 1100000100 Node degrees: 1 3 2 2 3 3 4 2 5 1 6 2 7 2 8 2 9 2 10 3 graph_adj_degree_max_test(): graph_adj_degree_max() computes the maximum degree of the nodes; The graph: 1 0010001001 2 0000100001 3 1000010010 4 0000001100 5 0100000000 6 0010000010 7 1001000000 8 0001000001 9 0010010000 10 1100000100 Maximum node degree is 3 graph_adj_degree_sequence_test(): graph_adj_degree_sequence() computes the degree sequence; The graph: 1 0010001001 2 0000100001 3 1000010010 4 0000001100 5 0100000000 6 0010000010 7 1001000000 8 0001000001 9 0010010000 10 1100000100 Degree sequence: 1 3 2 3 3 3 4 2 5 2 6 2 7 2 8 2 9 2 10 1 graph_adj_depth_first_test(): graph_adj_depth_first() does depth first search of graph. The graph: 1 0110011000000 2 0000000000000 3 0000000000000 4 0000000000000 5 0001001000000 6 0000100000000 7 0000000000000 8 0000000010000 9 0000000000000 10 0000000000111 11 0000000000000 12 0000000000001 13 0000000000000 Node, Dad, Order 1 0 1 2 1 2 3 1 3 4 5 6 5 6 5 6 1 4 7 5 7 8 0 8 9 8 9 10 0 10 11 10 11 12 10 12 13 12 13 graph_adj_depth_first_2_test(): graph_adj_depth_first_2() sets up depth-first traversal of a graph described by an adjacency matrix. The graph: 1 0111111100000 2 1000110100000 3 1001001000000 4 1010000000000 5 1100000000000 6 1100000000000 7 1010000000000 8 1100000000000 9 0000000001001 10 0000000010111 11 0000000001010 12 0000000001100 13 0000000011000 I, DAD(I), ORDER(I) 1 0 1 2 1 2 3 1 6 4 3 7 5 2 3 6 2 4 7 3 8 8 2 5 9 0 9 10 9 10 11 10 11 12 11 12 13 10 13 graph_adj_edge_count_test(): graph_adj_edge_count() counts the edges in a graph. Adjacency matrix: 1 0001000 2 0000100 3 0000100 4 1000111 5 0111000 6 0001000 7 0001000 Number of edges is 6 graph_adj_edge_select_test(): graph_adj_edge_select() selects an edge from a graph defined by an adjacency matrix. Adjacency matrix for bush example 1 0001000 2 0000100 3 0000100 4 1000111 5 0111000 6 0001000 7 0001000 An edge of this graph extends from node 1 to node 4 graph_adj_eigen_test(): graph_adj_eigen() computes the eigenvalues of a graph. The graph: 1 0010001001 2 0000100001 3 1000010010 4 0000001100 5 0100000000 6 0010000010 7 1001000000 8 0001000001 9 0010010000 10 1100000100 The eigenvalues: 1 -2.11644 2 -1.72209 3 -1.15483 4 -1.00000 5 -0.702785 6 0.429094 7 0.673286 8 1.26660 9 1.91496 10 2.41221 TEST036 GRAPH_ADJ_HAM_NEXT produces Hamilton circuits; The graph: 1 01000001000000000001 2 10100000000000100000 3 01010010000000000000 4 00101000000001000000 5 00010100000100000000 6 00001010010000000000 7 00100101000000000000 8 10000010100000000000 9 00000001010000000010 10 00000100101000000000 11 00000000010100000100 12 00001000001010000000 13 00000000000101001000 14 00010000000010100000 15 01000000000001010000 16 00000000000000101001 17 00000000000010010100 18 00000000001000001010 19 00000000100000000101 20 10000000000000010010 Circuits: 1 1 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 2 1 20 19 18 17 16 15 2 3 7 6 5 4 14 13 12 11 10 9 8 3 1 20 19 18 11 12 13 17 16 15 14 4 5 6 10 9 8 7 3 2 4 1 20 19 18 11 12 5 6 10 9 8 7 3 4 14 13 17 16 15 2 5 1 20 19 18 11 12 5 4 14 13 17 16 15 2 3 7 6 10 9 8 6 1 20 19 18 11 10 9 8 7 6 5 12 13 17 16 15 14 4 3 2 7 1 20 19 9 10 11 18 17 16 15 2 3 4 14 13 12 5 6 7 8 8 1 20 19 9 10 6 5 4 14 13 12 11 18 17 16 15 2 3 7 8 9 1 20 19 9 8 7 6 10 11 18 17 16 15 14 13 12 5 4 3 2 10 1 20 19 9 8 7 3 4 14 13 12 5 6 10 11 18 17 16 15 2 11 1 20 16 17 18 19 9 10 11 12 13 14 15 2 3 4 5 6 7 8 12 1 20 16 17 18 19 9 8 7 3 4 5 6 10 11 12 13 14 15 2 13 1 20 16 17 13 14 15 2 3 4 5 12 11 18 19 9 10 6 7 8 14 1 20 16 17 13 12 11 18 19 9 10 6 5 4 14 15 2 3 7 8 15 1 20 16 17 13 12 5 6 10 11 18 19 9 8 7 3 4 14 15 2 16 1 20 16 17 13 12 5 4 14 15 2 3 7 6 10 11 18 19 9 8 17 1 20 16 15 14 13 17 18 19 9 8 7 6 10 11 12 5 4 3 2 18 1 20 16 15 14 4 5 6 10 11 12 13 17 18 19 9 8 7 3 2 19 1 20 16 15 2 3 7 6 10 11 12 5 4 14 13 17 18 19 9 8 20 1 20 16 15 2 3 4 14 13 17 18 19 9 10 11 12 5 6 7 8 21 1 8 9 19 20 16 17 18 11 10 6 7 3 4 5 12 13 14 15 2 22 1 8 9 19 20 16 15 14 4 5 12 13 17 18 11 10 6 7 3 2 23 1 8 9 10 11 18 19 20 16 17 13 12 5 6 7 3 4 14 15 2 24 1 8 9 10 11 12 13 17 18 19 20 16 15 14 4 5 6 7 3 2 25 1 8 9 10 11 12 5 6 7 3 4 14 13 17 18 19 20 16 15 2 26 1 8 9 10 6 7 3 4 5 12 11 18 19 20 16 17 13 14 15 2 27 1 8 7 6 10 9 19 20 16 15 14 13 17 18 11 12 5 4 3 2 28 1 8 7 6 5 12 13 17 18 11 10 9 19 20 16 15 14 4 3 2 29 1 8 7 3 4 14 13 17 18 11 12 5 6 10 9 19 20 16 15 2 30 1 8 7 3 4 5 6 10 9 19 20 16 17 18 11 12 13 14 15 2 TEST0365 GRAPH_ADJ_HAM_NEXT produces Hamilton circuits; The graph: 1 010101000 2 101000100 3 010101000 4 101000100 5 000001101 6 101010010 7 010110000 8 000001001 9 000010010 Circuits: 1 1 6 8 9 5 7 4 3 2 2 1 6 8 9 5 7 2 3 4 3 1 4 7 5 9 8 6 3 2 4 1 4 3 6 8 9 5 7 2 graph_adj_ham_next_brute_test(): graph_adj_ham_next_brute() seeks circuits in a graph which visit every node. A brute force algorithm is used. The graph: 1 010101000 2 101000100 3 010101000 4 101000100 5 000001101 6 101010010 7 010110000 8 000001001 9 000010010 Circuits: 1 1 2 3 4 7 5 9 8 6 2 1 2 3 6 8 9 5 7 4 3 1 2 7 5 9 8 6 3 4 4 1 4 3 2 7 5 9 8 6 No more circuits were found. graph_adj_is_bipartite_test() graph_adj_is_bipartite() reports if a graph is bipartite. The graph: 1 1111110011 2 1000001100 3 1001100010 4 1001100000 5 1000000000 6 1101100010 7 1001100010 8 1110010011 9 1000001100 10 1000001100 The graph is NOT bipartite. graph_adj_is_edgewise_connected_test(): graph_adj_is_edgewise_connected() reports if a graph is edgewise connected; Number of nodes is 6 Number of edges is 8 The graph: 1 011100 2 100000 3 100000 4 100001 5 000001 6 000110 The graph IS edgewise connected. graph_adj_is_nodewise_connected_test(): graph_adj_is_nodewise_connected() reports if a graph is nodewise connected; Number of nodes is 6 Number of edges is 8 The graph: 1 000101 2 000001 3 000001 4 100000 5 000001 6 111010 The graph IS nodewise connected. graph_adj_is_tree_test(): graph_adj_is_tree() reports if a graph is a tree. Number of nodes is 6 Number of edges is 5 The graph: 1 000101 2 000000 3 000010 4 100010 5 001101 6 100010 The graph is NOT a tree. graph_adj_random_test(): graph_adj_random() returns a random graph, for which edges are generated with a given probability. Here, we show the effect of increasing connectivity on the singularity of the adjacency matrix. Probability of edge generation = 0.250000 Number of edges generated = 50 Maximum number of edges = 190 Generated / Maximum = 0.263158 The graph: 1 01000000001000000000 2 10111000111000010110 3 01000001000000000000 4 01000110000010000000 5 01000001100000100100 6 00010011000000001001 7 00010100001100100010 8 00101100000000000011 9 01001000000110101000 10 01000000000001010000 11 11000010000100100000 12 00000010101000111000 13 00010000100001111010 14 00000000010010010000 15 00001010101110011000 16 01000000010111100000 17 00000100100110100100 18 01001000000000001000 19 01000011000010000001 20 00000101000000000010 The eigenvalues: 1 -3.63546 2 -2.91609 3 -2.55333 4 -2.25133 5 -1.75484 6 -1.49366 7 -1.14586 8 -1.02982 9 -0.694049 10 -0.241816 11 -0.390492E-01 12 0.265101 13 0.351083 14 0.695847 15 1.09781 16 1.99129 17 2.15219 18 2.51596 19 2.94076 20 5.74526 Probability of edge generation = 0.400000 Number of edges generated = 79 Maximum number of edges = 190 Generated / Maximum = 0.415789 The graph: 1 00010000100101110010 2 00010100001111111100 3 00000011100100100000 4 11001111101100000010 5 00010100000011010111 6 01011000010110100100 7 00110001000100001110 8 00110010100110101001 9 10110001001000011000 10 00000100000100000000 11 01010000100010011001 12 11110111010010010010 13 01001101001101101011 14 11001000000010010110 15 11100101000010000001 16 11001000101101001101 17 01000011101010010110 18 01001110000001011010 19 10011010000111001100 20 00001001001010110000 The eigenvalues: 1 -3.71654 2 -3.47630 3 -2.83275 4 -2.76331 5 -2.52527 6 -2.02299 7 -1.84931 8 -1.08378 9 -0.865273 10 -0.427624 11 -0.181437 12 0.372692 13 0.610739 14 0.962867 15 1.45949 16 1.68504 17 2.44999 18 2.56813 19 3.19929 20 8.43636 Probability of edge generation = 0.650000 Number of edges generated = 130 Maximum number of edges = 190 Generated / Maximum = 0.684211 The graph: 1 00001001110101011101 2 00111110001111111101 3 01000110101011101000 4 01000011111111110001 5 11000111111111100111 6 01101000111111101111 7 01111000111111101011 8 10011000110010000111 9 10111111011001111101 10 10011111101111100001 11 01111110110011000111 12 11011110010010110011 13 01111111011101101111 14 11111110111010101111 15 01111110110111011110 16 11010000100100101001 17 11100110100011110111 18 11001101101011101011 19 00001111001111101101 20 11011111111111011110 The eigenvalues: 1 -3.74913 2 -3.41511 3 -3.17615 4 -2.79904 5 -2.21026 6 -2.04161 7 -1.71257 8 -1.46318 9 -1.24137 10 -0.595116 11 -0.335382 12 -0.290524 13 0.100764 14 0.342944 15 0.593779 16 1.46034 17 2.00993 18 2.27167 19 2.81961 20 13.4304 graph_adj_random_bipartite_test(): graph_adj_random_bipartite() returns a random bipartite graph; Number of nodes in set 1 is 4 Number of nodes in set 2 is 6 The graph: 1 1100000101 2 1001000101 3 1000101010 4 1000010000 5 1101000000 6 0000000000 7 1011000000 8 1000111010 9 1101000101 10 1000101010 Total number of edges is 0 Counted number of edges is 17 graph_adj_random_connected_test(): graph_adj_random_connected() returns a random connected graph; Number of nodes is 6 Number of edges is 8 The graph: 1 001000 2 000101 3 100010 4 010010 5 001100 6 010000 graph_adj_random_edges_test(): graph_adj_random_edges() returns a random graph with a specified number of edges. Number of edges requested = 10 The graph: 1 011100 2 101110 3 110011 4 110001 5 011001 6 001110 graph_adj_reduce_test(): graph_adj_reduce() finds the transitive reduction of a graph. The adjacency matrix for G: 1 10011000 2 01000000 3 00100011 4 10011000 5 10011100 6 00001100 7 00100010 8 00100001 Adjacency matrix for the transitive reduction of G: 1 00011000 2 00000000 3 00000011 4 10000000 5 10000100 6 00001000 7 00100000 8 00100000 graph_adj_span_tree_test(): graph_adj_span_tree() constructs a spanning tree of a graph. The graph: 1 0111111100000 2 1000110100000 3 1001001000000 4 1010000000000 5 1100000000000 6 1100000000000 7 1010000000000 8 1100000010000 9 0000000101001 10 0000000010111 11 0000000001010 12 0000000001100 13 0000000011000 The spanning tree: 1 1 2 2 1 3 3 1 4 4 1 5 5 1 6 6 1 7 7 1 8 8 8 9 9 9 10 10 9 13 11 10 11 12 10 12 graph_adj_span_tree_enum_test(): graph_adj_span_tree_enum() enumerates the spanning trees of a graph. The graph: 1 0111111100000 2 1000110100000 3 1001001000000 4 1010000000000 5 1100000000000 6 1100000000000 7 1010000000000 8 1100000010000 9 0000000101001 10 0000000010111 11 0000000001010 12 0000000001100 13 0000000011000 Total number of spanning trees is 1440 graph_adj_transitive_closure_test(): graph_adj_transitive_closure() finds the transitive closure of a graph; The adjacency matrix for G: 1 10011000 2 01000000 3 00100011 4 10011000 5 10011100 6 00001100 7 00100010 8 00100001 Adjacency matrix for the transitive closure of G: 1 10011100 2 01000000 3 00100011 4 10011100 5 10011100 6 10011100 7 00100011 8 00100011 graph_adj_test(): Normal end of execution. 09 May 2025 9:14:40.082 PM