1=pod 2 3=head1 NAME 4 5Graph - graph data structures and algorithms 6 7=head1 SYNOPSIS 8 9 use Graph; 10 my $g0 = Graph->new; # A directed graph. 11 12 use Graph::Directed; 13 my $g1 = Graph::Directed->new; # A directed graph. 14 15 use Graph::Undirected; 16 my $g2 = Graph::Undirected->new; # An undirected graph. 17 18 $g->add_edge(...); 19 $g->has_edge(...) 20 $g->any_edge(...) 21 $g->delete_edge(...); 22 23 $g->add_vertex(...); 24 $g->has_vertex(...); 25 $g->delete_vertex(...); 26 27 $g->vertices(...) 28 $g->edges(...) 29 30 # And many, many more, see below. 31 32=head1 DESCRIPTION 33 34=head2 Non-Description 35 36This module is not for B<drawing> or B<rendering> any sort of 37I<graphics> or I<images>, business, visualization, or otherwise. 38 39=head2 Description 40 41Instead, this module is for creating I<abstract data structures> 42called graphs, and for doing various operations on those. 43 44=head2 Perl 5.6.0 minimum 45 46The implementation depends on a Perl feature called "weak references" 47and Perl 5.6.0 was the first to have those. 48 49=head2 Constructors 50 51=over 4 52 53=item new 54 55Create an empty graph. 56 57=item Graph->new(%options) 58 59The options are a hash with option names as the hash keys and the option 60values as the hash values. 61 62The following options are available: 63 64=over 8 65 66=item directed 67 68A boolean option telling that a directed graph should be created. 69Often somewhat redundant because a directed graph is the default 70for the Graph class or one could simply use the C<new()> constructor 71of the Graph::Directed class. 72 73You can test the directness of a graph with $g->is_directed() and 74$g->is_undirected(). 75 76=item undirected 77 78A boolean option telling that an undirected graph should be created. 79One could also use the C<new()> constructor the Graph::Undirected class 80instead. 81 82Note that while often it is possible to think of undirected graphs as 83bidirectional graphs, or as directed graphs with edges going both ways, 84in this module directed graphs and undirected graphs are two different 85things that often behave differently. 86 87You can test the directness of a graph with $g->is_directed() and 88$g->is_undirected(). 89 90=item refvertexed 91 92=item refvertexed_stringified 93 94If you want to use references (including Perl objects) as vertices, 95use C<refvertexed>. 96 97Note that using C<refvertexed> means that internally the memory 98address of the reference (for example, a Perl object) is used as the 99"identifier" of the vertex, not the stringified form of the reference, 100even if you have defined your own stringification using C<overload>. 101 102This avoids the problem of the stringified references potentially 103being identical (because they are identical in value, for example) 104even if the references are different. If you really want to use 105references B<and> their stringified forms as the identities, use the 106C<refvertexed_stringified>. But please do B<not> stringify different 107objects to the same stringified value. 108 109=item unionfind 110 111If the graph is undirected, you can specify the C<unionfind> parameter 112to use the so-called union-find scheme to speed up the computation of 113I<connected components> of the graph (see L</is_connected>, 114L</connected_components>, L</connected_component_by_vertex>, 115L</connected_component_by_index>, and L</same_connected_components>). 116If C<unionfind> is used, adding edges (and vertices) becomes slower, 117but connectedness queries become faster. You B<must not> delete edges or 118vertices of an unionfind graph, only add them. You can test a graph for 119"union-findness" with 120 121=item has_union_find 122 123Returns true if the graph was created with a true C<unionfind> parameter. 124 125=item vertices 126 127An array reference of vertices to add. 128 129=item edges 130 131An array reference of array references of edge vertices to add. 132 133=back 134 135=item copy 136 137=item copy_graph 138 139 my $c = $g->copy_graph; 140 141Create a shallow copy of the structure (vertices and edges) of the 142graph. If you want a deep copy that includes attributes, see 143L</deep_copy>. The copy will have the same directedness as the 144original. 145 146Also the following vertex/edge attributes are copied: 147 148 refvertexed/countvertexed/multivertexed 149 hyperedged/countedged/multiedged 150 151B<NOTE>: You can get an even shallower copy of a graph by 152 153 my $c = $g->new; 154 155This will copy only the graph properties (directed, and so forth), 156but none of the vertices or edges. 157 158As of 0.9712, you can also copy the graph properties of an existing 159object, I<but> with overrides: 160 161 my $c = $g->new(multiedged => 0); 162 163=item deep_copy 164 165=item deep_copy_graph 166 167 my $c = $g->deep_copy_graph; 168 169Create a deep copy of the graph (vertices, edges, and attributes) of 170the graph. If you want a shallow copy that does not include 171attributes, see L</copy>. 172 173Note that copying code references only works with Perls 5.8 or later, 174and even then only if B::Deparse can reconstruct your code. This 175functionality uses either Storable or Data::Dumper behind the scenes, 176depending on which is available (Storable is preferred). 177 178If your vertices are references, the copied graph will have its 179connections fixed up. Support for this is new as of 0.9723, so please 180report any problems. 181 182=item undirected_copy 183 184=item undirected_copy_graph 185 186 my $c = $g->undirected_copy_graph; 187 188Create an undirected shallow copy (vertices and edges) of the directed graph 189so that for any directed edge (u, v) there is an undirected edge (u, v). 190 191=item undirected_copy_clear_cache 192 193 @path = $g->undirected_copy_clear_cache; 194 195See L</"Clearing cached results">. 196 197=item directed_copy 198 199=item directed_copy_graph 200 201 my $c = $g->directed_copy_graph; 202 203Create a directed shallow copy (vertices and edges) of the undirected graph 204so that for any undirected edge (u, v) there are two directed edges (u, v) 205and (v, u). 206 207=item transpose 208 209=item transpose_graph 210 211 my $t = $g->transpose_graph; 212 213Create a directed shallow transposed copy (vertices and edges) of the 214directed graph so that for any directed edge (u, v) there is a directed 215edge (v, u). 216 217You can also transpose a single edge with 218 219=over 8 220 221=item transpose_edge 222 223 $g->transpose_edge($u, $v) 224 225=back 226 227=item complete_graph 228 229=item complete 230 231 my $c = $g->complete_graph; 232 233Create a complete graph that has the same vertices as the original graph. 234A complete graph has an edge between every pair of vertices. 235 236=item complement_graph 237 238=item complement 239 240 my $c = $g->complement_graph; 241 242Create a complement graph that has the same vertices as the original graph. 243A complement graph has an edge (u,v) if and only if the original 244graph does not have edge (u,v). 245 246=item subgraph 247 248 my $c = $g->subgraph(\@src, \@dst); 249 my $c = $g->subgraph(\@src); 250 251Creates a subgraph of a given graph. The created subgraph has the 252same graph properties (directedness, and so forth) as the original 253graph, but none of the attributes (graph, vertex, or edge). 254 255A vertex is added to the subgraph if it is in the original graph. 256 257An edge is added to the subgraph if there is an edge in the original 258graph that starts from the C<src> set of vertices and ends in the 259C<dst> set of vertices. 260 261You can leave out C<dst> in which case C<dst> is assumed to be the same: 262this is called a I<vertex-induced subgraph>. 263 264=back 265 266See also L</random_graph> for a random constructor. 267 268=head2 Basics 269 270=over 4 271 272=item add_vertex 273 274 $g->add_vertex($v) 275 276Add the vertex to the graph. Returns the graph. 277 278By default idempotent, but a graph can be created I<countvertexed>. 279 280A vertex is also known as a I<node>. 281 282Adding C<undef> as vertex is not allowed. 283 284Note that unless you have isolated vertices (or I<countvertexed> 285vertices), you do not need to explicitly use C<add_vertex> since 286L</add_edge> will implicitly add its vertices. 287 288=item add_edge 289 290 $g->add_edge($u, $v) 291 292Add the edge to the graph. Implicitly first adds the vertices if the 293graph does not have them. Returns the graph. 294 295By default idempotent, but a graph can be created I<countedged>. 296 297An edge is also known as an I<arc>. 298 299For a hypergraph, the interface is different: if undirected, give a list 300of one or more vertices. If directed, give a list of two array-refs of 301vertices. As conceptually these are sets, the ordering of the contents 302is not important. 303 304=item has_vertex 305 306 $g->has_vertex($v) 307 308Return true if the vertex exists in the graph, false otherwise. 309 310=item has_edge 311 312 $g->has_edge($u, $v) 313 314Return true if the edge exactly as specified exists in the graph, 315false otherwise. 316 317Hyperedges which contain all the given vertices (in the right places 318if directed), but which also have others will not match. 319 320=item any_edge 321 322 $g->any_edge($u, $v) 323 324Return true if any edge in the graph connects the first vertex to the second, 325false otherwise. Note this is a different question from C<has_edge>. It 326will give the same result as checking the first vertex's L</successors> 327to see if any match the second one, but in a more efficient way. 328 329=item delete_vertex 330 331 $g->delete_vertex($v) 332 333Delete the vertex from the graph. Returns the graph, even if the 334vertex did not exist in the graph. 335 336If the graph has been created I<multivertexed> or I<countvertexed> 337and a vertex has been added multiple times, the vertex will require 338at least an equal number of deletions to become completely deleted. 339 340=item delete_vertices 341 342 $g->delete_vertices($v1, $v2, ...) 343 344Delete the vertices from the graph. Returns the graph, even if none 345of the vertices existed in the graph. 346 347If the graph has been created I<multivertexed> or I<countvertexed> 348and a vertex has been added multiple times, the vertex will require 349at least an equal number of deletions to become completely deleted. 350 351=item delete_edge 352 353 $g->delete_edge($u, $v) 354 355Delete the edge from the graph. Returns the graph, even 356if the edge did not exist in the graph. 357 358If the graph has been created I<multiedged> or I<countedged> 359and an edge has been added multiple times, the edge will require 360at least an equal number of deletions to become completely deleted. 361 362=item delete_edges 363 364 $g->delete_edges($u1, $v1, $u2, $v2, ...) 365 366Delete the edges from the graph. Returns the graph, even if none 367of the edges existed in the graph. 368 369If the graph has been created I<multiedged> or I<countedged> 370and an edge has been added multiple times, the edge will require 371at least an equal number of deletions to become completely deleted. 372 373=back 374 375=head2 Displaying 376 377Graphs have stringification overload, so you can do things like 378 379 print "The graph is $g\n" 380 381One-way (directed, unidirected) edges are shown as '-', two-way 382(undirected, bidirected) edges are shown as '='. If you want to, 383you can call the stringification via the method 384 385=over 4 386 387=item stringify 388 389=back 390 391=head2 Boolean 392 393Graphs have boolifying overload, so you can do things like 394 395 if ($g) { print "The graph is: $g\n" } 396 397which works even if the graph is empty. In fact, the boolify 398always returns true. If you want to test for example for vertices, 399test for vertices. 400 401=over 4 402 403=item boolify 404 405=back 406 407=head2 Comparing 408 409Testing for equality can be done either by the overloaded C<eq> 410operator 411 412 $g eq "a-b,a-c,d" 413 414or by the method 415 416=over 4 417 418=item eq 419 420 $g->eq("a-b,a-c,d") 421 422=back 423 424The equality testing compares the stringified forms, and therefore it 425assumes total equality, not isomorphism: all the vertices must be 426named the same, and they must have identical edges between them. 427 428For unequality there are correspondingly the overloaded C<ne> 429operator and the method 430 431=over 4 432 433=item ne 434 435 $g->ne("a-b,a-c,d") 436 437=back 438 439See also L</Isomorphism>. 440 441=head2 Paths and Cycles 442 443Paths and cycles are simple extensions of edges: paths are edges 444starting from where the previous edge ended, and cycles are paths 445returning back to the start vertex of the first edge. 446 447=over 4 448 449=item add_path 450 451 $g->add_path($a, $b, $c, ..., $x, $y, $z) 452 453Add the edges $a-$b, $b-$c, ..., $x-$y, $y-$z to the graph. 454Returns the graph. 455 456=item has_path 457 458 $g->has_path($a, $b, $c, ..., $x, $y, $z) 459 460Return true if the graph has all the edges $a-$b, $b-$c, ..., $x-$y, $y-$z, 461false otherwise. 462 463=item delete_path 464 465 $g->delete_path($a, $b, $c, ..., $x, $y, $z) 466 467Delete all the edges $a-$b, $b-$c, ..., $x-$y, $y-$z 468(regardless of whether they exist or not). Returns the graph. 469 470=item add_cycle 471 472 $g->add_cycle($a, $b, $c, ..., $x, $y, $z) 473 474Add the edges $a-$b, $b-$c, ..., $x-$y, $y-$z, and $z-$a to the graph. 475Returns the graph. 476 477=item has_cycle 478 479=item has_this_cycle 480 481 $g->has_cycle($a, $b, $c, ..., $x, $y, $z) 482 483Return true if the graph has all the edges $a-$b, $b-$c, ..., $x-$y, $y-$z, 484and $z-$a, false otherwise. 485 486B<NOTE:> This does not I<detect> cycles, see L</has_a_cycle> and 487L</find_a_cycle>. 488 489=item delete_cycle 490 491 $g->delete_cycle($a, $b, $c, ..., $x, $y, $z) 492 493Delete all the edges $a-$b, $b-$c, ..., $x-$y, $y-$z, and $z-$a 494(regardless of whether they exist or not). Returns the graph. 495 496=item has_a_cycle 497 498 $g->has_a_cycle 499 500Returns true if the graph has a cycle, false if not. 501 502=item find_a_cycle 503 504 $g->find_a_cycle 505 506Returns a cycle if the graph has one (as a list of vertices), an empty 507list if no cycle can be found. 508 509Note that this just returns the vertices of I<a cycle>: not any 510particular cycle, just the first one it finds. A repeated call 511might find the same cycle, or it might find a different one, and 512you cannot call this repeatedly to find all the cycles. 513 514=back 515 516=head2 Graph Types 517 518=over 4 519 520=item is_simple_graph 521 522 $g->is_simple_graph 523 524Return true if the graph has no multiedges, false otherwise. 525 526=item is_pseudo_graph 527 528 $g->is_pseudo_graph 529 530Return true if the graph has any multiedges or any self-loops, 531false otherwise. 532 533=item is_multi_graph 534 535 $g->is_multi_graph 536 537Return true if the graph has any multiedges but no self-loops, 538false otherwise. 539 540=item is_directed_acyclic_graph 541 542=item is_dag 543 544 $g->is_directed_acyclic_graph 545 $g->is_dag 546 547Return true if the graph is directed and acyclic, false otherwise. 548 549=item is_cyclic 550 551 $g->is_cyclic 552 553Return true if the graph is cyclic (contains at least one cycle). 554(This is identical to C<has_a_cycle>.) 555 556To find at least one such cycle, see L</find_a_cycle>. 557 558=item is_acyclic 559 560Return true if the graph is acyclic (does not contain any cycles). 561 562=back 563 564To find a cycle, use L</find_a_cycle>. 565 566=head2 Transitivity 567 568=over 4 569 570=item is_transitive 571 572 $g->is_transitive 573 574Return true if the graph is transitive, false otherwise. 575 576=item TransitiveClosure_Floyd_Warshall 577 578=item transitive_closure 579 580 $tcg = $g->TransitiveClosure_Floyd_Warshall 581 582Return the transitive closure graph of the graph. 583 584=item transitive_closure_matrix_clear_cache 585 586 $g->transitive_closure_matrix_clear_cache 587 588See L</"Clearing cached results">. 589 590=back 591 592You can query the reachability from $u to $v with 593 594=over 4 595 596=item is_reachable 597 598 $tcg->is_reachable($u, $v) 599 600=back 601 602See L<Graph::TransitiveClosure> for more information about creating 603and querying transitive closures. 604 605With 606 607=over 4 608 609=item transitive_closure_matrix 610 611 $tcm = $g->transitive_closure_matrix; 612 613=back 614 615you can (create if not existing and) query the transitive closure 616matrix that underlies the transitive closure graph. See 617L<Graph::TransitiveClosure::Matrix> for more information. 618 619=head2 Mutators 620 621=over 4 622 623=item add_vertices 624 625 $g->add_vertices('d', 'e', 'f') 626 627Add zero or more vertices to the graph. Returns the graph. 628 629=item add_edges 630 631 $g->add_edges(['d', 'e'], ['f', 'g']) 632 $g->add_edges(qw(d e f g)); 633 634Add zero or more edges to the graph. The edges are specified as 635a list of array references, or as a list of vertices where the 636even (0th, 2nd, 4th, ...) items are start vertices and the odd 637(1st, 3rd, 5th, ...) are the corresponding end vertices. 638Returns the graph. 639 640For a hypergraph, each item in this list must be an array-ref of arguments 641suitable for C<add_edge> - so for undirected, of vertices; 642for directed, of two array-refs of vertices. 643 644=item rename_vertex 645 646 $g->rename_vertex('d', 'e') 647 648Renames a vertex. It retains all of its edges. Throws exception if 649doesn't exist. 650 651Returns the graph. 652 653=item rename_vertices 654 655 $g->rename_vertices(sub { uc $_[0] }) 656 657Calls a function for each vertex-name, renaming it to the return value. 658 659Returns the graph. 660 661=item ingest 662 663 $g->ingest($g2) 664 665Ingests all the vertices and edges of the given graph, including 666attributes. Returns the ingesting graph. 667 668=back 669 670=head2 Accessors 671 672=over 4 673 674=item is_directed 675 676=item directed 677 678 $g->is_directed() 679 $g->directed() 680 681Return true if the graph is directed, false otherwise. 682 683=item is_undirected 684 685=item undirected 686 687 $g->is_undirected() 688 $g->undirected() 689 690Return true if the graph is undirected, false otherwise. 691 692=item is_refvertexed 693 694=item is_refvertexed_stringified 695 696=item refvertexed 697 698=item refvertexed_stringified 699 700Return true if the graph can handle references (including Perl objects) 701as vertices. 702 703=item vertices 704 705 my $V = $g->vertices 706 my @V = $g->vertices 707 708In scalar context, return the number of vertices in the graph. 709In list context, return the vertices, in no particular order. 710 711=item has_vertices 712 713 $g->has_vertices() 714 715Return true if the graph has any vertices, false otherwise. 716 717=item edges 718 719 my $E = $g->edges 720 my @E = $g->edges 721 722In scalar context, return the number of edges in the graph. 723In list context, return the edges, in no particular order. 724I<The edges are returned as anonymous arrays listing the vertices.> 725 726=item has_edges 727 728 $g->has_edges() 729 730Return true if the graph has any edges, false otherwise. 731 732=item is_connected 733 734 $g->is_connected 735 736For an undirected graph, return true if the graph is connected, false 737otherwise. Being connected means that from every vertex it is possible 738to reach every other vertex. 739 740If the graph has been created with a true C<unionfind> parameter, 741the time complexity is (essentially) O(V), otherwise O(V log V). 742 743See also L</connected_components>, L</connected_component_by_index>, 744L</connected_component_by_vertex>, and L</same_connected_components>, 745and L</biconnectivity>. 746 747For directed graphs, see L</is_strongly_connected> 748and L</is_weakly_connected>. 749 750=item connected_components 751 752 @cc = $g->connected_components() 753 754For an undirected graph, returns the vertices of the connected 755components of the graph as a list of anonymous arrays. The ordering 756of the anonymous arrays or the ordering of the vertices inside the 757anonymous arrays (the components) is undefined. 758 759For directed graphs, see L</strongly_connected_components> 760and L</weakly_connected_components>. 761 762=item connected_component_by_vertex 763 764 $i = $g->connected_component_by_vertex($v) 765 766For an undirected graph, return an index identifying the connected 767component the vertex belongs to, the indexing starting from zero. 768 769For the inverse, see L</connected_component_by_index>. 770 771If the graph has been created with a true C<unionfind> parameter, 772the time complexity is (essentially) O(1), otherwise O(V log V). 773 774See also L</biconnectivity>. 775 776For directed graphs, see L</strongly_connected_component_by_vertex> 777and L</weakly_connected_component_by_vertex>. 778 779=item connected_component_by_index 780 781 @v = $g->connected_component_by_index($i) 782 783For an undirected graph, return the vertices of the ith connected 784component, the indexing starting from zero. The order of vertices is 785undefined, while the order of the connected components is same as from 786connected_components(). 787 788For the inverse, see L</connected_component_by_vertex>. 789 790For directed graphs, see L</strongly_connected_component_by_index> 791and L</weakly_connected_component_by_index>. 792 793=item same_connected_components 794 795 $g->same_connected_components($u, $v, ...) 796 797For an undirected graph, return true if the vertices are in the same 798connected component. 799 800If the graph has been created with a true C<unionfind> parameter, 801the time complexity is (essentially) O(1), otherwise O(V log V). 802 803For directed graphs, see L</same_strongly_connected_components> 804and L</same_weakly_connected_components>. 805 806=item connected_graph 807 808 $cg = $g->connected_graph 809 810For an undirected graph, return its connected graph. 811 812=item connectivity_clear_cache 813 814 $g->connectivity_clear_cache 815 816See L</"Clearing cached results">. 817 818See L</"Connected Graphs and Their Components"> for further discussion. 819 820=item biconnectivity 821 822 my ($ap, $bc, $br) = $g->biconnectivity 823 824For an undirected graph, return the various biconnectivity components 825of the graph: the articulation points (cut vertices), biconnected 826components, and bridges. 827 828Note: currently only handles connected graphs. 829 830=item is_biconnected 831 832 $g->is_biconnected 833 834For an undirected graph, return true if the graph is biconnected 835(if it has no articulation points, also known as cut vertices). 836 837=item is_edge_connected 838 839 $g->is_edge_connected 840 841For an undirected graph, return true if the graph is edge-connected 842(if it has no bridges). 843 844Note: more precisely, this would be called is_edge_biconnected, 845since there is a more general concept of being k-connected. 846 847=item is_edge_separable 848 849 $g->is_edge_separable 850 851For an undirected graph, return true if the graph is edge-separable 852(if it has bridges). 853 854Note: more precisely, this would be called is_edge_biseparable, 855since there is a more general concept of being k-connected. 856 857=item articulation_points 858 859=item cut_vertices 860 861 $g->articulation_points 862 863For an undirected graph, return the articulation points (cut vertices) 864of the graph as a list of vertices. The order is undefined. 865 866=item biconnected_components 867 868 $g->biconnected_components 869 870For an undirected graph, return the biconnected components of the 871graph as a list of anonymous arrays of vertices in the components. 872The ordering of the anonymous arrays or the ordering of the vertices 873inside the anonymous arrays (the components) is undefined. Also note 874that one vertex can belong to more than one biconnected component. 875 876=item biconnected_component_by_vertex 877 878 $i = $g->biconnected_component_by_index($v) 879 880For an undirected graph, return the indices identifying the biconnected 881components the vertex belongs to, the indexing starting from zero. 882The order of of the components is undefined. 883 884For the inverse, see L</connected_component_by_index>. 885 886For directed graphs, see L</strongly_connected_component_by_index> 887and L</weakly_connected_component_by_index>. 888 889=item biconnected_component_by_index 890 891 @v = $g->biconnected_component_by_index($i) 892 893For an undirected graph, return the vertices in the ith biconnected 894component of the graph as an anonymous arrays of vertices in the 895component. The ordering of the vertices within a component is 896undefined. Also note that one vertex can belong to more than one 897biconnected component. 898 899=item same_biconnected_components 900 901 $g->same_biconnected_components($u, $v, ...) 902 903For an undirected graph, return true if the vertices are in the same 904biconnected component. 905 906=item biconnected_graph 907 908 $bcg = $g->biconnected_graph 909 910For an undirected graph, return its biconnected graph. 911 912See L</"Connected Graphs and Their Components"> for further discussion. 913 914=item bridges 915 916 $g->bridges 917 918For an undirected graph, return the bridges of the graph as a list of 919anonymous arrays of vertices in the bridges. The order of bridges and 920the order of vertices in them is undefined. 921 922=item biconnectivity_clear_cache 923 924 $g->biconnectivity_clear_cache 925 926See L</"Clearing cached results">. 927 928=item strongly_connected 929 930=item is_strongly_connected 931 932 $g->is_strongly_connected 933 934For a directed graph, return true if the directed graph is strongly 935connected, false if not. 936 937See also L</is_weakly_connected>. 938 939For undirected graphs, see L</is_connected>, or L</is_biconnected>. 940 941=item strongly_connected_component_by_vertex 942 943 $i = $g->strongly_connected_component_by_vertex($v) 944 945For a directed graph, return an index identifying the strongly 946connected component the vertex belongs to, the indexing starting from 947zero. 948 949For the inverse, see L</strongly_connected_component_by_index>. 950 951See also L</weakly_connected_component_by_vertex>. 952 953For undirected graphs, see L</connected_components> or 954L</biconnected_components>. 955 956=item strongly_connected_component_by_index 957 958 @v = $g->strongly_connected_component_by_index($i) 959 960For a directed graph, return the vertices of the ith connected 961component, the indexing starting from zero. The order of vertices 962within a component is undefined, while the order of the connected 963components is as from strongly_connected_components(). 964 965For the inverse, see L</strongly_connected_component_by_vertex>. 966 967For undirected graphs, see L</weakly_connected_component_by_index>. 968 969=item same_strongly_connected_components 970 971 $g->same_strongly_connected_components($u, $v, ...) 972 973For a directed graph, return true if the vertices are in the same 974strongly connected component. 975 976See also L</same_weakly_connected_components>. 977 978For undirected graphs, see L</same_connected_components> or 979L</same_biconnected_components>. 980 981=item strong_connectivity_clear_cache 982 983 $g->strong_connectivity_clear_cache 984 985See L</"Clearing cached results">. 986 987=item weakly_connected 988 989=item is_weakly_connected 990 991 $g->is_weakly_connected 992 993For a directed graph, return true if the directed graph is weakly 994connected, false if not. 995 996Weakly connected graph is also known as I<semiconnected> graph. 997 998See also L</is_strongly_connected>. 999 1000For undirected graphs, see L</is_connected> or L</is_biconnected>. 1001 1002=item weakly_connected_components 1003 1004 @wcc = $g->weakly_connected_components() 1005 1006For a directed graph, returns the vertices of the weakly connected 1007components of the graph as a list of anonymous arrays. The ordering 1008of the anonymous arrays or the ordering of the vertices inside the 1009anonymous arrays (the components) is undefined. 1010 1011See also L</strongly_connected_components>. 1012 1013For undirected graphs, see L</connected_components> or 1014L</biconnected_components>. 1015 1016=item weakly_connected_component_by_vertex 1017 1018 $i = $g->weakly_connected_component_by_vertex($v) 1019 1020For a directed graph, return an index identifying the weakly connected 1021component the vertex belongs to, the indexing starting from zero. 1022 1023For the inverse, see L</weakly_connected_component_by_index>. 1024 1025For undirected graphs, see L</connected_component_by_vertex> 1026and L</biconnected_component_by_vertex>. 1027 1028=item weakly_connected_component_by_index 1029 1030 @v = $g->weakly_connected_component_by_index($i) 1031 1032For a directed graph, return the vertices of the ith weakly connected 1033component, the indexing starting zero. The order of vertices within 1034a component is undefined, while the order of the weakly connected 1035components is same as from weakly_connected_components(). 1036 1037For the inverse, see L</weakly_connected_component_by_vertex>. 1038 1039For undirected graphs, see L<connected_component_by_index> 1040and L<biconnected_component_by_index>. 1041 1042=item same_weakly_connected_components 1043 1044 $g->same_weakly_connected_components($u, $v, ...) 1045 1046Return true if the vertices are in the same weakly connected component. 1047 1048=item weakly_connected_graph 1049 1050 $wcg = $g->weakly_connected_graph 1051 1052For a directed graph, return its weakly connected graph. 1053 1054For undirected graphs, see L</connected_graph> and L</biconnected_graph>. 1055 1056=item strongly_connected_components 1057 1058 my @scc = $g->strongly_connected_components; 1059 1060For a directed graph, return the strongly connected components as a 1061list of anonymous arrays. The elements in the anonymous arrays are 1062the vertices belonging to the strongly connected component; both the 1063elements and the components are in no particular order. 1064 1065Note that strongly connected components can have single-element 1066components even without self-loops: if a vertex is any of I<isolated>, 1067I<sink>, or a I<source>, the vertex is alone in its own strong component. 1068 1069See also L</weakly_connected_components>. 1070 1071For undirected graphs, see L</connected_components>, 1072or see L</biconnected_components>. 1073 1074=item strongly_connected_graph 1075 1076 my $scg = $g->strongly_connected_graph; 1077 1078See L</"Connected Graphs and Their Components"> for further discussion. 1079 1080Strongly connected graphs are also known as I<kernel graphs>. 1081 1082See also L</weakly_connected_graph>. 1083 1084For undirected graphs, see L</connected_graph>, or L</biconnected_graph>. 1085 1086=item is_sink_vertex 1087 1088 $g->is_sink_vertex($v) 1089 1090Return true if the vertex $v is a sink vertex, false if not. A sink 1091vertex is defined as a vertex with predecessors but no successors: 1092this definition means that isolated vertices are not sink vertices. 1093If you want also isolated vertices, use is_successorless_vertex(). 1094 1095=item is_source_vertex 1096 1097 $g->is_source_vertex($v) 1098 1099Return true if the vertex $v is a source vertex, false if not. A source 1100vertex is defined as a vertex with successors but no predecessors: 1101the definition means that isolated vertices are not source vertices. 1102If you want also isolated vertices, use is_predecessorless_vertex(). 1103 1104=item is_successorless_vertex 1105 1106 $g->is_successorless_vertex($v) 1107 1108Return true if the vertex $v has no successors (no edges 1109leaving the vertex), false if it has. 1110 1111Isolated vertices will return true: if you do not want this, 1112use is_sink_vertex(). 1113 1114=item is_successorful_vertex 1115 1116 $g->is_successorful_vertex($v) 1117 1118Return true if the vertex $v has successors, false if not. 1119 1120=item is_predecessorless_vertex 1121 1122 $g->is_predecessorless_vertex($v) 1123 1124Return true if the vertex $v has no predecessors (no edges 1125entering the vertex), false if it has. 1126 1127Isolated vertices will return true: if you do not want this, 1128use is_source_vertex(). 1129 1130=item is_predecessorful_vertex 1131 1132 $g->is_predecessorful_vertex($v) 1133 1134Return true if the vertex $v has predecessors, false if not. 1135 1136=item is_isolated_vertex 1137 1138 $g->is_isolated_vertex($v) 1139 1140Return true if the vertex $v is an isolated vertex: no successors 1141and no predecessors. 1142 1143=item is_interior_vertex 1144 1145 $g->is_interior_vertex($v) 1146 1147Return true if the vertex $v is an interior vertex: both successors 1148and predecessors. 1149 1150=item is_exterior_vertex 1151 1152 $g->is_exterior_vertex($v) 1153 1154Return true if the vertex $v is an exterior vertex: has either no 1155successors or no predecessors, or neither. 1156 1157=item is_self_loop_vertex 1158 1159 $g->is_self_loop_vertex($v) 1160 1161Return true if the vertex $v is a self loop vertex: has an edge 1162from itself to itself. 1163 1164For an undirected hypergraph, only true if an edge has the vertex as 1165its sole participant. 1166 1167=item sink_vertices 1168 1169 @v = $g->sink_vertices() 1170 1171Return the sink vertices of the graph. 1172In scalar context return the number of sink vertices. 1173See L</is_sink_vertex> for the definition of a sink vertex. 1174 1175=item source_vertices 1176 1177 @v = $g->source_vertices() 1178 1179Return the source vertices of the graph. 1180In scalar context return the number of source vertices. 1181See L</is_source_vertex> for the definition of a source vertex. 1182 1183=item successorful_vertices 1184 1185 @v = $g->successorful_vertices() 1186 1187Return the successorful vertices of the graph. 1188In scalar context return the number of successorful vertices. 1189 1190=item successorless_vertices 1191 1192 @v = $g->successorless_vertices() 1193 1194Return the successorless vertices of the graph. 1195In scalar context return the number of successorless vertices. 1196 1197=item successors 1198 1199 @s = $g->successors($v) 1200 1201Return the immediate successor vertices of the vertex. 1202 1203See also L</all_successors>, L</all_neighbours>, and L</all_reachable>. 1204 1205=item all_successors 1206 1207 @s = $g->all_successors(@v) 1208 1209For a directed graph, returns all successor vertices of the argument 1210vertices, recursively. 1211 1212For undirected graphs, see L</all_neighbours> and L</all_reachable>. 1213 1214See also L</successors>, L</successors_by_radius>. 1215 1216=item successors_by_radius 1217 1218 @s = $g->successors_by_radius(@v, $radius) 1219 1220For a directed graph, returns all successor vertices of the argument 1221vertices, recursively. 1222 1223For undirected graphs, see L</all_neighbours> and L</all_reachable>. 1224 1225See also L</successors>, L</successors_by_radius>. 1226 1227=item neighbors 1228 1229=item neighbours 1230 1231 @n = $g->neighbours($v) 1232 1233Return the neighboring/neighbouring vertices. Also known as the 1234I<adjacent vertices>. 1235 1236See also L</all_neighbours> L</all_reachable>, and L</neighbours_by_radius>. 1237 1238=item all_neighbors 1239 1240=item all_neighbours 1241 1242 @n = $g->all_neighbours(@v) 1243 1244Return the neighboring/neighbouring vertices of the argument vertices, 1245recursively. For a directed graph, recurses up predecessors and down 1246successors. For an undirected graph, returns all the vertices 1247reachable from the argument vertices: equivalent to C<all_reachable>. 1248 1249See also L</neighbours>, L</all_reachable>, and L</neighbours_by_radius>. 1250 1251=item neighbors_by_radius 1252 1253=item neighbours_by_radius 1254 1255 @n = $g->neighbours_by_radius(@v, $radius) 1256 1257Return the neighboring/neighbouring vertices of the argument vertices, 1258recursively, out to the given radius. 1259 1260=item all_reachable 1261 1262 @r = $g->all_reachable(@v) 1263 1264Return all the vertices reachable from the argument vertices, 1265recursively. For a directed graph, equivalent to C<all_successors>. 1266For an undirected graph, equivalent to C<all_neighbours>. The argument 1267vertices are not included in the results unless there are explicit 1268self-loops. 1269 1270See also L</neighbours>, L</all_neighbours>, L</all_successors>, and 1271L</reachable_by_radius>. 1272 1273=item reachable_by_radius 1274 1275 @r = $g->reachable_by_radius(@v, $radius) 1276 1277Return all the vertices reachable from the argument vertices, 1278recursively, out to the given radius. 1279 1280=item predecessorful_vertices 1281 1282 @v = $g->predecessorful_vertices() 1283 1284Return the predecessorful vertices of the graph. 1285In scalar context return the number of predecessorful vertices. 1286 1287=item predecessorless_vertices 1288 1289 @v = $g->predecessorless_vertices() 1290 1291Return the predecessorless vertices of the graph. 1292In scalar context return the number of predecessorless vertices. 1293 1294=item predecessors 1295 1296 @p = $g->predecessors($v) 1297 1298Return the immediate predecessor vertices of the vertex. 1299 1300See also L</all_predecessors>, L</all_neighbours>, and L</all_reachable>. 1301 1302=item all_predecessors 1303 1304 @p = $g->all_predecessors(@v) 1305 1306For a directed graph, returns all predecessor vertices of the argument 1307vertices, recursively. 1308 1309For undirected graphs, see L</all_neighbours> and L</all_reachable>. 1310 1311See also L</predecessors>, L</predecessors_by_radius>. 1312 1313=item predecessors_by_radius 1314 1315 @p = $g->predecessors_by_radius(@v, $radius) 1316 1317For a directed graph, returns all predecessor vertices of the argument 1318vertices, recursively, out to the given radius. 1319 1320=item isolated_vertices 1321 1322 @v = $g->isolated_vertices() 1323 1324Return the isolated vertices of the graph. 1325In scalar context return the number of isolated vertices. 1326See L</is_isolated_vertex> for the definition of an isolated vertex. 1327 1328=item interior_vertices 1329 1330 @v = $g->interior_vertices() 1331 1332Return the interior vertices of the graph. 1333In scalar context return the number of interior vertices. 1334See L</is_interior_vertex> for the definition of an interior vertex. 1335 1336=item exterior_vertices 1337 1338 @v = $g->exterior_vertices() 1339 1340Return the exterior vertices of the graph. 1341In scalar context return the number of exterior vertices. 1342See L</is_exterior_vertex> for the definition of an exterior vertex. 1343 1344=item self_loop_vertices 1345 1346 @v = $g->self_loop_vertices() 1347 1348Return the self-loop vertices of the graph. 1349In scalar context return the number of self-loop vertices. 1350See L</is_self_loop_vertex> for the definition of a self-loop vertex. 1351 1352=item as_hashes 1353 1354 ($nodes, $edges) = $g->as_hashes 1355 1356Return hash-refs which map vertices to their attributes, and for edges, 1357a two-level hash mapping the predecessor to its successors, mapped to 1358the attributes. 1359 1360If C<multivertexed> is true, the vertices hash will have the second-level 1361values be the multivertex's ID, and the third level will be attributes 1362as above. 1363 1364If C<multiedged> is true, similar will be true for the edges hash. 1365 1366For a hypergraph, the edges will instead be an array-ref of hashes with 1367a key of C<attributes>, value a hash-ref (if C<multiedged>, two-level 1368as above). Then with values of array-refs of vertex-names, for undirected: 1369 1370=over 1371 1372=item vertices 1373 1374=back 1375 1376And directed: 1377 1378=over 1379 1380=item predecessors 1381 1382=item successors 1383 1384=back 1385 1386=back 1387 1388=head2 Connected Graphs and Their Components 1389 1390In this discussion I<connected graph> refers to any of 1391I<connected graphs>, I<biconnected graphs>, and I<strongly 1392connected graphs>. 1393 1394B<NOTE>: if the vertices of the original graph are Perl objects, 1395(in other words, references, so you must be using C<refvertexed>) 1396the vertices of the I<connected graph> are NOT by default usable 1397as Perl objects because they are blessed into a package with 1398a rather unusable name. 1399 1400By default, the vertex names of the I<connected graph> are formed from 1401the names of the vertices of the original graph by (alphabetically 1402sorting them and) concatenating their names with C<+>. The vertex 1403attribute C<subvertices> is also used to store the list (as an array 1404reference) of the original vertices. To change the 'supercomponent' 1405vertex names and the whole logic of forming these supercomponents 1406use the C<super_component>) option to the method calls: 1407 1408 $g->connected_graph(super_component => sub { ... }) 1409 $g->biconnected_graph(super_component => sub { ... }) 1410 $g->strongly_connected_graph(super_component => sub { ... }) 1411 1412The subroutine reference gets the 'subcomponents' (the vertices of the 1413original graph) as arguments, and it is supposed to return the new 1414supercomponent vertex, the "stringified" form of which is used as the 1415vertex name. 1416 1417=head2 Degree 1418 1419A vertex has a degree based on the number of incoming and outgoing edges. 1420This really makes sense only for directed graphs. 1421 1422=over 4 1423 1424=item degree 1425 1426=item vertex_degree 1427 1428 $d = $g->degree($v) 1429 $d = $g->vertex_degree($v) 1430 1431For directed graphs: the in-degree minus the out-degree at the vertex. 1432 1433For undirected graphs: the number of edges at the vertex (identical to 1434C<in_degree()>, C<out_degree()>). 1435 1436=item in_degree 1437 1438 $d = $g->in_degree($v) 1439 1440For directed graphs: the number of incoming edges at the vertex. 1441 1442For undirected graphs: the number of edges at the vertex (identical to 1443C<out_degree()>, C<degree()>, C<vertex_degree()>). 1444 1445=item out_degree 1446 1447 $o = $g->out_degree($v) 1448 1449For directed graphs: The number of outgoing edges at the vertex. 1450 1451For undirected graphs: the number of edges at the vertex (identical to 1452C<in_degree()>, C<degree()>, C<vertex_degree()>). 1453 1454=back 1455 1456Related methods are 1457 1458=over 4 1459 1460=item edges_at 1461 1462 @e = $g->edges_at($v) 1463 1464The union of edges from, and edges to, the vertex. 1465 1466=item edges_from 1467 1468 @e = $g->edges_from($v) 1469 1470The edges leaving the vertex. 1471 1472=item edges_to 1473 1474 @e = $g->edges_to($v) 1475 1476The edges entering the vertex. 1477 1478=back 1479 1480=head2 Counted Vertices 1481 1482I<Counted vertices> are vertices with more than one instance, normally 1483adding vertices is idempotent. To enable counted vertices on a graph, 1484give the C<countvertexed> parameter a true value 1485 1486 use Graph; 1487 my $g = Graph->new(countvertexed => 1); 1488 1489To find out how many times the vertex has been added: 1490 1491=over 4 1492 1493=item get_vertex_count 1494 1495 my $c = $g->get_vertex_count($v); 1496 1497Return the count of the vertex, or undef if the vertex does not exist. 1498 1499=back 1500 1501=head2 Multiedges, Multivertices, Multigraphs 1502 1503I<Multiedges> are edges with more than one "life", meaning that one 1504has to delete them as many times as they have been added. Normally 1505adding edges is idempotent (in other words, adding edges more than 1506once makes no difference). 1507 1508There are two kinds or degrees of creating multiedges and multivertices. 1509The two kinds are mutually exclusive. 1510 1511The weaker kind is called I<counted>, in which the edge or vertex has 1512a count on it: add operations increase the count, and delete 1513operations decrease the count, and once the count goes to zero, the 1514edge or vertex is deleted. If there are attributes, they all are 1515attached to the same vertex. You can think of this as the graph 1516elements being I<refcounted>, or I<reference counted>, if that sounds 1517more familiar. 1518 1519The stronger kind is called (true) I<multi>, in which the edge or vertex 1520really has multiple separate identities, so that you can for example 1521attach different attributes to different instances. 1522 1523To enable multiedges on a graph: 1524 1525 use Graph; 1526 my $g0 = Graph->new(countedged => 1); 1527 my $g0 = Graph->new(multiedged => 1); 1528 1529Similarly for vertices 1530 1531 use Graph; 1532 my $g1 = Graph->new(countvertexed => 1); 1533 my $g1 = Graph->new(multivertexed => 1); 1534 1535You can test for these by 1536 1537=over 4 1538 1539=item is_countedged 1540 1541=item countedged 1542 1543 $g->is_countedged 1544 $g->countedged 1545 1546Return true if the graph is countedged. 1547 1548=item is_countvertexed 1549 1550=item countvertexed 1551 1552 $g->is_countvertexed 1553 $g->countvertexed 1554 1555Return true if the graph is countvertexed. 1556 1557=item is_multiedged 1558 1559=item multiedged 1560 1561 $g->is_multiedged 1562 $g->multiedged 1563 1564Return true if the graph is multiedged. 1565 1566=item is_multivertexed 1567 1568=item multivertexed 1569 1570 $g->is_multivertexed 1571 $g->multivertexed 1572 1573Return true if the graph is multivertexed. 1574 1575=back 1576 1577A multiedged (either the weak kind or the strong kind) graph is 1578a I<multigraph>, for which you can test with C<is_multi_graph()>. 1579 1580B<NOTE>: The various graph algorithms do not in general work well with 1581multigraphs (they often assume I<simple graphs>, that is, no 1582multiedges or loops), and no effort has been made to test the 1583algorithms with multigraphs. 1584 1585vertices() and edges() will return the multiple elements: if you want 1586just the unique elements, use 1587 1588=over 4 1589 1590=item unique_vertices 1591 1592=item unique_edges 1593 1594 @uv = $g->unique_vertices; # unique 1595 @mv = $g->vertices; # possible multiples 1596 @ue = $g->unique_edges; 1597 @me = $g->edges; 1598 1599=back 1600 1601If you are using (the stronger kind of) multielements, you should use 1602the I<by_id> variants: 1603 1604=over 4 1605 1606=item add_vertex_by_id 1607 1608=item has_vertex_by_id 1609 1610=item delete_vertex_by_id 1611 1612=item add_edge_by_id 1613 1614=item has_edge_by_id 1615 1616=item delete_edge_by_id 1617 1618=back 1619 1620 $g->add_vertex_by_id($v, $id) 1621 $g->has_vertex_by_id($v, $id) 1622 $g->delete_vertex_by_id($v, $id) 1623 1624 $g->add_edge_by_id($u, $v, $id) 1625 $g->has_edge_by_id($u, $v, $id) 1626 $g->delete_edge_by_id($u, $v, $id) 1627 1628These interfaces only apply to multivertices and multiedges. 1629When you delete the last vertex/edge in a multivertex/edge, the whole 1630vertex/edge is deleted. You can use add_vertex()/add_edge() on 1631a multivertex/multiedge graph, in which case an id is generated 1632automatically. To find out which the generated id was, you need 1633to use 1634 1635=over 4 1636 1637=item add_vertex_get_id 1638 1639=item add_edge_get_id 1640 1641=back 1642 1643 $idv = $g->add_vertex_get_id($v) 1644 $ide = $g->add_edge_get_id($u, $v) 1645 1646To return all the ids of vertices/edges in a multivertex/multiedge, use 1647 1648=over 4 1649 1650=item get_multivertex_ids 1651 1652=item get_multiedge_ids 1653 1654=back 1655 1656 $g->get_multivertex_ids($v) 1657 $g->get_multiedge_ids($u, $v) 1658 1659The ids are returned in random order. 1660 1661To find out how many times the edge has been added (this works for 1662either kind of multiedges): 1663 1664=over 4 1665 1666=item get_edge_count 1667 1668 my $c = $g->get_edge_count($u, $v); 1669 1670Return the count (the "countedness") of the edge, or undef if the 1671edge does not exist. 1672 1673=back 1674 1675The following multi-entity utility functions exist, mirroring 1676the non-multi vertices and edges: 1677 1678=over 4 1679 1680=item add_weighted_edge_by_id 1681 1682=item add_weighted_edges_by_id 1683 1684=item add_weighted_path_by_id 1685 1686=item add_weighted_vertex_by_id 1687 1688=item add_weighted_vertices_by_id 1689 1690=item delete_edge_weight_by_id 1691 1692=item delete_vertex_weight_by_id 1693 1694=item get_edge_weight_by_id 1695 1696=item get_vertex_weight_by_id 1697 1698=item has_edge_weight_by_id 1699 1700=item has_vertex_weight_by_id 1701 1702=item set_edge_weight_by_id 1703 1704=item set_vertex_weight_by_id 1705 1706=back 1707 1708=head2 Topological Sort 1709 1710=over 4 1711 1712=item topological_sort 1713 1714=item toposort 1715 1716 my @ts = $g->topological_sort; 1717 1718Return the vertices of the graph sorted topologically. Note that 1719there may be several possible topological orderings; one of them 1720is returned. 1721 1722If the graph contains a cycle, a fatal error is thrown, you 1723can either use C<eval> to trap that, or supply the C<empty_if_cyclic> 1724argument with a true value 1725 1726 my @ts = $g->topological_sort(empty_if_cyclic => 1); 1727 1728in which case an empty array is returned if the graph is cyclic. 1729 1730=back 1731 1732=head2 Minimum Spanning Trees (MST) 1733 1734Minimum Spanning Trees or MSTs are tree subgraphs derived from an 1735undirected graph. MSTs "span the graph" (covering all the vertices) 1736using as lightly weighted (hence the "minimum") edges as possible. 1737 1738=over 4 1739 1740=item MST_Kruskal 1741 1742 $mstg = $g->MST_Kruskal; 1743 1744Returns the Kruskal MST of the graph. 1745 1746=item MST_Prim 1747 1748 $mstg = $g->MST_Prim(%opt); 1749 1750Returns the Prim MST of the graph. 1751 1752You can choose the first vertex with $opt{ first_root }. 1753 1754=item MST_Dijkstra 1755 1756=item minimum_spanning_tree 1757 1758 $mstg = $g->MST_Dijkstra; 1759 $mstg = $g->minimum_spanning_tree; 1760 1761Aliases for MST_Prim. 1762 1763=back 1764 1765=head2 Single-Source Shortest Paths (SSSP) 1766 1767Single-source shortest paths, also known as Shortest Path Trees 1768(SPTs). For either a directed or an undirected graph, return a (tree) 1769subgraph that from a single start vertex (the "single source") travels 1770the shortest possible paths (the paths with the lightest weights) to 1771all the other vertices. Note that the SSSP is neither reflexive (the 1772shortest paths do not include the zero-length path from the source 1773vertex to the source vertex) nor transitive (the shortest paths do not 1774include transitive closure paths). If no weight is defined for an 1775edge, 1 (one) is assumed. 1776 1777=over 4 1778 1779=item SPT_Dijkstra 1780 1781 $sptg = $g->SPT_Dijkstra($root) 1782 $sptg = $g->SPT_Dijkstra(%opt) 1783 1784Return as a graph the the single-source shortest paths of the graph 1785using Dijkstra's algorithm. The graph cannot contain negative edges 1786(negative edges cause the algorithm to abort with an error message 1787C<Graph::SPT_Dijkstra: edge ... is negative>). 1788 1789You can choose the first vertex of the result with either a single 1790vertex argument or with $opt{ first_root }, otherwise a random vertex 1791is chosen. 1792 1793B<NOTE>: note that all the vertices might not be reachable from the 1794selected (explicit or random) start vertex. 1795 1796B<NOTE>: after the first reachable tree from the first start vertex 1797has been finished, and if there still are unvisited vertices, 1798SPT_Dijkstra will keep on selecting unvisited vertices. 1799 1800The next roots (in case the first tree doesn't visit all the vertices) 1801can be chosen by setting one of the following options to true: 1802C<next_root>, C<next_alphabetic>, C<next_numeric>, C<next_random>. 1803 1804The C<next_root> is the most customizable: the value needs to be 1805a subroutine reference which will receive the graph and the unvisited 1806vertices as hash reference. If you want to only visit the first tree, 1807use C<next_root => sub { undef }>. The rest of these options are 1808booleans. If none of them are true, a random unvisited vertex will be 1809selected. 1810 1811The first start vertex is available as the graph attribute 1812C<SPT_Dijkstra_root>). 1813 1814The result weights of vertices can be retrieved from the result graph by 1815 1816 my $w = $sptg->get_vertex_attribute($v, 'weight'); 1817 1818The predecessor vertex of a vertex in the result graph 1819can be retrieved by 1820 1821 my $u = $sptg->get_vertex_attribute($v, 'p'); 1822 1823("A successor vertex" cannot be retrieved as simply because a single 1824vertex can have several successors. You can first find the 1825C<neighbors()> vertices and then remove the predecessor vertex.) 1826 1827If you want to find the shortest path between two vertices, 1828see L</SP_Dijkstra>. 1829 1830=item SSSP_Dijkstra 1831 1832=item single_source_shortest_paths 1833 1834Aliases for SPT_Dijkstra. 1835 1836=item SP_Dijkstra 1837 1838 @path = $g->SP_Dijkstra($u, $v) 1839 1840Return the vertices in the shortest path in the graph $g between the 1841two vertices $u, $v. If no path can be found, an empty list is returned. 1842 1843Uses SPT_Dijkstra(). 1844 1845=item SPT_Dijkstra_clear_cache 1846 1847 $g->SPT_Dijkstra_clear_cache 1848 1849See L</"Clearing cached results">. 1850 1851=item SPT_Bellman_Ford 1852 1853 $sptg = $g->SPT_Bellman_Ford(%opt) 1854 1855Return as a graph the single-source shortest paths of the graph using 1856Bellman-Ford's algorithm. The graph can contain negative edges but 1857not negative cycles (negative cycles cause the algorithm to abort 1858with an error message C<Graph::SPT_Bellman_Ford: negative cycle exists>). 1859 1860You can choose the start vertex of the result with either a single 1861vertex argument or with $opt{ first_root }, otherwise a random vertex 1862is chosen. 1863 1864B<NOTE>: note that all the vertices might not be reachable from the 1865selected (explicit or random) start vertex. 1866 1867The start vertex is available as the graph attribute 1868C<SPT_Bellman_Ford_root>). 1869 1870The result weights of vertices can be retrieved from the result graph by 1871 1872 my $w = $sptg->get_vertex_attribute($v, 'weight'); 1873 1874The predecessor vertex of a vertex in the result graph 1875can be retrieved by 1876 1877 my $u = $sptg->get_vertex_attribute($v, 'p'); 1878 1879("A successor vertex" cannot be retrieved as simply because a single 1880vertex can have several successors. You can first find the 1881C<neighbors()> vertices and then remove the predecessor vertex.) 1882 1883If you want to find the shortest path between two vertices, 1884see L</SP_Bellman_Ford>. 1885 1886=item SSSP_Bellman_Ford 1887 1888Alias for SPT_Bellman_Ford. 1889 1890=item SP_Bellman_Ford 1891 1892 @path = $g->SP_Bellman_Ford($u, $v) 1893 1894Return the vertices in the shortest path in the graph $g between the 1895two vertices $u, $v. If no path can be found, an empty list is returned. 1896 1897Uses SPT_Bellman_Ford(). 1898 1899=item SPT_Bellman_Ford_clear_cache 1900 1901 $g->SPT_Bellman_Ford_clear_cache 1902 1903See L</"Clearing cached results">. 1904 1905=back 1906 1907=head2 All-Pairs Shortest Paths (APSP) 1908 1909For either a directed or an undirected graph, return the APSP object 1910describing all the possible paths between any two vertices of the 1911graph. If no weight is defined for an edge, 1 (one) is assumed. 1912 1913Note that weight of 0 (zero) does not mean do not use this edge, it 1914means essentially the opposite: an edge that has zero cost, an edge 1915that makes the vertices the same. 1916 1917=over 4 1918 1919=item APSP_Floyd_Warshall 1920 1921=item all_pairs_shortest_paths 1922 1923 my $apsp = $g->APSP_Floyd_Warshall(...); 1924 1925Return the all-pairs shortest path object computed from the graph 1926using the Floyd-Warshall algorithm, of class L<Graph::TransitiveClosure>. 1927 1928The length of a path between two vertices is the sum of weight attribute 1929of the edges along the shortest path between the two vertices. If no 1930weight attribute name is specified explicitly 1931 1932 $g->APSP_Floyd_Warshall(attribute_name => 'height'); 1933 1934the attribute C<weight> is assumed. 1935 1936B<If an edge has no defined weight attribute, the value of one is 1937assumed when getting the attribute.> 1938 1939Once computed, you can query the APSP object with 1940 1941=over 8 1942 1943=item path_length 1944 1945 my $l = $apsp->path_length($u, $v); 1946 1947Return the length of the shortest path between the two vertices. 1948 1949=item path_vertices 1950 1951 my @v = $apsp->path_vertices($u, $v); 1952 1953Return the list of vertices along the shortest path. 1954 1955=item path_successor 1956 1957 my $u = $apsp->path_successor($u, $v); 1958 1959Returns the successor of vertex $u in the all-pairs shortest path to $v. 1960 1961=item all_paths 1962 1963 my @paths = $apsp->all_paths($u, $v); 1964 1965Return list of array-refs with all the paths from $u to $v. 1966 1967=item average_path_length 1968 1969 my $apl = $g->average_path_length; # All vertex pairs. 1970 1971 my $apl = $g->average_path_length($u); # From $u. 1972 my $apl = $g->average_path_length($u, undef); # From $u. 1973 1974 my $apl = $g->average_path_length($u, $v); # From $u to $v. 1975 1976 my $apl = $g->average_path_length(undef, $v); # To $v. 1977 1978Return the average (shortest) path length over all the non-zero paths 1979between vertex pairs of the graph's transitive closure. Depending on 1980the arguments, this can be from a vertex, between two vertices, or to 1981a vertex. An undefined (or not-given) vertex will match all. 1982 1983=item longest_path 1984 1985 my @lp = $g->longest_path; 1986 my $lp = $g->longest_path; 1987 1988In scalar context return the I<longest shortest> path length over all 1989the vertex pairs of the graph. In list context return the vertices 1990along a I<longest shortest> path. Note that there might be more than 1991one such path; this interface returns a random one of them. 1992 1993B<NOTE>: this returns the I<longest shortest> path, B<not> the I<longest> path. 1994 1995=item diameter 1996 1997=item graph_diameter 1998 1999 my $gd = $g->diameter; 2000 2001The longest path over all the vertex pairs is known as the 2002I<graph diameter>. 2003 2004For an unconnected graph, single-vertex, or empty graph, returns C<undef>. 2005 2006=item shortest_path 2007 2008 my @sp = $g->shortest_path; 2009 my $sp = $g->shortest_path; 2010 2011In scalar context return the shortest length over all the vertex pairs 2012of the graph. In list context return the vertices along a shortest 2013path. Note that there might be more than one such path; this 2014interface returns a random one of them. 2015 2016For an unconnected, single-vertex, or empty graph, returns C<undef> 2017or an empty list. 2018 2019=item radius 2020 2021 my $gr = $g->radius; 2022 2023The I<shortest longest> path over all the vertex pairs is known as the 2024I<graph radius>. See also L</diameter>. 2025 2026For an unconnected, single-vertex, or empty graph, returns Infinity. 2027 2028=item center_vertices 2029 2030=item centre_vertices 2031 2032 my @c = $g->center_vertices; 2033 my @c = $g->center_vertices($delta); 2034 2035The I<graph center> is the set of vertices for which the I<vertex 2036eccentricity> is equal to the I<graph radius>. The vertices are 2037returned in random order. By specifying a delta value you can widen 2038the criterion from strict equality (handy for non-integer edge weights). 2039 2040For an unconnected, single-vertex, or empty graph, returns an empty list. 2041 2042=item vertex_eccentricity 2043 2044 my $ve = $g->vertex_eccentricity($v); 2045 2046The longest path to a vertex is known as the I<vertex eccentricity>. 2047 2048If the graph is unconnected, single-vertex, or empty graph, returns Inf. 2049 2050=back 2051 2052You can walk through the matrix of the shortest paths by using 2053 2054=over 4 2055 2056=item for_shortest_paths 2057 2058 $n = $g->for_shortest_paths($callback) 2059 2060The number of shortest paths is returned (this should be equal to V*V). 2061The $callback is a sub reference that receives four arguments: 2062the transitive closure object from Graph::TransitiveClosure, the two 2063vertices, and the index to the current shortest paths (0..V*V-1). 2064 2065=back 2066 2067=back 2068 2069=head2 Clearing cached results 2070 2071For many graph algorithms there are several different but equally valid 2072results. (Pseudo)Randomness is used internally by the Graph module to 2073for example pick a random starting vertex, and to select random edges 2074from a vertex. 2075 2076For efficiency the computed result is often cached to avoid 2077recomputing the potentially expensive operation, and this also gives 2078additional determinism (once a correct result has been computed, the 2079same result will always be given). 2080 2081However, sometimes the exact opposite is desirable, and the possible 2082alternative results are wanted (within the limits of the pseudorandomness: 2083not all the possible solutions are guaranteed to be returned, usually only 2084a subset is returned). To undo the caching, the following methods are 2085available: 2086 2087=over 4 2088 2089=item * 2090 2091connectivity_clear_cache 2092 2093Affects L</connected_components>, L</connected_component_by_vertex>, 2094L</connected_component_by_index>, L</same_connected_components>, 2095L</connected_graph>, L</is_connected>, L</is_weakly_connected>, 2096L</weakly_connected_components>, L</weakly_connected_component_by_vertex>, 2097L</weakly_connected_component_by_index>, L</same_weakly_connected_components>, 2098L</weakly_connected_graph>. 2099 2100=item * 2101 2102biconnectivity_clear_cache 2103 2104Affects L</biconnected_components>, 2105L</biconnected_component_by_vertex>, 2106L</biconnected_component_by_index>, L</is_edge_connected>, 2107L</is_edge_separable>, L</articulation_points>, L</cut_vertices>, 2108L</is_biconnected>, L</biconnected_graph>, 2109L</same_biconnected_components>, L</bridges>. 2110 2111=item * 2112 2113strong_connectivity_clear_cache 2114 2115Affects L</strongly_connected_components>, 2116L</strongly_connected_component_by_vertex>, 2117L</strongly_connected_component_by_index>, 2118L</same_strongly_connected_components>, L</is_strongly_connected>, 2119L</strongly_connected>, L</strongly_connected_graph>. 2120 2121=item * 2122 2123SPT_Dijkstra_clear_cache 2124 2125Affects L</SPT_Dijkstra>, L</SSSP_Dijkstra>, L</single_source_shortest_paths>, 2126L</SP_Dijkstra>. 2127 2128=item * 2129 2130SPT_Bellman_Ford_clear_cache 2131 2132Affects L</SPT_Bellman_Ford>, L</SSSP_Bellman_Ford>, L</SP_Bellman_Ford>. 2133 2134=back 2135 2136Note that any such computed and cached results are of course always 2137automatically discarded whenever the graph is modified. 2138 2139=head2 Random 2140 2141You can either ask for random elements of existing graphs or create 2142random graphs. 2143 2144=over 4 2145 2146=item random_vertex 2147 2148 my $v = $g->random_vertex; 2149 2150Return a random vertex of the graph, or undef if there are no vertices. 2151 2152=item random_edge 2153 2154 my $e = $g->random_edge; 2155 2156Return a random edge of the graph as an array reference having the 2157vertices as elements, or undef if there are no edges. 2158 2159=item random_successor 2160 2161 my $v = $g->random_successor($v); 2162 2163Return a random successor of the vertex in the graph, or undef if there 2164are no successors. 2165 2166=item random_predecessor 2167 2168 my $u = $g->random_predecessor($v); 2169 2170Return a random predecessor of the vertex in the graph, or undef if there 2171are no predecessors. 2172 2173=item random_graph 2174 2175 my $g = Graph->random_graph(%opt); 2176 2177Construct a random graph. The I<%opt> B<must> contain the C<vertices> 2178argument 2179 2180 vertices => vertices_def 2181 2182where the I<vertices_def> is one of 2183 2184=over 8 2185 2186=item * 2187 2188an array reference where the elements of the array reference are the 2189vertices 2190 2191=item * 2192 2193a number N in which case the vertices will be integers 0..N-1 2194 2195=back 2196 2197=back 2198 2199The %opt may have either of the argument C<edges> or the argument 2200C<edges_fill>. Both are used to define how many random edges to 2201add to the graph; C<edges> is an absolute number, while C<edges_fill> 2202is a relative number (relative to the number of edges in a complete 2203graph, C). The number of edges can be larger than C, but only if the 2204graph is countedged. The random edges will not include self-loops. 2205If neither C<edges> nor C<edges_fill> is specified, an C<edges_fill> 2206of 0.5 is assumed. 2207 2208If you want repeatable randomness (what is an oxymoron?) 2209you can use the C<random_seed> option: 2210 2211 $g = Graph->random_graph(vertices => 10, random_seed => 1234); 2212 2213As this uses the standard Perl srand(), the usual caveat applies: 2214use it sparingly, and consider instead using a single srand() call 2215at the top level of your application. 2216 2217The default random distribution of edges is flat, that is, any pair of 2218vertices is equally likely to appear. To define your own distribution, 2219use the C<random_edge> option: 2220 2221 $g = Graph->random_graph(vertices => 10, random_edge => \&d); 2222 2223where C<d> is a code reference receiving I<($g, $u, $v, $p)> as 2224parameters, where the I<$g> is the random graph, I<$u> and I<$v> are 2225the vertices, and the I<$p> is the probability ([0,1]) for a flat 2226distribution. It must return a probability ([0,1]) that the vertices 2227I<$u> and I<$v> have an edge between them. Note that returning one 2228for a particular pair of vertices doesn't guarantee that the edge will 2229be present in the resulting graph because the required number of edges 2230might be reached before that particular pair is tested for the 2231possibility of an edge. Be very careful to adjust also C<edges> 2232or C<edges_fill> so that there is a possibility of the filling process 2233terminating. 2234 2235B<NOTE>: a known problem with randomness in openbsd pre-perl-5.20 is that 2236using a seed does not give you deterministic randomness. This affects any 2237Perl code, not just Graph. 2238 2239=head2 Attributes 2240 2241You can attach free-form attributes (key-value pairs, in effect a full 2242Perl hash) to each vertex, edge, and the graph itself. 2243 2244Note that attaching attributes does slow down some other operations 2245on the graph by a factor of three to ten. For example adding edge 2246attributes does slow down anything that walks through all the edges. 2247 2248For vertex attributes: 2249 2250=over 4 2251 2252=item set_vertex_attribute 2253 2254 $g->set_vertex_attribute($v, $name, $value) 2255 2256Set the named vertex attribute. 2257 2258If the vertex does not exist, the set_...() will create it, and the 2259other vertex attribute methods will return false or empty. 2260 2261B<NOTE: any attributes beginning with an underscore/underline (_) 2262are reserved for the internal use of the Graph module.> 2263 2264=item get_vertex_attribute 2265 2266 $value = $g->get_vertex_attribute($v, $name) 2267 2268Return the named vertex attribute. 2269 2270=item has_vertex_attribute 2271 2272 $g->has_vertex_attribute($v, $name) 2273 2274Return true if the vertex has an attribute, false if not. 2275 2276=item delete_vertex_attribute 2277 2278 $g->delete_vertex_attribute($v, $name) 2279 2280Delete the named vertex attribute. 2281 2282=item set_vertex_attributes 2283 2284 $g->set_vertex_attributes($v, $attr) 2285 2286Set all the attributes of the vertex from the anonymous hash $attr. 2287 2288B<NOTE>: any attributes beginning with an underscore (C<_>) are 2289reserved for the internal use of the Graph module. 2290 2291=item get_vertex_attributes 2292 2293 $attr = $g->get_vertex_attributes($v) 2294 2295Return all the attributes of the vertex as an anonymous hash, or C<undef> 2296if no such vertex. 2297 2298=item get_vertex_attribute_names 2299 2300 @name = $g->get_vertex_attribute_names($v) 2301 2302Return the names of vertex attributes. 2303 2304=item get_vertex_attribute_values 2305 2306 @value = $g->get_vertex_attribute_values($v) 2307 2308Return the values of vertex attributes. 2309 2310=item has_vertex_attributes 2311 2312 $g->has_vertex_attributes($v) 2313 2314Return true if the vertex has any attributes, false if not. 2315 2316=item delete_vertex_attributes 2317 2318 $g->delete_vertex_attributes($v) 2319 2320Delete all the attributes of the named vertex. 2321 2322=back 2323 2324If you are using multivertices, use the I<by_id> variants: 2325 2326=over 4 2327 2328=item set_vertex_attribute_by_id 2329 2330=item get_vertex_attribute_by_id 2331 2332=item has_vertex_attribute_by_id 2333 2334=item delete_vertex_attribute_by_id 2335 2336=item set_vertex_attributes_by_id 2337 2338=item get_vertex_attributes_by_id 2339 2340=item get_vertex_attribute_names_by_id 2341 2342=item get_vertex_attribute_values_by_id 2343 2344=item has_vertex_attributes_by_id 2345 2346=item delete_vertex_attributes_by_id 2347 2348 $g->set_vertex_attribute_by_id($v, $id, $name, $value) 2349 $g->get_vertex_attribute_by_id($v, $id, $name) 2350 $g->has_vertex_attribute_by_id($v, $id, $name) 2351 $g->delete_vertex_attribute_by_id($v, $id, $name) 2352 $g->set_vertex_attributes_by_id($v, $id, $attr) 2353 $g->get_vertex_attributes_by_id($v, $id) 2354 $g->get_vertex_attribute_values_by_id($v, $id) 2355 $g->get_vertex_attribute_names_by_id($v, $id) 2356 $g->has_vertex_attributes_by_id($v, $id) 2357 $g->delete_vertex_attributes_by_id($v, $id) 2358 2359=back 2360 2361For edge attributes: 2362 2363=over 4 2364 2365=item set_edge_attribute 2366 2367 $g->set_edge_attribute($u, $v, $name, $value) 2368 2369Set the named edge attribute. 2370 2371If the edge does not exist, the set_...() will create it, and the other 2372edge attribute methods will return false or empty. 2373 2374B<NOTE>: any attributes beginning with an underscore (C<_>) are 2375reserved for the internal use of the Graph module. 2376 2377=item get_edge_attribute 2378 2379 $value = $g->get_edge_attribute($u, $v, $name) 2380 2381Return the named edge attribute. 2382 2383=item has_edge_attribute 2384 2385 $g->has_edge_attribute($u, $v, $name) 2386 2387Return true if the edge has an attribute, false if not. 2388 2389=item delete_edge_attribute 2390 2391 $g->delete_edge_attribute($u, $v, $name) 2392 2393Delete the named edge attribute. 2394 2395=item set_edge_attributes 2396 2397 $g->set_edge_attributes($u, $v, $attr) 2398 2399Set all the attributes of the edge from the anonymous hash $attr. 2400 2401B<NOTE>: any attributes beginning with an underscore (C<_>) are 2402reserved for the internal use of the Graph module. 2403 2404=item get_edge_attributes 2405 2406 $attr = $g->get_edge_attributes($u, $v) 2407 2408Return all the attributes of the edge as an anonymous hash, or C<undef> 2409if no such edge. 2410 2411=item get_edge_attribute_names 2412 2413 @name = $g->get_edge_attribute_names($u, $v) 2414 2415Return the names of edge attributes. 2416 2417=item get_edge_attribute_values 2418 2419 @value = $g->get_edge_attribute_values($u, $v) 2420 2421Return the values of edge attributes. 2422 2423=item has_edge_attributes 2424 2425 $g->has_edge_attributes($u, $v) 2426 2427Return true if the edge has any attributes, false if not. 2428 2429=item delete_edge_attributes 2430 2431 $g->delete_edge_attributes($u, $v) 2432 2433Delete all the attributes of the named edge. 2434 2435=back 2436 2437If you are using multiedges, use the I<by_id> variants: 2438 2439=over 4 2440 2441=item set_edge_attribute_by_id 2442 2443=item get_edge_attribute_by_id 2444 2445=item has_edge_attribute_by_id 2446 2447=item delete_edge_attribute_by_id 2448 2449=item set_edge_attributes_by_id 2450 2451=item get_edge_attributes_by_id 2452 2453=item get_edge_attribute_names_by_id 2454 2455=item get_edge_attribute_values_by_id 2456 2457=item has_edge_attributes_by_id 2458 2459=item delete_edge_attributes_by_id 2460 2461 $g->set_edge_attribute_by_id($u, $v, $id, $name, $value) 2462 $g->get_edge_attribute_by_id($u, $v, $id, $name) 2463 $g->has_edge_attribute_by_id($u, $v, $id, $name) 2464 $g->delete_edge_attribute_by_id($u, $v, $id, $name) 2465 $g->set_edge_attributes_by_id($u, $v, $id, $attr) 2466 $g->get_edge_attributes_by_id($u, $v, $id) 2467 $g->get_edge_attribute_values_by_id($u, $v, $id) 2468 $g->get_edge_attribute_names_by_id($u, $v, $id) 2469 $g->has_edge_attributes_by_id($u, $v, $id) 2470 $g->delete_edge_attributes_by_id($u, $v, $id) 2471 2472=back 2473 2474For graph attributes: 2475 2476=over 4 2477 2478=item set_graph_attribute 2479 2480 $g->set_graph_attribute($name, $value) 2481 2482Set the named graph attribute. 2483 2484B<NOTE>: any attributes beginning with an underscore (C<_>) are 2485reserved for the internal use of the Graph module. 2486 2487=item get_graph_attribute 2488 2489 $value = $g->get_graph_attribute($name) 2490 2491Return the named graph attribute. 2492 2493=item has_graph_attribute 2494 2495 $g->has_graph_attribute($name) 2496 2497Return true if the graph has an attribute, false if not. 2498 2499=item delete_graph_attribute 2500 2501 $g->delete_graph_attribute($name) 2502 2503Delete the named graph attribute. 2504 2505=item set_graph_attributes 2506 2507 $g->get_graph_attributes($attr) 2508 2509Set all the attributes of the graph from the anonymous hash $attr. 2510 2511B<NOTE>: any attributes beginning with an underscore (C<_>) are 2512reserved for the internal use of the Graph module. 2513 2514=item get_graph_attributes 2515 2516 $attr = $g->get_graph_attributes() 2517 2518Return all the attributes of the graph as an anonymous hash. 2519 2520=item get_graph_attribute_names 2521 2522 @name = $g->get_graph_attribute_names() 2523 2524Return the names of graph attributes. 2525 2526=item get_graph_attribute_values 2527 2528 @value = $g->get_graph_attribute_values() 2529 2530Return the values of graph attributes. 2531 2532=item has_graph_attributes 2533 2534 $g->has_graph_attributes() 2535 2536Return true if the graph has any attributes, false if not. 2537 2538=item delete_graph_attributes 2539 2540 $g->delete_graph_attributes() 2541 2542Delete all the attributes of the named graph. 2543 2544=back 2545 2546=head2 Weighted 2547 2548As convenient shortcuts the following methods add, query, and 2549manipulate the attribute C<weight> with the specified value to the 2550respective Graph elements. 2551 2552=over 4 2553 2554=item add_weighted_edge 2555 2556 $g->add_weighted_edge($u, $v, $weight) 2557 2558=item add_weighted_edges 2559 2560 $g->add_weighted_edges($u1, $v1, $weight1, ...) 2561 2562=item add_weighted_path 2563 2564 $g->add_weighted_path($v1, $weight1, $v2, $weight2, $v3, ...) 2565 2566=item add_weighted_vertex 2567 2568 $g->add_weighted_vertex($v, $weight) 2569 2570=item add_weighted_vertices 2571 2572 $g->add_weighted_vertices($v1, $weight1, $v2, $weight2, ...) 2573 2574=item delete_edge_weight 2575 2576 $g->delete_edge_weight($u, $v) 2577 2578=item delete_vertex_weight 2579 2580 $g->delete_vertex_weight($v) 2581 2582=item get_edge_weight 2583 2584 $g->get_edge_weight($u, $v) 2585 2586=item get_vertex_weight 2587 2588 $g->get_vertex_weight($v) 2589 2590=item has_edge_weight 2591 2592 $g->has_edge_weight($u, $v) 2593 2594=item has_vertex_weight 2595 2596 $g->has_vertex_weight($v) 2597 2598=item set_edge_weight 2599 2600 $g->set_edge_weight($u, $v, $weight) 2601 2602=item set_vertex_weight 2603 2604 $g->set_vertex_weight($v, $weight) 2605 2606=back 2607 2608=head2 Isomorphism 2609 2610Two graphs being I<isomorphic> means that they are structurally the 2611same graph, the difference being that the vertices might have been 2612I<renamed> or I<substituted>. For example in the below example $g0 2613and $g1 are isomorphic: the vertices C<b c d> have been renamed as 2614C<z x y>. 2615 2616 $g0 = Graph->new; 2617 $g0->add_edges(qw(a b a c c d)); 2618 $g1 = Graph->new; 2619 $g1->add_edges(qw(a x x y a z)); 2620 2621In the general case determining isomorphism is I<NP-hard>, in other 2622words, really hard (time-consuming), no other ways of solving the problem 2623are known than brute force check of of all the possibilities (with possible 2624optimization tricks, of course, but brute force still rules at the end of 2625the day). 2626 2627A B<very rough guess> at whether two graphs B<could> be isomorphic 2628is possible via the method 2629 2630=over 4 2631 2632=item could_be_isomorphic 2633 2634 $g0->could_be_isomorphic($g1) 2635 2636=back 2637 2638If the graphs do not have the same number of vertices and edges, false 2639is returned. If the distribution of I<in-degrees> and I<out-degrees> 2640at the vertices of the graphs does not match, false is returned. 2641Otherwise, true is returned. 2642 2643What is actually returned is the maximum number of possible isomorphic 2644graphs between the two graphs, after the above sanity checks have been 2645conducted. It is basically the product of the factorials of the 2646absolute values of in-degrees and out-degree pairs at each vertex, 2647with the isolated vertices ignored (since they could be reshuffled and 2648renamed arbitrarily). Note that for large graphs the product of these 2649factorials can overflow the maximum presentable number (the floating 2650point number) in your computer (in Perl) and you might get for example 2651I<Infinity> as the result. 2652 2653=head2 Miscellaneous 2654 2655=over 4 2656 2657=item betweenness 2658 2659 %b = $g->betweenness 2660 2661Returns a map of vertices to their Freeman's betweennesses: 2662 2663 C_b(v) = \sum_{s \neq v \neq t \in V} \frac{\sigma_{s,t}(v)}{\sigma_{s,t}} 2664 2665It is described in: 2666 2667 Freeman, A set of measures of centrality based on betweenness, http://arxiv.org/pdf/cond-mat/0309045 2668 2669and based on the algorithm from: 2670 2671 "A Faster Algorithm for Betweenness Centrality" 2672 2673=item clustering_coefficient 2674 2675 $gamma = $g->clustering_coefficient() 2676 ($gamma, %clustering) = $g->clustering_coefficient() 2677 2678Returns the clustering coefficient gamma as described in 2679 2680 Duncan J. Watts and Steven Strogatz, Collective dynamics of 'small-world' networks, https://web.archive.org/web/20120616204225/http://audiophile.tam.cornell.edu/SS_nature_smallworld.pdf 2681 2682In scalar context returns just the average gamma, in list context 2683returns the average gamma and a hash of vertices to clustering 2684coefficients. 2685 2686Returns an empty list (and therefore undefined in scalar context) if 2687the graph has no vertices. 2688 2689=item subgraph_by_radius 2690 2691 $s = $g->subgraph_by_radius(@v, $radius); 2692 2693Returns a subgraph representing the ball of $radius around the given vertices 2694(breadth-first search). 2695 2696=back 2697 2698The "expect" methods can be used to test a graph and croak if the 2699graph call is not as expected. 2700 2701=over 4 2702 2703=item expect_acyclic 2704 2705=item expect_dag 2706 2707=item expect_directed 2708 2709=item expect_hyperedged 2710 2711=item expect_multiedge 2712 2713=item expect_multiedged 2714 2715=item expect_multivertex 2716 2717=item expect_multivertexed 2718 2719=item expect_no_args 2720 2721=item expect_non_multiedge 2722 2723=item expect_non_multiedged 2724 2725=item expect_non_multivertex 2726 2727=item expect_non_multivertexed 2728 2729=item expect_non_unionfind 2730 2731=item expect_undirected 2732 2733=back 2734 2735In many algorithms it is useful to have a value representing the 2736infinity. The Graph provides (and itself uses): 2737 2738=over 4 2739 2740=item Infinity 2741 2742(Not exported, use Graph::Infinity explicitly) 2743 2744=back 2745 2746=head2 Size Requirements 2747 2748A graph takes up at least 1172 bytes of memory. 2749 2750A vertex takes up at least 100 bytes of memory. 2751 2752An edge takes up at least 400 bytes of memory. 2753 2754(A Perl scalar value takes 16 bytes, or 12 bytes if it's a reference.) 2755 2756These size approximations are B<very> approximate and optimistic 2757(they are based on total_size() of Devel::Size). In real life many 2758factors affect these numbers, for example how Perl is configured. 2759The numbers are for a 32-bit platform and for Perl 5.8.8. 2760 2761Roughly, the above numbers mean that in a megabyte of memory you can 2762fit for example a graph of about 1000 vertices and about 2500 edges. 2763 2764=head2 Hyperedges, hypergraphs 2765 2766B<BEWARE>: this is a rather thinly tested feature, and the theory 2767is even less so. Do not expect this to stay as it is (or at all) 2768in future releases. 2769 2770B<NOTE>: most usual graph algorithms (and basic concepts) break 2771horribly (or at least will look funny) with these hyperthingies. 2772Caveat emptor. 2773 2774Hyperedges are edges that connect a number of vertices different 2775from the usual two. 2776 2777Hypergraphs are graphs with hyperedges. 2778 2779To enable hyperness when constructing Graphs use the C<hyperedged> 2780attribute: 2781 2782 my $h = Graph->new(hyperedged => 1); 2783 2784To test for hyperness of a graph use the 2785 2786=over 4 2787 2788=item is_hyperedged 2789 2790=item hyperedged 2791 2792 $g->is_hyperedged 2793 $g->hyperedged 2794 2795=back 2796 2797Edges in hypergraphs are either directed or undirected, as with simple 2798graphs. If undirected, the edge is a blob of 0 or more vertices. For 2799directed, the set of heads and set of tails are also possibly empty. In 2800general, hypergraphs are simply generalisations of simple-graph ideas, 2801with some of the arbitrary limitations removed. 2802 2803For more information on directed hypergraphs, see 2804L<Directed Hypergraphs and Applications, Gallo-Longo-Pallottino-Nguyen|https://doi.org/10.1016/0166-218X%2893%2990045-P>. 2805It defines hyperarcs (directed edges in a hypergraph) as ordered pairs 2806of subsets of V, and hyperedges (undirected) as single subsets of 2807V. Since sets are unordered and elements within them are unique, this 2808implies that the only valuable use for hypergraphs is where in a given 2809connection entity (edge or arc), each vertex only appears at most once. 2810Additionally, how the C<hyper> property of edges works may 2811change. The underpinning notion is that each edge will be considered 2812an entry in an incidence matrix (dimensions |V| x |E|), with values of 2813either (0, 1=participating) for undirected (hyperedges), or (-1=tail, 28140, 1=head) for directed (hyperarcs) against each vertex. 2815 2816An extension to this is that to extend directed multigraphs with 2817self-loops (aka "quivers") to hypergraphs, the incidence-matrix values 2818will instead be a bitfield, with bit 0 being participation in the tail, 2819and bit 1 in the head. 2820 2821=head2 DIAGNOSTICS 2822 2823=over 4 2824 2825=item * 2826 2827Graph::...Map...: arguments X expected Y ... 2828 2829If you see these (more user-friendly error messages should have been 2830triggered above and before these) please report any such occurrences, 2831but in general you should be happy to see these since it means that an 2832attempt to call something with a wrong number of arguments was caught 2833in time. 2834 2835=item * 2836 2837Graph::add_edge: graph is not hyperedged ... 2838 2839Maybe you used add_weighted_edge() with only the two vertex arguments. 2840 2841=item * 2842 2843Not an ARRAY reference at lib/Graph.pm ... 2844 2845One possibility is that you have code based on Graph 0.2xxxx that 2846assumes Graphs being blessed hash references, possibly also assuming 2847that certain hash keys are available to use for your own purposes. 2848In Graph 0.50 none of this is true. Please do not expect any 2849particular internal implementation of Graphs. Use inheritance 2850and graph/vertex/edge attributes instead. 2851 2852Another possibility is that you meant to have objects (blessed 2853references) as graph vertices, but forgot to use C<refvertexed> 2854(see L</refvertexed>) when creating the graph. 2855 2856=item * 2857 2858Deep recursion on subroutine "Graph::_biconnectivity_dfs" at ... 2859 2860If you have more than 100 vertices, the recursive algorithm will 2861trigger Perl's recursion protection. If you set environment variable 2862C<GRAPH_ALLOW_RECURSION> to a true value, this protection will be 2863disabled, e.g.: 2864 2865 $ GRAPH_ALLOW_RECURSION=1 perl -Ilib util/grand.pl --test=bcc 101 2866 2867=back 2868 2869=head1 ACKNOWLEDGEMENTS 2870 2871All bad terminology, bugs, and inefficiencies are naturally mine, all 2872mine, and not the fault of the below. 2873 2874Thanks to Nathan Goodman and Andras Salamon for bravely betatesting my 2875pre-0.50 code. If they missed something, that was only because of my 2876fiendish code. 2877 2878The following literature for algorithms and some test cases: 2879 2880=over 4 2881 2882=item * 2883 2884Algorithms in C, Third Edition, Part 5, Graph Algorithms, Robert Sedgewick, Addison Wesley 2885 2886=item * 2887 2888Introduction to Algorithms, First Edition, Cormen-Leiserson-Rivest, McGraw Hill 2889 2890=item * 2891 2892Graphs, Networks and Algorithms, Dieter Jungnickel, Springer 2893 2894=back 2895 2896=head1 SEE ALSO 2897 2898Persistent/Serialized graphs? You want to read/write Graphs? See the 2899L<Graph::Reader> and L<Graph::Writer> in CPAN. 2900 2901=head1 AUTHOR 2902 2903Jarkko Hietaniemi F<jhi@iki.fi> 2904 2905Now being maintained by Neil Bowers E<lt>neilb@cpan.orgE<gt> 2906 2907=head1 COPYRIGHT AND LICENSE 2908 2909Copyright (c) 1998-2014 Jarkko Hietaniemi. All rights reserved. 2910 2911This is free software; you can redistribute it and/or modify it under 2912the same terms as the Perl 5 programming language system itself. 2913 2914=cut 2915