1Graph(3)              User Contributed Perl Documentation             Graph(3)
2
3
4

NAME

6       Graph - graph data structures and algorithms
7

SYNOPSIS

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

DESCRIPTION

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

ACKNOWLEDGEMENTS

2359       All bad terminology, bugs, and inefficiencies are naturally mine, all
2360       mine, and not the fault of the below.
2361
2362       Thanks to Nathan Goodman and Andras Salamon for bravely betatesting my
2363       pre-0.50 code.  If they missed something, that was only because of my
2364       fiendish code.
2365
2366       The following literature for algorithms and some test cases:
2367
2368       •   Algorithms in C, Third Edition, Part 5, Graph Algorithms, Robert
2369           Sedgewick, Addison Wesley
2370
2371       •   Introduction to Algorithms, First Edition, Cormen-Leiserson-Rivest,
2372           McGraw Hill
2373
2374       •   Graphs, Networks and Algorithms, Dieter Jungnickel, Springer
2375

SEE ALSO

2377       Persistent/Serialized graphs?  You want to read/write Graphs?  See the
2378       Graph::Reader and Graph::Writer in CPAN.
2379

AUTHOR

2381       Jarkko Hietaniemi jhi@iki.fi
2382
2383       Now being maintained by Neil Bowers <neilb@cpan.org>
2384
2386       Copyright (c) 1998-2014 Jarkko Hietaniemi.  All rights reserved.
2387
2388       This is free software; you can redistribute it and/or modify it under
2389       the same terms as the Perl 5 programming language system itself.
2390
2391
2392
2393perl v5.34.0                      2022-01-21                          Graph(3)
Impressum