12 March 2023 9:36:33.897 AM graph_theory_test(): FORTRAN90 version graph_theory() implements graph algorithms. degree_sequence_is_graphic_test(): degree_sequence_is_graphic() reports whether a given sequence can represent the degree sequence of a graph. The degree sequence: 1 5 2 5 3 3 4 2 5 2 6 1 The sequence is NOT graphic. The degree sequence: 1 5 2 5 3 3 4 3 5 2 6 1 The sequence is NOT graphic. The degree sequence: 1 4 2 2 3 2 4 2 5 2 6 2 The sequence IS graphic. The degree sequence: 1 5 2 4 3 3 4 2 5 1 6 1 The sequence is NOT graphic. The degree sequence: 1 4 2 4 3 2 4 2 5 1 6 1 The sequence IS graphic. degree_sequence_to_graph_adj_test() degree_sequence_to_graph_adj() is given a degree sequence, and constructs the adjancency matrix of a corresponding graph. The degree sequence: 1 5 2 5 3 4 4 3 5 3 6 2 The graph: 1 011111 2 101111 3 110110 4 111000 5 111000 6 110000 face_check_test() face_check() checks faces; max_face = 10 max_order = 4 Get a test example Face, Order, Nodes 1 4 9 10 12 11 2 3 14 13 15 3 4 1 2 6 5 4 4 6 7 3 2 5 4 3 4 8 7 6 3 13 12 11 7 4 1 2 3 4 8 4 5 6 7 8 Determine edge-connected objects. Number of objects = 3 Face, Object, Tier 1 1 1 2 2 1 3 3 1 4 3 2 5 3 3 6 1 2 7 3 2 8 3 2 Preferred order: Order, Face 1 1 2 6 3 2 4 3 5 4 6 7 7 8 8 5 Reorder the faces. Face, Label, Object, Tier 1 1 1 1 2 6 1 2 3 2 2 1 4 3 3 1 5 4 3 2 6 7 3 2 7 8 3 2 8 5 3 3 Construct the edge list. (While doing so, check for edges used more than twice.) Edge, Node1, Node2, Face1, Face2, Tier, Object I, node1(i), node2(i), face1(i), face2(i) 1 9 10 1 0 2 10 12 1 0 3 12 11 1 2 4 11 9 1 0 5 12 13 2 0 6 13 11 2 0 7 14 13 3 0 8 13 15 3 0 9 15 14 3 0 10 1 2 4 5 11 2 6 4 6 12 6 5 4 7 13 5 1 4 0 14 1 4 5 0 15 4 3 5 8 16 3 2 5 6 17 3 7 6 8 18 7 6 6 7 19 7 8 7 8 20 8 5 7 0 21 4 8 8 0 Face, Order, Nodes 1 4 9 10 12 11 2 3 11 12 13 3 3 14 13 15 4 4 1 2 6 5 5 4 2 1 4 3 6 4 2 3 7 6 7 4 5 6 7 8 8 4 3 4 8 7 Force faces to consistent orientation. Face, Order, Nodes 1 4 9 10 12 11 2 3 11 12 13 3 3 14 13 15 4 4 1 2 6 5 5 4 2 1 4 3 6 4 2 3 7 6 7 4 5 6 7 8 8 4 3 4 8 7 List boundary edges. EDGE_BOUND Number of boundary edges = 12 TEST060 VLA_TO_GRAPH_ARC converts VLA edge data to a graph defined by arcs; GRAPH_ARC_FACE constructs the faces of an orientable graph. FACE_TO_IV writes face data to an IV file. VLA_TO_GRAPH_ARC - Note: The graph was read properly. Number of nodes = 135 Number of edges = 389 Sort the edges: Determine the faces: Number of faces found was 259 Euler predicted 256 FACE_TO_IV: The data was written to the file: fish_faces.iv grf_read_test(): grf_read() reads a GRF file, graph_arc_to_ps() writes a PostScript version of it. GRF_READ - Input file statistics: Text lines: 64 Bad text lines: 0 Nodes: 64 Edges: 336 Node, X, Y 1 0.112000 0.940000 2 0.224000 0.948000 3 0.324000 0.952000 4 0.420000 0.946000 5 0.514000 0.952000 6 0.610000 0.950000 7 0.694000 0.950000 8 0.798000 0.946000 9 0.104000 0.878000 10 0.216000 0.874000 11 0.302000 0.866000 12 0.410000 0.870000 13 0.520000 0.868000 14 0.614000 0.860000 15 0.700000 0.864000 16 0.804000 0.866000 17 0.102000 0.802000 18 0.210000 0.790000 19 0.296000 0.792000 20 0.410000 0.786000 21 0.512000 0.782000 22 0.614000 0.776000 23 0.700000 0.772000 24 0.804000 0.774000 25 0.840000E-01 0.718000 26 0.194000 0.698000 27 0.300000 0.696000 28 0.404000 0.700000 29 0.508000 0.698000 30 0.614000 0.696000 31 0.706000 0.692000 32 0.802000 0.688000 33 0.860000E-01 0.620000 34 0.192000 0.622000 35 0.294000 0.624000 36 0.404000 0.616000 37 0.506000 0.610000 38 0.604000 0.606000 39 0.702000 0.590000 40 0.792000 0.588000 41 0.880000E-01 0.508000 42 0.180000 0.528000 43 0.288000 0.522000 44 0.402000 0.518000 45 0.502000 0.510000 46 0.604000 0.512000 47 0.700000 0.490000 48 0.792000 0.484000 49 0.760000E-01 0.430000 50 0.178000 0.422000 51 0.286000 0.414000 52 0.390000 0.414000 53 0.498000 0.402000 54 0.596000 0.404000 55 0.698000 0.392000 56 0.794000 0.394000 57 0.700000E-01 0.330000 58 0.178000 0.322000 59 0.282000 0.304000 60 0.390000 0.308000 61 0.500000 0.298000 62 0.594000 0.294000 63 0.694000 0.286000 64 0.792000 0.292000 The graph: 1 0000000000100000010000000000000000000000000000000000000000000000 2 0000000000010000101000000000000000000000000000000000000000000000 3 0000000010001000010100000000000000000000000000000000000000000000 4 0000000001000100001010000000000000000000000000000000000000000000 5 0000000000100010000101000000000000000000000000000000000000000000 6 0000000000010001000010100000000000000000000000000000000000000000 7 0000000000001000000001010000000000000000000000000000000000000000 8 0000000000000100000000100000000000000000000000000000000000000000 9 0010000000000000001000000100000000000000000000000000000000000000 10 0001000000000000000100001010000000000000000000000000000000000000 11 1000100000000000100010000101000000000000000000000000000000000000 12 0100010000000000010001000010100000000000000000000000000000000000 13 0010001000000000001000100001010000000000000000000000000000000000 14 0001000100000000000100010000101000000000000000000000000000000000 15 0000100000000000000010000000010100000000000000000000000000000000 16 0000010000000000000001000000001000000000000000000000000000000000 17 0100000000100000000000000010000001000000000000000000000000000000 18 1010000000010000000000000001000010100000000000000000000000000000 19 0101000010001000000000001000100001010000000000000000000000000000 20 0010100001000100000000000100010000101000000000000000000000000000 21 0001010000100010000000000010001000010100000000000000000000000000 22 0000101000010001000000000001000100001010000000000000000000000000 23 0000010100001000000000000000100000000101000000000000000000000000 24 0000001000000100000000000000010000000010000000000000000000000000 25 0000000001000000001000000000000000100000010000000000000000000000 26 0000000010100000000100000000000000010000101000000000000000000000 27 0000000001010000100010000000000010001000010100000000000000000000 28 0000000000101000010001000000000001000100001010000000000000000000 29 0000000000010100001000100000000000100010000101000000000000000000 30 0000000000001010000100010000000000010001000010100000000000000000 31 0000000000000101000010000000000000001000000001010000000000000000 32 0000000000000010000001000000000000000100000000100000000000000000 33 0000000000000000010000000010000000000000001000000100000000000000 34 0000000000000000101000000001000000000000000100001010000000000000 35 0000000000000000010100001000100000000000100010000101000000000000 36 0000000000000000001010000100010000000000010001000010100000000000 37 0000000000000000000101000010001000000000001000100001010000000000 38 0000000000000000000010100001000100000000000100010000101000000000 39 0000000000000000000001010000100000000000000010000000010100000000 40 0000000000000000000000100000010000000000000001000000001000000000 41 0000000000000000000000000100000000100000000000000010000001000000 42 0000000000000000000000001010000000010000000000000001000010100000 43 0000000000000000000000000101000010001000000000001000100001010000 44 0000000000000000000000000010100001000100000000000100010000101000 45 0000000000000000000000000001010000100010000000000010001000010100 46 0000000000000000000000000000101000010001000000000001000100001010 47 0000000000000000000000000000010100001000000000000000100000000101 48 0000000000000000000000000000001000000100000000000000010000000010 49 0000000000000000000000000000000001000000001000000000000000100000 50 0000000000000000000000000000000010100000000100000000000000010000 51 0000000000000000000000000000000001010000100010000000000010001000 52 0000000000000000000000000000000000101000010001000000000001000100 53 0000000000000000000000000000000000010100001000100000000000100010 54 0000000000000000000000000000000000001010000100010000000000010001 55 0000000000000000000000000000000000000101000010000000000000001000 56 0000000000000000000000000000000000000010000001000000000000000100 57 0000000000000000000000000000000000000000010000000010000000000000 58 0000000000000000000000000000000000000000101000000001000000000000 59 0000000000000000000000000000000000000000010100001000100000000000 60 0000000000000000000000000000000000000000001010000100010000000000 61 0000000000000000000000000000000000000000000101000010001000000000 62 0000000000000000000000000000000000000000000010100001000100000000 63 0000000000000000000000000000000000000000000001010000100000000000 64 0000000000000000000000000000000000000000000000100000010000000000 GRAPH_ARC_TO_PS The data was written to the file: knightstour.eps network_flow_max_test(): network_flow_max() finds the maximum flow on a network. The source is node 1 The sink is node 6 Endpoint array: 1 2 1 3 2 3 2 4 2 5 3 4 3 5 4 5 4 6 5 6 2 1 3 1 3 2 4 2 5 2 4 3 5 3 5 4 6 4 6 5 Input edge capacity array: 3 0 7 0 2 0 5 0 4 0 1 0 4 0 2 0 8 0 3 0 Reordered endpoint array: 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 2 3 1 3 4 5 1 2 4 5 2 3 5 6 2 3 4 6 4 5 Output edge capacity/flow array: 3 7 0 2 5 4 0 0 1 4 0 0 2 8 0 0 0 3 0 0 3 4 -3 0 3 0 -4 0 1 3 -3 -1 0 4 0 -3 0 3 -4 -3 Minimal node cut vector: 1 1 2 0 3 1 4 0 5 1 6 0 Nodal flow vector: 1 7 2 3 3 4 4 4 5 3 6 7 node_relax_test(): node_relax() smooths a surface. Old coordinates 1 0.00000 0.00000 0.00000 2 1.00000 0.00000 0.00000 3 1.00000 1.00000 0.00000 4 0.00000 1.00000 0.00000 5 0.00000 0.00000 1.00000 6 1.00000 0.00000 1.00000 7 1.00000 1.00000 1.00000 8 0.00000 1.00000 1.00000 After 1 step 1 0.333333 0.333333 0.333333 2 0.666667 0.333333 0.333333 3 0.666667 0.666667 0.333333 4 0.333333 0.666667 0.333333 5 0.333333 0.333333 0.666667 6 0.666667 0.333333 0.666667 7 0.666667 0.666667 0.666667 8 0.333333 0.666667 0.666667 After 2 steps 1 0.444444 0.444444 0.444444 2 0.555556 0.444444 0.444444 3 0.555556 0.555556 0.444444 4 0.444444 0.555556 0.444444 5 0.444444 0.444444 0.555556 6 0.555556 0.444444 0.555556 7 0.555556 0.555556 0.555556 8 0.444444 0.555556 0.555556 After 3 steps 1 0.481481 0.481481 0.481481 2 0.518519 0.481481 0.481481 3 0.518519 0.518519 0.481481 4 0.481481 0.518519 0.481481 5 0.481481 0.481481 0.518519 6 0.518519 0.481481 0.518519 7 0.518519 0.518519 0.518519 8 0.481481 0.518519 0.518519 perm_inc_test() perm_inc() increments a permutation. 1 1 2 3 4 2 1 2 4 3 3 1 3 2 4 4 1 3 4 2 5 1 4 2 3 6 1 4 3 2 7 2 1 3 4 8 2 1 4 3 9 2 3 1 4 10 2 3 4 1 11 2 4 1 3 12 2 4 3 1 13 3 1 2 4 14 3 1 4 2 15 3 2 1 4 16 3 2 4 1 17 3 4 1 2 18 3 4 2 1 19 4 1 2 3 20 4 1 3 2 21 4 2 1 3 22 4 2 3 1 23 4 3 1 2 24 4 3 2 1 poly_to_tri_test(): poly_to_tri() replaces a polygonal mesh with a triangular one. Number of faces = 4 Faces and number of vertices: 1 4 2 3 3 5 4 4 Face Vertices 1 1 3 5 7 2 2 3 9 3 3 7 8 23 2 4 4 7 8 23 Number of faces = 8 Faces and number of vertices: 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 Face Vertices 1 1 3 5 2 1 5 7 3 2 3 9 4 3 7 8 5 3 8 23 6 3 23 2 7 4 7 8 8 4 8 23 TEST0695 VLA_TO_GRAPH_ARC reads a VLA file and converts it to a graph defined by an arc list. SHAPE_3D_NODES_TO_PS writes the nodes to a PostScript file. VLA_TO_GRAPH_ARC - Note: The graph was read properly. Number of nodes = 135 Number of edges = 389 SHAPE_3D_NODES_TO_PS The data was written to the file: fish_nodes.ps TEST0696 VLA_TO_GRAPH_ARC reads a VLA file and converts it to a graph defined by an arc list. SHAPE_3D_EDGES_TO_PS writes the edges to a PostScript file. VLA_TO_GRAPH_ARC - Note: The graph was read properly. Number of nodes = 135 Number of edges = 389 Sort the edges: Determine the faces: The faces were determined. Number of faces found was 259 Euler predicted 256 SHAPE_3D_EDGES_TO_PS The data was written to the file: fish_edges.ps TEST0697 VLA_TO_GRAPH_ARC reads a VLA file and converts it to a graph defined by an arc list. SHAPE_3D_FACES_TO_PS writes the faces to a PostScript file. VLA_TO_GRAPH_ARC - Note: The graph was read properly. Number of nodes = 135 Number of edges = 389 Number of faces found was 259 Euler predicted 256 SHAPE_3D_EDGES_TO_PS The data was written to the file: fish_faces.ps sort_heap_external_test(): sort_heap_external() sorts objects externally. Before sorting: 1 20 2 19 3 5 4 17 5 10 6 18 7 7 8 12 9 15 10 15 11 3 12 20 13 5 14 6 15 8 16 10 17 15 18 9 19 1 20 5 After sorting: 1 1 2 3 3 5 4 5 5 5 6 6 7 7 8 8 9 9 10 10 11 10 12 12 13 15 14 15 15 15 16 17 17 18 18 19 19 20 20 20 span_forest_test(): span_forest() constructs a spanning forest for a graph. Initial end point array: 2 4 1 7 5 2 6 2 3 4 3 7 9 11 8 5 10 8 8 11 Reordered endpoint array: 1 2 8 2 4 4 6 2 3 7 9 8 5 3 11 7 10 5 8 11 Number of connected components = 7 Node, Component 1 1 2 2 3 2 4 3 5 2 6 4 7 3 8 2 9 1 10 4 11 3 12 5 13 6 14 7 span_tree_next_test(): span_tree_next() constructs spanning trees of a graph using a backtrack search. Node1 Node2 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5 Edges in spanning tree: 1 4 8 9 10 2 4 7 9 10 3 4 7 8 10 4 4 7 8 9 5 4 6 9 10 6 4 6 8 10 7 4 6 8 9 8 4 6 7 10 9 4 6 7 9 10 4 6 7 8 11 4 5 9 10 12 4 5 8 10 13 4 5 8 9 14 4 5 7 10 15 4 5 7 9 16 4 5 7 8 17 4 5 6 10 18 4 5 6 9 19 4 5 6 7 20 3 8 9 10 21 3 7 9 10 22 3 7 8 10 23 3 7 8 9 24 3 6 9 10 25 3 6 8 10 26 3 6 8 9 27 3 6 7 10 28 3 6 7 9 29 3 6 7 8 30 3 5 9 10 31 3 5 8 10 32 3 5 8 9 33 3 5 7 10 34 3 5 7 8 35 3 5 6 10 36 3 5 6 9 37 3 5 6 8 38 3 5 6 7 39 3 4 7 9 40 3 4 7 8 41 3 4 6 9 42 3 4 6 8 43 3 4 5 9 44 3 4 5 8 45 3 4 5 7 46 3 4 5 6 47 2 7 9 10 48 2 7 8 10 49 2 7 8 9 50 2 6 9 10 51 2 6 8 10 52 2 6 8 9 53 2 6 7 9 54 2 6 7 8 55 2 5 9 10 56 2 5 8 10 57 2 5 8 9 58 2 5 7 10 59 2 5 7 9 60 2 5 7 8 61 2 5 6 10 62 2 5 6 9 63 2 5 6 8 64 2 5 6 7 65 2 4 7 10 66 2 4 7 8 67 2 4 6 10 68 2 4 6 8 69 2 4 6 7 70 2 4 5 10 71 2 4 5 8 72 2 4 5 6 73 2 3 7 10 74 2 3 7 9 75 2 3 6 10 76 2 3 6 9 77 2 3 6 7 78 2 3 5 10 79 2 3 5 9 80 2 3 5 7 81 2 3 4 7 82 2 3 4 6 83 2 3 4 5 84 1 7 9 10 85 1 7 8 10 86 1 7 8 9 87 1 6 9 10 88 1 6 8 10 89 1 6 7 9 90 1 6 7 8 91 1 5 8 9 92 1 5 7 10 93 1 5 7 8 94 1 5 6 10 95 1 5 6 9 96 1 5 6 7 97 1 4 9 10 98 1 4 8 10 99 1 4 8 9 100 1 4 6 9 101 1 4 6 8 102 1 4 5 10 103 1 4 5 8 104 1 4 5 6 105 1 3 9 10 106 1 3 8 10 107 1 3 8 9 108 1 3 7 9 109 1 3 7 8 110 1 3 5 10 111 1 3 5 9 112 1 3 5 7 113 1 3 4 9 114 1 3 4 8 115 1 3 4 5 116 1 2 9 10 117 1 2 8 10 118 1 2 8 9 119 1 2 7 10 120 1 2 7 8 121 1 2 6 10 122 1 2 6 9 123 1 2 6 7 124 1 2 4 10 125 1 2 4 8 126 1 2 4 6 127 1 2 3 10 128 1 2 3 9 129 1 2 3 7 130 1 2 3 4 Number of spanning trees found was 130 graph_theory_test(): Normal end of execution. 12 March 2023 9:36:33.926 AM