share/graphs/rtest_graphs.mac

   1 (kill(all), load(graphs), 0);
   2 0;
   3
   4 /* a helper macro to capture output to a string ("print to string") */
   5 (p2s([L])::=buildq([L, f: gensym()],
   6     block([f: make_string_output_stream()],
   7       with_stdout(f, splice(L)),
   8       get_output_stream_string(f))), 'done);
   9 'done$
  10
  11 p2s(print_graph(create_graph([1,2,3], [[1,2], [2,3], [1,3]])));
  12 "
  13 Graph on 3 vertices with 3 edges.
  14 Adjacencies:
  15   1 :  3  2
  16   2 :  3  1
  17   3 :  1  2
  18 "$
  19
  20 p2s(print_graph(create_graph(
  21                   [1,2,3,4],
  22                   [
  23                    [1,3], [1,4],
  24                    [2,3], [2,4]
  25                   ],
  26                   'directed = true)));
  27 "
  28 Digraph on 4 vertices with 4 arcs.
  29 Adjacencies:
  30   1 :  4  3
  31   2 :  4  3
  32   3 :
  33   4 :
  34 "$
  35
  36 p2s(print_graph(circulant_graph(10, [1, 3])));
  37 "
  38 Graph on 10 vertices with 20 edges.
  39 Adjacencies:
  40   9 :  2  6  0  8
  41   8 :  1  5  9  7
  42   7 :  0  4  8  6
  43   6 :  9  3  7  5
  44   5 :  8  2  6  4
  45   4 :  7  1  5  3
  46   3 :  6  0  4  2
  47   2 :  9  5  3  1
  48   1 :  8  4  2  0
  49   0 :  7  3  9  1
  50 "$
  51
  52 (g:create_graph([1,2,3,4,5],[[1,2],[2,3],[1,3],[4,5]]), 0);
  53 0;
  54
  55 vertices(g);
  56 [1,2,3,4,5];
  57
  58 edges(g);
  59 [[4,5],[1,3],[2,3],[1,2]];
  60
  61 neighbors(4,g);
  62 [5];
  63
  64 neighbors(1,g);
  65 [3,2];
  66
  67 is_connected(g);
  68 false;
  69
  70 connected_components(g);
  71 [[5,4],[3,2,1]];
  72
  73 vertex_distance(1,5,g);
  74 inf;
  75
  76 (g:create_graph([1,2,3,4,5],[[1,2],[2,3],[1,3],[3,4],[4,5]]), 0);
  77 0;
  78
  79 is_connected(g);
  80 true;
  81
  82 is_biconnected(g);
  83 false;
  84
  85 biconnected_components(g);
  86 [[1,2,3],[3,4],[4,5]];
  87
  88 vertex_distance(1,5,g);
  89 3;
  90
  91 shortest_path(1,5,g);
  92 [1,3,4,5];
  93
  94 is_connected(empty_graph(1));
  95 true;
  96
  97 is_connected(empty_graph(0));
  98 true;
  99
 100 is_connected(complete_graph(4));
 101 true;
 102
 103 max_clique(complete_graph(5));
 104 [0,1,2,3,4];
 105
 106 max_clique(empty_graph(5));
 107 [0];
 108
 109 max_clique(empty_graph(0));
 110 [];
 111
 112 is_bipartite(flower_snark(4));
 113 true;
 114
 115 chromatic_number(flower_snark(4));
 116 2;
 117
 118 chromatic_index(flower_snark(4));
 119 3;
 120
 121 is_bipartite(flower_snark(5));
 122 false;
 123
 124 chromatic_number(flower_snark(5));
 125 3;
 126
 127 chromatic_index(flower_snark(5));
 128 4;
 129
 130 is_bipartite(empty_graph(1));
 131 true;
 132
 133 is_bipartite(empty_graph(0));
 134 true;
 135
 136 is_bipartite(complete_graph(0));
 137 true;
 138
 139 chromatic_number(empty_graph(0));
 140 0;
 141
 142 chromatic_number(empty_graph(1));
 143 1;
 144
 145 chromatic_number(empty_graph(2));
 146 1;
 147
 148 chromatic_number(complete_graph(2));
 149 2;
 150
 151 chromatic_index(empty_graph(3));
 152 0;
 153
 154 chromatic_index(cycle_graph(3));
 155 3;
 156
 157 chromatic_index(cycle_graph(4));
 158 2;
 159
 160 girth(flower_snark(4));
 161 4;
 162
 163 girth(flower_snark(5));
 164 5;
 165
 166 girth(flower_snark(6));
 167 6;
 168
 169 girth(flower_snark(7));
 170 6;
 171
 172 odd_girth(flower_snark(4));
 173 inf;
 174
 175 odd_girth(flower_snark(5));
 176 5;
 177
 178 odd_girth(flower_snark(6));
 179 inf;
 180
 181 odd_girth(flower_snark(7));
 182 7;
 183
 184 is_isomorphic(empty_graph(0), empty_graph(0));
 185 true;
 186
 187 is_isomorphic(empty_digraph(0), empty_digraph(0));
 188 true;
 189
 190 is_isomorphic(empty_graph(1), empty_graph(1));
 191 true;
 192
 193 is_isomorphic(graph_product(path_graph(3), path_graph(5)), graph_product(path_graph(5), path_graph(3)));
 194 true;
 195
 196 is_isomorphic(graph_union(cycle_graph(3), cycle_graph(3)), cycle_graph(6));
 197 false;
 198
 199 is_isomorphic(petersen_graph(), complement_graph(line_graph(complete_graph(5))));
 200 true;
 201
 202 is_planar(empty_graph(0));
 203 true;
 204
 205 is_planar(empty_graph(2));
 206 true;
 207
 208 is_planar(dodecahedron_graph());
 209 true;
 210
 211 is_planar(flower_snark(5));
 212 false;
 213
 214 is_planar(complete_graph(4));
 215 true;
 216
 217 is_planar(complete_graph(5));
 218 false;
 219
 220 is_planar(complete_graph(6));
 221 false;
 222
 223 is_planar(complete_bipartite_graph(3,3));
 224 false;
 225
 226 is_planar(complete_bipartite_graph(2,4));
 227 true;
 228
 229 is_tree(empty_graph(0));
 230 false;
 231
 232 is_tree(empty_graph(1));
 233 true;
 234
 235 is_tree(empty_graph(2));
 236 false;
 237
 238 is_tree(path_graph(4));
 239 true;
 240
 241 is_tree(cycle_graph(4));
 242 false;
 243
 244 (g:graph_union(cycle_graph(3), cycle_graph(4)), 0);
 245 0;
 246
 247 vertex_connectivity(g);
 248 0;
 249
 250 edge_connectivity(g);
 251 0;
 252
 253 (add_edge([0,3], g), 0);
 254 0;
 255
 256 vertex_connectivity(g);
 257 1;
 258
 259 edge_connectivity(g);
 260 1;
 261
 262 min_edge_cut(g);
 263 [[0,3]];
 264
 265 (add_edge([0,4], g), 0);
 266 0;
 267
 268 vertex_connectivity(g);
 269 1;
 270
 271 min_vertex_cut(g);
 272 [0];
 273
 274 edge_connectivity(g);
 275 2;
 276
 277 (g: graph_union(complete_graph(5), complete_graph(5)), connect_vertices([5,6],[2,3,4], g), 0);
 278 0;
 279
 280 vertex_connectivity(g);
 281 2;
 282
 283 vertex_connectivity(path_graph(2));
 284 inf;
 285
 286 edge_connectivity(path_graph(2));
 287 1;
 288
 289 vertex_connectivity(empty_graph(1));
 290 inf;
 291
 292 edge_connectivity(empty_graph(1));
 293 inf;
 294
 295 (g:graph6_decode("H|twgsN"),0);
 296 0;
 297
 298 is_planar(g);
 299 true;
 300
 301 vertex_connectivity(g);
 302 3;
 303
 304 edge_connectivity(g);
 305 4;
 306
 307 min_vertex_cut(g);
 308 [3,4,5];
 309
 310 (g:create_graph(
 311   [1,2,3,4,5],
 312   [
 313    [1,2], [2,5],
 314    [5,3],
 315    [5,4], [3,4], [1,3]
 316   ],
 317   directed=true),
 318 0);
 319 0;
 320
 321 topological_sort(g);
 322 [1,2,5,3,4];
 323
 324 topological_sort(path_digraph(3));
 325 [0,1,2];
 326
 327 topological_sort(cycle_digraph(3));
 328 [];
 329
 330 /* Check for edge weight copying on digraphs (Bug 2541) */
 331 block([dg: cycle_digraph(3), dg2],
 332       set_edge_weight([0,1], 100, dg),
 333       dg2: copy_graph(dg),
 334       is (get_edge_weight([0,1], dg2) = get_edge_weight([0,1], dg)));
 335 true;
 336
 337 edge_coloring(cycle_graph(4));
 338 [2,[[[0,1],2],[[1,2],1],[[2,3],2],[[0,3],1]]]$
 339
 340 edge_coloring(petersen_graph());
 341 [4,
 342  [[[0,5],3],[[5,7],1],[[0,1],1],[[1,6],2],[[6,8],1],[[1,2],3],[[2,7],4],
 343   [[7,9],2],[[2,3],2],[[3,8],3],[[5,8],2],[[3,4],1],[[4,9],4],[[6,9],3],
 344   [[0,4],2]]]$
 345
 346 /* larger example which triggers ADJUST-ARRAY
 347  * this example is to ensure that result of shortest_weighted_path doesn't change
 348  */
 349 block ([g200_20 : petersen_graph(200, 20)],
 350        for e in edges(g200_20) do set_edge_weight(e, e[1]+e[2], g200_20),
 351        shortest_weighted_path(0, 100, g200_20));
 352 [3100, [0, 200, 220, 240, 260, 280, 300, 100]];
 353
 354 /* test vertex labels */
 355
 356 (vv: [[17, "foo"], [29, "foo"], [1729, "bar"], 2, 4, 6, 8],
 357  G: create_graph (vv, []),
 358  get_unique_vertex_by_label ("bar", G));
 359 1729;
 360
 361 get_unique_vertex_by_label ("baz", G);
 362 false;
 363
 364 errcatch (get_unique_vertex_by_label ("foo", G));
 365 [];
 366
 367 get_all_vertices_by_label ("foo", G);
 368 [17, 29];
 369
 370 (for v in [2, 17, 29, 4, 6] do set_vertex_label (v, "baz", G),
 371  get_all_vertices_by_label ("baz", G));
 372 [2, 4, 6, 17, 29];
 373
 374 makelist (get_vertex_label (v, G), v, [8, 2, 4, 6, 1729, 17, 29]);
 375 [false, "baz", "baz", "baz", "bar", "baz", "baz"];
 376