doc/info/graphs.texi

   1 @menu
   2 * Introduction to graphs::
   3 * Functions and Variables for graphs::
   4 @end menu
   5
   6 @node Introduction to graphs, Functions and Variables for graphs, graphs-pkg, graphs-pkg
   7 @section Introduction to graphs
   8
   9 The @code{graphs} package provides graph and digraph data structure for
  10 Maxima. Graphs and digraphs are simple (have no multiple edges nor
  11 loops), although digraphs can have a directed edge from @var{u} to
  12 @var{v} and a directed edge from @var{v} to @var{u}.
  13
  14 Internally graphs are represented by adjacency lists and implemented as
  15 a lisp structures. Vertices are identified by their ids (an id is an
  16 integer). Edges/arcs are represented by lists of length 2. Labels can be
  17 assigned to vertices of graphs/digraphs and weights can be assigned to
  18 edges/arcs of graphs/digraphs.
  19
  20 There is a @code{draw_graph} function for drawing graphs. Graphs are
  21 drawn using a force based vertex positioning
  22 algorithm. @code{draw_graph} can also use graphviz programs available
  23 from @url{https://www.graphviz.org}. @code{draw_graph} is based on the maxima
  24 @code{draw} package.
  25
  26 To use the @code{graphs} package, first load it with @code{load("graphs")}.
  27
  28 @opencatbox{Categories:}
  29 @category{Share packages}
  30 @category{Package graphs}
  31 @closecatbox
  32
  33 @node Functions and Variables for graphs, , Introduction to graphs, graphs-pkg
  34 @section Functions and Variables for graphs
  35
  36 @subsection Building graphs
  37
  38 @anchor{create_graph}
  39 @deffn {Function} create_graph @
  40 @fname{create_graph} (@var{v_list}, @var{e_list}) @
  41 @fname{create_graph} (@var{n}, @var{e_list}) @
  42 @fname{create_graph} (@var{v_list}, @var{e_list}, @var{directed})
  43
  44 Creates a new graph on the set of vertices @var{v_list} and with edges @var{e_list}.
  45
  46 @var{v_list} is a list of vertices (@code{[v1, v2,..., vn]}) or a
  47 list of vertices together with vertex labels (@code{[[v1,l1], [v2,l2],..., [vn,ln]]}).
  48
  49 @var{n} is the number of vertices. Vertices will be identified by integers from 0 to n-1.
  50
  51 @var{e_list} is a list of edges (@code{[e1, e2,..., em]}) or a list of
  52 edges together with edge-weights (@code{[[e1, w1], ..., [em, wm]]}).
  53
  54 If @var{directed} is not @code{false}, a directed graph will be returned.
  55
  56 Example 1: create a cycle on 3 vertices:
  57 @c ===beg===
  58 @c load ("graphs")$
  59 @c g : create_graph([1,2,3], [[1,2], [2,3], [1,3]])$
  60 @c print_graph(g)$
  61 @c ===end===
  62 @example
  63 (%i1) load ("graphs")$
  64 (%i2) g : create_graph([1,2,3], [[1,2], [2,3], [1,3]])$
  65 (%i3) print_graph(g)$
  66 Graph on 3 vertices with 3 edges.
  67 Adjacencies:
  68   3 :  1  2
  69   2 :  3  1
  70   1 :  3  2
  71 @end example
  72
  73 Example 2: create a cycle on 3 vertices with edge weights:
  74 @c ===beg===
  75 @c load ("graphs")$
  76 @c g : create_graph([1,2,3], [[[1,2], 1.0], [[2,3], 2.0],
  77 @c                           [[1,3], 3.0]])$
  78 @c print_graph(g)$
  79 @c ===end===
  80 @example
  81 (%i1) load ("graphs")$
  82 (%i2) g : create_graph([1,2,3], [[[1,2], 1.0], [[2,3], 2.0],
  83                           [[1,3], 3.0]])$
  84 (%i3) print_graph(g)$
  85 Graph on 3 vertices with 3 edges.
  86 Adjacencies:
  87   3 :  1  2
  88   2 :  3  1
  89   1 :  3  2
  90 @end example
  91
  92 Example 3: create a directed graph:
  93 @c ===beg===
  94 @c load ("graphs")$
  95 @c d : create_graph(
  96 @c         [1,2,3,4],
  97 @c         [
  98 @c          [1,3], [1,4],
  99 @c          [2,3], [2,4]
 100 @c         ],
 101 @c         'directed = true)$
 102 @c print_graph(d)$
 103 @c ===end===
 104 @example
 105 (%i1) load ("graphs")$
 106 (%i2) d : create_graph(
 107         [1,2,3,4],
 108         [
 109          [1,3], [1,4],
 110          [2,3], [2,4]
 111         ],
 112         'directed = true)$
 113 (%i3) print_graph(d)$
 114 Digraph on 4 vertices with 4 arcs.
 115 Adjacencies:
 116   4 :
 117   3 :
 118   2 :  4  3
 119   1 :  4  3
 120 @end example
 121
 122 @opencatbox{Categories:}
 123 @category{Package graphs}
 124 @closecatbox
 125 @end deffn
 126
 127 @anchor{copy_graph}
 128 @deffn {Function} copy_graph (@var{g})
 129 Returns a copy of the graph @var{g}.
 130
 131 @opencatbox{Categories:}
 132 @category{Package graphs}
 133 @category{Package graphs - constructions}
 134 @closecatbox
 135 @end deffn
 136
 137 @anchor{circulant_graph}
 138 @deffn {Function} circulant_graph (@var{n}, @var{d})
 139 Returns the circulant graph with parameters @var{n} and @var{d}.
 140
 141 Example:
 142 @c ===beg===
 143 @c load ("graphs")$
 144 @c g : circulant_graph(10, [1,3])$
 145 @c print_graph(g)$
 146 @c ===end===
 147 @example
 148 (%i1) load ("graphs")$
 149 (%i2) g : circulant_graph(10, [1,3])$
 150 (%i3) print_graph(g)$
 151 Graph on 10 vertices with 20 edges.
 152 Adjacencies:
 153   9 :  2  6  0  8
 154   8 :  1  5  9  7
 155   7 :  0  4  8  6
 156   6 :  9  3  7  5
 157   5 :  8  2  6  4
 158   4 :  7  1  5  3
 159   3 :  6  0  4  2
 160   2 :  9  5  3  1
 161   1 :  8  4  2  0
 162   0 :  7  3  9  1
 163 @end example
 164
 165 @opencatbox{Categories:}
 166 @category{Package graphs}
 167 @category{Package graphs - constructions}
 168 @closecatbox
 169 @end deffn
 170
 171 @anchor{clebsch_graph}
 172 @deffn {Function} clebsch_graph ()
 173 Returns the Clebsch graph.
 174
 175 @opencatbox{Categories:}
 176 @category{Package graphs}
 177 @category{Package graphs - constructions}
 178 @closecatbox
 179 @end deffn
 180
 181 @anchor{complement_graph}
 182 @deffn {Function} complement_graph (@var{g})
 183 Returns the complement of the graph @var{g}.
 184
 185 @opencatbox{Categories:}
 186 @category{Package graphs}
 187 @category{Package graphs - constructions}
 188 @closecatbox
 189 @end deffn
 190
 191 @anchor{complete_bipartite_graph}
 192 @deffn {Function} complete_bipartite_graph (@var{n}, @var{m})
 193 Returns the complete bipartite graph on @var{n+m} vertices.
 194
 195 @opencatbox{Categories:}
 196 @category{Package graphs}
 197 @category{Package graphs - constructions}
 198 @closecatbox
 199 @end deffn
 200
 201 @anchor{complete_graph}
 202 @deffn {Function} complete_graph (@var{n})
 203 Returns the complete graph on @var{n} vertices.
 204
 205 @opencatbox{Categories:}
 206 @category{Package graphs}
 207 @category{Package graphs - constructions}
 208 @closecatbox
 209 @end deffn
 210
 211 @anchor{cycle_digraph}
 212 @deffn {Function} cycle_digraph (@var{n})
 213 Returns the directed cycle on @var{n} vertices.
 214
 215 @opencatbox{Categories:}
 216 @category{Package graphs}
 217 @category{Package graphs - constructions}
 218 @closecatbox
 219 @end deffn
 220
 221 @anchor{cycle_graph}
 222 @deffn {Function} cycle_graph (@var{n})
 223 Returns the cycle on @var{n} vertices.
 224
 225 @opencatbox{Categories:}
 226 @category{Package graphs}
 227 @category{Package graphs - constructions}
 228 @closecatbox
 229 @end deffn
 230
 231 @anchor{cuboctahedron_graph}
 232 @deffn {Function} cuboctahedron_graph (@var{n})
 233 Returns the cuboctahedron graph.
 234
 235 @opencatbox{Categories:}
 236 @category{Package graphs}
 237 @category{Package graphs - constructions}
 238 @closecatbox
 239 @end deffn
 240
 241 @anchor{cube_graph}
 242 @deffn {Function} cube_graph (@var{n})
 243 Returns the @var{n}-dimensional cube.
 244
 245 @opencatbox{Categories:}
 246 @category{Package graphs}
 247 @category{Package graphs - constructions}
 248 @closecatbox
 249 @end deffn
 250
 251 @anchor{dodecahedron_graph}
 252 @deffn {Function} dodecahedron_graph ()
 253 Returns the dodecahedron graph.
 254
 255 @opencatbox{Categories:}
 256 @category{Package graphs}
 257 @category{Package graphs - constructions}
 258 @closecatbox
 259 @end deffn
 260
 261 @anchor{empty_graph}
 262 @deffn {Function} empty_graph (@var{n})
 263 Returns the empty graph on @var{n} vertices.
 264
 265 @opencatbox{Categories:}
 266 @category{Package graphs}
 267 @category{Package graphs - constructions}
 268 @closecatbox
 269 @end deffn
 270
 271 @anchor{flower_snark}
 272 @deffn {Function} flower_snark (@var{n})
 273 Returns the flower graph on @var{4n} vertices.
 274
 275 Example:
 276 @c ===beg===
 277 @c load ("graphs")$
 278 @c f5 : flower_snark(5)$
 279 @c chromatic_index(f5);
 280 @c ===end===
 281 @example
 282 (%i1) load ("graphs")$
 283 (%i2) f5 : flower_snark(5)$
 284 (%i3) chromatic_index(f5);
 285 (%o3)                           4
 286 @end example
 287
 288 @opencatbox{Categories:}
 289 @category{Package graphs}
 290 @category{Package graphs - constructions}
 291 @closecatbox
 292 @end deffn
 293
 294 @anchor{from_adjacency_matrix}
 295 @deffn {Function} from_adjacency_matrix (@var{A})
 296 Returns the graph represented by its adjacency matrix @var{A}.
 297
 298 @opencatbox{Categories:}
 299 @category{Package graphs}
 300 @category{Package graphs - constructions}
 301 @closecatbox
 302 @end deffn
 303
 304 @anchor{frucht_graph}
 305 @deffn {Function} frucht_graph ()
 306 Returns the Frucht graph.
 307
 308 @opencatbox{Categories:}
 309 @category{Package graphs}
 310 @category{Package graphs - constructions}
 311 @closecatbox
 312 @end deffn
 313
 314 @anchor{graph_product}
 315 @deffn {Function} graph_product (@var{g1}, @var{g1})
 316 Returns the direct product of graphs @var{g1} and @var{g2}.
 317
 318 Example:
 319 @c ===beg===
 320 @c load ("graphs")$
 321 @c grid : graph_product(path_graph(3), path_graph(4))$
 322 @c draw_graph(grid)$
 323 @c ===end===
 324 @example
 325 (%i1) load ("graphs")$
 326 (%i2) grid : graph_product(path_graph(3), path_graph(4))$
 327 (%i3) draw_graph(grid)$
 328 @end example
 329
 330 @opencatbox{Categories:}
 331 @category{Package graphs}
 332 @category{Package graphs - constructions}
 333 @closecatbox
 334 @end deffn
 335
 336 @ifhtml
 337 @image{figures/graphs01,6cm}
 338 @end ifhtml
 339
 340 @anchor{graph_union}
 341 @deffn {Function} graph_union (@var{g1}, @var{g1})
 342 Returns the union (sum) of graphs @var{g1} and @var{g2}.
 343
 344 @opencatbox{Categories:}
 345 @category{Package graphs}
 346 @category{Package graphs - constructions}
 347 @closecatbox
 348 @end deffn
 349
 350 @anchor{grid_graph}
 351 @deffn {Function} grid_graph (@var{n}, @var{m})
 352 Returns the @var{n x m} grid.
 353
 354 @opencatbox{Categories:}
 355 @category{Package graphs}
 356 @category{Package graphs - constructions}
 357 @closecatbox
 358 @end deffn
 359
 360 @anchor{great_rhombicosidodecahedron_graph}
 361 @deffn {Function} great_rhombicosidodecahedron_graph ()
 362 Returns the great rhombicosidodecahedron graph.
 363
 364 @opencatbox{Categories:}
 365 @category{Package graphs}
 366 @category{Package graphs - constructions}
 367 @closecatbox
 368 @end deffn
 369
 370 @anchor{great_rhombicuboctahedron_graph}
 371 @deffn {Function} great_rhombicuboctahedron_graph ()
 372 Returns the great rhombicuboctahedron graph.
 373
 374 @opencatbox{Categories:}
 375 @category{Package graphs}
 376 @category{Package graphs - constructions}
 377 @closecatbox
 378 @end deffn
 379
 380 @anchor{grotzch_graph}
 381 @deffn {Function} grotzch_graph ()
 382 Returns the Grotzch graph.
 383
 384 @opencatbox{Categories:}
 385 @category{Package graphs}
 386 @category{Package graphs - constructions}
 387 @closecatbox
 388 @end deffn
 389
 390 @anchor{heawood_graph}
 391 @deffn {Function} heawood_graph ()
 392 Returns the Heawood graph.
 393
 394 @opencatbox{Categories:}
 395 @category{Package graphs}
 396 @category{Package graphs - constructions}
 397 @closecatbox
 398 @end deffn
 399
 400 @anchor{icosahedron_graph}
 401 @deffn {Function} icosahedron_graph ()
 402 Returns the icosahedron graph.
 403
 404 @opencatbox{Categories:}
 405 @category{Package graphs}
 406 @category{Package graphs - constructions}
 407 @closecatbox
 408 @end deffn
 409
 410 @anchor{icosidodecahedron_graph}
 411 @deffn {Function} icosidodecahedron_graph ()
 412 Returns the icosidodecahedron graph.
 413
 414 @opencatbox{Categories:}
 415 @category{Package graphs}
 416 @category{Package graphs - constructions}
 417 @closecatbox
 418 @end deffn
 419
 420 @anchor{induced_subgraph}
 421 @deffn {Function} induced_subgraph (@var{V}, @var{g})
 422 Returns the graph induced on the subset @var{V} of vertices of the graph
 423 @var{g}.
 424
 425 Example:
 426 @c ===beg===
 427 @c load ("graphs")$
 428 @c p : petersen_graph()$
 429 @c V : [0,1,2,3,4]$
 430 @c g : induced_subgraph(V, p)$
 431 @c print_graph(g)$
 432 @c ===end===
 433 @example
 434 (%i1) load ("graphs")$
 435 (%i2) p : petersen_graph()$
 436 (%i3) V : [0,1,2,3,4]$
 437 (%i4) g : induced_subgraph(V, p)$
 438 (%i5) print_graph(g)$
 439 Graph on 5 vertices with 5 edges.
 440 Adjacencies:
 441   4 :  3  0
 442   3 :  2  4
 443   2 :  1  3
 444   1 :  0  2
 445   0 :  1  4
 446 @end example
 447
 448 @opencatbox{Categories:}
 449 @category{Package graphs}
 450 @category{Package graphs - constructions}
 451 @closecatbox
 452 @end deffn
 453
 454 @anchor{line_graph}
 455 @deffn {Function} line_graph (@var{g})
 456 Returns the line graph of the graph @var{g}.
 457
 458 @opencatbox{Categories:}
 459 @category{Package graphs}
 460 @category{Package graphs - constructions}
 461 @closecatbox
 462 @end deffn
 463
 464 @anchor{make_graph}
 465 @deffn {Function} make_graph @
 466 @fname{make_graph} (@var{vrt}, @var{f}) @
 467 @fname{make_graph} (@var{vrt}, @var{f}, @var{oriented})
 468
 469 Creates a graph using a predicate function @var{f}.
 470
 471 @var{vrt} is a list/set of vertices or an integer. If @var{vrt} is an
 472 integer, then vertices of the graph will be integers from 1 to
 473 @var{vrt}.
 474
 475 @var{f} is a predicate function. Two vertices @var{a} and @var{b} will
 476 be connected if @code{f(a,b)=true}.
 477
 478 If @var{directed} is not @var{false}, then the graph will be directed.
 479
 480 Example 1:
 481 @c ===beg===
 482 @c load("graphs")$
 483 @c g : make_graph(powerset({1,2,3,4,5}, 2), disjointp)$
 484 @c is_isomorphic(g, petersen_graph());
 485 @c get_vertex_label(1, g);
 486 @c ===end===
 487 @example
 488 (%i1) load("graphs")$
 489 (%i2) g : make_graph(powerset(@{1,2,3,4,5@}, 2), disjointp)$
 490 (%i3) is_isomorphic(g, petersen_graph());
 491 (%o3)                         true
 492 (%i4) get_vertex_label(1, g);
 493 (%o4)                        @{1, 2@}
 494 @end example
 495
 496 Example 2:
 497 @c ===beg===
 498 @c load("graphs")$
 499 @c f(i, j) := is (mod(j, i)=0)$
 500 @c g : make_graph(20, f, directed=true)$
 501 @c out_neighbors(4, g);
 502 @c in_neighbors(18, g);
 503 @c ===end===
 504 @example
 505 (%i1) load("graphs")$
 506 (%i2) f(i, j) := is (mod(j, i)=0)$
 507 (%i3) g : make_graph(20, f, directed=true)$
 508 (%i4) out_neighbors(4, g);
 509 (%o4)                    [8, 12, 16, 20]
 510 (%i5) in_neighbors(18, g);
 511 (%o5)                    [1, 2, 3, 6, 9]
 512 @end example
 513
 514 @opencatbox{Categories:}
 515 @category{Package graphs}
 516 @category{Package graphs - constructions}
 517 @closecatbox
 518 @end deffn
 519
 520 @anchor{mycielski_graph}
 521 @deffn {Function} mycielski_graph (@var{g})
 522 Returns the mycielskian graph of the graph @var{g}.
 523
 524 @opencatbox{Categories:}
 525 @category{Package graphs}
 526 @category{Package graphs - constructions}
 527 @closecatbox
 528 @end deffn
 529
 530 @anchor{new_graph}
 531 @deffn {Function} new_graph ()
 532 Returns the graph with no vertices and no edges.
 533
 534 @opencatbox{Categories:}
 535 @category{Package graphs}
 536 @category{Package graphs - constructions}
 537 @closecatbox
 538 @end deffn
 539
 540 @anchor{path_digraph}
 541 @deffn {Function} path_digraph (@var{n})
 542 Returns the directed path on @var{n} vertices.
 543
 544 @opencatbox{Categories:}
 545 @category{Package graphs}
 546 @category{Package graphs - constructions}
 547 @closecatbox
 548 @end deffn
 549
 550 @anchor{path_graph}
 551 @deffn {Function} path_graph (@var{n})
 552 Returns the path on @var{n} vertices.
 553
 554 @opencatbox{Categories:}
 555 @category{Package graphs}
 556 @category{Package graphs - constructions}
 557 @closecatbox
 558 @end deffn
 559
 560 @anchor{petersen_graph}
 561 @deffn {Function} petersen_graph @
 562 @fname{petersen_graph} () @
 563 @fname{petersen_graph} (@var{n}, @var{d})
 564
 565 Returns the petersen graph @var{P_@{n,d@}}. The default values for
 566 @var{n} and @var{d} are @code{n=5} and @code{d=2}.
 567
 568 @opencatbox{Categories:}
 569 @category{Package graphs}
 570 @category{Package graphs - constructions}
 571 @closecatbox
 572 @end deffn
 573
 574 @anchor{random_bipartite_graph}
 575 @deffn {Function} random_bipartite_graph (@var{a}, @var{b}, @var{p})
 576 Returns a random bipartite graph on @code{a+b} vertices. Each edge is
 577 present with probability @var{p}.
 578
 579 @opencatbox{Categories:}
 580 @category{Package graphs}
 581 @category{Package graphs - constructions}
 582 @closecatbox
 583 @end deffn
 584
 585 @anchor{random_digraph}
 586 @deffn {Function} random_digraph (@var{n}, @var{p})
 587 Returns a random directed graph on @var{n} vertices. Each arc is present
 588 with probability @var{p}.
 589
 590 @opencatbox{Categories:}
 591 @category{Package graphs}
 592 @category{Package graphs - constructions}
 593 @closecatbox
 594 @end deffn
 595
 596 @anchor{random_regular_graph}
 597 @deffn {Function} random_regular_graph @
 598 @fname{random_regular_graph} (@var{n}) @
 599 @fname{random_regular_graph} (@var{n}, @var{d})
 600
 601 Returns a random @var{d}-regular graph on @var{n} vertices. The default
 602 value for @var{d} is @code{d=3}.
 603
 604 @opencatbox{Categories:}
 605 @category{Package graphs}
 606 @category{Package graphs - constructions}
 607 @closecatbox
 608 @end deffn
 609
 610 @anchor{random_graph}
 611 @deffn {Function} random_graph (@var{n}, @var{p})
 612 Returns a random graph on @var{n} vertices. Each edge is present with
 613 probability @var{p}.
 614
 615 @opencatbox{Categories:}
 616 @category{Package graphs}
 617 @category{Package graphs - constructions}
 618 @closecatbox
 619 @end deffn
 620
 621 @anchor{random_graph1}
 622 @deffn {Function} random_graph1 (@var{n}, @var{m})
 623 Returns a random graph on @var{n} vertices and random @var{m} edges.
 624
 625 @opencatbox{Categories:}
 626 @category{Package graphs}
 627 @category{Package graphs - constructions}
 628 @closecatbox
 629 @end deffn
 630
 631 @anchor{random_network}
 632 @deffn {Function} random_network (@var{n}, @var{p}, @var{w})
 633 Returns a random network on @var{n} vertices. Each arc is present with
 634 probability @var{p} and has a weight in the range @code{[0,w]}. The
 635 function returns a list @code{[network, source, sink]}.
 636
 637 Example:
 638 @c ===beg===
 639 @c load ("graphs")$
 640 @c [net, s, t] : random_network(50, 0.2, 10.0);
 641 @c max_flow(net, s, t)$
 642 @c first(%);
 643 @c ===end===
 644 @example
 645 (%i1) load ("graphs")$
 646 (%i2) [net, s, t] : random_network(50, 0.2, 10.0);
 647 (%o2)                   [DIGRAPH, 50, 51]
 648 (%i3) max_flow(net, s, t)$
 649 (%i4) first(%);
 650 (%o4)                   27.65981397932507
 651 @end example
 652
 653 @opencatbox{Categories:}
 654 @category{Package graphs}
 655 @category{Package graphs - constructions}
 656 @closecatbox
 657 @end deffn
 658
 659 @anchor{random_tournament}
 660 @deffn {Function} random_tournament (@var{n})
 661 Returns a random tournament on @var{n} vertices.
 662
 663 @opencatbox{Categories:}
 664 @category{Package graphs}
 665 @category{Package graphs - constructions}
 666 @closecatbox
 667 @end deffn
 668
 669 @anchor{random_tree}
 670 @deffn {Function} random_tree (@var{n})
 671 Returns a random tree on @var{n} vertices.
 672
 673 @opencatbox{Categories:}
 674 @category{Package graphs}
 675 @category{Package graphs - constructions}
 676 @closecatbox
 677 @end deffn
 678
 679 @anchor{small_rhombicosidodecahedron_graph}
 680 @deffn {Function} small_rhombicosidodecahedron_graph ()
 681 Returns the small rhombicosidodecahedron graph.
 682
 683 @opencatbox{Categories:}
 684 @category{Package graphs}
 685 @category{Package graphs - constructions}
 686 @closecatbox
 687 @end deffn
 688
 689 @anchor{small_rhombicuboctahedron_graph}
 690 @deffn {Function} small_rhombicuboctahedron_graph ()
 691 Returns the small rhombicuboctahedron graph.
 692
 693 @opencatbox{Categories:}
 694 @category{Package graphs}
 695 @category{Package graphs - constructions}
 696 @closecatbox
 697 @end deffn
 698
 699 @anchor{snub_cube_graph}
 700 @deffn {Function} snub_cube_graph ()
 701 Returns the snub cube graph.
 702
 703 @opencatbox{Categories:}
 704 @category{Package graphs}
 705 @category{Package graphs - constructions}
 706 @closecatbox
 707 @end deffn
 708
 709 @anchor{snub_dodecahedron_graph}
 710 @deffn {Function} snub_dodecahedron_graph ()
 711 Returns the snub dodecahedron graph.
 712
 713 @opencatbox{Categories:}
 714 @category{Package graphs}
 715 @category{Package graphs - constructions}
 716 @closecatbox
 717 @end deffn
 718
 719 @anchor{truncated_cube_graph}
 720 @deffn {Function} truncated_cube_graph ()
 721 Returns the truncated cube graph.
 722
 723 @opencatbox{Categories:}
 724 @category{Package graphs}
 725 @category{Package graphs - constructions}
 726 @closecatbox
 727 @end deffn
 728
 729 @anchor{truncated_dodecahedron_graph}
 730 @deffn {Function} truncated_dodecahedron_graph ()
 731 Returns the truncated dodecahedron graph.
 732
 733 @opencatbox{Categories:}
 734 @category{Package graphs}
 735 @category{Package graphs - constructions}
 736 @closecatbox
 737 @end deffn
 738
 739
 740 @anchor{truncated_icosahedron_graph}
 741 @deffn {Function} truncated_icosahedron_graph ()
 742 Returns the truncated icosahedron graph.
 743
 744 @opencatbox{Categories:}
 745 @category{Package graphs}
 746 @category{Package graphs - constructions}
 747 @closecatbox
 748 @end deffn
 749
 750
 751 @anchor{truncated_tetrahedron_graph}
 752 @deffn {Function} truncated_tetrahedron_graph ()
 753 Returns the truncated tetrahedron graph.
 754
 755 @opencatbox{Categories:}
 756 @category{Package graphs}
 757 @category{Package graphs - constructions}
 758 @closecatbox
 759 @end deffn
 760
 761 @anchor{tutte_graph}
 762 @deffn {Function} tutte_graph ()
 763 Returns the Tutte graph.
 764
 765 @opencatbox{Categories:}
 766 @category{Package graphs}
 767 @category{Package graphs - constructions}
 768 @closecatbox
 769 @end deffn
 770
 771 @anchor{underlying_graph}
 772 @deffn {Function} underlying_graph (@var{g})
 773 Returns the underlying graph of the directed graph @var{g}.
 774
 775 @opencatbox{Categories:}
 776 @category{Package graphs}
 777 @category{Package graphs - constructions}
 778 @closecatbox
 779 @end deffn
 780
 781 @anchor{wheel_graph}
 782 @deffn {Function} wheel_graph (@var{n})
 783 Returns the wheel graph on @var{n+1} vertices.
 784
 785 @opencatbox{Categories:}
 786 @category{Package graphs}
 787 @category{Package graphs - constructions}
 788 @closecatbox
 789 @end deffn
 790
 791 @subsection Graph properties
 792
 793 @anchor{adjacency_matrix}
 794 @deffn {Function} adjacency_matrix (@var{gr})
 795 Returns the adjacency matrix of the graph @var{gr}.
 796
 797 Example:
 798 @c ===beg===
 799 @c load ("graphs")$
 800 @c c5 : cycle_graph(4)$
 801 @c adjacency_matrix(c5);
 802 @c ===end===
 803 @example
 804 (%i1) load ("graphs")$
 805 (%i2) c5 : cycle_graph(4)$
 806 (%i3) adjacency_matrix(c5);
 807                          [ 0  1  0  1 ]
 808                          [            ]
 809                          [ 1  0  1  0 ]
 810 (%o3)                    [            ]
 811                          [ 0  1  0  1 ]
 812                          [            ]
 813                          [ 1  0  1  0 ]
 814 @end example
 815
 816 @opencatbox{Categories:}
 817 @category{Package graphs}
 818 @category{Package graphs - properties}
 819 @closecatbox
 820 @end deffn
 821
 822 @anchor{average_degree}
 823 @deffn {Function} average_degree (@var{gr})
 824 Returns the average degree of vertices in the graph @var{gr}.
 825
 826 Example:
 827 @c ===beg===
 828 @c load ("graphs")$
 829 @c average_degree(grotzch_graph());
 830 @c ===end===
 831 @example
 832 (%i1) load ("graphs")$
 833 (%i2) average_degree(grotzch_graph());
 834                                40
 835 (%o2)                          --
 836                                11
 837 @end example
 838
 839 @opencatbox{Categories:}
 840 @category{Package graphs}
 841 @category{Package graphs - properties}
 842 @closecatbox
 843 @end deffn
 844
 845 @anchor{biconnected_components}
 846 @deffn {Function} biconnected_components (@var{gr})
 847 Returns the (vertex sets of) 2-connected components of the graph
 848 @var{gr}.
 849
 850 Example:
 851 @c ===beg===
 852 @c load ("graphs")$
 853 @c g : create_graph(
 854 @c             [1,2,3,4,5,6,7],
 855 @c             [
 856 @c              [1,2],[2,3],[2,4],[3,4],
 857 @c              [4,5],[5,6],[4,6],[6,7]
 858 @c             ])$
 859 @c biconnected_components(g);
 860 @c ===end===
 861 @example
 862 (%i1) load ("graphs")$
 863 (%i2) g : create_graph(
 864             [1,2,3,4,5,6,7],
 865             [
 866              [1,2],[2,3],[2,4],[3,4],
 867              [4,5],[5,6],[4,6],[6,7]
 868             ])$
 869 (%i3) biconnected_components(g);
 870 (%o3)        [[6, 7], [4, 5, 6], [1, 2], [2, 3, 4]]
 871 @end example
 872
 873 @ifhtml
 874 @image{figures/graphs13,6cm}
 875 @end ifhtml
 876
 877 @opencatbox{Categories:}
 878 @category{Package graphs}
 879 @category{Package graphs - properties}
 880 @closecatbox
 881 @end deffn
 882
 883 @anchor{bipartition}
 884 @deffn {Function} bipartition (@var{gr})
 885 Returns a bipartition of the vertices of the graph @var{gr} or an empty
 886 list if @var{gr} is not bipartite.
 887
 888 Example:
 889
 890 @c ===beg===
 891 @c load ("graphs")$
 892 @c h : heawood_graph()$
 893 @c [A,B]:bipartition(h);
 894 @c draw_graph(h, show_vertices=A, program=circular)$
 895 @c ===end===
 896 @example
 897 (%i1) load ("graphs")$
 898 (%i2) h : heawood_graph()$
 899 (%i3) [A,B]:bipartition(h);
 900 (%o3)  [[8, 12, 6, 10, 0, 2, 4], [13, 5, 11, 7, 9, 1, 3]]
 901 (%i4) draw_graph(h, show_vertices=A, program=circular)$
 902 @end example
 903
 904 @opencatbox{Categories:}
 905 @category{Package graphs}
 906 @category{Package graphs - properties}
 907 @closecatbox
 908 @end deffn
 909
 910 @ifhtml
 911 @image{figures/graphs02,6cm}
 912 @end ifhtml
 913
 914 @anchor{chromatic_index}
 915 @deffn {Function} chromatic_index (@var{gr})
 916 Returns the chromatic index of the graph @var{gr}.
 917
 918 Example:
 919 @c ===beg===
 920 @c load ("graphs")$
 921 @c p : petersen_graph()$
 922 @c chromatic_index(p);
 923 @c ===end===
 924 @example
 925 (%i1) load ("graphs")$
 926 (%i2) p : petersen_graph()$
 927 (%i3) chromatic_index(p);
 928 (%o3)                           4
 929 @end example
 930
 931 @opencatbox{Categories:}
 932 @category{Package graphs}
 933 @category{Package graphs - properties}
 934 @closecatbox
 935 @end deffn
 936
 937 @anchor{chromatic_number}
 938 @deffn {Function} chromatic_number (@var{gr})
 939 Returns the chromatic number of the graph @var{gr}.
 940
 941 Example:
 942 @c ===beg===
 943 @c load ("graphs")$
 944 @c chromatic_number(cycle_graph(5));
 945 @c chromatic_number(cycle_graph(6));
 946 @c ===end===
 947 @example
 948 (%i1) load ("graphs")$
 949 (%i2) chromatic_number(cycle_graph(5));
 950 (%o2)                           3
 951 (%i3) chromatic_number(cycle_graph(6));
 952 (%o3)                           2
 953 @end example
 954
 955 @opencatbox{Categories:}
 956 @category{Package graphs}
 957 @category{Package graphs - properties}
 958 @closecatbox
 959 @end deffn
 960
 961 @anchor{clear_edge_weight}
 962 @deffn {Function} clear_edge_weight (@var{e}, @var{gr})
 963 Removes the weight of the edge  @var{e} in the graph @var{gr}.
 964
 965 Example:
 966
 967 @c ===beg===
 968 @c load ("graphs")$
 969 @c g : create_graph(3, [[[0,1], 1.5], [[1,2], 1.3]])$
 970 @c get_edge_weight([0,1], g);
 971 @c clear_edge_weight([0,1], g)$
 972 @c get_edge_weight([0,1], g);
 973 @c ===end===
 974 @example
 975 (%i1) load ("graphs")$
 976 (%i2) g : create_graph(3, [[[0,1], 1.5], [[1,2], 1.3]])$
 977 (%i3) get_edge_weight([0,1], g);
 978 (%o3)                          1.5
 979 (%i4) clear_edge_weight([0,1], g)$
 980 (%i5) get_edge_weight([0,1], g);
 981 (%o5)                           1
 982 @end example
 983
 984 @opencatbox{Categories:}
 985 @category{Package graphs}
 986 @category{Package graphs - properties}
 987 @closecatbox
 988 @end deffn
 989
 990 @anchor{clear_vertex_label}
 991 @deffn {Function} clear_vertex_label (@var{v}, @var{gr})
 992 Removes the label of the vertex @var{v} in the graph @var{gr}.
 993
 994 Example:
 995 @c ===beg===
 996 @c load ("graphs")$
 997 @c g : create_graph([[0,"Zero"], [1, "One"]], [[0,1]])$
 998 @c get_vertex_label(0, g);
 999 @c clear_vertex_label(0, g);
1000 @c get_vertex_label(0, g);
1001 @c ===end===
1002 @example
1003 (%i1) load ("graphs")$
1004 (%i2) g : create_graph([[0,"Zero"], [1, "One"]], [[0,1]])$
1005 (%i3) get_vertex_label(0, g);
1006 (%o3)                         Zero
1007 (%i4) clear_vertex_label(0, g);
1008 (%o4)                         done
1009 (%i5) get_vertex_label(0, g);
1010 (%o5)                         false
1011 @end example
1012
1013 @opencatbox{Categories:}
1014 @category{Package graphs}
1015 @category{Package graphs - properties}
1016 @closecatbox
1017 @end deffn
1018
1019 @anchor{connected_components}
1020 @deffn {Function} connected_components (@var{gr})
1021 Returns the (vertex sets of) connected components of the graph @var{gr}.
1022
1023 Example:
1024 @c ===beg===
1025 @c load ("graphs")$
1026 @c g: graph_union(cycle_graph(5), path_graph(4))$
1027 @c connected_components(g);
1028 @c ===end===
1029 @example
1030 (%i1) load ("graphs")$
1031 (%i2) g: graph_union(cycle_graph(5), path_graph(4))$
1032 (%i3) connected_components(g);
1033 (%o3)            [[1, 2, 3, 4, 0], [8, 7, 6, 5]]
1034 @end example
1035
1036 @opencatbox{Categories:}
1037 @category{Package graphs}
1038 @category{Package graphs - properties}
1039 @closecatbox
1040 @end deffn
1041
1042 @anchor{diameter}
1043 @deffn {Function} diameter (@var{gr})
1044 Returns the diameter of the graph @var{gr}.
1045
1046 Example:
1047 @c ===beg===
1048 @c load ("graphs")$
1049 @c diameter(dodecahedron_graph());
1050 @c ===end===
1051 @example
1052 (%i1) load ("graphs")$
1053 (%i2) diameter(dodecahedron_graph());
1054 (%o2)                           5
1055 @end example
1056
1057 @opencatbox{Categories:}
1058 @category{Package graphs}
1059 @category{Package graphs - properties}
1060 @closecatbox
1061 @end deffn
1062
1063 @anchor{edge_coloring}
1064 @deffn {Function} edge_coloring (@var{gr})
1065 Returns an optimal coloring of the edges of the graph @var{gr}.
1066
1067 The function returns the chromatic index and a list representing the
1068 coloring of the edges of @var{gr}.
1069
1070 Example:
1071 @c ===beg===
1072 @c load ("graphs")$
1073 @c p : petersen_graph()$
1074 @c [ch_index, col] : edge_coloring(p);
1075 @c assoc([0,1], col);
1076 @c assoc([0,5], col);
1077 @c ===end===
1078 @example
1079 (%i1) load ("graphs")$
1080 (%i2) p : petersen_graph()$
1081 (%i3) [ch_index, col] : edge_coloring(p);
1082 (%o3) [4, [[[0, 5], 3], [[5, 7], 1], [[0, 1], 1], [[1, 6], 2],
1083 [[6, 8], 1], [[1, 2], 3], [[2, 7], 4], [[7, 9], 2], [[2, 3], 2],
1084 [[3, 8], 3], [[5, 8], 2], [[3, 4], 1], [[4, 9], 4], [[6, 9], 3],
1085 [[0, 4], 2]]]
1086 (%i4) assoc([0,1], col);
1087 (%o4)                           1
1088 (%i5) assoc([0,5], col);
1089 (%o5)                           3
1090 @end example
1091
1092 @opencatbox{Categories:}
1093 @category{Package graphs}
1094 @category{Package graphs - properties}
1095 @closecatbox
1096 @end deffn
1097
1098 @anchor{degree_sequence}
1099 @deffn {Function} degree_sequence (@var{gr})
1100 Returns the list of vertex degrees of the graph @var{gr}.
1101
1102 Example:
1103 @c ===beg===
1104 @c load ("graphs")$
1105 @c degree_sequence(random_graph(10, 0.4));
1106 @c ===end===
1107 @example
1108 (%i1) load ("graphs")$
1109 (%i2) degree_sequence(random_graph(10, 0.4));
1110 (%o2)            [2, 2, 2, 2, 2, 2, 3, 3, 3, 3]
1111 @end example
1112
1113 @opencatbox{Categories:}
1114 @category{Package graphs}
1115 @category{Package graphs - properties}
1116 @closecatbox
1117 @end deffn
1118
1119 @anchor{edge_connectivity}
1120 @deffn {Function} edge_connectivity (@var{gr})
1121 Returns the edge-connectivity of the graph @var{gr}.
1122
1123 See also @mref{min_edge_cut}.
1124
1125 @opencatbox{Categories:}
1126 @category{Package graphs}
1127 @category{Package graphs - properties}
1128 @closecatbox
1129 @end deffn
1130
1131 @anchor{edges}
1132 @deffn {Function} edges (@var{gr})
1133 Returns the list of edges (arcs) in a (directed) graph @var{gr}.
1134
1135 Example:
1136 @c ===beg===
1137 @c load ("graphs")$
1138 @c edges(complete_graph(4));
1139 @c ===end===
1140 @example
1141 (%i1) load ("graphs")$
1142 (%i2) edges(complete_graph(4));
1143 (%o2)   [[2, 3], [1, 3], [1, 2], [0, 3], [0, 2], [0, 1]]
1144 @end example
1145
1146 @opencatbox{Categories:}
1147 @category{Package graphs}
1148 @category{Package graphs - properties}
1149 @closecatbox
1150 @end deffn
1151
1152 @anchor{get_edge_weight}
1153 @deffn {Function} get_edge_weight @
1154 @fname{get_edge_weight} (@var{e}, @var{gr}) @
1155 @fname{get_edge_weight} (@var{e}, @var{gr}, @var{ifnot})
1156
1157 Returns the weight of the edge @var{e} in the graph @var{gr}.
1158
1159 If there is no weight assigned to the edge, the function returns 1. If
1160 the edge is not present in the graph, the function signals an error or
1161 returns the optional argument @var{ifnot}.
1162
1163 Example:
1164 @c ===beg===
1165 @c load ("graphs")$
1166 @c c5 : cycle_graph(5)$
1167 @c get_edge_weight([1,2], c5);
1168 @c set_edge_weight([1,2], 2.0, c5);
1169 @c get_edge_weight([1,2], c5);
1170 @c ===end===
1171 @example
1172 (%i1) load ("graphs")$
1173 (%i2) c5 : cycle_graph(5)$
1174 (%i3) get_edge_weight([1,2], c5);
1175 (%o3)                           1
1176 (%i4) set_edge_weight([1,2], 2.0, c5);
1177 (%o4)                         done
1178 (%i5) get_edge_weight([1,2], c5);
1179 (%o5)                          2.0
1180 @end example
1181
1182 @opencatbox{Categories:}
1183 @category{Package graphs}
1184 @category{Package graphs - properties}
1185 @closecatbox
1186 @end deffn
1187
1188 @anchor{get_vertex_label}
1189 @deffn {Function} get_vertex_label (@var{v}, @var{gr})
1190 Returns the label of the vertex @var{v} in the graph @var{gr}.
1191
1192 Example:
1193 @c ===beg===
1194 @c load ("graphs")$
1195 @c g : create_graph([[0,"Zero"], [1, "One"]], [[0,1]])$
1196 @c get_vertex_label(0, g);
1197 @c ===end===
1198 @example
1199 (%i1) load ("graphs")$
1200 (%i2) g : create_graph([[0,"Zero"], [1, "One"]], [[0,1]])$
1201 (%i3) get_vertex_label(0, g);
1202 (%o3)                         Zero
1203 @end example
1204
1205 @opencatbox{Categories:}
1206 @category{Package graphs}
1207 @category{Package graphs - properties}
1208 @closecatbox
1209 @end deffn
1210
1211 @anchor{graph_charpoly}
1212 @deffn {Function} graph_charpoly (@var{gr}, @var{x})
1213 Returns the characteristic polynomial (in variable @var{x}) of the graph
1214 @var{gr}.
1215
1216 Example:
1217 @c ===beg===
1218 @c load ("graphs")$
1219 @c p : petersen_graph()$
1220 @c graph_charpoly(p, x), factor;
1221 @c ===end===
1222 @example
1223 (%i1) load ("graphs")$
1224 (%i2) p : petersen_graph()$
1225 (%i3) graph_charpoly(p, x), factor;
1226                                    5        4
1227 (%o3)               (x - 3) (x - 1)  (x + 2)
1228 @end example
1229
1230 @opencatbox{Categories:}
1231 @category{Package graphs}
1232 @category{Package graphs - properties}
1233 @closecatbox
1234 @end deffn
1235
1236 @anchor{graph_center}
1237 @deffn {Function} graph_center (@var{gr})
1238 Returns the center of the graph @var{gr}.
1239
1240 Example:
1241 @c ===beg===
1242 @c load ("graphs")$
1243 @c g : grid_graph(5,5)$
1244 @c graph_center(g);
1245 @c ===end===
1246 @example
1247 (%i1) load ("graphs")$
1248 (%i2) g : grid_graph(5,5)$
1249 (%i3) graph_center(g);
1250 (%o3)                         [12]
1251 @end example
1252
1253 @opencatbox{Categories:}
1254 @category{Package graphs}
1255 @category{Package graphs - properties}
1256 @closecatbox
1257 @end deffn
1258
1259 @anchor{graph_eigenvalues}
1260 @deffn {Function} graph_eigenvalues (@var{gr})
1261 Returns the eigenvalues of the graph @var{gr}. The function returns
1262 eigenvalues in the same format as maxima @mref{eigenvalues} function.
1263
1264 Example:
1265 @c ===beg===
1266 @c load ("graphs")$
1267 @c p : petersen_graph()$
1268 @c graph_eigenvalues(p);
1269 @c ===end===
1270 @example
1271 (%i1) load ("graphs")$
1272 (%i2) p : petersen_graph()$
1273 (%i3) graph_eigenvalues(p);
1274 (%o3)               [[3, - 2, 1], [1, 4, 5]]
1275 @end example
1276
1277 @opencatbox{Categories:}
1278 @category{Package graphs}
1279 @category{Package graphs - properties}
1280 @closecatbox
1281 @end deffn
1282
1283 @anchor{graph_periphery}
1284 @deffn {Function} graph_periphery (@var{gr})
1285 Returns the periphery of the graph @var{gr}.
1286
1287 Example:
1288 @c ===beg===
1289 @c load ("graphs")$
1290 @c g : grid_graph(5,5)$
1291 @c graph_periphery(g);
1292 @c ===end===
1293 @example
1294 (%i1) load ("graphs")$
1295 (%i2) g : grid_graph(5,5)$
1296 (%i3) graph_periphery(g);
1297 (%o3)                    [24, 20, 4, 0]
1298 @end example
1299
1300 @opencatbox{Categories:}
1301 @category{Package graphs}
1302 @category{Package graphs - properties}
1303 @closecatbox
1304 @end deffn
1305
1306 @anchor{graph_size}
1307 @deffn {Function} graph_size (@var{gr})
1308 Returns the number of edges in the graph @var{gr}.
1309
1310 Example:
1311 @c ===beg===
1312 @c load ("graphs")$
1313 @c p : petersen_graph()$
1314 @c graph_size(p);
1315 @c ===end===
1316 @example
1317 (%i1) load ("graphs")$
1318 (%i2) p : petersen_graph()$
1319 (%i3) graph_size(p);
1320 (%o3)                          15
1321 @end example
1322
1323 @opencatbox{Categories:}
1324 @category{Package graphs}
1325 @category{Package graphs - properties}
1326 @closecatbox
1327 @end deffn
1328
1329 @anchor{graph_order}
1330 @deffn {Function} graph_order (@var{gr})
1331 Returns the number of vertices in the graph @var{gr}.
1332
1333 Example:
1334 @c ===beg===
1335 @c load ("graphs")$
1336 @c p : petersen_graph()$
1337 @c graph_order(p);
1338 @c ===end===
1339 @example
1340 (%i1) load ("graphs")$
1341 (%i2) p : petersen_graph()$
1342 (%i3) graph_order(p);
1343 (%o3)                          10
1344 @end example
1345
1346 @opencatbox{Categories:}
1347 @category{Package graphs}
1348 @category{Package graphs - properties}
1349 @closecatbox
1350 @end deffn
1351
1352 @anchor{girth}
1353 @deffn {Function} girth (@var{gr})
1354 Returns the length of the shortest cycle in @var{gr}.
1355
1356 Example:
1357 @c ===beg===
1358 @c load ("graphs")$
1359 @c g : heawood_graph()$
1360 @c girth(g);
1361 @c ===end===
1362 @example
1363 (%i1) load ("graphs")$
1364 (%i2) g : heawood_graph()$
1365 (%i3) girth(g);
1366 (%o3)                           6
1367 @end example
1368
1369 @opencatbox{Categories:}
1370 @category{Package graphs}
1371 @category{Package graphs - properties}
1372 @closecatbox
1373 @end deffn
1374
1375 @anchor{hamilton_cycle}
1376 @deffn {Function} hamilton_cycle (@var{gr})
1377 Returns the Hamilton cycle of the graph @var{gr} or an empty list if
1378 @var{gr} is not hamiltonian.
1379
1380 Example:
1381 @c ===beg===
1382 @c load ("graphs")$
1383 @c c : cube_graph(3)$
1384 @c hc : hamilton_cycle(c);
1385 @c draw_graph(c, show_edges=vertices_to_cycle(hc))$
1386 @c ===end===
1387 @example
1388 (%i1) load ("graphs")$
1389 (%i2) c : cube_graph(3)$
1390 (%i3) hc : hamilton_cycle(c);
1391 (%o3)              [7, 3, 2, 6, 4, 0, 1, 5, 7]
1392 (%i4) draw_graph(c, show_edges=vertices_to_cycle(hc))$
1393 @end example
1394
1395 @opencatbox{Categories:}
1396 @category{Package graphs}
1397 @category{Package graphs - properties}
1398 @closecatbox
1399 @end deffn
1400
1401 @ifhtml
1402 @image{figures/graphs03,6cm}
1403 @end ifhtml
1404
1405 @anchor{hamilton_path}
1406 @deffn {Function} hamilton_path (@var{gr})
1407 Returns the Hamilton path of the graph @var{gr} or an empty list if
1408 @var{gr} does not have a Hamilton path.
1409
1410 Example:
1411 @c ===beg===
1412 @c load ("graphs")$
1413 @c p : petersen_graph()$
1414 @c hp : hamilton_path(p);
1415 @c draw_graph(p, show_edges=vertices_to_path(hp))$
1416 @c ===end===
1417 @example
1418 (%i1) load ("graphs")$
1419 (%i2) p : petersen_graph()$
1420 (%i3) hp : hamilton_path(p);
1421 (%o3)            [0, 5, 7, 2, 1, 6, 8, 3, 4, 9]
1422 (%i4) draw_graph(p, show_edges=vertices_to_path(hp))$
1423 @end example
1424
1425 @opencatbox{Categories:}
1426 @category{Package graphs}
1427 @category{Package graphs - properties}
1428 @closecatbox
1429 @end deffn
1430
1431 @ifhtml
1432 @image{figures/graphs04,6cm}
1433 @end ifhtml
1434
1435 @anchor{isomorphism}
1436 @deffn {Function} isomorphism (@var{gr1}, @var{gr2})
1437
1438 Returns a an isomorphism between graphs/digraphs @var{gr1} and
1439 @var{gr2}. If @var{gr1} and @var{gr2} are not isomorphic, it returns
1440 an empty list.
1441
1442 Example:
1443 @c ===beg===
1444 @c load ("graphs")$
1445 @c clk5:complement_graph(line_graph(complete_graph(5)))$
1446 @c isomorphism(clk5, petersen_graph());
1447 @c ===end===
1448 @example
1449 (%i1) load ("graphs")$
1450 (%i2) clk5:complement_graph(line_graph(complete_graph(5)))$
1451 (%i3) isomorphism(clk5, petersen_graph());
1452 (%o3) [9 -> 0, 2 -> 1, 6 -> 2, 5 -> 3, 0 -> 4, 1 -> 5, 3 -> 6,
1453                                           4 -> 7, 7 -> 8, 8 -> 9]
1454 @end example
1455
1456 @opencatbox{Categories:}
1457 @category{Package graphs}
1458 @category{Package graphs - properties}
1459 @closecatbox
1460 @end deffn
1461
1462 @anchor{in_neighbors}
1463 @deffn {Function} in_neighbors (@var{v}, @var{gr})
1464 Returns the list of in-neighbors of the vertex @var{v} in the directed
1465 graph @var{gr}.
1466
1467 Example:
1468 @c ===beg===
1469 @c load ("graphs")$
1470 @c p : path_digraph(3)$
1471 @c in_neighbors(2, p);
1472 @c out_neighbors(2, p);
1473 @c ===end===
1474 @example
1475 (%i1) load ("graphs")$
1476 (%i2) p : path_digraph(3)$
1477 (%i3) in_neighbors(2, p);
1478 (%o3)                          [1]
1479 (%i4) out_neighbors(2, p);
1480 (%o4)                          []
1481 @end example
1482
1483 @opencatbox{Categories:}
1484 @category{Package graphs}
1485 @category{Package graphs - properties}
1486 @closecatbox
1487 @end deffn
1488
1489 @anchor{is_biconnected}
1490 @deffn {Function} is_biconnected (@var{gr})
1491 Returns @code{true} if @var{gr} is 2-connected and @code{false} otherwise.
1492
1493 Example:
1494 @c ===beg===
1495 @c load ("graphs")$
1496 @c is_biconnected(cycle_graph(5));
1497 @c is_biconnected(path_graph(5));
1498 @c ===end===
1499 @example
1500 (%i1) load ("graphs")$
1501 (%i2) is_biconnected(cycle_graph(5));
1502 (%o2)                         true
1503 (%i3) is_biconnected(path_graph(5));
1504 (%o3)                         false
1505 @end example
1506
1507 @opencatbox{Categories:}
1508 @category{Package graphs}
1509 @category{Package graphs - properties}
1510 @closecatbox
1511 @end deffn
1512
1513 @anchor{is_bipartite}
1514 @deffn {Function} is_bipartite (@var{gr})
1515 Returns @code{true} if @var{gr} is bipartite (2-colorable) and @code{false} otherwise.
1516
1517 Example:
1518 @c ===beg===
1519 @c load ("graphs")$
1520 @c is_bipartite(petersen_graph());
1521 @c is_bipartite(heawood_graph());
1522 @c ===end===
1523 @example
1524 (%i1) load ("graphs")$
1525 (%i2) is_bipartite(petersen_graph());
1526 (%o2)                         false
1527 (%i3) is_bipartite(heawood_graph());
1528 (%o3)                         true
1529 @end example
1530
1531 @opencatbox{Categories:}
1532 @category{Package graphs}
1533 @category{Package graphs - properties}
1534 @closecatbox
1535 @end deffn
1536
1537 @anchor{is_connected}
1538 @deffn {Function} is_connected (@var{gr})
1539 Returns @code{true} if the graph @var{gr} is connected and @code{false} otherwise.
1540
1541 Example:
1542 @c ===beg===
1543 @c load ("graphs")$
1544 @c is_connected(graph_union(cycle_graph(4), path_graph(3)));
1545 @c ===end===
1546 @example
1547 (%i1) load ("graphs")$
1548 (%i2) is_connected(graph_union(cycle_graph(4), path_graph(3)));
1549 (%o2)                         false
1550 @end example
1551
1552 @opencatbox{Categories:}
1553 @category{Package graphs}
1554 @category{Package graphs - properties}
1555 @closecatbox
1556 @end deffn
1557
1558 @anchor{is_digraph}
1559 @deffn {Function} is_digraph (@var{gr})
1560 Returns @code{true} if @var{gr} is a directed graph and @code{false} otherwise.
1561
1562 Example:
1563 @c ===beg===
1564 @c load ("graphs")$
1565 @c is_digraph(path_graph(5));
1566 @c is_digraph(path_digraph(5));
1567 @c ===end===
1568 @example
1569 (%i1) load ("graphs")$
1570 (%i2) is_digraph(path_graph(5));
1571 (%o2)                         false
1572 (%i3) is_digraph(path_digraph(5));
1573 (%o3)                         true
1574 @end example
1575
1576 @opencatbox{Categories:}
1577 @category{Package graphs}
1578 @category{Package graphs - properties}
1579 @closecatbox
1580 @end deffn
1581
1582 @anchor{is_edge_in_graph}
1583 @deffn {Function} is_edge_in_graph (@var{e}, @var{gr})
1584 Returns @code{true} if @var{e} is an edge (arc) in the (directed) graph @var{g}
1585 and @code{false} otherwise.
1586
1587 Example:
1588 @c ===beg===
1589 @c load ("graphs")$
1590 @c c4 : cycle_graph(4)$
1591 @c is_edge_in_graph([2,3], c4);
1592 @c is_edge_in_graph([3,2], c4);
1593 @c is_edge_in_graph([2,4], c4);
1594 @c is_edge_in_graph([3,2], cycle_digraph(4));
1595 @c ===end===
1596 @example
1597 (%i1) load ("graphs")$
1598 (%i2) c4 : cycle_graph(4)$
1599 (%i3) is_edge_in_graph([2,3], c4);
1600 (%o3)                         true
1601 (%i4) is_edge_in_graph([3,2], c4);
1602 (%o4)                         true
1603 (%i5) is_edge_in_graph([2,4], c4);
1604 (%o5)                         false
1605 (%i6) is_edge_in_graph([3,2], cycle_digraph(4));
1606 (%o6)                         false
1607 @end example
1608
1609 @opencatbox{Categories:}
1610 @category{Package graphs}
1611 @category{Package graphs - properties}
1612 @closecatbox
1613 @end deffn
1614
1615 @anchor{is_graph}
1616 @deffn {Function} is_graph (@var{gr})
1617 Returns @code{true} if @var{gr} is a graph and @code{false} otherwise.
1618
1619 Example:
1620 @c ===beg===
1621 @c load ("graphs")$
1622 @c is_graph(path_graph(5));
1623 @c is_graph(path_digraph(5));
1624 @c ===end===
1625 @example
1626 (%i1) load ("graphs")$
1627 (%i2) is_graph(path_graph(5));
1628 (%o2)                         true
1629 (%i3) is_graph(path_digraph(5));
1630 (%o3)                         false
1631 @end example
1632
1633 @opencatbox{Categories:}
1634 @category{Package graphs}
1635 @category{Package graphs - properties}
1636 @closecatbox
1637 @end deffn
1638
1639 @anchor{is_graph_or_digraph}
1640 @deffn {Function} is_graph_or_digraph (@var{gr})
1641 Returns @code{true} if @var{gr} is a graph or a directed graph and @code{false} otherwise.
1642
1643 Example:
1644 @c ===beg===
1645 @c load ("graphs")$
1646 @c is_graph_or_digraph(path_graph(5));
1647 @c is_graph_or_digraph(path_digraph(5));
1648 @c ===end===
1649 @example
1650 (%i1) load ("graphs")$
1651 (%i2) is_graph_or_digraph(path_graph(5));
1652 (%o2)                         true
1653 (%i3) is_graph_or_digraph(path_digraph(5));
1654 (%o3)                         true
1655 @end example
1656
1657 @opencatbox{Categories:}
1658 @category{Package graphs}
1659 @category{Package graphs - properties}
1660 @closecatbox
1661 @end deffn
1662
1663 @anchor{is_isomorphic}
1664 @deffn {Function} is_isomorphic (@var{gr1}, @var{gr2})
1665
1666 Returns @code{true} if graphs/digraphs @var{gr1} and @var{gr2} are isomorphic
1667 and @code{false} otherwise.
1668
1669 See also @mrefdot{isomorphism}
1670
1671 Example:
1672 @c ===beg===
1673 @c load ("graphs")$
1674 @c clk5:complement_graph(line_graph(complete_graph(5)))$
1675 @c is_isomorphic(clk5, petersen_graph());
1676 @c ===end===
1677 @example
1678 (%i1) load ("graphs")$
1679 (%i2) clk5:complement_graph(line_graph(complete_graph(5)))$
1680 (%i3) is_isomorphic(clk5, petersen_graph());
1681 (%o3)                         true
1682 @end example
1683
1684 @opencatbox{Categories:}
1685 @category{Package graphs}
1686 @category{Package graphs - properties}
1687 @closecatbox
1688 @end deffn
1689
1690 @anchor{is_planar}
1691 @deffn {Function} is_planar (@var{gr})
1692
1693 Returns @code{true} if @var{gr} is a planar graph and @code{false} otherwise.
1694
1695 The algorithm used is the Demoucron's algorithm, which is a quadratic time
1696 algorithm.
1697
1698 Example:
1699 @c ===beg===
1700 @c load ("graphs")$
1701 @c is_planar(dodecahedron_graph());
1702 @c is_planar(petersen_graph());
1703 @c is_planar(petersen_graph(10,2));
1704 @c ===end===
1705 @example
1706 (%i1) load ("graphs")$
1707 (%i2) is_planar(dodecahedron_graph());
1708 (%o2)                         true
1709 (%i3) is_planar(petersen_graph());
1710 (%o3)                         false
1711 (%i4) is_planar(petersen_graph(10,2));
1712 (%o4)                         true
1713 @end example
1714
1715 @opencatbox{Categories:}
1716 @category{Package graphs}
1717 @category{Package graphs - properties}
1718 @closecatbox
1719 @end deffn
1720
1721 @anchor{is_sconnected}
1722 @deffn {Function} is_sconnected (@var{gr})
1723 Returns @code{true} if the directed graph @var{gr} is strongly connected and
1724 @code{false} otherwise.
1725
1726 Example:
1727 @c ===beg===
1728 @c load ("graphs")$
1729 @c is_sconnected(cycle_digraph(5));
1730 @c is_sconnected(path_digraph(5));
1731 @c ===end===
1732 @example
1733 (%i1) load ("graphs")$
1734 (%i2) is_sconnected(cycle_digraph(5));
1735 (%o2)                         true
1736 (%i3) is_sconnected(path_digraph(5));
1737 (%o3)                         false
1738 @end example
1739
1740 @opencatbox{Categories:}
1741 @category{Package graphs}
1742 @category{Package graphs - properties}
1743 @closecatbox
1744 @end deffn
1745
1746 @anchor{is_vertex_in_graph}
1747 @deffn {Function} is_vertex_in_graph (@var{v}, @var{gr})
1748 Returns @code{true} if @var{v} is a vertex in the graph @var{g} and @code{false}  otherwise.
1749
1750 Example:
1751 @c ===beg===
1752 @c load ("graphs")$
1753 @c c4 : cycle_graph(4)$
1754 @c is_vertex_in_graph(0, c4);
1755 @c is_vertex_in_graph(6, c4);
1756 @c ===end===
1757 @example
1758 (%i1) load ("graphs")$
1759 (%i2) c4 : cycle_graph(4)$
1760 (%i3) is_vertex_in_graph(0, c4);
1761 (%o3)                         true
1762 (%i4) is_vertex_in_graph(6, c4);
1763 (%o4)                         false
1764 @end example
1765
1766 @opencatbox{Categories:}
1767 @category{Package graphs}
1768 @category{Package graphs - properties}
1769 @closecatbox
1770 @end deffn
1771
1772 @anchor{is_tree}
1773 @deffn {Function} is_tree (@var{gr})
1774 Returns @code{true} if @var{gr} is a tree and @code{false}  otherwise.
1775
1776 Example:
1777 @c ===beg===
1778 @c load ("graphs")$
1779 @c is_tree(random_tree(4));
1780 @c is_tree(graph_union(random_tree(4), random_tree(5)));
1781 @c ===end===
1782 @example
1783 (%i1) load ("graphs")$
1784 (%i2) is_tree(random_tree(4));
1785 (%o2)                         true
1786 (%i3) is_tree(graph_union(random_tree(4), random_tree(5)));
1787 (%o3)                         false
1788 @end example
1789
1790 @opencatbox{Categories:}
1791 @category{Package graphs}
1792 @category{Package graphs - properties}
1793 @closecatbox
1794 @end deffn
1795
1796 @anchor{laplacian_matrix}
1797 @deffn {Function} laplacian_matrix (@var{gr})
1798 Returns the laplacian matrix of the graph @var{gr}.
1799
1800 Example:
1801 @c ===beg===
1802 @c load ("graphs")$
1803 @c laplacian_matrix(cycle_graph(5));
1804 @c ===end===
1805 @example
1806 (%i1) load ("graphs")$
1807 (%i2) laplacian_matrix(cycle_graph(5));
1808                    [  2   - 1   0    0   - 1 ]
1809                    [                         ]
1810                    [ - 1   2   - 1   0    0  ]
1811                    [                         ]
1812 (%o2)              [  0   - 1   2   - 1   0  ]
1813                    [                         ]
1814                    [  0    0   - 1   2   - 1 ]
1815                    [                         ]
1816                    [ - 1   0    0   - 1   2  ]
1817 @end example
1818
1819 @opencatbox{Categories:}
1820 @category{Package graphs}
1821 @category{Package graphs - properties}
1822 @closecatbox
1823 @end deffn
1824
1825 @anchor{max_clique}
1826 @deffn {Function} max_clique (@var{gr})
1827 Returns a maximum clique of the graph @var{gr}.
1828
1829 Example:
1830 @c ===beg===
1831 @c load ("graphs")$
1832 @c g : random_graph(100, 0.5)$
1833 @c max_clique(g);
1834 @c ===end===
1835 @example
1836 (%i1) load ("graphs")$
1837 (%i2) g : random_graph(100, 0.5)$
1838 (%i3) max_clique(g);
1839 (%o3)          [6, 12, 31, 36, 52, 59, 62, 63, 80]
1840 @end example
1841
1842 @opencatbox{Categories:}
1843 @category{Package graphs}
1844 @category{Package graphs - properties}
1845 @closecatbox
1846 @end deffn
1847
1848 @anchor{max_degree}
1849 @deffn {Function} max_degree (@var{gr})
1850 Returns the maximal degree of vertices of the graph @var{gr} and a
1851 vertex of maximal degree.
1852
1853 Example:
1854 @c ===beg===
1855 @c load ("graphs")$
1856 @c g : random_graph(100, 0.02)$
1857 @c max_degree(g);
1858 @c vertex_degree(95, g);
1859 @c ===end===
1860 @example
1861 (%i1) load ("graphs")$
1862 (%i2) g : random_graph(100, 0.02)$
1863 (%i3) max_degree(g);
1864 (%o3)                        [6, 79]
1865 (%i4) vertex_degree(95, g);
1866 (%o4)                           2
1867 @end example
1868
1869 @opencatbox{Categories:}
1870 @category{Package graphs}
1871 @category{Package graphs - properties}
1872 @closecatbox
1873 @end deffn
1874
1875 @anchor{max_flow}
1876 @deffn {Function} max_flow (@var{net}, @var{s}, @var{t})
1877 Returns a maximum flow through the network @var{net} with the source
1878 @var{s} and the sink @var{t}.
1879
1880 The function returns the value of the maximal flow and a list
1881 representing the weights of the arcs in the optimal flow.
1882
1883 Example:
1884 @c ===beg===
1885 @c load ("graphs")$
1886 @c net : create_graph(
1887 @c   [1,2,3,4,5,6],
1888 @c   [[[1,2], 1.0],
1889 @c    [[1,3], 0.3],
1890 @c    [[2,4], 0.2],
1891 @c    [[2,5], 0.3],
1892 @c    [[3,4], 0.1],
1893 @c    [[3,5], 0.1],
1894 @c    [[4,6], 1.0],
1895 @c    [[5,6], 1.0]],
1896 @c   directed=true)$
1897 @c [flow_value, flow] : max_flow(net, 1, 6);
1898 @c fl : 0$
1899 @c for u in out_neighbors(1, net)
1900 @c      do fl : fl + assoc([1, u], flow)$
1901 @c fl;
1902 @c ===end===
1903 @example
1904 (%i1) load ("graphs")$
1905 (%i2) net : create_graph(
1906   [1,2,3,4,5,6],
1907   [[[1,2], 1.0],
1908    [[1,3], 0.3],
1909    [[2,4], 0.2],
1910    [[2,5], 0.3],
1911    [[3,4], 0.1],
1912    [[3,5], 0.1],
1913    [[4,6], 1.0],
1914    [[5,6], 1.0]],
1915   directed=true)$
1916 (%i3) [flow_value, flow] : max_flow(net, 1, 6);
1917 (%o3) [0.7, [[[1, 2], 0.5], [[1, 3], 0.2], [[2, 4], 0.2],
1918 [[2, 5], 0.3], [[3, 4], 0.1], [[3, 5], 0.1], [[4, 6], 0.3],
1919 [[5, 6], 0.4]]]
1920 (%i4) fl : 0$
1921 (%i5) for u in out_neighbors(1, net)
1922      do fl : fl + assoc([1, u], flow)$
1923 (%i6) fl;
1924 (%o6)                          0.7
1925 @end example
1926
1927 @opencatbox{Categories:}
1928 @category{Package graphs}
1929 @category{Package graphs - properties}
1930 @closecatbox
1931 @end deffn
1932
1933 @anchor{max_independent_set}
1934 @deffn {Function} max_independent_set (@var{gr})
1935 Returns a maximum independent set of the graph @var{gr}.
1936
1937 Example:
1938 @c ===beg===
1939 @c load ("graphs")$
1940 @c d : dodecahedron_graph()$
1941 @c mi : max_independent_set(d);
1942 @c draw_graph(d, show_vertices=mi)$
1943 @c ===end===
1944 @example
1945 (%i1) load ("graphs")$
1946 (%i2) d : dodecahedron_graph()$
1947 (%i3) mi : max_independent_set(d);
1948 (%o3)             [0, 3, 5, 9, 10, 11, 18, 19]
1949 (%i4) draw_graph(d, show_vertices=mi)$
1950 @end example
1951
1952 @opencatbox{Categories:}
1953 @category{Package graphs}
1954 @category{Package graphs - properties}
1955 @closecatbox
1956 @end deffn
1957
1958 @ifhtml
1959 @image{figures/graphs05,6cm}
1960 @end ifhtml
1961
1962 @anchor{max_matching}
1963 @deffn {Function} max_matching (@var{gr})
1964 Returns a maximum matching of the graph @var{gr}.
1965
1966 Example:
1967 @c ===beg===
1968 @c load ("graphs")$
1969 @c d : dodecahedron_graph()$
1970 @c m : max_matching(d);
1971 @c draw_graph(d, show_edges=m)$
1972 @c ===end===
1973 @example
1974 (%i1) load ("graphs")$
1975 (%i2) d : dodecahedron_graph()$
1976 (%i3) m : max_matching(d);
1977 (%o3) [[5, 7], [8, 9], [6, 10], [14, 19], [13, 18], [12, 17],
1978                                [11, 16], [0, 15], [3, 4], [1, 2]]
1979 (%i4) draw_graph(d, show_edges=m)$
1980 @end example
1981
1982 @opencatbox{Categories:}
1983 @category{Package graphs}
1984 @category{Package graphs - properties}
1985 @closecatbox
1986 @end deffn
1987
1988 @ifhtml
1989 @image{figures/graphs06,6cm}
1990 @end ifhtml
1991
1992 @anchor{min_degree}
1993 @deffn {Function} min_degree (@var{gr})
1994 Returns the minimum degree of vertices of the graph @var{gr} and a
1995 vertex of minimum degree.
1996
1997 Example:
1998 @c ===beg===
1999 @c load ("graphs")$
2000 @c g : random_graph(100, 0.1)$
2001 @c min_degree(g);
2002 @c vertex_degree(21, g);
2003 @c ===end===
2004 @example
2005 (%i1) load ("graphs")$
2006 (%i2) g : random_graph(100, 0.1)$
2007 (%i3) min_degree(g);
2008 (%o3)                        [3, 49]
2009 (%i4) vertex_degree(21, g);
2010 (%o4)                           9
2011 @end example
2012
2013 @opencatbox{Categories:}
2014 @category{Package graphs}
2015 @category{Package graphs - properties}
2016 @closecatbox
2017 @end deffn
2018
2019 @anchor{min_edge_cut}
2020 @deffn {Function} min_edge_cut (@var{gr})
2021 Returns the minimum edge cut in the graph @var{gr}.
2022
2023 See also @mrefdot{edge_connectivity}
2024
2025 @opencatbox{Categories:}
2026 @category{Package graphs}
2027 @category{Package graphs - properties}
2028 @closecatbox
2029 @end deffn
2030
2031 @anchor{min_vertex_cover}
2032 @deffn {Function} min_vertex_cover (@var{gr})
2033 Returns the minimum vertex cover of the graph @var{gr}.
2034
2035 @opencatbox{Categories:}
2036 @category{Package graphs}
2037 @category{Package graphs - properties}
2038 @closecatbox
2039 @end deffn
2040
2041 @anchor{min_vertex_cut}
2042 @deffn {Function} min_vertex_cut (@var{gr})
2043 Returns the minimum vertex cut in the graph @var{gr}.
2044
2045 See also @mrefdot{vertex_connectivity}
2046
2047 @opencatbox{Categories:}
2048 @category{Package graphs}
2049 @category{Package graphs - properties}
2050 @closecatbox
2051 @end deffn
2052
2053 @anchor{minimum_spanning_tree}
2054 @deffn {Function} minimum_spanning_tree (@var{gr})
2055 Returns the minimum spanning tree of the graph @var{gr}.
2056
2057 Example:
2058 @c ===beg===
2059 @c load ("graphs")$
2060 @c g : graph_product(path_graph(10), path_graph(10))$
2061 @c t : minimum_spanning_tree(g)$
2062 @c draw_graph(g, show_edges=edges(t))$
2063 @c ===end===
2064 @example
2065 (%i1) load ("graphs")$
2066 (%i2) g : graph_product(path_graph(10), path_graph(10))$
2067 (%i3) t : minimum_spanning_tree(g)$
2068 (%i4) draw_graph(g, show_edges=edges(t))$
2069 @end example
2070
2071 @opencatbox{Categories:}
2072 @category{Package graphs}
2073 @category{Package graphs - properties}
2074 @closecatbox
2075 @end deffn
2076
2077 @ifhtml
2078 @image{figures/graphs07,6cm}
2079 @end ifhtml
2080
2081 @anchor{neighbors}
2082 @deffn {Function} neighbors (@var{v}, @var{gr})
2083 Returns the list of neighbors of the vertex @var{v} in the graph @var{gr}.
2084
2085 Example:
2086 @c ===beg===
2087 @c load ("graphs")$
2088 @c p : petersen_graph()$
2089 @c neighbors(3, p);
2090 @c ===end===
2091 @example
2092 (%i1) load ("graphs")$
2093 (%i2) p : petersen_graph()$
2094 (%i3) neighbors(3, p);
2095 (%o3)                       [4, 8, 2]
2096 @end example
2097
2098 @opencatbox{Categories:}
2099 @category{Package graphs}
2100 @category{Package graphs - properties}
2101 @closecatbox
2102 @end deffn
2103
2104 @anchor{odd_girth}
2105 @deffn {Function} odd_girth (@var{gr})
2106 Returns the length of the shortest odd cycle in the graph @var{gr}.
2107
2108 Example:
2109 @c ===beg===
2110 @c load ("graphs")$
2111 @c g : graph_product(cycle_graph(4), cycle_graph(7))$
2112 @c girth(g);
2113 @c odd_girth(g);
2114 @c ===end===
2115 @example
2116 (%i1) load ("graphs")$
2117 (%i2) g : graph_product(cycle_graph(4), cycle_graph(7))$
2118 (%i3) girth(g);
2119 (%o3)                           4
2120 (%i4) odd_girth(g);
2121 (%o4)                           7
2122 @end example
2123
2124 @opencatbox{Categories:}
2125 @category{Package graphs}
2126 @category{Package graphs - properties}
2127 @closecatbox
2128 @end deffn
2129
2130 @anchor{out_neighbors}
2131 @deffn {Function} out_neighbors (@var{v}, @var{gr})
2132 Returns the list of out-neighbors of the vertex @var{v} in the directed
2133 graph @var{gr}.
2134
2135 Example:
2136 @c ===beg===
2137 @c load ("graphs")$
2138 @c p : path_digraph(3)$
2139 @c in_neighbors(2, p);
2140 @c out_neighbors(2, p);
2141 @c ===end===
2142 @example
2143 (%i1) load ("graphs")$
2144 (%i2) p : path_digraph(3)$
2145 (%i3) in_neighbors(2, p);
2146 (%o3)                          [1]
2147 (%i4) out_neighbors(2, p);
2148 (%o4)                          []
2149 @end example
2150
2151 @opencatbox{Categories:}
2152 @category{Package graphs}
2153 @category{Package graphs - properties}
2154 @closecatbox
2155 @end deffn
2156
2157 @anchor{planar_embedding}
2158 @deffn {Function} planar_embedding (@var{gr})
2159
2160 Returns the list of facial walks in a planar embedding of @var{gr} and
2161 @code{false} if @var{gr} is not a planar graph.
2162
2163 The graph @var{gr} must be biconnected.
2164
2165 The algorithm used is the Demoucron's algorithm, which is a quadratic time
2166 algorithm.
2167
2168 Example:
2169 @c ===beg===
2170 @c load ("graphs")$
2171 @c planar_embedding(grid_graph(3,3));
2172 @c ===end===
2173 @example
2174 (%i1) load ("graphs")$
2175 (%i2) planar_embedding(grid_graph(3,3));
2176 (%o2) [[3, 6, 7, 8, 5, 2, 1, 0], [4, 3, 0, 1], [3, 4, 7, 6],
2177                                       [8, 7, 4, 5], [1, 2, 5, 4]]
2178 @end example
2179
2180 @opencatbox{Categories:}
2181 @category{Package graphs}
2182 @category{Package graphs - properties}
2183 @closecatbox
2184 @end deffn
2185
2186 @anchor{print_graph}
2187 @deffn {Function} print_graph (@var{gr})
2188 Prints some information about the graph @var{gr}.
2189
2190 Example:
2191 @c ===beg===
2192 @c load ("graphs")$
2193 @c c5 : cycle_graph(5)$
2194 @c print_graph(c5)$
2195 @c dc5 : cycle_digraph(5)$
2196 @c print_graph(dc5)$
2197 @c out_neighbors(0, dc5);
2198 @c ===end===
2199 @example
2200 (%i1) load ("graphs")$
2201 (%i2) c5 : cycle_graph(5)$
2202 (%i3) print_graph(c5)$
2203 Graph on 5 vertices with 5 edges.
2204 Adjacencies:
2205   4 :  0  3
2206   3 :  4  2
2207   2 :  3  1
2208   1 :  2  0
2209   0 :  4  1
2210 (%i4) dc5 : cycle_digraph(5)$
2211 (%i5) print_graph(dc5)$
2212 Digraph on 5 vertices with 5 arcs.
2213 Adjacencies:
2214   4 :  0
2215   3 :  4
2216   2 :  3
2217   1 :  2
2218   0 :  1
2219 (%i6) out_neighbors(0, dc5);
2220 (%o6)                          [1]
2221 @end example
2222
2223 @opencatbox{Categories:}
2224 @category{Package graphs}
2225 @closecatbox
2226 @end deffn
2227
2228 @anchor{radius}
2229 @deffn {Function} radius (@var{gr})
2230 Returns the radius of the graph @var{gr}.
2231
2232 Example:
2233 @c ===beg===
2234 @c load ("graphs")$
2235 @c radius(dodecahedron_graph());
2236 @c ===end===
2237 @example
2238 (%i1) load ("graphs")$
2239 (%i2) radius(dodecahedron_graph());
2240 (%o2)                           5
2241 @end example
2242
2243 @opencatbox{Categories:}
2244 @category{Package graphs}
2245 @category{Package graphs - properties}
2246 @closecatbox
2247 @end deffn
2248
2249 @anchor{set_edge_weight}
2250 @deffn {Function} set_edge_weight (@var{e}, @var{w}, @var{gr})
2251 Assigns the weight @var{w} to the edge @var{e} in the graph @var{gr}.
2252
2253 Example:
2254 @c ===beg===
2255 @c load ("graphs")$
2256 @c g : create_graph([1, 2], [[[1,2], 1.2]])$
2257 @c get_edge_weight([1,2], g);
2258 @c set_edge_weight([1,2], 2.1, g);
2259 @c get_edge_weight([1,2], g);
2260 @c ===end===
2261 @example
2262 (%i1) load ("graphs")$
2263 (%i2) g : create_graph([1, 2], [[[1,2], 1.2]])$
2264 (%i3) get_edge_weight([1,2], g);
2265 (%o3)                          1.2
2266 (%i4) set_edge_weight([1,2], 2.1, g);
2267 (%o4)                         done
2268 (%i5) get_edge_weight([1,2], g);
2269 (%o5)                          2.1
2270 @end example
2271
2272 @opencatbox{Categories:}
2273 @category{Package graphs}
2274 @category{Package graphs - properties}
2275 @closecatbox
2276 @end deffn
2277
2278 @anchor{set_vertex_label}
2279 @deffn {Function} set_vertex_label (@var{v}, @var{l}, @var{gr})
2280 Assigns the label @var{l} to the vertex @var{v} in the graph @var{gr}.
2281
2282 Example:
2283 @c ===beg===
2284 @c load ("graphs")$
2285 @c g : create_graph([[1, "One"], [2, "Two"]], [[1,2]])$
2286 @c get_vertex_label(1, g);
2287 @c set_vertex_label(1, "oNE", g);
2288 @c get_vertex_label(1, g);
2289 @c ===end===
2290 @example
2291 (%i1) load ("graphs")$
2292 (%i2) g : create_graph([[1, "One"], [2, "Two"]], [[1,2]])$
2293 (%i3) get_vertex_label(1, g);
2294 (%o3)                          One
2295 (%i4) set_vertex_label(1, "oNE", g);
2296 (%o4)                         done
2297 (%i5) get_vertex_label(1, g);
2298 (%o5)                          oNE
2299 @end example
2300
2301 @opencatbox{Categories:}
2302 @category{Package graphs}
2303 @category{Package graphs - properties}
2304 @closecatbox
2305 @end deffn
2306
2307 @anchor{shortest_path}
2308 @deffn {Function} shortest_path (@var{u}, @var{v}, @var{gr})
2309 Returns the shortest path from @var{u} to @var{v} in the graph @var{gr}.
2310
2311 Example:
2312 @c ===beg===
2313 @c load ("graphs")$
2314 @c d : dodecahedron_graph()$
2315 @c path : shortest_path(0, 7, d);
2316 @c draw_graph(d, show_edges=vertices_to_path(path))$
2317 @c ===end===
2318 @example
2319 (%i1) load ("graphs")$
2320 (%i2) d : dodecahedron_graph()$
2321 (%i3) path : shortest_path(0, 7, d);
2322 (%o3)                   [0, 1, 19, 13, 7]
2323 (%i4) draw_graph(d, show_edges=vertices_to_path(path))$
2324 @end example
2325
2326 @opencatbox{Categories:}
2327 @category{Package graphs}
2328 @category{Package graphs - properties}
2329 @closecatbox
2330 @end deffn
2331
2332 @ifhtml
2333 @image{figures/graphs08,6cm}
2334 @end ifhtml
2335
2336 @anchor{shortest_weighted_path}
2337 @deffn {Function} shortest_weighted_path (@var{u}, @var{v}, @var{gr})
2338 Returns the length of the shortest weighted path and the shortest
2339 weighted path from @var{u} to @var{v} in the graph @var{gr}.
2340
2341 The length of a weighted path is the sum of edge weights of edges in the
2342 path. If an edge has no weight, then it has a default weight 1.
2343
2344 Example:
2345
2346 @c ===beg===
2347 @c load ("graphs")$
2348 @c g: petersen_graph(20, 2)$
2349 @c for e in edges(g) do set_edge_weight(e, random(1.0), g)$
2350 @c shortest_weighted_path(0, 10, g);
2351 @c ===end===
2352 @example
2353 (%i1) load ("graphs")$
2354 (%i2) g: petersen_graph(20, 2)$
2355 (%i3) for e in edges(g) do set_edge_weight(e, random(1.0), g)$
2356 (%i4) shortest_weighted_path(0, 10, g);
2357 (%o4) [2.575143920268482, [0, 20, 38, 36, 34, 32, 30, 10]]
2358 @end example
2359
2360 @opencatbox{Categories:}
2361 @category{Package graphs}
2362 @category{Package graphs - properties}
2363 @closecatbox
2364 @end deffn
2365
2366 @anchor{strong_components}
2367 @deffn {Function} strong_components (@var{gr})
2368 Returns the strong components of a directed graph @var{gr}.
2369
2370 Example:
2371 @c ===beg===
2372 @c load ("graphs")$
2373 @c t : random_tournament(4)$
2374 @c strong_components(t);
2375 @c vertex_out_degree(3, t);
2376 @c ===end===
2377 @example
2378 (%i1) load ("graphs")$
2379 (%i2) t : random_tournament(4)$
2380 (%i3) strong_components(t);
2381 (%o3)                 [[1], [0], [2], [3]]
2382 (%i4) vertex_out_degree(3, t);
2383 (%o4)                           3
2384 @end example
2385
2386 @opencatbox{Categories:}
2387 @category{Package graphs}
2388 @category{Package graphs - properties}
2389 @closecatbox
2390 @end deffn
2391
2392 @anchor{topological_sort}
2393 @deffn {Function} topological_sort (@var{dag})
2394
2395 Returns a topological sorting of the vertices of a directed graph
2396 @var{dag} or an empty list if @var{dag} is not a directed acyclic graph.
2397
2398 Example:
2399 @c ===beg===
2400 @c load ("graphs")$
2401 @c g:create_graph(
2402 @c          [1,2,3,4,5],
2403 @c          [
2404 @c           [1,2], [2,5], [5,3],
2405 @c           [5,4], [3,4], [1,3]
2406 @c          ],
2407 @c          directed=true)$
2408 @c topological_sort(g);
2409 @c ===end===
2410 @example
2411 (%i1) load ("graphs")$
2412 (%i2) g:create_graph(
2413          [1,2,3,4,5],
2414          [
2415           [1,2], [2,5], [5,3],
2416           [5,4], [3,4], [1,3]
2417          ],
2418          directed=true)$
2419 (%i3) topological_sort(g);
2420 (%o3)                    [1, 2, 5, 3, 4]
2421 @end example
2422
2423 @opencatbox{Categories:}
2424 @category{Package graphs}
2425 @category{Package graphs - properties}
2426 @closecatbox
2427 @end deffn
2428
2429 @anchor{vertex_connectivity}
2430 @deffn {Function} vertex_connectivity (@var{g})
2431 Returns the vertex connectivity of the graph @var{g}.
2432
2433 See also @mrefdot{min_vertex_cut}
2434
2435 @opencatbox{Categories:}
2436 @category{Package graphs}
2437 @category{Package graphs - properties}
2438 @closecatbox
2439 @end deffn
2440
2441 @anchor{vertex_degree}
2442 @deffn {Function} vertex_degree (@var{v}, @var{gr})
2443 Returns the degree of the vertex @var{v} in the graph @var{gr}.
2444
2445 @opencatbox{Categories:}
2446 @category{Package graphs}
2447 @category{Package graphs - properties}
2448 @closecatbox
2449 @end deffn
2450
2451 @anchor{vertex_distance}
2452 @deffn {Function} vertex_distance (@var{u}, @var{v}, @var{gr})
2453 Returns the length of the shortest path between @var{u} and @var{v} in
2454 the (directed) graph @var{gr}.
2455
2456 Example:
2457 @c ===beg===
2458 @c load ("graphs")$
2459 @c d : dodecahedron_graph()$
2460 @c vertex_distance(0, 7, d);
2461 @c shortest_path(0, 7, d);
2462 @c ===end===
2463 @example
2464 (%i1) load ("graphs")$
2465 (%i2) d : dodecahedron_graph()$
2466 (%i3) vertex_distance(0, 7, d);
2467 (%o3)                           4
2468 (%i4) shortest_path(0, 7, d);
2469 (%o4)                   [0, 1, 19, 13, 7]
2470 @end example
2471
2472 @opencatbox{Categories:}
2473 @category{Package graphs}
2474 @category{Package graphs - properties}
2475 @closecatbox
2476 @end deffn
2477
2478 @anchor{vertex_eccentricity}
2479 @deffn {Function} vertex_eccentricity (@var{v}, @var{gr})
2480
2481 Returns the eccentricity of the vertex @var{v} in the graph @var{gr}.
2482
2483 Example:
2484 @c ===beg===
2485 @c load ("graphs")$
2486 @c g:cycle_graph(7)$
2487 @c vertex_eccentricity(0, g);
2488 @c ===end===
2489 @example
2490 (%i1) load ("graphs")$
2491 (%i2) g:cycle_graph(7)$
2492 (%i3) vertex_eccentricity(0, g);
2493 (%o3)                           3
2494 @end example
2495
2496 @opencatbox{Categories:}
2497 @category{Package graphs}
2498 @category{Package graphs - properties}
2499 @closecatbox
2500 @end deffn
2501
2502 @anchor{vertex_in_degree}
2503 @deffn {Function} vertex_in_degree (@var{v}, @var{gr})
2504 Returns the in-degree of the vertex @var{v} in the directed graph @var{gr}.
2505
2506 Example:
2507 @c ===beg===
2508 @c load ("graphs")$
2509 @c p5 : path_digraph(5)$
2510 @c print_graph(p5)$
2511 @c vertex_in_degree(4, p5);
2512 @c in_neighbors(4, p5);
2513 @c ===end===
2514 @example
2515 (%i1) load ("graphs")$
2516 (%i2) p5 : path_digraph(5)$
2517 (%i3) print_graph(p5)$
2518 Digraph on 5 vertices with 4 arcs.
2519 Adjacencies:
2520   4 :
2521   3 :  4
2522   2 :  3
2523   1 :  2
2524   0 :  1
2525 (%i4) vertex_in_degree(4, p5);
2526 (%o4)                           1
2527 (%i5) in_neighbors(4, p5);
2528 (%o5)                          [3]
2529 @end example
2530
2531 @opencatbox{Categories:}
2532 @category{Package graphs}
2533 @category{Package graphs - properties}
2534 @closecatbox
2535 @end deffn
2536
2537 @anchor{vertex_out_degree}
2538 @deffn {Function} vertex_out_degree (@var{v}, @var{gr})
2539 Returns the out-degree of the vertex @var{v} in the directed graph @var{gr}.
2540
2541 Example:
2542 @c ===beg===
2543 @c load ("graphs")$
2544 @c t : random_tournament(10)$
2545 @c vertex_out_degree(0, t);
2546 @c out_neighbors(0, t);
2547 @c ===end===
2548 @example
2549 (%i1) load ("graphs")$
2550 (%i2) t : random_tournament(10)$
2551 (%i3) vertex_out_degree(0, t);
2552 (%o3)                           2
2553 (%i4) out_neighbors(0, t);
2554 (%o4)                        [7, 1]
2555 @end example
2556
2557 @opencatbox{Categories:}
2558 @category{Package graphs}
2559 @category{Package graphs - properties}
2560 @closecatbox
2561 @end deffn
2562
2563 @anchor{vertices}
2564 @deffn {Function} vertices (@var{gr})
2565 Returns the list of vertices in the graph @var{gr}.
2566
2567 Example:
2568 @c ===beg===
2569 @c load ("graphs")$
2570 @c vertices(complete_graph(4));
2571 @c ===end===
2572 @example
2573 (%i1) load ("graphs")$
2574 (%i2) vertices(complete_graph(4));
2575 (%o2)                     [3, 2, 1, 0]
2576 @end example
2577
2578 @opencatbox{Categories:}
2579 @category{Package graphs}
2580 @category{Package graphs - properties}
2581 @closecatbox
2582 @end deffn
2583
2584 @anchor{vertex_coloring}
2585 @deffn {Function} vertex_coloring (@var{gr})
2586 Returns an optimal coloring of the vertices of the graph @var{gr}.
2587
2588 The function returns the chromatic number and a list representing the
2589 coloring of the vertices of @var{gr}.
2590
2591 Example:
2592 @c ===beg===
2593 @c load ("graphs")$
2594 @c p:petersen_graph()$
2595 @c vertex_coloring(p);
2596 @c ===end===
2597 @example
2598 (%i1) load ("graphs")$
2599 (%i2) p:petersen_graph()$
2600 (%i3) vertex_coloring(p);
2601 (%o3) [3, [[0, 2], [1, 3], [2, 2], [3, 3], [4, 1], [5, 3],
2602                                  [6, 1], [7, 1], [8, 2], [9, 2]]]
2603 @end example
2604
2605 @opencatbox{Categories:}
2606 @category{Package graphs}
2607 @category{Package graphs - properties}
2608 @closecatbox
2609 @end deffn
2610
2611 @anchor{wiener_index}
2612 @deffn {Function} wiener_index (@var{gr})
2613 Returns the Wiener index of the graph @var{gr}.
2614
2615 Example:
2616 @c ===beg===
2617 @c load ("graphs")$
2618 @c wiener_index(dodecahedron_graph());
2619 @c ===end===
2620 @example
2621 (%i2) wiener_index(dodecahedron_graph());
2622 (%o2)                          500
2623 @end example
2624
2625 @opencatbox{Categories:}
2626 @category{Package graphs}
2627 @category{Package graphs - properties}
2628 @closecatbox
2629 @end deffn
2630
2631 @subsection Modifying graphs
2632
2633 @anchor{add_edge}
2634 @deffn {Function} add_edge (@var{e}, @var{gr})
2635 Adds the edge @var{e} to the graph @var{gr}.
2636
2637 Example:
2638 @c ===beg===
2639 @c load ("graphs")$
2640 @c p : path_graph(4)$
2641 @c neighbors(0, p);
2642 @c add_edge([0,3], p);
2643 @c neighbors(0, p);
2644 @c ===end===
2645 @example
2646 (%i1) load ("graphs")$
2647 (%i2) p : path_graph(4)$
2648 (%i3) neighbors(0, p);
2649 (%o3)                          [1]
2650 (%i4) add_edge([0,3], p);
2651 (%o4)                         done
2652 (%i5) neighbors(0, p);
2653 (%o5)                        [3, 1]
2654 @end example
2655
2656 @opencatbox{Categories:}
2657 @category{Package graphs}
2658 @category{Package graphs - modifications}
2659 @closecatbox
2660 @end deffn
2661
2662 @anchor{add_edges}
2663 @deffn {Function} add_edges (@var{e_list}, @var{gr})
2664 Adds all edges in the list @var{e_list} to the graph @var{gr}.
2665
2666 Example:
2667 @c ===beg===
2668 @c load ("graphs")$
2669 @c g : empty_graph(3)$
2670 @c add_edges([[0,1],[1,2]], g)$
2671 @c print_graph(g)$
2672 @c ===end===
2673 @example
2674 (%i1) load ("graphs")$
2675 (%i2) g : empty_graph(3)$
2676 (%i3) add_edges([[0,1],[1,2]], g)$
2677 (%i4) print_graph(g)$
2678 Graph on 3 vertices with 2 edges.
2679 Adjacencies:
2680   2 :  1
2681   1 :  2  0
2682   0 :  1
2683 @end example
2684
2685 @opencatbox{Categories:}
2686 @category{Package graphs}
2687 @category{Package graphs - modifications}
2688 @closecatbox
2689 @end deffn
2690
2691 @anchor{add_vertex}
2692 @deffn {Function} add_vertex (@var{v}, @var{gr})
2693 Adds the vertex @var{v} to the graph @var{gr}.
2694
2695 Example:
2696 @c ===beg===
2697 @c load ("graphs")$
2698 @c g : path_graph(2)$
2699 @c add_vertex(2, g)$
2700 @c print_graph(g)$
2701 @c ===end===
2702 @example
2703 (%i1) load ("graphs")$
2704 (%i2) g : path_graph(2)$
2705 (%i3) add_vertex(2, g)$
2706 (%i4) print_graph(g)$
2707 Graph on 3 vertices with 1 edges.
2708 Adjacencies:
2709   2 :
2710   1 :  0
2711   0 :  1
2712 @end example
2713
2714 @opencatbox{Categories:}
2715 @category{Package graphs}
2716 @category{Package graphs - modifications}
2717 @closecatbox
2718 @end deffn
2719
2720 @anchor{add_vertices}
2721 @deffn {Function} add_vertices (@var{v_list}, @var{gr})
2722 Adds all vertices in the list @var{v_list} to the graph @var{gr}.
2723
2724 @opencatbox{Categories:}
2725 @category{Package graphs}
2726 @category{Package graphs - modifications}
2727 @closecatbox
2728 @end deffn
2729
2730 @anchor{connect_vertices}
2731 @deffn {Function} connect_vertices (@var{v_list}, @var{u_list}, @var{gr})
2732 Connects all vertices from the list @var{v_list} with the vertices in
2733 the list @var{u_list} in the graph @var{gr}.
2734
2735 @var{v_list} and @var{u_list} can be single vertices or lists of
2736 vertices.
2737
2738 Example:
2739 @c ===beg===
2740 @c load ("graphs")$
2741 @c g : empty_graph(4)$
2742 @c connect_vertices(0, [1,2,3], g)$
2743 @c print_graph(g)$
2744 @c ===end===
2745 @example
2746 (%i1) load ("graphs")$
2747 (%i2) g : empty_graph(4)$
2748 (%i3) connect_vertices(0, [1,2,3], g)$
2749 (%i4) print_graph(g)$
2750 Graph on 4 vertices with 3 edges.
2751 Adjacencies:
2752   3 :  0
2753   2 :  0
2754   1 :  0
2755   0 :  3  2  1
2756 @end example
2757
2758 @opencatbox{Categories:}
2759 @category{Package graphs}
2760 @category{Package graphs - modifications}
2761 @closecatbox
2762 @end deffn
2763
2764 @anchor{contract_edge}
2765 @deffn {Function} contract_edge (@var{e}, @var{gr})
2766 Contracts the edge @var{e} in the graph @var{gr}.
2767
2768 Example:
2769 @c ===beg===
2770 @c load ("graphs")$
2771 @c g: create_graph(
2772 @c       8, [[0,3],[1,3],[2,3],[3,4],[4,5],[4,6],[4,7]])$
2773 @c print_graph(g)$
2774 @c contract_edge([3,4], g)$
2775 @c print_graph(g)$
2776 @c ===end===
2777 @example
2778 (%i1) load ("graphs")$
2779 (%i2) g: create_graph(
2780       8, [[0,3],[1,3],[2,3],[3,4],[4,5],[4,6],[4,7]])$
2781 (%i3) print_graph(g)$
2782 Graph on 8 vertices with 7 edges.
2783 Adjacencies:
2784   7 :  4
2785   6 :  4
2786   5 :  4
2787   4 :  7  6  5  3
2788   3 :  4  2  1  0
2789   2 :  3
2790   1 :  3
2791   0 :  3
2792 (%i4) contract_edge([3,4], g)$
2793 (%i5) print_graph(g)$
2794 Graph on 7 vertices with 6 edges.
2795 Adjacencies:
2796   7 :  3
2797   6 :  3
2798   5 :  3
2799   3 :  5  6  7  2  1  0
2800   2 :  3
2801   1 :  3
2802   0 :  3
2803 @end example
2804
2805 @opencatbox{Categories:}
2806 @category{Package graphs}
2807 @category{Package graphs - modifications}
2808 @closecatbox
2809 @end deffn
2810
2811 @anchor{remove_edge}
2812 @deffn {Function} remove_edge (@var{e}, @var{gr})
2813 Removes the edge @var{e} from the graph @var{gr}.
2814
2815 Example:
2816 @c ===beg===
2817 @c load ("graphs")$
2818 @c c3 : cycle_graph(3)$
2819 @c remove_edge([0,1], c3)$
2820 @c print_graph(c3)$
2821 @c ===end===
2822 @example
2823 (%i1) load ("graphs")$
2824 (%i2) c3 : cycle_graph(3)$
2825 (%i3) remove_edge([0,1], c3)$
2826 (%i4) print_graph(c3)$
2827 Graph on 3 vertices with 2 edges.
2828 Adjacencies:
2829   2 :  0  1
2830   1 :  2
2831   0 :  2
2832 @end example
2833
2834 @opencatbox{Categories:}
2835 @category{Package graphs}
2836 @category{Package graphs - modifications}
2837 @closecatbox
2838 @end deffn
2839
2840 @anchor{remove_vertex}
2841 @deffn {Function} remove_vertex (@var{v}, @var{gr})
2842 Removes the vertex @var{v} from the graph @var{gr}.
2843
2844 @opencatbox{Categories:}
2845 @category{Package graphs}
2846 @closecatbox
2847 @end deffn
2848
2849 @subsection Reading and writing to files
2850
2851 @anchor{dimacs_export}
2852 @deffn {Function} dimacs_export @
2853 @fname{dimacs_export} (@var{gr}, @var{fl}) @
2854 @fname{dimacs_export} (@var{gr}, @var{fl}, @var{comment1}, ..., @var{commentn})
2855
2856 Exports the graph into the file @var{fl} in the DIMACS format. Optional
2857 comments will be added to the top of the file.
2858
2859 @opencatbox{Categories:}
2860 @category{Package graphs}
2861 @category{Package graphs - io}
2862 @closecatbox
2863 @end deffn
2864
2865 @anchor{dimacs_import}
2866 @deffn {Function} dimacs_import (@var{fl})
2867
2868 Returns the graph from file @var{fl} in the DIMACS format.
2869
2870 @opencatbox{Categories:}
2871 @category{Package graphs}
2872 @category{Package graphs - io}
2873 @closecatbox
2874 @end deffn
2875
2876 @anchor{graph6_decode}
2877 @deffn {Function} graph6_decode (@var{str})
2878
2879 Returns the graph encoded in the graph6 format in the string @var{str}.
2880
2881 @opencatbox{Categories:}
2882 @category{Package graphs}
2883 @category{Package graphs - io}
2884 @closecatbox
2885 @end deffn
2886
2887 @anchor{graph6_encode}
2888 @deffn {Function} graph6_encode (@var{gr})
2889
2890 Returns a string which encodes the graph @var{gr} in the graph6 format.
2891
2892 @opencatbox{Categories:}
2893 @category{Package graphs}
2894 @category{Package graphs - io}
2895 @closecatbox
2896 @end deffn
2897
2898 @anchor{graph6_export}
2899 @deffn {Function} graph6_export (@var{gr_list}, @var{fl})
2900
2901 Exports graphs in the list @var{gr_list} to the file @var{fl} in the
2902 graph6 format.
2903
2904 @opencatbox{Categories:}
2905 @category{Package graphs}
2906 @category{Package graphs - io}
2907 @closecatbox
2908 @end deffn
2909
2910 @anchor{graph6_import}
2911 @deffn {Function} graph6_import (@var{fl})
2912
2913 Returns a list of graphs from the file @var{fl} in the graph6 format.
2914
2915 @opencatbox{Categories:}
2916 @category{Package graphs}
2917 @category{Package graphs - io}
2918 @closecatbox
2919 @end deffn
2920
2921 @anchor{sparse6_decode}
2922 @deffn {Function} sparse6_decode (@var{str})
2923
2924 Returns the graph encoded in the sparse6 format in the string @var{str}.
2925
2926 @opencatbox{Categories:}
2927 @category{Package graphs}
2928 @category{Package graphs - io}
2929 @closecatbox
2930 @end deffn
2931
2932 @anchor{sparse6_encode}
2933 @deffn {Function} sparse6_encode (@var{gr})
2934
2935 Returns a string which encodes the graph @var{gr} in the sparse6 format.
2936
2937 @opencatbox{Categories:}
2938 @category{Package graphs}
2939 @category{Package graphs - io}
2940 @closecatbox
2941 @end deffn
2942
2943 @anchor{sparse6_export}
2944 @deffn {Function} sparse6_export (@var{gr_list}, @var{fl})
2945
2946 Exports graphs in the list @var{gr_list} to the file @var{fl} in the
2947 sparse6 format.
2948
2949 @opencatbox{Categories:}
2950 @category{Package graphs}
2951 @category{Package graphs - io}
2952 @closecatbox
2953 @end deffn
2954
2955 @anchor{sparse6_import}
2956 @deffn {Function} sparse6_import (@var{fl})
2957
2958 Returns a list of graphs from the file @var{fl} in the sparse6 format.
2959
2960 @opencatbox{Categories:}
2961 @category{Package graphs}
2962 @category{Package graphs - io}
2963 @closecatbox
2964 @end deffn
2965
2966 @subsection Visualization
2967
2968 @anchor{draw_graph}
2969 @deffn {Function} draw_graph @
2970 @fname{draw_graph} (@var{graph}) @
2971 @fname{draw_graph} (@var{graph}, @var{option1}, ..., @var{optionk})
2972
2973 Draws the graph using the @ref{draw-pkg} package.
2974
2975 The algorithm used to position vertices is specified by the optional
2976 argument @var{program}. The default value is
2977 @code{program=spring_embedding}. @var{draw_graph} can also use the
2978 graphviz programs for positioning vertices, but graphviz must be
2979 installed separately.
2980
2981 Example 1:
2982
2983 @c ===beg===
2984 @c load ("graphs")$
2985 @c g:grid_graph(10,10)$
2986 @c m:max_matching(g)$
2987 @c draw_graph(g,
2988 @c    spring_embedding_depth=100,
2989 @c    show_edges=m, edge_type=dots,
2990 @c    vertex_size=0)$
2991 @c ===end===
2992 @example
2993 (%i1) load ("graphs")$
2994 (%i2) g:grid_graph(10,10)$
2995 (%i3) m:max_matching(g)$
2996 (%i4) draw_graph(g,
2997    spring_embedding_depth=100,
2998    show_edges=m, edge_type=dots,
2999    vertex_size=0)$
3000 @end example
3001
3002 @ifhtml
3003 @image{figures/graphs09,6cm}
3004 @end ifhtml
3005
3006 Example 2:
3007
3008 @c ===beg===
3009 @c load ("graphs")$
3010 @c g:create_graph(16,
3011 @c     [
3012 @c      [0,1],[1,3],[2,3],[0,2],[3,4],[2,4],
3013 @c      [5,6],[6,4],[4,7],[6,7],[7,8],[7,10],[7,11],
3014 @c      [8,10],[11,10],[8,9],[11,12],[9,15],[12,13],
3015 @c      [10,14],[15,14],[13,14]
3016 @c     ])$
3017 @c t:minimum_spanning_tree(g)$
3018 @c draw_graph(
3019 @c     g,
3020 @c     show_edges=edges(t),
3021 @c     show_edge_width=4,
3022 @c     show_edge_color=green,
3023 @c     vertex_type=filled_square,
3024 @c     vertex_size=2
3025 @c     )$
3026 @c ===end===
3027 @example
3028 (%i1) load ("graphs")$
3029 (%i2) g:create_graph(16,
3030     [
3031      [0,1],[1,3],[2,3],[0,2],[3,4],[2,4],
3032      [5,6],[6,4],[4,7],[6,7],[7,8],[7,10],[7,11],
3033      [8,10],[11,10],[8,9],[11,12],[9,15],[12,13],
3034      [10,14],[15,14],[13,14]
3035     ])$
3036 (%i3) t:minimum_spanning_tree(g)$
3037 (%i4) draw_graph(
3038     g,
3039     show_edges=edges(t),
3040     show_edge_width=4,
3041     show_edge_color=green,
3042     vertex_type=filled_square,
3043     vertex_size=2
3044     )$
3045 @end example
3046
3047 @ifhtml
3048 @image{figures/graphs10,6cm}
3049 @end ifhtml
3050
3051 Example 3:
3052
3053 @c ===beg===
3054 @c load ("graphs")$
3055 @c g:create_graph(16,
3056 @c     [
3057 @c      [0,1],[1,3],[2,3],[0,2],[3,4],[2,4],
3058 @c      [5,6],[6,4],[4,7],[6,7],[7,8],[7,10],[7,11],
3059 @c      [8,10],[11,10],[8,9],[11,12],[9,15],[12,13],
3060 @c      [10,14],[15,14],[13,14]
3061 @c     ])$
3062 @c mi : max_independent_set(g)$
3063 @c draw_graph(
3064 @c     g,
3065 @c     show_vertices=mi,
3066 @c     show_vertex_type=filled_up_triangle,
3067 @c     show_vertex_size=2,
3068 @c     edge_color=cyan,
3069 @c     edge_width=3,
3070 @c     show_id=true,
3071 @c     text_color=brown
3072 @c     )$
3073 @c ===end===
3074 @example
3075 (%i1) load ("graphs")$
3076 (%i2) g:create_graph(16,
3077     [
3078      [0,1],[1,3],[2,3],[0,2],[3,4],[2,4],
3079      [5,6],[6,4],[4,7],[6,7],[7,8],[7,10],[7,11],
3080      [8,10],[11,10],[8,9],[11,12],[9,15],[12,13],
3081      [10,14],[15,14],[13,14]
3082     ])$
3083 (%i3) mi : max_independent_set(g)$
3084 (%i4) draw_graph(
3085     g,
3086     show_vertices=mi,
3087     show_vertex_type=filled_up_triangle,
3088     show_vertex_size=2,
3089     edge_color=cyan,
3090     edge_width=3,
3091     show_id=true,
3092     text_color=brown
3093     )$
3094 @end example
3095
3096 @ifhtml
3097 @image{figures/graphs11,6cm}
3098 @end ifhtml
3099
3100 Example 4:
3101
3102 @c ===beg===
3103 @c load ("graphs")$
3104 @c net : create_graph(
3105 @c     [0,1,2,3,4,5],
3106 @c     [
3107 @c      [[0,1], 3], [[0,2], 2],
3108 @c      [[1,3], 1], [[1,4], 3],
3109 @c      [[2,3], 2], [[2,4], 2],
3110 @c      [[4,5], 2], [[3,5], 2]
3111 @c     ],
3112 @c     directed=true
3113 @c     )$
3114 @c draw_graph(
3115 @c     net,
3116 @c     show_weight=true,
3117 @c     vertex_size=0,
3118 @c     show_vertices=[0,5],
3119 @c     show_vertex_type=filled_square,
3120 @c     head_length=0.2,
3121 @c     head_angle=10,
3122 @c     edge_color="dark-green",
3123 @c     text_color=blue
3124 @c     )$
3125 @c ===end===
3126 @example
3127 (%i1) load ("graphs")$
3128 (%i2) net : create_graph(
3129     [0,1,2,3,4,5],
3130     [
3131      [[0,1], 3], [[0,2], 2],
3132      [[1,3], 1], [[1,4], 3],
3133      [[2,3], 2], [[2,4], 2],
3134      [[4,5], 2], [[3,5], 2]
3135     ],
3136     directed=true
3137     )$
3138 (%i3) draw_graph(
3139     net,
3140     show_weight=true,
3141     vertex_size=0,
3142     show_vertices=[0,5],
3143     show_vertex_type=filled_square,
3144     head_length=0.2,
3145     head_angle=10,
3146     edge_color="dark-green",
3147     text_color=blue
3148     )$
3149 @end example
3150
3151 @ifhtml
3152 @image{figures/graphs12,6cm}
3153 @end ifhtml
3154
3155 Example 5:
3156
3157 @c ===beg===
3158 @c load("graphs")$
3159 @c g: petersen_graph(20, 2);
3160 @c draw_graph(g, redraw=true, program=planar_embedding);
3161 @c ===end===
3162 @example
3163 (%i1) load("graphs")$
3164 (%i2) g: petersen_graph(20, 2);
3165 (%o2)                         GRAPH
3166 (%i3) draw_graph(g, redraw=true, program=planar_embedding);
3167 (%o3)                         done
3168 @end example
3169
3170 @ifhtml
3171 @image{figures/graphs14,6cm}
3172 @end ifhtml
3173
3174 Example 6:
3175
3176 @c ===beg===
3177 @c load("graphs")$
3178 @c t: tutte_graph();
3179 @c draw_graph(t, redraw=true,
3180 @c               fixed_vertices=[1,2,3,4,5,6,7,8,9]);
3181 @c ===end===
3182 @example
3183 (%i1) load("graphs")$
3184 (%i2) t: tutte_graph();
3185 (%o2)                         GRAPH
3186 (%i3) draw_graph(t, redraw=true,
3187                     fixed_vertices=[1,2,3,4,5,6,7,8,9]);
3188 (%o3)                         done
3189 @end example
3190
3191 @ifhtml
3192 @image{figures/graphs15,6cm}
3193 @end ifhtml
3194
3195 @opencatbox{Categories:}
3196 @category{Package graphs}
3197 @closecatbox
3198 @end deffn
3199
3200 @anchor{draw_graph_program}
3201 @defvr {Option variable} draw_graph_program
3202 Default value: @var{spring_embedding}
3203
3204 The default value for the program used to position vertices in
3205 @code{draw_graph} program.
3206
3207 @opencatbox{Categories:}
3208 @category{Package graphs}
3209 @category{Package graphs - draw_graphs options}
3210 @closecatbox
3211 @end defvr
3212
3213 @anchor{show_id}
3214 @defvr {draw_graph option} show_id
3215 Default value: @var{false}
3216
3217 If @var{true} then ids of the vertices are displayed.
3218
3219 @opencatbox{Categories:}
3220 @category{Package graphs}
3221 @category{Package graphs - draw_graphs options}
3222 @closecatbox
3223 @end defvr
3224
3225 @anchor{show_label}
3226 @defvr {draw_graph option} show_label
3227 Default value: @var{false}
3228
3229 If @var{true} then labels of the vertices are displayed.
3230
3231 @opencatbox{Categories:}
3232 @category{Package graphs}
3233 @category{Package graphs - draw_graphs options}
3234 @closecatbox
3235 @end defvr
3236
3237 @anchor{label_alignment_graphs}
3238 @defvr {draw_graph option} label_alignment
3239 Default value: @var{center}
3240
3241 Determines how to align the labels/ids of the vertices. Can
3242 be @code{left}, @code{center} or @code{right}.
3243
3244 @opencatbox{Categories:}
3245 @category{Package graphs}
3246 @category{Package graphs - draw_graphs options}
3247 @closecatbox
3248 @end defvr
3249
3250 @anchor{show_weight }
3251 @defvr {draw_graph option} show_weight
3252 Default value: @var{false}
3253
3254 If @var{true} then weights of the edges are displayed.
3255
3256 @opencatbox{Categories:}
3257 @category{Package graphs}
3258 @category{Package graphs - draw_graphs options}
3259 @closecatbox
3260 @end defvr
3261
3262 @anchor{vertex_type}
3263 @defvr {draw_graph option} vertex_type
3264 Default value: @var{circle}
3265
3266 Defines how vertices are displayed. See the @var{point_type} option for
3267 the @code{draw} package for possible values.
3268
3269 @opencatbox{Categories:}
3270 @category{Package graphs}
3271 @category{Package graphs - draw_graphs options}
3272 @closecatbox
3273 @end defvr
3274
3275 @anchor{vertex_size}
3276 @defvr {draw_graph option} vertex_size
3277 The size of vertices.
3278
3279 @opencatbox{Categories:}
3280 @category{Package graphs}
3281 @category{Package graphs - draw_graphs options}
3282 @closecatbox
3283 @end defvr
3284
3285 @anchor{vertex_color }
3286 @defvr {draw_graph option} vertex_color
3287 The color used for displaying vertices.
3288
3289 @opencatbox{Categories:}
3290 @category{Package graphs}
3291 @category{Package graphs - draw_graphs options}
3292 @closecatbox
3293 @end defvr
3294
3295 @anchor{show_vertices}
3296 @defvr {draw_graph option} show_vertices
3297 Default value: []
3298
3299 Display selected vertices in the using a different color.
3300
3301 @opencatbox{Categories:}
3302 @category{Package graphs}
3303 @category{Package graphs - draw_graphs options}
3304 @closecatbox
3305 @end defvr
3306
3307 @anchor{show_vertex_type}
3308 @defvr {draw_graph option} show_vertex_type
3309 Defines how vertices specified in @var{show_vertices} are displayed.
3310 See the @var{point_type} option for the @code{draw} package for possible
3311 values.
3312
3313 @opencatbox{Categories:}
3314 @category{Package graphs}
3315 @category{Package graphs - draw_graphs options}
3316 @closecatbox
3317 @end defvr
3318
3319 @anchor{show_vertex_size}
3320 @defvr {draw_graph option} show_vertex_size
3321 The size of vertices in @var{show_vertices}.
3322
3323 @opencatbox{Categories:}
3324 @category{Package graphs}
3325 @category{Package graphs - draw_graphs options}
3326 @closecatbox
3327 @end defvr
3328
3329 @anchor{show_vertex_color }
3330 @defvr {draw_graph option} show_vertex_color
3331 The color used for displaying vertices in the @var{show_vertices} list.
3332
3333 @opencatbox{Categories:}
3334 @category{Package graphs}
3335 @category{Package graphs - draw_graphs options}
3336 @closecatbox
3337 @end defvr
3338
3339 @anchor{vertex_partition}
3340 @defvr {draw_graph option} vertex_partition
3341 Default value: []
3342
3343 A partition @code{[[v1,v2,...],...,[vk,...,vn]]} of the vertices of the
3344 graph. The vertices of each list in the partition will be drawn in a
3345 different color.
3346
3347 @opencatbox{Categories:}
3348 @category{Package graphs}
3349 @category{Package graphs - draw_graphs options}
3350 @closecatbox
3351 @end defvr
3352
3353 @anchor{vertex_coloring_variable}
3354 @defvr {draw_graph option} vertex_coloring
3355 Specifies coloring of the vertices. The coloring @var{col} must be
3356 specified in the format as returned by @var{vertex_coloring}.
3357
3358 @opencatbox{Categories:}
3359 @category{Package graphs}
3360 @category{Package graphs - draw_graphs options}
3361 @closecatbox
3362 @end defvr
3363
3364 @anchor{edge_color }
3365 @defvr {draw_graph option} edge_color
3366 The color used for displaying edges.
3367
3368 @opencatbox{Categories:}
3369 @category{Package graphs}
3370 @category{Package graphs - draw_graphs options}
3371 @closecatbox
3372 @end defvr
3373
3374 @anchor{edge_width}
3375 @defvr {draw_graph option} edge_width
3376 The width of edges.
3377
3378 @opencatbox{Categories:}
3379 @category{Package graphs}
3380 @category{Package graphs - draw_graphs options}
3381 @closecatbox
3382 @end defvr
3383
3384 @anchor{edge_type}
3385 @defvr {draw_graph option} edge_type
3386 Defines how edges are displayed. See the @var{line_type} option for the
3387 @code{draw} package.
3388
3389 @opencatbox{Categories:}
3390 @category{Package graphs}
3391 @category{Package graphs - draw_graphs options}
3392 @closecatbox
3393 @end defvr
3394
3395 @anchor{show_edges}
3396 @defvr {draw_graph option} show_edges
3397 Display edges specified in the list @var{e_list} using a different
3398 color.
3399
3400 @opencatbox{Categories:}
3401 @category{Package graphs}
3402 @category{Package graphs - draw_graphs options}
3403 @closecatbox
3404 @end defvr
3405
3406 @anchor{show_edge_color}
3407 @defvr {draw_graph option} show_edge_color
3408 The color used for displaying edges in the @var{show_edges} list.
3409
3410 @opencatbox{Categories:}
3411 @category{Package graphs}
3412 @category{Package graphs - draw_graphs options}
3413 @closecatbox
3414 @end defvr
3415
3416 @anchor{show_edge_width}
3417 @defvr {draw_graph option} show_edge_width
3418 The width of edges in @var{show_edges}.
3419
3420 @opencatbox{Categories:}
3421 @category{Package graphs}
3422 @category{Package graphs - draw_graphs options}
3423 @closecatbox
3424 @end defvr
3425
3426 @anchor{show_edge_type}
3427 @defvr {draw_graph option} show_edge_type
3428 Defines how edges in @var{show_edges} are displayed. See the
3429 @var{line_type} option for the @code{draw} package.
3430
3431 @opencatbox{Categories:}
3432 @category{Package graphs}
3433 @category{Package graphs - draw_graphs options}
3434 @closecatbox
3435 @end defvr
3436
3437 @anchor{edge_partition}
3438 @defvr {draw_graph option} edge_partition
3439 A partition @code{[[e1,e2,...],...,[ek,...,em]]} of edges of the
3440 graph. The edges of each list in the partition will be drawn using a
3441 different color.
3442
3443 @opencatbox{Categories:}
3444 @category{Package graphs}
3445 @category{Package graphs - draw_graphs options}
3446 @closecatbox
3447 @end defvr
3448
3449 @anchor{edge_coloring_variable}
3450 @defvr {draw_graph option} edge_coloring
3451 The coloring of edges. The coloring must be specified in the
3452 format as returned by the function @var{edge_coloring}.
3453
3454 @opencatbox{Categories:}
3455 @category{Package graphs}
3456 @category{Package graphs - draw_graphs options}
3457 @closecatbox
3458 @end defvr
3459
3460 @anchor{redraw }
3461 @defvr {draw_graph option} redraw
3462 Default value: @var{false}
3463
3464 If @code{true}, vertex positions are recomputed even if the positions
3465 have been saved from a previous drawing of the graph.
3466
3467 @opencatbox{Categories:}
3468 @category{Package graphs}
3469 @category{Package graphs - draw_graphs options}
3470 @closecatbox
3471 @end defvr
3472
3473 @anchor{head_angle_graphs}
3474 @defvr {draw_graph option} head_angle
3475 Default value: 15
3476
3477 The angle for the arrows displayed on arcs (in directed graphs).
3478
3479 @opencatbox{Categories:}
3480 @category{Package graphs}
3481 @category{Package graphs - draw_graphs options}
3482 @closecatbox
3483 @end defvr
3484
3485 @anchor{head_length_graphs}
3486 @defvr {draw_graph option} head_length
3487 Default value: 0.1
3488
3489 The length for the arrows displayed on arcs (in directed graphs).
3490
3491 @opencatbox{Categories:}
3492 @category{Package graphs}
3493 @category{Package graphs - draw_graphs options}
3494 @closecatbox
3495 @end defvr
3496
3497 @anchor{spring_embedding_depth}
3498 @defvr {draw_graph option} spring_embedding_depth
3499 Default value: 50
3500
3501 The number of iterations in the spring embedding graph drawing
3502 algorithm.
3503
3504 @opencatbox{Categories:}
3505 @category{Package graphs}
3506 @category{Package graphs - draw_graphs options}
3507 @closecatbox
3508 @end defvr
3509
3510 @anchor{terminal_graphs}
3511 @defvr {draw_graph option} terminal
3512 The terminal used for drawing (see the @var{terminal} option in the
3513 @code{draw} package).
3514
3515 @opencatbox{Categories:}
3516 @category{Package graphs}
3517 @category{Package graphs - draw_graphs options}
3518 @closecatbox
3519 @end defvr
3520
3521 @anchor{file_name_graphs}
3522 @defvr {draw_graph option} file_name
3523 The filename of the drawing if terminal is not screen.
3524
3525 @opencatbox{Categories:}
3526 @category{Package graphs}
3527 @category{Package graphs - draw_graphs options}
3528 @closecatbox
3529 @end defvr
3530
3531 @anchor{program}
3532 @defvr {draw_graph option} program
3533 Defines the program used for positioning vertices of the graph. Can be
3534 one of the graphviz programs (dot, neato, twopi, circ, fdp),
3535 @var{circular}, @var{spring_embedding} or
3536 @var{planar_embedding}. @var{planar_embedding} is only available for
3537 2-connected planar graphs. When @code{program=spring_embedding}, a set
3538 of vertices with fixed position can be specified with the
3539 @var{fixed_vertices} option.
3540
3541 @opencatbox{Categories:}
3542 @category{Package graphs}
3543 @category{Package graphs - draw_graphs options}
3544 @closecatbox
3545 @end defvr
3546
3547 @anchor{fixed_vertices}
3548 @defvr {draw_graph option} fixed_vertices
3549 Specifies a list of vertices which will have positions fixed along a regular polygon.
3550 Can be used when @code{program=spring_embedding}.
3551
3552 @opencatbox{Categories:}
3553 @category{Package graphs}
3554 @category{Package graphs - draw_graphs options}
3555 @closecatbox
3556 @end defvr
3557
3558 @anchor{vertices_to_path}
3559 @deffn {Function} vertices_to_path (@var{v_list})
3560 Converts a list @var{v_list} of vertices to a list of edges of the path
3561 defined by @var{v_list}.
3562
3563 @opencatbox{Categories:}
3564 @category{Package graphs}
3565 @closecatbox
3566 @end deffn
3567
3568 @anchor{vertices_to_cycle}
3569 @deffn {Function} vertices_to_cycle (@var{v_list})
3570 Converts a list @var{v_list} of vertices to a list of edges of the cycle
3571 defined by @var{v_list}.
3572
3573 @opencatbox{Categories:}
3574 @category{Package graphs}
3575 @closecatbox
3576 @end deffn