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

NAME

6       Graph - graph data structures and algorithms
7

SYNOPSIS

9               use Graph;
10               my $g0 = Graph->new;             # A directed graph.
11
12               use Graph::Directed;
13               my $g1 = Graph::Directed->new;   # A directed graph.
14
15               use Graph::Undirected;
16               my $g2 = Graph::Undirected->new; # An undirected graph.
17
18               $g->add_edge(...);
19               $g->has_edge(...)
20               $g->any_edge(...)
21               $g->delete_edge(...);
22
23               $g->add_vertex(...);
24               $g->has_vertex(...);
25               $g->delete_vertex(...);
26
27               $g->vertices(...)
28               $g->edges(...)
29
30               # And many, many more, see below.
31

DESCRIPTION

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

ACKNOWLEDGEMENTS

2331       All bad terminology, bugs, and inefficiencies are naturally mine, all
2332       mine, and not the fault of the below.
2333
2334       Thanks to Nathan Goodman and Andras Salamon for bravely betatesting my
2335       pre-0.50 code.  If they missed something, that was only because of my
2336       fiendish code.
2337
2338       The following literature for algorithms and some test cases:
2339
2340       •   Algorithms in C, Third Edition, Part 5, Graph Algorithms, Robert
2341           Sedgewick, Addison Wesley
2342
2343       •   Introduction to Algorithms, First Edition, Cormen-Leiserson-Rivest,
2344           McGraw Hill
2345
2346       •   Graphs, Networks and Algorithms, Dieter Jungnickel, Springer
2347

SEE ALSO

2349       Persistent/Serialized graphs?  You want to read/write Graphs?  See the
2350       Graph::Reader and Graph::Writer in CPAN.
2351

AUTHOR

2353       Jarkko Hietaniemi jhi@iki.fi
2354
2355       Now being maintained by Neil Bowers <neilb@cpan.org>
2356
2358       Copyright (c) 1998-2014 Jarkko Hietaniemi.  All rights reserved.
2359
2360       This is free software; you can redistribute it and/or modify it under
2361       the same terms as the Perl 5 programming language system itself.
2362
2363
2364
2365perl v5.32.1                      2021-01-27                          Graph(3)
Impressum