1Graph(3) User Contributed Perl Documentation Graph(3)
2
6 Graph - graph data structures and algorithms
7
9 use Graph;
10 my $g0 = Graph->new; # A directed graph.
11 use Graph::Directed;
13 my $g1 = Graph::Directed->new; # A directed graph.
14 use Graph::Undirected;
16 my $g2 = Graph::Undirected->new; # An undirected graph.
17 $g->add_edge(...);
19 $g->has_edge(...)
20 $g->delete_edge(...);
21 $g->add_vertex(...);
23 $g->has_vertex(...);
24 $g->delete_vertex(...);
25 $g->vertices(...)
27 $g->edges(...)
28 # And many, many more, see below.
30
32 Non-Description
33 This module is not for drawing or rendering any sort of graphics or
34 images, business, visualization, or otherwise.
35 Description
37 Instead, this module is for creating abstract data structures called
38 graphs, and for doing various operations on those.
39 Perl 5.6.0 minimum
41 The implementation depends on a Perl feature called "weak references"
42 and Perl 5.6.0 was the first to have those.
43 Constructors
45 new Create an empty graph.
46 Graph->new(%options)
48 The options are a hash with option names as the hash keys and the
49 option values as the hash values.
50 The following options are available:
52 directed
54 A boolean option telling that a directed graph should be
55 created. Often somewhat redundant because a directed graph
56 is the default for the Graph class or one could simply use
57 the "new()" constructor of the Graph::Directed class.
58 You can test the directness of a graph with
60 $g->is_directed() and $g->is_undirected().
61 undirected
63 A boolean option telling that an undirected graph should be
64 created. One could also use the "new()" constructor the
65 Graph::Undirected class instead.
66 Note that while often it is possible to think undirected
68 graphs as bidirectional graphs, or as directed graphs with
69 edges going both ways, in this module directed graphs and
70 undirected graphs are two different things that often
71 behave differently.
72 You can test the directness of a graph with
74 $g->is_directed() and $g->is_undirected().
75 refvertexed
77 refvertexed_stringified
78 If you want to use references (including Perl objects) as
79 vertices, use "refvertexed".
80 Note that using "refvertexed" means that internally the
82 memory address of the reference (for example, a Perl
83 object) is used as the "identifier" of the vertex, not the
84 stringified form of the reference, even if you have defined
85 your own stringification using "overload".
86 This avoids the problem of the stringified references
88 potentially being identical (because they are identical in
89 value, for example) even if the references are different.
90 If you really want to use references and their stringified
91 forms as the identities, use the "refvertexed_stringified".
92 But please do not stringify different objects to the same
93 stringified value.
94 unionfind
96 If the graph is undirected, you can specify the "unionfind"
97 parameter to use the so-called union-find scheme to speed
98 up the computation of connected components of the graph
99 (see "is_connected", "connected_components",
100 "connected_component_by_vertex",
101 "connected_component_by_index", and
102 "same_connected_components"). If "unionfind" is used,
103 adding edges (and vertices) becomes slower, but
104 connectedness queries become faster. You must not delete
105 egdes or vertices of an unionfind graph, only add them.
106 You can test a graph for "union-findness" with
107 has_union_find
109 Returns true if the graph was created with a true
110 "unionfind" parameter.
111 vertices
113 An array reference of vertices to add.
114 edges An array reference of array references of edge vertices to
116 add.
117 copy
119 copy_graph
120 my $c = $g->copy_graph;
121 Create a shallow copy of the structure (vertices and edges) of the
123 graph. If you want a deep copy that includes attributes, see
124 "deep_copy". The copy will have the same directedness as the
125 original, and if the original was a "compat02" graph, the copy will
126 be, too.
127 Also the following vertex/edge attributes are copied:
129 refvertexed/hypervertexed/countvertexed/multivertexed
131 hyperedged/countedged/multiedged/omniedged
132 NOTE: You can get an even shallower copy of a graph by
134 my $c = $g->new;
136 This will copy only the graph properties (directed, and so forth),
138 but none of the vertices or edges.
139 deep_copy
141 deep_copy_graph
142 my $c = $g->deep_copy_graph;
143 Create a deep copy of the graph (vertices, edges, and attributes)
145 of the graph. If you want a shallow copy that does not include
146 attributes, see "copy".
147 Note that copying code references only works with Perls 5.8 or
149 later, and even then only if B::Deparse can reconstruct your code.
150 This functionality uses either Storable or Data::Dumper behind the
151 scenes, depending on which is available (Storable is preferred).
152 undirected_copy
154 undirected_copy_graph
155 my $c = $g->undirected_copy_graph;
156 Create an undirected shallow copy (vertices and edges) of the
158 directed graph so that for any directed edge (u, v) there is an
159 undirected edge (u, v).
160 undirected_copy_clear_cache
162 @path = $g->undirected_copy_clear_cache;
163 See "Clearing cached results".
165 directed_copy
167 directed_copy_graph
168 my $c = $g->directed_copy_graph;
169 Create a directed shallow copy (vertices and edges) of the
171 undirected graph so that for any undirected edge (u, v) there are
172 two directed edges (u, v) and (v, u).
173 transpose
175 transpose_graph
176 my $t = $g->transpose_graph;
177 Create a directed shallow transposed copy (vertices and edges) of
179 the directed graph so that for any directed edge (u, v) there is a
180 directed edge (v, u).
181 You can also transpose a single edge with
183 transpose_edge
185 $g->transpose_edge($u, $v)
186 complete_graph
188 complete
189 my $c = $g->complete_graph;
190 Create a complete graph that has the same vertices as the original
192 graph. A complete graph has an edge between every pair of
193 vertices.
194 complement_graph
196 complement
197 my $c = $g->complement_graph;
198 Create a complement graph that has the same vertices as the
200 original graph. A complement graph has an edge (u,v) if and only
201 if the original graph does not have edge (u,v).
202 subgraph
204 my $c = $g->subgraph(\@src, \@dst);
205 my $c = $g->subgraph(\@src);
206 Creates a subgraph of a given graph. The created subgraph has the
208 same graph properties (directedness, and so forth) as the original
209 graph, but none of the attributes (graph, vertex, or edge).
210 A vertex is added to the subgraph if it is in the original graph.
212 An edge is added to the subgraph if there is an edge in the
214 original graph that starts from the "src" set of vertices and ends
215 in the "dst" set of vertices.
216 You can leave out "dst" in which case "dst" is assumed to be the
218 same: this is called a vertex-induced subgraph.
219 See also "random_graph" for a random constructor.
221 Basics
223 add_vertex
224 $g->add_vertex($v)
225 Add the vertex to the graph. Returns the graph.
227 By default idempotent, but a graph can be created countvertexed.
229 A vertex is also known as a node.
231 Adding "undef" as vertex is not allowed.
233 Note that unless you have isolated vertices (or countvertexed
235 vertices), you do not need to explicitly use "add_vertex" since
236 "add_edge" will implicitly add its vertices.
237 add_edge
239 $g->add_edge($u, $v)
240 Add the edge to the graph. Implicitly first adds the vertices if
242 the graph does not have them. Returns the graph.
243 By default idempotent, but a graph can be created countedged.
245 An edge is also known as an arc.
247 has_vertex
249 $g->has_vertex($v)
250 Return true if the vertex exists in the graph, false otherwise.
252 has_edge
254 $g->has_edge($u, $v)
255 Return true if the edge exists in the graph, false otherwise.
257 delete_vertex
259 $g->delete_vertex($v)
260 Delete the vertex from the graph. Returns the graph, even if the
262 vertex did not exist in the graph.
263 If the graph has been created multivertexed or countvertexed and a
265 vertex has been added multiple times, the vertex will require at
266 least an equal number of deletions to become completely deleted.
267 delete_vertices
269 $g->delete_vertices($v1, $v2, ...)
270 Delete the vertices from the graph. Returns the graph, even if
272 none of the vertices existed in the graph.
273 If the graph has been created multivertexed or countvertexed and a
275 vertex has been added multiple times, the vertex will require at
276 least an equal number of deletions to become completely deleteted.
277 delete_edge
279 $g->delete_edge($u, $v)
280 Delete the edge from the graph. Returns the graph, even if the
282 edge did not exist in the graph.
283 If the graph has been created multivertexed or countedged and an
285 edge has been added multiple times, the edge will require at least
286 an equal number of deletions to become completely deleted.
287 delete_edges
289 $g->delete_edges($u1, $v1, $u2, $v2, ...)
290 Delete the edges from the graph. Returns the graph, even if none
292 of the edges existed in the graph.
293 If the graph has been created multivertexed or countedged and an
295 edge has been added multiple times, the edge will require at least
296 an equal number of deletions to become completely deleted.
297 Displaying
299 Graphs have stringification overload, so you can do things like
300 print "The graph is $g\n"
302 One-way (directed, unidirected) edges are shown as '-', two-way
304 (undirected, bidirected) edges are shown as '='. If you want to, you
305 can call the stringification via the method
306 stringify
308 Boolean
310 Graphs have boolifying overload, so you can do things like
311 if ($g) { print "The graph is: $g\n" }
313 which works even if the graph is empty. In fact, the boolify always
315 returns true. If you want to test for example for vertices, test for
316 vertices.
317 boolify
319 Comparing
321 Testing for equality can be done either by the overloaded "eq" operator
322 $g eq "a-b,a-c,d"
324 or by the method
326 eq
328 $g->eq("a-b,a-c,d")
329 The equality testing compares the stringified forms, and therefore it
331 assumes total equality, not isomorphism: all the vertices must be named
332 the same, and they must have identical edges between them.
333 For unequality there are correspondingly the overloaded "ne" operator
335 and the method
336 ne
338 $g->ne("a-b,a-c,d")
339 See also "Isomorphism".
341 Paths and Cycles
343 Paths and cycles are simple extensions of edges: paths are edges
344 starting from where the previous edge ended, and cycles are paths
345 returning back to the start vertex of the first edge.
346 add_path
348 $g->add_path($a, $b, $c, ..., $x, $y, $z)
349 Add the edges $a-$b, $b-$c, ..., $x-$y, $y-$z to the graph.
351 Returns the graph.
352 has_path
354 $g->has_path($a, $b, $c, ..., $x, $y, $z)
355 Return true if the graph has all the edges $a-$b, $b-$c, ...,
357 $x-$y, $y-$z, false otherwise.
358 delete_path
360 $g->delete_path($a, $b, $c, ..., $x, $y, $z)
361 Delete all the edges edges $a-$b, $b-$c, ..., $x-$y, $y-$z
363 (regardless of whether they exist or not). Returns the graph.
364 add_cycle
366 $g->add_cycle($a, $b, $c, ..., $x, $y, $z)
367 Add the edges $a-$b, $b-$c, ..., $x-$y, $y-$z, and $z-$a to the
369 graph. Returns the graph.
370 has_cycle
372 has_this_cycle
373 $g->has_cycle($a, $b, $c, ..., $x, $y, $z)
374 Return true if the graph has all the edges $a-$b, $b-$c, ...,
376 $x-$y, $y-$z, and $z-$a, false otherwise.
377 NOTE: This does not detect cycles, see "has_a_cycle" and
379 "find_a_cycle".
380 delete_cycle
382 $g->delete_cycle($a, $b, $c, ..., $x, $y, $z)
383 Delete all the edges edges $a-$b, $b-$c, ..., $x-$y, $y-$z, and
385 $z-$a (regardless of whether they exist or not). Returns the
386 graph.
387 has_a_cycle
389 $g->has_a_cycle
390 Returns true if the graph has a cycle, false if not.
392 find_a_cycle
394 $g->find_a_cycle
395 Returns a cycle if the graph has one (as a list of vertices), an
397 empty list if no cycle can be found.
398 Note that this just returns the vertices of a cycle: not any
400 particular cycle, just the first one it finds. A repeated call
401 might find the same cycle, or it might find a different one, and
402 you cannot call this repeatedly to find all the cycles.
403 Graph Types
405 is_simple_graph
406 $g->is_simple_graph
407 Return true if the graph has no multiedges, false otherwise.
409 is_pseudo_graph
411 $g->is_pseudo_graph
412 Return true if the graph has any multiedges or any self-loops,
414 false otherwise.
415 is_multi_graph
417 $g->is_multi_graph
418 Return true if the graph has any multiedges but no self-loops,
420 false otherwise.
421 is_directed_acyclic_graph
423 is_dag
424 $g->is_directed_acyclic_graph
425 $g->is_dag
426 Return true if the graph is directed and acyclic, false otherwise.
428 is_cyclic
430 $g->is_cyclic
431 Return true if the graph is cyclic (contains at least one cycle).
433 (This is identical to "has_a_cycle".)
434 To find at least one such cycle, see "find_a_cycle".
436 is_acyclic
438 Return true if the graph is acyclic (does not contain any cycles).
439 To find a cycle, use "find_a_cycle".
441 Transitivity
443 is_transitive
444 $g->is_transitive
445 Return true if the graph is transitive, false otherwise.
447 TransitiveClosure_Floyd_Warshall
449 transitive_closure
450 $tcg = $g->TransitiveClosure_Floyd_Warshall
451 Return the transitive closure graph of the graph.
453 You can query the reachability from $u to $v with
455 is_reachable
457 $tcg->is_reachable($u, $v)
458 See Graph::TransitiveClosure for more information about creating and
460 querying transitive closures.
461 With
463 transitive_closure_matrix
465 $tcm = $g->transitive_closure_matrix;
466 you can (create if not existing and) query the transitive closure
468 matrix that underlies the transitive closure graph. See
469 Graph::TransitiveClosure::Matrix for more information.
470 Mutators
472 add_vertices
473 $g->add_vertices('d', 'e', 'f')
474 Add zero or more vertices to the graph. Returns the graph.
476 add_edges
478 $g->add_edges(['d', 'e'], ['f', 'g'])
479 $g->add_edges(qw(d e f g));
480 Add zero or more edges to the graph. The edges are specified as a
482 list of array references, or as a list of vertices where the even
483 (0th, 2nd, 4th, ...) items are start vertices and the odd (1st,
484 3rd, 5th, ...) are the corresponding end vertices. Returns the
485 graph.
486 Accessors
488 is_directed
489 directed
490 $g->is_directed()
491 $g->directed()
492 Return true if the graph is directed, false otherwise.
494 is_undirected
496 undirected
497 $g->is_undirected()
498 $g->undirected()
499 Return true if the graph is undirected, false otherwise.
501 is_refvertexed
503 is_refvertexed_stringified
504 refvertexed
505 refvertexed_stringified
506 Return true if the graph can handle references (including Perl
507 objects) as vertices.
508 vertices
510 my $V = $g->vertices
511 my @V = $g->vertices
512 In scalar context, return the number of vertices in the graph. In
514 list context, return the vertices, in no particular order.
515 has_vertices
517 $g->has_vertices()
518 Return true if the graph has any vertices, false otherwise.
520 edges
522 my $E = $g->edges
523 my @E = $g->edges
524 In scalar context, return the number of edges in the graph. In
526 list context, return the edges, in no particular order. The edges
527 are returned as anonymous arrays listing the vertices.
528 has_edges
530 $g->has_edges()
531 Return true if the graph has any edges, false otherwise.
533 is_connected
535 $g->is_connected
536 For an undirected graph, return true is the graph is connected,
538 false otherwise. Being connected means that from every vertex it
539 is possible to reach every other vertex.
540 If the graph has been created with a true "unionfind" parameter,
542 the time complexity is (essentially) O(V), otherwise O(V log V).
543 See also "connected_components", "connected_component_by_index",
545 "connected_component_by_vertex", and "same_connected_components",
546 and "biconnectivity".
547 For directed graphs, see "is_strongly_connected" and
549 "is_weakly_connected".
550 connected_components
552 @cc = $g->connected_components()
553 For an undirected graph, returns the vertices of the connected
555 components of the graph as a list of anonymous arrays. The
556 ordering of the anonymous arrays or the ordering of the vertices
557 inside the anonymous arrays (the components) is undefined.
558 For directed graphs, see "strongly_connected_components" and
560 "weakly_connected_components".
561 connected_component_by_vertex
563 $i = $g->connected_component_by_vertex($v)
564 For an undirected graph, return an index identifying the connected
566 component the vertex belongs to, the indexing starting from zero.
567 For the inverse, see "connected_component_by_index".
569 If the graph has been created with a true "unionfind" parameter,
571 the time complexity is (essentially) O(1), otherwise O(V log V).
572 See also "biconnectivity".
574 For directed graphs, see "strongly_connected_component_by_vertex"
576 and "weakly_connected_component_by_vertex".
577 connected_component_by_index
579 @v = $g->connected_component_by_index($i)
580 For an undirected graph, return the vertices of the ith connected
582 component, the indexing starting from zero. The order of vertices
583 is undefined, while the order of the connected components is same
584 as from connected_components().
585 For the inverse, see "connected_component_by_vertex".
587 For directed graphs, see "strongly_connected_component_by_index"
589 and "weakly_connected_component_by_index".
590 same_connected_components
592 $g->same_connected_components($u, $v, ...)
593 For an undirected graph, return true if the vertices are in the
595 same connected component.
596 If the graph has been created with a true "unionfind" parameter,
598 the time complexity is (essentially) O(1), otherwise O(V log V).
599 For directed graphs, see "same_strongly_connected_components" and
601 "same_weakly_connected_components".
602 connected_graph
604 $cg = $g->connected_graph
605 For an undirected graph, return its connected graph.
607 connectivity_clear_cache
609 $g->connectivity_clear_cache
610 See "Clearing cached results".
612 See "Connected Graphs and Their Components" for further discussion.
614 biconnectivity
616 my ($ap, $bc, $br) = $g->biconnectivity
617 For an undirected graph, return the various biconnectivity
619 components of the graph: the articulation points (cut vertices),
620 biconnected components, and bridges.
621 Note: currently only handles connected graphs.
623 is_biconnected
625 $g->is_biconnected
626 For an undirected graph, return true if the graph is biconnected
628 (if it has no articulation points, also known as cut vertices).
629 is_edge_connected
631 $g->is_edge_connected
632 For an undirected graph, return true if the graph is edge-connected
634 (if it has no bridges).
635 Note: more precisely, this would be called is_edge_biconnected,
637 since there is a more general concept of being k-connected.
638 is_edge_separable
640 $g->is_edge_separable
641 For an undirected graph, return true if the graph is edge-separable
643 (if it has bridges).
644 Note: more precisely, this would be called is_edge_biseparable,
646 since there is a more general concept of being k-connected.
647 articulation_points
649 cut_vertices
650 $g->articulation_points
651 For an undirected graph, return the articulation points (cut
653 vertices) of the graph as a list of vertices. The order is
654 undefined.
655 biconnected_components
657 $g->biconnected_components
658 For an undirected graph, return the biconnected components of the
660 graph as a list of anonymous arrays of vertices in the components.
661 The ordering of the anonymous arrays or the ordering of the
662 vertices inside the anonymous arrays (the components) is undefined.
663 Also note that one vertex can belong to more than one biconnected
664 component.
665 biconnected_component_by_vertex
667 $i = $g->biconnected_component_by_index($v)
668 For an undirected graph, return the indices identifying the
670 biconnected components the vertex belongs to, the indexing starting
671 from zero. The order of of the components is undefined.
672 For the inverse, see "connected_component_by_index".
674 For directed graphs, see "strongly_connected_component_by_index"
676 and "weakly_connected_component_by_index".
677 biconnected_component_by_index
679 @v = $g->biconnected_component_by_index($i)
680 For an undirected graph, return the vertices in the ith biconnected
682 component of the graph as an anonymous arrays of vertices in the
683 component. The ordering of the vertices within a component is
684 undefined. Also note that one vertex can belong to more than one
685 biconnected component.
686 same_biconnected_components
688 $g->same_biconnected_components($u, $v, ...)
689 For an undirected graph, return true if the vertices are in the
691 same biconnected component.
692 biconnected_graph
694 $bcg = $g->biconnected_graph
695 For an undirected graph, return its biconnected graph.
697 See "Connected Graphs and Their Components" for further discussion.
699 bridges
701 $g->bridges
702 For an undirected graph, return the bridges of the graph as a list
704 of anonymous arrays of vertices in the bridges. The order of
705 bridges and the order of vertices in them is undefined.
706 biconnectivity_clear_cache
708 $g->biconnectivity_clear_cache
709 See "Clearing cached results".
711 strongly_connected
713 is_strongly_connected
714 $g->is_strongly_connected
715 For a directed graph, return true is the directed graph is strongly
717 connected, false if not.
718 See also "is_weakly_connected".
720 For undirected graphs, see "is_connected", or "is_biconnected".
722 strongly_connected_component_by_vertex
724 $i = $g->strongly_connected_component_by_vertex($v)
725 For a directed graph, return an index identifying the strongly
727 connected component the vertex belongs to, the indexing starting
728 from zero.
729 For the inverse, see "strongly_connected_component_by_index".
731 See also "weakly_connected_component_by_vertex".
733 For undirected graphs, see "connected_components" or
735 "biconnected_components".
736 strongly_connected_component_by_index
738 @v = $g->strongly_connected_component_by_index($i)
739 For a directed graph, return the vertices of the ith connected
741 component, the indexing starting from zero. The order of vertices
742 within a component is undefined, while the order of the connected
743 components is the as from strongly_connected_components().
744 For the inverse, see "strongly_connected_component_by_vertex".
746 For undirected graphs, see "weakly_connected_component_by_index".
748 same_strongly_connected_components
750 $g->same_strongly_connected_components($u, $v, ...)
751 For a directed graph, return true if the vertices are in the same
753 strongly connected component.
754 See also "same_weakly_connected_components".
756 For undirected graphs, see "same_connected_components" or
758 "same_biconnected_components".
759 strong_connectivity_clear_cache
761 $g->strong_connectivity_clear_cache
762 See "Clearing cached results".
764 weakly_connected
766 is_weakly_connected
767 $g->is_weakly_connected
768 For a directed graph, return true is the directed graph is weakly
770 connected, false if not.
771 Weakly connected graph is also known as semiconnected graph.
773 See also "is_strongly_connected".
775 For undirected graphs, see "is_connected" or "is_biconnected".
777 weakly_connected_components
779 @wcc = $g->weakly_connected_components()
780 For a directed graph, returns the vertices of the weakly connected
782 components of the graph as a list of anonymous arrays. The
783 ordering of the anonymous arrays or the ordering of the vertices
784 inside the anonymous arrays (the components) is undefined.
785 See also "strongly_connected_components".
787 For undirected graphs, see "connected_components" or
789 "biconnected_components".
790 weakly_connected_component_by_vertex
792 $i = $g->weakly_connected_component_by_vertex($v)
793 For a directed graph, return an index identifying the weakly
795 connected component the vertex belongs to, the indexing starting
796 from zero.
797 For the inverse, see "weakly_connected_component_by_index".
799 For undirected graphs, see "connected_component_by_vertex" and
801 "biconnected_component_by_vertex".
802 weakly_connected_component_by_index
804 @v = $g->weakly_connected_component_by_index($i)
805 For a directed graph, return the vertices of the ith weakly
807 connected component, the indexing starting zero. The order of
808 vertices within a component is undefined, while the order of the
809 weakly connected components is same as from
810 weakly_connected_components().
811 For the inverse, see "weakly_connected_component_by_vertex".
813 For undirected graphs, see connected_component_by_index and
815 biconnected_component_by_index.
816 same_weakly_connected_components
818 $g->same_weakly_connected_components($u, $v, ...)
819 Return true if the vertices are in the same weakly connected
821 component.
822 weakly_connected_graph
824 $wcg = $g->weakly_connected_graph
825 For a directed graph, return its weakly connected graph.
827 For undirected graphs, see "connected_graph" and
829 "biconnected_graph".
830 strongly_connected_components
832 my @scc = $g->strongly_connected_components;
833 For a directed graph, return the strongly connected components as a
835 list of anonymous arrays. The elements in the anonymous arrays are
836 the vertices belonging to the strongly connected component; both
837 the elements and the components are in no particular order.
838 Note that strongly connected components can have single-element
840 components even without self-loops: if a vertex is any of isolated,
841 sink, or a source, the vertex is alone in its own strong component.
842 See also "weakly_connected_components".
844 For undirected graphs, see "connected_components", or see
846 "biconnected_components".
847 strongly_connected_graph
849 my $scg = $g->strongly_connected_graph;
850 See "Connected Graphs and Their Components" for further discussion.
852 Strongly connected graphs are also known as kernel graphs.
854 See also "weakly_connected_graph".
856 For undirected graphs, see "connected_graph", or
858 "biconnected_graph".
859 is_sink_vertex
861 $g->is_sink_vertex($v)
862 Return true if the vertex $v is a sink vertex, false if not. A
864 sink vertex is defined as a vertex with predecessors but no
865 successors: this definition means that isolated vertices are not
866 sink vertices. If you want also isolated vertices, use
867 is_successorless_vertex().
868 is_source_vertex
870 $g->is_source_vertex($v)
871 Return true if the vertex $v is a source vertex, false if not. A
873 source vertex is defined as a vertex with successors but no
874 predecessors: the definition means that isolated vertices are not
875 source vertices. If you want also isolated vertices, use
876 is_predecessorless_vertex().
877 is_successorless_vertex
879 $g->is_successorless_vertex($v)
880 Return true if the vertex $v has no succcessors (no edges leaving
882 the vertex), false if it has.
883 Isolated vertices will return true: if you do not want this, use
885 is_sink_vertex().
886 is_successorful_vertex
888 $g->is_successorful_vertex($v)
889 Return true if the vertex $v has successors, false if not.
891 is_predecessorless_vertex
893 $g->is_predecessorless_vertex($v)
894 Return true if the vertex $v has no predecessors (no edges entering
896 the vertex), false if it has.
897 Isolated vertices will return true: if you do not want this, use
899 is_source_vertex().
900 is_predecessorful_vertex
902 $g->is_predecessorful_vertex($v)
903 Return true if the vertex $v has predecessors, false if not.
905 is_isolated_vertex
907 $g->is_isolated_vertex($v)
908 Return true if the vertex $v is an isolated vertex: no successors
910 and no predecessors.
911 is_interior_vertex
913 $g->is_interior_vertex($v)
914 Return true if the vertex $v is an interior vertex: both successors
916 and predecessors.
917 is_exterior_vertex
919 $g->is_exterior_vertex($v)
920 Return true if the vertex $v is an exterior vertex: has either no
922 successors or no predecessors, or neither.
923 is_self_loop_vertex
925 $g->is_self_loop_vertex($v)
926 Return true if the vertex $v is a self loop vertex: has an edge
928 from itself to itself.
929 sink_vertices
931 @v = $g->sink_vertices()
932 Return the sink vertices of the graph. In scalar context return
934 the number of sink vertices. See "is_sink_vertex" for the
935 definition of a sink vertex.
936 source_vertices
938 @v = $g->source_vertices()
939 Return the source vertices of the graph. In scalar context return
941 the number of source vertices. See "is_source_vertex" for the
942 definition of a source vertex.
943 successorful_vertices
945 @v = $g->successorful_vertices()
946 Return the successorful vertices of the graph. In scalar context
948 return the number of successorful vertices.
949 successorless_vertices
951 @v = $g->successorless_vertices()
952 Return the successorless vertices of the graph. In scalar context
954 return the number of successorless vertices.
955 successors
957 @s = $g->successors($v)
958 Return the immediate successor vertices of the vertex.
960 See also "all_successors", "all_neighbours", and "all_reachable".
962 all_successors
964 @s = $g->all_successors(@v)
965 For a directed graph, returns all successor vertices of the
967 argument vertices, recursively.
968 For undirected graphs, see "all_neighbours" and "all_reachable".
970 See also "successors".
972 neighbors
974 neighbours
975 @n = $g->neighbours($v)
976 Return the neighboring/neighbouring vertices. Also known as the
978 adjacent vertices.
979 See also "all_neighbours" and "all_reachable".
981 all_neighbors
983 all_neighbours
984 @n = $g->all_neighbours(@v)
985 Return the neighboring/neighbouring vertices of the argument
987 vertices, recursively. For a directed graph, recurses up
988 predecessors and down successors. For an undirected graph, returns
989 all the vertices reachable from the argument vertices: equivalent
990 to "all_reachable".
991 See also "neighbours" and "all_reachable".
993 all_reachable
995 @r = $g->all_reachable(@v)
996 Return all the vertices reachable from of the argument vertices,
998 recursively. For a directed graph, equivalent to "all_successors".
999 For an undirected graph, equivalent to "all_neighbours". The
1000 argument vertices are not included in the results unless there are
1001 explicit self-loops.
1002 See also "neighbours", "all_neighbours", and "all_successors".
1004 predecessorful_vertices
1006 @v = $g->predecessorful_vertices()
1007 Return the predecessorful vertices of the graph. In scalar context
1009 return the number of predecessorful vertices.
1010 predecessorless_vertices
1012 @v = $g->predecessorless_vertices()
1013 Return the predecessorless vertices of the graph. In scalar
1015 context return the number of predecessorless vertices.
1016 predecessors
1018 @p = $g->predecessors($v)
1019 Return the immediate predecessor vertices of the vertex.
1021 See also "all_predecessors", "all_neighbours", and "all_reachable".
1023 all_predecessors
1025 @p = $g->all_predecessors(@v)
1026 For a directed graph, returns all predecessor vertices of the
1028 argument vertices, recursively.
1029 For undirected graphs, see "all_neighbours" and "all_reachable".
1031 See also "predecessors".
1033 isolated_vertices
1035 @v = $g->isolated_vertices()
1036 Return the isolated vertices of the graph. In scalar context
1038 return the number of isolated vertices. See "is_isolated_vertex"
1039 for the definition of an isolated vertex.
1040 interior_vertices
1042 @v = $g->interior_vertices()
1043 Return the interior vertices of the graph. In scalar context
1045 return the number of interior vertices. See "is_interior_vertex"
1046 for the definition of an interior vertex.
1047 exterior_vertices
1049 @v = $g->exterior_vertices()
1050 Return the exterior vertices of the graph. In scalar context
1052 return the number of exterior vertices. See "is_exterior_vertex"
1053 for the definition of an exterior vertex.
1054 self_loop_vertices
1056 @v = $g->self_loop_vertices()
1057 Return the self-loop vertices of the graph. In scalar context
1059 return the number of self-loop vertices. See "is_self_loop_vertex"
1060 for the definition of a self-loop vertex.
1061 Connected Graphs and Their Components
1063 In this discussion connected graph refers to any of connected graphs,
1064 biconnected graphs, and strongly connected graphs.
1065 NOTE: if the vertices of the original graph are Perl objects, (in other
1067 words, references, so you must be using "refvertexed") the vertices of
1068 the connected graph are NOT by default usable as Perl objects because
1069 they are blessed into a package with a rather unusable name.
1070 By default, the vertex names of the connected graph are formed from the
1072 names of the vertices of the original graph by (alphabetically sorting
1073 them and) concatenating their names with "+". The vertex attribute
1074 "subvertices" is also used to store the list (as an array reference) of
1075 the original vertices. To change the 'supercomponent' vertex names and
1076 the whole logic of forming these supercomponents use the
1077 "super_component") option to the method calls:
1078 $g->connected_graph(super_component => sub { ... })
1080 $g->biconnected_graph(super_component => sub { ... })
1081 $g->strongly_connected_graph(super_component => sub { ... })
1082 The subroutine reference gets the 'subcomponents' (the vertices of the
1084 original graph) as arguments, and it is supposed to return the new
1085 supercomponent vertex, the "stringified" form of which is used as the
1086 vertex name.
1087 Degree
1089 A vertex has a degree based on the number of incoming and outgoing
1090 edges. This really makes sense only for directed graphs.
1091 degree
1093 vertex_degree
1094 $d = $g->degree($v)
1095 $d = $g->vertex_degree($v)
1096 For directed graphs: the in-degree minus the out-degree at the
1098 vertex.
1099 For undirected graphs: the number of edges at the vertex
1101 (identical to "in_degree()", "out_degree()").
1102 in_degree
1104 $d = $g->in_degree($v)
1105 For directed graphs: the number of incoming edges at the vertex.
1107 For undirected graphs: the number of edges at the vertex (identical
1109 to "out_degree()", "degree()", "vertex_degree()").
1110 out_degree
1112 $o = $g->out_degree($v)
1113 For directed graphs: The number of outgoing edges at the vertex.
1115 For undirected graphs: the number of edges at the vertex (identical
1117 to "in_degree()", "degree()", "vertex_degree()").
1118 average_degree
1120 my $ad = $g->average_degree;
1121 Return the average degree (as in "degree()" or "vertex_degree()")
1123 taken over all vertices.
1124 Related methods are
1126 edges_at
1128 @e = $g->edges_at($v)
1129 The union of edges from and edges to at the vertex.
1131 edges_from
1133 @e = $g->edges_from($v)
1134 The edges leaving the vertex.
1136 edges_to
1138 @e = $g->edges_to($v)
1139 The edges entering the vertex.
1141 See also "average_degree".
1143 Counted Vertices
1145 Counted vertices are vertices with more than one instance, normally
1146 adding vertices is idempotent. To enable counted vertices on a graph,
1147 give the "countvertexed" parameter a true value
1148 use Graph;
1150 my $g = Graph->new(countvertexed => 1);
1151 To find out how many times the vertex has been added:
1153 get_vertex_count
1155 my $c = $g->get_vertex_count($v);
1156 Return the count of the vertex, or undef if the vertex does not
1158 exist.
1159 Multiedges, Multivertices, Multigraphs
1161 Multiedges are edges with more than one "life", meaning that one has to
1162 delete them as many times as they have been added. Normally adding
1163 edges is idempotent (in other words, adding edges more than once makes
1164 no difference).
1165 There are two kinds or degrees of creating multiedges and
1167 multivertices. The two kinds are mutually exclusive.
1168 The weaker kind is called counted, in which the edge or vertex has a
1170 count on it: add operations increase the count, and delete operations
1171 decrease the count, and once the count goes to zero, the edge or vertex
1172 is deleted. If there are attributes, they all are attached to the same
1173 vertex. You can think of this as the graph elements being refcounted,
1174 or reference counted, if that sounds more familiar.
1175 The stronger kind is called (true) multi, in which the edge or vertex
1177 really has multiple separate identities, so that you can for example
1178 attach different attributes to different instances.
1179 To enable multiedges on a graph:
1181 use Graph;
1183 my $g0 = Graph->new(countedged => 1);
1184 my $g0 = Graph->new(multiedged => 1);
1185 Similarly for vertices
1187 use Graph;
1189 my $g1 = Graph->new(countvertexed => 1);
1190 my $g1 = Graph->new(multivertexed => 1);
1191 You can test for these by
1193 is_countedged
1195 countedged
1196 $g->is_countedged
1197 $g->countedged
1198 Return true if the graph is countedged.
1200 is_countvertexed
1202 countvertexed
1203 $g->is_countvertexed
1204 $g->countvertexed
1205 Return true if the graph is countvertexed.
1207 is_multiedged
1209 multiedged
1210 $g->is_multiedged
1211 $g->multiedged
1212 Return true if the graph is multiedged.
1214 is_multivertexed
1216 multivertexed
1217 $g->is_multivertexed
1218 $g->multivertexed
1219 Return true if the graph is multivertexed.
1221 A multiedged (either the weak kind or the strong kind) graph is a
1223 multigraph, for which you can test with "is_multi_graph()".
1224 NOTE: The various graph algorithms do not in general work well with
1226 multigraphs (they often assume simple graphs, that is, no multiedges or
1227 loops), and no effort has been made to test the algorithms with
1228 multigraphs.
1229 vertices() and edges() will return the multiple elements: if you want
1231 just the unique elements, use
1232 unique_vertices
1234 unique_edges
1235 @uv = $g->unique_vertices; # unique
1236 @mv = $g->vertices; # possible multiples
1237 @ue = $g->unique_edges;
1238 @me = $g->edges;
1239 If you are using (the stronger kind of) multielements, you should use
1241 the by_id variants:
1242 add_vertex_by_id
1244 has_vertex_by_id
1245 delete_vertex_by_id
1246 add_edge_by_id
1247 has_edge_by_id
1248 delete_edge_by_id
1249 $g->add_vertex_by_id($v, $id)
1251 $g->has_vertex_by_id($v, $id)
1252 $g->delete_vertex_by_id($v, $id)
1253 $g->add_edge_by_id($u, $v, $id)
1255 $g->has_edge_by_id($u, $v, $id)
1256 $g->delete_edge_by_id($u, $v, $id)
1257 These interfaces only apply to multivertices and multiedges. When you
1259 delete the last vertex/edge in a multivertex/edge, the whole
1260 vertex/edge is deleted. You can use add_vertex()/add_edge() on a
1261 multivertex/multiedge graph, in which case an id is generated
1262 automatically. To find out which the generated id was, you need to use
1263 add_vertex_get_id
1265 add_edge_get_id
1266 $idv = $g->add_vertex_get_id($v)
1268 $ide = $g->add_edge_get_id($u, $v)
1269 To return all the ids of vertices/edges in a multivertex/multiedge, use
1271 get_multivertex_ids
1273 get_multiedge_ids
1274 $g->get_multivertex_ids($v)
1276 $g->get_multiedge_ids($u, $v)
1277 The ids are returned in random order.
1279 To find out how many times the edge has been added (this works for
1281 either kind of multiedges):
1282 get_edge_count
1284 my $c = $g->get_edge_count($u, $v);
1285 Return the count (the "countedness") of the edge, or undef if the
1287 edge does not exist.
1288 The following multi-entity utility functions exist, mirroring the non-
1290 multi vertices and edges:
1291 add_weighted_edge_by_id
1293 add_weighted_edges_by_id
1294 add_weighted_path_by_id
1295 add_weighted_vertex_by_id
1296 add_weighted_vertices_by_id
1297 delete_edge_weight_by_id
1298 delete_vertex_weight_by_id
1299 get_edge_weight_by_id
1300 get_vertex_weight_by_id
1301 has_edge_weight_by_id
1302 has_vertex_weight_by_id
1303 set_edge_weight_by_id
1304 set_vertex_weight_by_id
1305 Topological Sort
1307 topological_sort
1308 toposort
1309 my @ts = $g->topological_sort;
1310 Return the vertices of the graph sorted topologically. Note that
1312 there may be several possible topological orderings; one of them is
1313 returned.
1314 If the graph contains a cycle, a fatal error is thrown, you can
1316 either use "eval" to trap that, or supply the "empty_if_cyclic"
1317 argument with a true value
1318 my @ts = $g->topological_sort(empty_if_cyclic => 1);
1320 in which case an empty array is returned if the graph is cyclic.
1322 Minimum Spanning Trees (MST)
1324 Minimum Spanning Trees or MSTs are tree subgraphs derived from an
1325 undirected graph. MSTs "span the graph" (covering all the vertices)
1326 using as lightly weighted (hence the "minimum") edges as possible.
1327 MST_Kruskal
1329 $mstg = $g->MST_Kruskal;
1330 Returns the Kruskal MST of the graph.
1332 MST_Prim
1334 $mstg = $g->MST_Prim(%opt);
1335 Returns the Prim MST of the graph.
1337 You can choose the first vertex with $opt{ first_root }.
1339 MST_Dijkstra
1341 minimum_spanning_tree
1342 $mstg = $g->MST_Dijkstra;
1343 $mstg = $g->minimum_spanning_tree;
1344 Aliases for MST_Prim.
1346 Single-Source Shortest Paths (SSSP)
1348 Single-source shortest paths, also known as Shortest Path Trees (SPTs).
1349 For either a directed or an undirected graph, return a (tree) subgraph
1350 that from a single start vertex (the "single source") travels the
1351 shortest possible paths (the paths with the lightest weights) to all
1352 the other vertices. Note that the SSSP is neither reflexive (the
1353 shortest paths do not include the zero-length path from the source
1354 vertex to the source vertex) nor transitive (the shortest paths do not
1355 include transitive closure paths). If no weight is defined for an
1356 edge, 1 (one) is assumed.
1357 SPT_Dijkstra
1359 $sptg = $g->SPT_Dijkstra($root)
1360 $sptg = $g->SPT_Dijkstra(%opt)
1361 Return as a graph the the single-source shortest paths of the graph
1363 using Dijkstra's algorithm. The graph cannot contain negative
1364 edges (negative edges cause the algorithm to abort with an error
1365 message "Graph::SPT_Dijkstra: edge ... is negative").
1366 You can choose the first vertex of the result with either a single
1368 vertex argument or with $opt{ first_root }, otherwise a random
1369 vertex is chosen.
1370 NOTE: note that all the vertices might not be reachable from the
1372 selected (explicit or random) start vertex.
1373 NOTE: after the first reachable tree from the first start vertex
1375 has been finished, and if there still are unvisited vertices,
1376 SPT_Dijkstra will keep on selecting unvisited vertices.
1377 The next roots (in case the first tree doesn't visit all the
1379 vertices) can be chosen by setting one of the following options to
1380 true: "next_root", "next_alphabetic", "next_numeric",
1381 "next_random".
1382 The "next_root" is the most customizable: the value needs to be a
1384 subroutine reference which will receive the graph and the unvisited
1385 vertices as hash reference. If you want to only visit the first
1386 tree, use "next_root =" sub { undef }>. The rest of these options
1387 are booleans. If none of them are true, a random unvisited vertex
1388 will be selected.
1389 The first start vertex is be available as the graph attribute
1391 "SPT_Dijkstra_root").
1392 The result weights of vertices can be retrieved from the result
1394 graph by
1395 my $w = $sptg->get_vertex_attribute($v, 'weight');
1397 The predecessor vertex of a vertex in the result graph can be
1399 retrieved by
1400 my $u = $sptg->get_vertex_attribute($v, 'p');
1402 ("A successor vertex" cannot be retrieved as simply because a
1404 single vertex can have several successors. You can first find the
1405 "neighbors()" vertices and then remove the predecessor vertex.)
1406 If you want to find the shortest path between two vertices, see
1408 "SP_Dijkstra".
1409 SSSP_Dijkstra
1411 single_source_shortest_paths
1412 Aliases for SPT_Dijkstra.
1413 SP_Dijkstra
1415 @path = $g->SP_Dijkstra($u, $v)
1416 Return the vertices in the shortest path in the graph $g between
1418 the two vertices $u, $v. If no path can be found, an empty list is
1419 returned.
1420 Uses SPT_Dijkstra().
1422 SPT_Dijkstra_clear_cache
1424 $g->SPT_Dijkstra_clear_cache
1425 See "Clearing cached results".
1427 SPT_Bellman_Ford
1429 $sptg = $g->SPT_Bellman_Ford(%opt)
1430 Return as a graph the single-source shortest paths of the graph
1432 using Bellman-Ford's algorithm. The graph can contain negative
1433 edges but not negative cycles (negative cycles cause the algorithm
1434 to abort with an error message "Graph::SPT_Bellman_Ford: negative
1435 cycle exists/").
1436 You can choose the start vertex of the result with either a single
1438 vertex argument or with $opt{ first_root }, otherwise a random
1439 vertex is chosen.
1440 NOTE: note that all the vertices might not be reachable from the
1442 selected (explicit or random) start vertex.
1443 The start vertex is be available as the graph attribute
1445 "SPT_Bellman_Ford_root").
1446 The result weights of vertices can be retrieved from the result
1448 graph by
1449 my $w = $sptg->get_vertex_attribute($v, 'weight');
1451 The predecessor vertex of a vertex in the result graph can be
1453 retrieved by
1454 my $u = $sptg->get_vertex_attribute($v, 'p');
1456 ("A successor vertex" cannot be retrieved as simply because a
1458 single vertex can have several successors. You can first find the
1459 "neighbors()" vertices and then remove the predecessor vertex.)
1460 If you want to find the shortes path between two vertices, see
1462 "SP_Bellman_Ford".
1463 SSSP_Bellman_Ford
1465 Alias for SPT_Bellman_Ford.
1466 SP_Bellman_Ford
1468 @path = $g->SP_Bellman_Ford($u, $v)
1469 Return the vertices in the shortest path in the graph $g between
1471 the two vertices $u, $v. If no path can be found, an empty list is
1472 returned.
1473 Uses SPT_Bellman_Ford().
1475 SPT_Bellman_Ford_clear_cache
1477 $g->SPT_Bellman_Ford_clear_cache
1478 See "Clearing cached results".
1480 All-Pairs Shortest Paths (APSP)
1482 For either a directed or an undirected graph, return the APSP object
1483 describing all the possible paths between any two vertices of the
1484 graph. If no weight is defined for an edge, 1 (one) is assumed.
1485 Note that weight of 0 (zero) does not mean do not use this edge, it
1487 means essentially the opposite: an edge that has zero cost, an edge
1488 that makes the vertices the same.
1489 APSP_Floyd_Warshall
1491 all_pairs_shortest_paths
1492 my $apsp = $g->APSP_Floyd_Warshall(...);
1493 Return the all-pairs shortest path object computed from the graph
1495 using Floyd-Warshall's algorithm. The length of a path between two
1496 vertices is the sum of weight attribute of the edges along the
1497 shortest path between the two vertices. If no weight attribute
1498 name is specified explicitly
1499 $g->APSP_Floyd_Warshall(attribute_name => 'height');
1501 the attribute "weight" is assumed.
1503 If an edge has no defined weight attribute, the value of one is
1505 assumed when getting the attribute.
1506 Once computed, you can query the APSP object with
1508 path_length
1510 my $l = $apsp->path_length($u, $v);
1511 Return the length of the shortest path between the two
1513 vertices.
1514 path_vertices
1516 my @v = $apsp->path_vertices($u, $v);
1517 Return the list of vertices along the shortest path.
1519 path_predecessor
1521 my $u = $apsp->path_predecessor($v);
1522 Returns the predecessor of vertex $v in the all-pairs
1524 shortest paths.
1525 average_path_length
1527 my $apl = $g->average_path_length; # All vertex pairs.
1528 my $apl = $g->average_path_length($u); # From $u.
1530 my $apl = $g->average_path_length($u, undef); # From $u.
1531 my $apl = $g->average_path_length($u, $v); # From $u to $v.
1533 my $apl = $g->average_path_length(undef, $v); # To $v.
1535 Return the average (shortest) path length over all the
1537 vertex pairs of the graph, from a vertex, between two
1538 vertices, and to a vertex.
1539 longest_path
1541 my @lp = $g->longest_path;
1542 my $lp = $g->longest_path;
1543 In scalar context return the longest shortest path length
1545 over all the vertex pairs of the graph. In list context
1546 return the vertices along a longest shortest path. Note
1547 that there might be more than one such path; this interface
1548 returns a random one of them.
1549 NOTE: this returns the longest shortest path, not the
1551 longest path.
1552 diameter
1554 graph_diameter
1555 my $gd = $g->diameter;
1556 The longest path over all the vertex pairs is known as the
1558 graph diameter.
1559 For an unconnected graph, single-vertex, or empty graph,
1561 returns "undef".
1562 shortest_path
1564 my @sp = $g->shortest_path;
1565 my $sp = $g->shortest_path;
1566 In scalar context return the shortest length over all the
1568 vertex pairs of the graph. In list context return the
1569 vertices along a shortest path. Note that there might be
1570 more than one such path; this interface returns a random
1571 one of them.
1572 For an unconnected, single-vertex, or empty graph, returns
1574 "undef" or an empty list.
1575 radius
1577 my $gr = $g->radius;
1578 The shortest longest path over all the vertex pairs is
1580 known as the graph radius. See also "diameter".
1581 For an unconnected, single-vertex, or empty graph, returns
1583 Infinity.
1584 center_vertices
1586 centre_vertices
1587 my @c = $g->center_vertices;
1588 my @c = $g->center_vertices($delta);
1589 The graph center is the set of vertices for which the
1591 vertex eccentricity is equal to the graph radius. The
1592 vertices are returned in random order. By specifying a
1593 delta value you can widen the criterion from strict
1594 equality (handy for non-integer edge weights).
1595 For an unconnected, single-vertex, or empty graph, returns
1597 an empty list.
1598 vertex_eccentricity
1600 my $ve = $g->vertex_eccentricity($v);
1601 The longest path to a vertex is known as the vertex
1603 eccentricity.
1604 If the graph is unconnected, single-vertex, or empty graph,
1606 returns Inf.
1607 You can walk through the matrix of the shortest paths by using
1609 for_shortest_paths
1611 $n = $g->for_shortest_paths($callback)
1612 The number of shortest paths is returned (this should be equal
1614 to V*V). The $callback is a sub reference that receives four
1615 arguments: the transitive closure object from
1616 Graph::TransitiveClosure, the two vertices, and the index to
1617 the current shortest paths (0..V*V-1).
1618 Clearing cached results
1620 For many graph algorithms there are several different but equally valid
1621 results. (Pseudo)Randomness is used internally by the Graph module to
1622 for example pick a random starting vertex, and to select random edges
1623 from a vertex.
1624 For efficiency the computed result is often cached to avoid recomputing
1626 the potentially expensive operation, and this also gives additional
1627 determinism (once a correct result has been computed, the same result
1628 will always be given).
1629 However, sometimes the exact opposite is desireable, and the possible
1631 alternative results are wanted (within the limits of the
1632 pseudorandomness: not all the possible solutions are guaranteed to be
1633 returned, usually only a subset is retuned). To undo the caching, the
1634 following methods are available:
1635 · connectivity_clear_cache
1637 Affects "connected_components", "connected_component_by_vertex",
1639 "connected_component_by_index", "same_connected_components",
1640 "connected_graph", "is_connected", "is_weakly_connected",
1641 "weakly_connected_components",
1642 "weakly_connected_component_by_vertex",
1643 "weakly_connected_component_by_index",
1644 "same_weakly_connected_components", "weakly_connected_graph".
1645 · biconnectivity_clear_cache
1647 Affects "biconnected_components",
1649 "biconnected_component_by_vertex",
1650 "biconnected_component_by_index", "is_edge_connected",
1651 "is_edge_separable", "articulation_points", "cut_vertices",
1652 "is_biconnected", "biconnected_graph",
1653 "same_biconnected_components", "bridges".
1654 · strong_connectivity_clear_cache
1656 Affects "strongly_connected_components",
1658 "strongly_connected_component_by_vertex",
1659 "strongly_connected_component_by_index",
1660 "same_strongly_connected_components", "is_strongly_connected",
1661 "strongly_connected", "strongly_connected_graph".
1662 · SPT_Dijkstra_clear_cache
1664 Affects "SPT_Dijkstra", "SSSP_Dijkstra",
1666 "single_source_shortest_paths", "SP_Dijkstra".
1667 · SPT_Bellman_Ford_clear_cache
1669 Affects "SPT_Bellman_Ford", "SSSP_Bellman_Ford", "SP_Bellman_Ford".
1671 Note that any such computed and cached results are of course always
1673 automatically discarded whenever the graph is modified.
1674 Random
1676 You can either ask for random elements of existing graphs or create
1677 random graphs.
1678 random_vertex
1680 my $v = $g->random_vertex;
1681 Return a random vertex of the graph, or undef if there are no
1683 vertices.
1684 random_edge
1686 my $e = $g->random_edge;
1687 Return a random edge of the graph as an array reference having the
1689 vertices as elements, or undef if there are no edges.
1690 random_successor
1692 my $v = $g->random_successor($v);
1693 Return a random successor of the vertex in the graph, or undef if
1695 there are no successors.
1696 random_predecessor
1698 my $u = $g->random_predecessor($v);
1699 Return a random predecessor of the vertex in the graph, or undef if
1701 there are no predecessors.
1702 random_graph
1704 my $g = Graph->random_graph(%opt);
1705 Construct a random graph. The %opt must contain the "vertices"
1707 argument
1708 vertices => vertices_def
1710 where the vertices_def is one of
1712 · an array reference where the elements of the array
1714 reference are the vertices
1715 · a number N in which case the vertices will be integers
1717 0..N-1
1718 The %opt may have either of the argument "edges" or the argument
1720 "edges_fill". Both are used to define how many random edges to add to
1721 the graph; "edges" is an absolute number, while "edges_fill" is a
1722 relative number (relative to the number of edges in a complete graph,
1723 C). The number of edges can be larger than C, but only if the graph is
1724 countedged. The random edges will not include self-loops. If neither
1725 "edges" nor "edges_fill" is specified, an "edges_fill" of 0.5 is
1726 assumed.
1727 If you want repeatable randomness (what is an oxymoron?) you can use
1729 the "random_seed" option:
1730 $g = Graph->random_graph(vertices => 10, random_seed => 1234);
1732 As this uses the standard Perl srand(), the usual caveat applies: use
1734 it sparingly, and consider instead using a single srand() call at the
1735 top level of your application.
1736 The default random distribution of edges is flat, that is, any pair of
1738 vertices is equally likely to appear. To define your own distribution,
1739 use the "random_edge" option:
1740 $g = Graph->random_graph(vertices => 10, random_edge => \&d);
1742 where "d" is a code reference receiving ($g, $u, $v, $p) as parameters,
1744 where the $g is the random graph, $u and $v are the vertices, and the
1745 $p is the probability ([0,1]) for a flat distribution. It must return
1746 a probability ([0,1]) that the vertices $u and $v have an edge between
1747 them. Note that returning one for a particular pair of vertices
1748 doesn't guarantee that the edge will be present in the resulting graph
1749 because the required number of edges might be reached before that
1750 particular pair is tested for the possibility of an edge. Be very
1751 careful to adjust also "edges" or "edges_fill" so that there is a
1752 possibility of the filling process terminating.
1753 NOTE: a known problem with randomness in openbsd pre-perl-5.20 is that
1755 using a seed does not give you deterministic randomness. This affects
1756 any Perl code, not just Graph.
1757 Attributes
1759 You can attach free-form attributes (key-value pairs, in effect a full
1760 Perl hash) to each vertex, edge, and the graph itself.
1761 Note that attaching attributes does slow down some other operations on
1763 the graph by a factor of three to ten. For example adding edge
1764 attributes does slow down anything that walks through all the edges.
1765 For vertex attributes:
1767 set_vertex_attribute
1769 $g->set_vertex_attribute($v, $name, $value)
1770 Set the named vertex attribute.
1772 If the vertex does not exist, the set_...() will create it, and the
1774 other vertex attribute methods will return false or empty.
1775 NOTE: any attributes beginning with an underscore/underline (_) are
1777 reserved for the internal use of the Graph module.
1778 get_vertex_attribute
1780 $value = $g->get_vertex_attribute($v, $name)
1781 Return the named vertex attribute.
1783 has_vertex_attribute
1785 $g->has_vertex_attribute($v, $name)
1786 Return true if the vertex has an attribute, false if not.
1788 delete_vertex_attribute
1790 $g->delete_vertex_attribute($v, $name)
1791 Delete the named vertex attribute.
1793 set_vertex_attributes
1795 $g->set_vertex_attributes($v, $attr)
1796 Set all the attributes of the vertex from the anonymous hash $attr.
1798 NOTE: any attributes beginning with an underscore ("_") are
1800 reserved for the internal use of the Graph module.
1801 get_vertex_attributes
1803 $attr = $g->get_vertex_attributes($v)
1804 Return all the attributes of the vertex as an anonymous hash.
1806 get_vertex_attribute_names
1808 @name = $g->get_vertex_attribute_names($v)
1809 Return the names of vertex attributes.
1811 get_vertex_attribute_values
1813 @value = $g->get_vertex_attribute_values($v)
1814 Return the values of vertex attributes.
1816 has_vertex_attributes
1818 $g->has_vertex_attributes($v)
1819 Return true if the vertex has any attributes, false if not.
1821 delete_vertex_attributes
1823 $g->delete_vertex_attributes($v)
1824 Delete all the attributes of the named vertex.
1826 If you are using multivertices, use the by_id variants:
1828 set_vertex_attribute_by_id
1830 get_vertex_attribute_by_id
1831 has_vertex_attribute_by_id
1832 delete_vertex_attribute_by_id
1833 set_vertex_attributes_by_id
1834 get_vertex_attributes_by_id
1835 get_vertex_attribute_names_by_id
1836 get_vertex_attribute_values_by_id
1837 has_vertex_attributes_by_id
1838 delete_vertex_attributes_by_id
1839 $g->set_vertex_attribute_by_id($v, $id, $name, $value)
1840 $g->get_vertex_attribute_by_id($v, $id, $name)
1841 $g->has_vertex_attribute_by_id($v, $id, $name)
1842 $g->delete_vertex_attribute_by_id($v, $id, $name)
1843 $g->set_vertex_attributes_by_id($v, $id, $attr)
1844 $g->get_vertex_attributes_by_id($v, $id)
1845 $g->get_vertex_attribute_values_by_id($v, $id)
1846 $g->get_vertex_attribute_names_by_id($v, $id)
1847 $g->has_vertex_attributes_by_id($v, $id)
1848 $g->delete_vertex_attributes_by_id($v, $id)
1849 For edge attributes:
1851 set_edge_attribute
1853 $g->set_edge_attribute($u, $v, $name, $value)
1854 Set the named edge attribute.
1856 If the edge does not exist, the set_...() will create it, and the
1858 other edge attribute methods will return false or empty.
1859 NOTE: any attributes beginning with an underscore ("_") are
1861 reserved for the internal use of the Graph module.
1862 get_edge_attribute
1864 $value = $g->get_edge_attribute($u, $v, $name)
1865 Return the named edge attribute.
1867 has_edge_attribute
1869 $g->has_edge_attribute($u, $v, $name)
1870 Return true if the edge has an attribute, false if not.
1872 delete_edge_attribute
1874 $g->delete_edge_attribute($u, $v, $name)
1875 Delete the named edge attribute.
1877 set_edge_attributes
1879 $g->set_edge_attributes($u, $v, $attr)
1880 Set all the attributes of the edge from the anonymous hash $attr.
1882 NOTE: any attributes beginning with an underscore ("_") are
1884 reserved for the internal use of the Graph module.
1885 get_edge_attributes
1887 $attr = $g->get_edge_attributes($u, $v)
1888 Return all the attributes of the edge as an anonymous hash.
1890 get_edge_attribute_names
1892 @name = $g->get_edge_attribute_names($u, $v)
1893 Return the names of edge attributes.
1895 get_edge_attribute_values
1897 @value = $g->get_edge_attribute_values($u, $v)
1898 Return the values of edge attributes.
1900 has_edge_attributes
1902 $g->has_edge_attributes($u, $v)
1903 Return true if the edge has any attributes, false if not.
1905 delete_edge_attributes
1907 $g->delete_edge_attributes($u, $v)
1908 Delete all the attributes of the named edge.
1910 If you are using multiedges, use the by_id variants:
1912 set_edge_attribute_by_id
1914 get_edge_attribute_by_id
1915 has_edge_attribute_by_id
1916 delete_edge_attribute_by_id
1917 set_edge_attributes_by_id
1918 get_edge_attributes_by_id
1919 get_edge_attribute_names_by_id
1920 get_edge_attribute_values_by_id
1921 has_edge_attributes_by_id
1922 delete_edge_attributes_by_id
1923 $g->set_edge_attribute_by_id($u, $v, $id, $name, $value)
1924 $g->get_edge_attribute_by_id($u, $v, $id, $name)
1925 $g->has_edge_attribute_by_id($u, $v, $id, $name)
1926 $g->delete_edge_attribute_by_id($u, $v, $id, $name)
1927 $g->set_edge_attributes_by_id($u, $v, $id, $attr)
1928 $g->get_edge_attributes_by_id($u, $v, $id)
1929 $g->get_edge_attribute_values_by_id($u, $v, $id)
1930 $g->get_edge_attribute_names_by_id($u, $v, $id)
1931 $g->has_edge_attributes_by_id($u, $v, $id)
1932 $g->delete_edge_attributes_by_id($u, $v, $id)
1933 For graph attributes:
1935 set_graph_attribute
1937 $g->set_graph_attribute($name, $value)
1938 Set the named graph attribute.
1940 NOTE: any attributes beginning with an underscore ("_") are
1942 reserved for the internal use of the Graph module.
1943 get_graph_attribute
1945 $value = $g->get_graph_attribute($name)
1946 Return the named graph attribute.
1948 has_graph_attribute
1950 $g->has_graph_attribute($name)
1951 Return true if the graph has an attribute, false if not.
1953 delete_graph_attribute
1955 $g->delete_graph_attribute($name)
1956 Delete the named graph attribute.
1958 set_graph_attributes
1960 $g->get_graph_attributes($attr)
1961 Set all the attributes of the graph from the anonymous hash $attr.
1963 NOTE: any attributes beginning with an underscore ("_") are
1965 reserved for the internal use of the Graph module.
1966 get_graph_attributes
1968 $attr = $g->get_graph_attributes()
1969 Return all the attributes of the graph as an anonymous hash.
1971 get_graph_attribute_names
1973 @name = $g->get_graph_attribute_names()
1974 Return the names of graph attributes.
1976 get_graph_attribute_values
1978 @value = $g->get_graph_attribute_values()
1979 Return the values of graph attributes.
1981 has_graph_attributes
1983 $g->has_graph_attributes()
1984 Return true if the graph has any attributes, false if not.
1986 delete_graph_attributes
1988 $g->delete_graph_attributes()
1989 Delete all the attributes of the named graph.
1991 Weighted
1993 As convenient shortcuts the following methods add, query, and
1994 manipulate the attribute "weight" with the specified value to the
1995 respective Graph elements.
1996 add_weighted_edge
1998 $g->add_weighted_edge($u, $v, $weight)
1999 add_weighted_edges
2001 $g->add_weighted_edges($u1, $v1, $weight1, ...)
2002 add_weighted_path
2004 $g->add_weighted_path($v1, $weight1, $v2, $weight2, $v3, ...)
2005 add_weighted_vertex
2007 $g->add_weighted_vertex($v, $weight)
2008 add_weighted_vertices
2010 $g->add_weighted_vertices($v1, $weight1, $v2, $weight2, ...)
2011 delete_edge_weight
2013 $g->delete_edge_weight($u, $v)
2014 delete_vertex_weight
2016 $g->delete_vertex_weight($v)
2017 get_edge_weight
2019 $g->get_edge_weight($u, $v)
2020 get_vertex_weight
2022 $g->get_vertex_weight($v)
2023 has_edge_weight
2025 $g->has_edge_weight($u, $v)
2026 has_vertex_weight
2028 $g->has_vertex_weight($v)
2029 set_edge_weight
2031 $g->set_edge_weight($u, $v, $weight)
2032 set_vertex_weight
2034 $g->set_vertex_weight($v, $weight)
2035 Isomorphism
2037 Two graphs being isomorphic means that they are structurally the same
2038 graph, the difference being that the vertices might have been renamed
2039 or substituted. For example in the below example $g0 and $g1 are
2040 isomorphic: the vertices "b c d" have been renamed as "z x y".
2041 $g0 = Graph->new;
2043 $g0->add_edges(qw(a b a c c d));
2044 $g1 = Graph->new;
2045 $g1->add_edges(qw(a x x y a z));
2046 In the general case determining isomorphism is NP-hard, in other words,
2048 really hard (time-consuming), no other ways of solving the problem are
2049 known than brute force check of of all the possibilities (with possible
2050 optimization tricks, of course, but brute force still rules at the end
2051 of the day).
2052 A very rough guess at whether two graphs could be isomorphic is
2054 possible via the method
2055 could_be_isomorphic
2057 $g0->could_be_isomorphic($g1)
2058 If the graphs do not have the same number of vertices and edges, false
2060 is returned. If the distribution of in-degrees and out-degrees at the
2061 vertices of the graphs does not match, false is returned. Otherwise,
2062 true is returned.
2063 What is actually returned is the maximum number of possible isomorphic
2065 graphs between the two graphs, after the above sanity checks have been
2066 conducted. It is basically the product of the factorials of the
2067 absolute values of in-degrees and out-degree pairs at each vertex, with
2068 the isolated vertices ignored (since they could be reshuffled and
2069 renamed arbitrarily). Note that for large graphs the product of these
2070 factorials can overflow the maximum presentable number (the floating
2071 point number) in your computer (in Perl) and you might get for example
2072 Infinity as the result.
2073 Miscellaneous
2075 betweenness
2076 %b = $g->betweenness
2077 Returns a map of vertices to their Freeman's betweennesses:
2079 C_b(v) = \sum_{s \neq v \neq t \in V} \frac{\sigma_{s,t}(v)}{\sigma_{s,t}}
2081 It is described in:
2083 Freeman, A set of measures of centrality based on betweenness, http://arxiv.org/pdf/cond-mat/0309045
2085 and based on the algorithm from:
2087 "A Faster Algorithm for Betweenness Centrality"
2089 clustering_coefficient
2091 $gamma = $g->clustering_coefficient()
2092 ($gamma, %clustering) = $g->clustering_coefficient()
2093 Returns the clustering coefficient gamma as described in
2095 Duncan J. Watts and Steven Strogatz, Collective dynamics of 'small-world' networks, http://audiophile.tam.cornell.edu/SS_nature_smallworld.pdf
2097 In scalar context returns just the average gamma, in list context
2099 returns the average gamma and a hash of vertices to clustering
2100 coefficients.
2101 subgraph_by_radius
2103 $s = $g->subgraph_by_radius($n, $radius);
2104 Returns a subgraph representing the ball of $radius around node $n
2106 (breadth-first search).
2107 The "expect" methods can be used to test a graph and croak if the graph
2109 call is not as expected.
2110 expect_acyclic
2112 expect_dag
2113 expect_directed
2114 expect_hyperedged
2115 expect_hypervertexed
2116 expect_multiedged
2117 expect_multivertexed
2118 expect_no_args
2119 expect_non_multiedged
2120 expect_non_multivertexed
2121 expect_non_unionfind
2122 expect_undirected
2123 In many algorithms it is useful to have a value representing the
2125 infinity. The Graph provides (and itself uses):
2126 Infinity
2128 (Not exported, use Graph::Infinity explicitly)
2129 Size Requirements
2131 A graph takes up at least 1172 bytes of memory.
2132 A vertex takes up at least 100 bytes of memory.
2134 An edge takes up at least 400 bytes of memory.
2136 (A Perl scalar value takes 16 bytes, or 12 bytes if it's a reference.)
2138 These size approximations are very approximate and optimistic (they are
2140 based on total_size() of Devel::Size). In real life many factors
2141 affect these numbers, for example how Perl is configured. The numbers
2142 are for a 32-bit platform and for Perl 5.8.8.
2143 Roughly, the above numbers mean that in a megabyte of memory you can
2145 fit for example a graph of about 1000 vertices and about 2500 edges.
2146 Hyperedges, hypervertices, hypergraphs
2148 BEWARE: this is a rather thinly tested feature, and the theory is even
2149 less so. Do not expect this to stay as it is (or at all) in future
2150 releases.
2151 NOTE: most usual graph algorithms (and basic concepts) break horribly
2153 (or at least will look funny) with these hyperthingies. Caveat emptor.
2154 Hyperedges are edges that connect a number of vertices different from
2156 the usual two.
2157 Hypervertices are vertices that consist of a number of vertices
2159 different from the usual one.
2160 Note that for hypervertices there is an asymmetry: when adding
2162 hypervertices, the single vertices are also implicitly added.
2163 Hypergraphs are graphs with hyperedges.
2165 To enable hyperness when constructing Graphs use the "hyperedged" and
2167 "hypervertexed" attributes:
2168 my $h = Graph->new(hyperedged => 1, hypervertexed => 1);
2170 To add hypervertexes, either explicitly use more than one vertex (or,
2172 indeed, no vertices) when using add_vertex()
2173 $h->add_vertex("a", "b")
2175 $h->add_vertex()
2176 or implicitly with array references when using add_edge()
2178 $h->add_edge(["a", "b"], "c")
2180 $h->add_edge()
2181 Testing for existence and deletion of hypervertices and hyperedges
2183 works similarly.
2184 To test for hyperness of a graph use the
2186 is_hypervertexed
2188 hypervertexed
2189 $g->is_hypervertexed
2190 $g->hypervertexed
2191 is_hyperedged
2193 hyperedged
2194 $g->is_hyperedged
2195 $g->hyperedged
2196 Since hypervertices consist of more than one vertex:
2198 vertices_at
2200 $g->vertices_at($v)
2201 Return the vertices at the vertex. This may return just the vertex or
2203 also other vertices.
2204 To go with the concept of undirected in normal (non-hyper) graphs,
2206 there is a similar concept of omnidirected (this is my own coinage,
2207 "all-directions") for hypergraphs, and you can naturally test for it by
2208 is_omnidirected
2210 omnidirected
2211 is_omniedged
2212 omniedged
2213 $g->is_omniedged
2214 $g->omniedged
2216 $g->is_omnidirected
2218 $g->omnidirected
2220 Return true if the graph is omnidirected (edges have no direction),
2222 false if not.
2223 You may be wondering why on earth did I make up this new concept, why
2225 didn't the "undirected" work for me? Well, because of this:
2226 $g = Graph->new(hypervertexed => 1, omnivertexed => 1);
2228 That's right, vertices can be omni, too - and that is indeed the
2230 default. You can turn it off and then $g->add_vertex(qw(a b)) no more
2231 means adding also the (hyper)vertex qw(b a). In other words, the
2232 "directivity" is orthogonal to (or independent of) the number of
2233 vertices in the vertex/edge.
2234 is_omnivertexed
2236 omnivertexed
2237 Another oddity that fell out of the implementation is the uniqueness
2239 attribute, that comes naturally in "uniqedged" and "uniqvertexed"
2240 flavours. It does what it sounds like, to unique or not the vertices
2241 participating in edges and vertices (is the hypervertex qw(a b a) the
2242 same as the hypervertex qw(a b), for example). Without too much
2243 explanation:
2244 is_uniqedged
2246 uniqedged
2247 is_uniqvertexed
2248 uniqvertexed
2249 Backward compatibility with Graph 0.2
2251 The Graph 0.2 (and 0.2xxxx) had the following features
2252 · vertices() always sorted the vertex list, which most of the time is
2254 unnecessary and wastes CPU.
2255 · edges() returned a flat list where the begin and end vertices of
2257 the edges were intermingled: every even index had an edge begin
2258 vertex, and every odd index had an edge end vertex. This had the
2259 unfortunate consequence of "scalar(@e = edges)" being twice the
2260 number of edges, and complicating any algorithm walking through the
2261 edges.
2262 · The vertex list returned by edges() was sorted, the primary key
2264 being the edge begin vertices, and the secondary key being the edge
2265 end vertices.
2266 · The attribute API was oddly position dependent and dependent on the
2268 number of arguments. Use ..._graph_attribute(),
2269 ..._vertex_attribute(), ..._edge_attribute() instead.
2270 In future releases of Graph (any release after 0.50) the 0.2xxxx
2272 compatibility will be removed. Upgrade your code now.
2273 If you want to continue using these (mis)features you can use the
2275 "compat02" flag when creating a graph:
2276 my $g = Graph->new(compat02 => 1);
2278 This will change the vertices() and edges() appropriately. This,
2280 however, is not recommended, since it complicates all the code using
2281 vertices() and edges(). Instead it is recommended that the
2282 vertices02() and edges02() methods are used. The corresponding new
2283 style (unsorted, and edges() returning a list of references) methods
2284 are called vertices05() and edges05().
2285 To test whether a graph has the compatibility turned on
2287 is_compat02
2289 compat02
2290 $g->is_compat02
2291 $g->compat02
2292 The following are not backward compatibility methods, strictly
2294 speaking, because they did not exist before.
2295 edges02
2297 Return the edges as a flat list of vertices, elements at even
2298 indices being the start vertices and elements at odd indices being
2299 the end vertices.
2300 edges05
2302 Return the edges as a list of array references, each element
2303 containing the vertices of each edge. (This is not a backward
2304 compatibility interface as such since it did not exist before.)
2305 vertices02
2307 Return the vertices in sorted order.
2308 vertices05
2310 Return the vertices in random order.
2311 For the attributes the recommended way is to use the new API.
2313 Do not expect new methods to work for compat02 graphs.
2315 The following compatibility methods exist:
2317 has_attribute
2319 has_attributes
2320 get_attribute
2321 get_attributes
2322 set_attribute
2323 set_attributes
2324 delete_attribute
2325 delete_attributes
2326 Do not use the above, use the new attribute interfaces instead.
2327 vertices_unsorted
2329 Alias for vertices() (or rather, vertices05()) since the vertices()
2330 now always returns the vertices in an unsorted order. You can also
2331 use the unsorted_vertices import, but only with a true value (false
2332 values will cause an error).
2333 density_limits
2335 my ($sparse, $dense, $complete) = $g->density_limits;
2336 Return the "density limits" used to classify graphs as "sparse" or
2338 "dense". The first limit is C/4 and the second limit is 3C/4,
2339 where C is the number of edges in a complete graph (the last
2340 "limit").
2341 density
2343 my $density = $g->density;
2344 Return the density of the graph, the ratio of the number of edges
2346 to the number of edges in a complete graph.
2347 vertex
2349 my $v = $g->vertex($v);
2350 Return the vertex if the graph has the vertex, undef otherwise.
2352 out_edges
2354 in_edges
2355 edges($v)
2356 This is now called edges_at($v).
2357 DIAGNOSTICS
2359 · Graph::...Map...: arguments X expected Y ...
2360 If you see these (more user-friendly error messages should have
2362 been triggered above and before these) please report any such
2363 occurrences, but in general you should be happy to see these since
2364 it means that an attempt to call something with a wrong number of
2365 arguments was caught in time.
2366 · Graph::add_edge: graph is not hyperedged ...
2368 Maybe you used add_weighted_edge() with only the two vertex
2370 arguments.
2371 · Not an ARRAY reference at lib/Graph.pm ...
2373 One possibility is that you have code based on Graph 0.2xxxx that
2375 assumes Graphs being blessed hash references, possibly also
2376 assuming that certain hash keys are available to use for your own
2377 purposes. In Graph 0.50 none of this is true. Please do not
2378 expect any particular internal implementation of Graphs. Use
2379 inheritance and graph/vertex/edge attributes instead.
2380 Another possibility is that you meant to have objects (blessed
2382 references) as graph vertices, but forgot to use "refvertexed" (see
2383 "refvertexed") when creating the graph.
2384
2386 All bad terminology, bugs, and inefficiencies are naturally mine, all
2387 mine, and not the fault of the below.
2388 Thanks to Nathan Goodman and Andras Salamon for bravely betatesting my
2390 pre-0.50 code. If they missed something, that was only because of my
2391 fiendish code.
2392 The following literature for algorithms and some test cases:
2394 · Algorithms in C, Third Edition, Part 5, Graph Algorithms, Robert
2396 Sedgewick, Addison Wesley
2397 · Introduction to Algorithms, First Edition, Cormen-Leiserson-Rivest,
2399 McGraw Hill
2400 · Graphs, Networks and Algorithms, Dieter Jungnickel, Springer
2402
2404 Persistent/Serialized graphs? You want to read/write Graphs? See the
2405 Graph::Reader and Graph::Writer in CPAN.
2406
2408 <https://github.com/neilbowers/Graph>
2409
2411 Jarkko Hietaniemi jhi@iki.fi
2412 Now being maintained by Neil Bowers <neilb@cpan.org>
2414
2416 Copyright (c) 1998-2014 Jarkko Hietaniemi. All rights reserved.
2417 This is free software; you can redistribute it and/or modify it under
2419 the same terms as the Perl 5 programming language system itself.
2420perl v5.30.1 2020-01-30 Graph(3)