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->delete_edge(...);
21
22               $g->add_vertex(...);
23               $g->has_vertex(...);
24               $g->delete_vertex(...);
25
26               $g->vertices(...)
27               $g->edges(...)
28
29               # And many, many more, see below.
30

DESCRIPTION

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

ACKNOWLEDGEMENTS

2386       All bad terminology, bugs, and inefficiencies are naturally mine, all
2387       mine, and not the fault of the below.
2388
2389       Thanks to Nathan Goodman and Andras Salamon for bravely betatesting my
2390       pre-0.50 code.  If they missed something, that was only because of my
2391       fiendish code.
2392
2393       The following literature for algorithms and some test cases:
2394
2395       ·   Algorithms in C, Third Edition, Part 5, Graph Algorithms, Robert
2396           Sedgewick, Addison Wesley
2397
2398       ·   Introduction to Algorithms, First Edition, Cormen-Leiserson-Rivest,
2399           McGraw Hill
2400
2401       ·   Graphs, Networks and Algorithms, Dieter Jungnickel, Springer
2402

SEE ALSO

2404       Persistent/Serialized graphs?  You want to read/write Graphs?  See the
2405       Graph::Reader and Graph::Writer in CPAN.
2406

REPOSITORY

2408       <https://github.com/neilbowers/Graph>
2409

AUTHOR

2411       Jarkko Hietaniemi jhi@iki.fi
2412
2413       Now being maintained by Neil Bowers <neilb@cpan.org>
2414
2416       Copyright (c) 1998-2014 Jarkko Hietaniemi.  All rights reserved.
2417
2418       This is free software; you can redistribute it and/or modify it under
2419       the same terms as the Perl 5 programming language system itself.
2420
2421
2422
2423perl v5.30.1                      2020-01-30                          Graph(3)
Impressum