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->any_edge(...)
21 $g->delete_edge(...);
22 $g->add_vertex(...);
24 $g->has_vertex(...);
25 $g->delete_vertex(...);
26 $g->vertices(...)
28 $g->edges(...)
29 # And many, many more, see below.
31
33 Non-Description
34 This module is not for drawing or rendering any sort of graphics or
35 images, business, visualization, or otherwise.
36 Description
38 Instead, this module is for creating abstract data structures called
39 graphs, and for doing various operations on those.
40 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 Constructors
46 new Create an empty graph.
47 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 The following options are available:
53 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 You can test the directness of a graph with
61 $g->is_directed() and $g->is_undirected().
62 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 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 You can test the directness of a graph with
75 $g->is_directed() and $g->is_undirected().
76 refvertexed
78 refvertexed_stringified
79 If you want to use references (including Perl objects) as
80 vertices, use "refvertexed".
81 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 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 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 has_union_find
110 Returns true if the graph was created with a true
111 "unionfind" parameter.
112 vertices
114 An array reference of vertices to add.
115 edges An array reference of array references of edge vertices to
117 add.
118 copy
120 copy_graph
121 my $c = $g->copy_graph;
122 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 Also the following vertex/edge attributes are copied:
129 refvertexed/countvertexed/multivertexed
131 hyperedged/countedged/multiedged
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 As of 0.9712, you can also copy the graph properties of an existing
141 object, but with overrides:
142 my $c = $g->new(multiedged => 0);
144 deep_copy
146 deep_copy_graph
147 my $c = $g->deep_copy_graph;
148 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 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 If your vertices are references, the copied graph will have its
159 connections fixed up. Support for this is new as of 0.9723, so
160 please report any problems.
161 undirected_copy
163 undirected_copy_graph
164 my $c = $g->undirected_copy_graph;
165 Create an undirected shallow copy (vertices and edges) of the
167 directed graph so that for any directed edge (u, v) there is an
168 undirected edge (u, v).
169 undirected_copy_clear_cache
171 @path = $g->undirected_copy_clear_cache;
172 See "Clearing cached results".
174 directed_copy
176 directed_copy_graph
177 my $c = $g->directed_copy_graph;
178 Create a directed shallow copy (vertices and edges) of the
180 undirected graph so that for any undirected edge (u, v) there are
181 two directed edges (u, v) and (v, u).
182 transpose
184 transpose_graph
185 my $t = $g->transpose_graph;
186 Create a directed shallow transposed copy (vertices and edges) of
188 the directed graph so that for any directed edge (u, v) there is a
189 directed edge (v, u).
190 You can also transpose a single edge with
192 transpose_edge
194 $g->transpose_edge($u, $v)
195 complete_graph
197 complete
198 my $c = $g->complete_graph;
199 Create a complete graph that has the same vertices as the original
201 graph. A complete graph has an edge between every pair of
202 vertices.
203 complement_graph
205 complement
206 my $c = $g->complement_graph;
207 Create a complement graph that has the same vertices as the
209 original graph. A complement graph has an edge (u,v) if and only
210 if the original graph does not have edge (u,v).
211 subgraph
213 my $c = $g->subgraph(\@src, \@dst);
214 my $c = $g->subgraph(\@src);
215 Creates a subgraph of a given graph. The created subgraph has the
217 same graph properties (directedness, and so forth) as the original
218 graph, but none of the attributes (graph, vertex, or edge).
219 A vertex is added to the subgraph if it is in the original graph.
221 An edge is added to the subgraph if there is an edge in the
223 original graph that starts from the "src" set of vertices and ends
224 in the "dst" set of vertices.
225 You can leave out "dst" in which case "dst" is assumed to be the
227 same: this is called a vertex-induced subgraph.
228 See also "random_graph" for a random constructor.
230 Basics
232 add_vertex
233 $g->add_vertex($v)
234 Add the vertex to the graph. Returns the graph.
236 By default idempotent, but a graph can be created countvertexed.
238 A vertex is also known as a node.
240 Adding "undef" as vertex is not allowed.
242 Note that unless you have isolated vertices (or countvertexed
244 vertices), you do not need to explicitly use "add_vertex" since
245 "add_edge" will implicitly add its vertices.
246 add_edge
248 $g->add_edge($u, $v)
249 Add the edge to the graph. Implicitly first adds the vertices if
251 the graph does not have them. Returns the graph.
252 By default idempotent, but a graph can be created countedged.
254 An edge is also known as an arc.
256 For a hypergraph, the interface is different: if undirected, give a
258 list of one or more vertices. If directed, give a list of two
259 array-refs of vertices. As conceptually these are sets, the
260 ordering of the contents is not important.
261 has_vertex
263 $g->has_vertex($v)
264 Return true if the vertex exists in the graph, false otherwise.
266 has_edge
268 $g->has_edge($u, $v)
269 Return true if the edge exactly as specified exists in the graph,
271 false otherwise.
272 Hyperedges which contain all the given vertices (in the right
274 places if directed), but which also have others will not match.
275 any_edge
277 $g->any_edge($u, $v)
278 Return true if any edge in the graph connects the first vertex to
280 the second, false otherwise. Note this is a different question from
281 "has_edge". It will give the same result as checking the first
282 vertex's "successors" to see if any match the second one, but in a
283 more efficient way.
284 delete_vertex
286 $g->delete_vertex($v)
287 Delete the vertex from the graph. Returns the graph, even if the
289 vertex did not exist in the graph.
290 If the graph has been created multivertexed or countvertexed and a
292 vertex has been added multiple times, the vertex will require at
293 least an equal number of deletions to become completely deleted.
294 delete_vertices
296 $g->delete_vertices($v1, $v2, ...)
297 Delete the vertices from the graph. Returns the graph, even if
299 none of the vertices existed in the graph.
300 If the graph has been created multivertexed or countvertexed and a
302 vertex has been added multiple times, the vertex will require at
303 least an equal number of deletions to become completely deleted.
304 delete_edge
306 $g->delete_edge($u, $v)
307 Delete the edge from the graph. Returns the graph, even if the
309 edge did not exist in the graph.
310 If the graph has been created multiedged or countedged and an edge
312 has been added multiple times, the edge will require at least an
313 equal number of deletions to become completely deleted.
314 delete_edges
316 $g->delete_edges($u1, $v1, $u2, $v2, ...)
317 Delete the edges from the graph. Returns the graph, even if none
319 of the edges existed in the graph.
320 If the graph has been created multiedged or countedged and an edge
322 has been added multiple times, the edge will require at least an
323 equal number of deletions to become completely deleted.
324 Displaying
326 Graphs have stringification overload, so you can do things like
327 print "The graph is $g\n"
329 One-way (directed, unidirected) edges are shown as '-', two-way
331 (undirected, bidirected) edges are shown as '='. If you want to, you
332 can call the stringification via the method
333 stringify
335 Boolean
337 Graphs have boolifying overload, so you can do things like
338 if ($g) { print "The graph is: $g\n" }
340 which works even if the graph is empty. In fact, the boolify always
342 returns true. If you want to test for example for vertices, test for
343 vertices.
344 boolify
346 Comparing
348 Testing for equality can be done either by the overloaded "eq" operator
349 $g eq "a-b,a-c,d"
351 or by the method
353 eq
355 $g->eq("a-b,a-c,d")
356 The equality testing compares the stringified forms, and therefore it
358 assumes total equality, not isomorphism: all the vertices must be named
359 the same, and they must have identical edges between them.
360 For unequality there are correspondingly the overloaded "ne" operator
362 and the method
363 ne
365 $g->ne("a-b,a-c,d")
366 See also "Isomorphism".
368 Paths and Cycles
370 Paths and cycles are simple extensions of edges: paths are edges
371 starting from where the previous edge ended, and cycles are paths
372 returning back to the start vertex of the first edge.
373 add_path
375 $g->add_path($a, $b, $c, ..., $x, $y, $z)
376 Add the edges $a-$b, $b-$c, ..., $x-$y, $y-$z to the graph.
378 Returns the graph.
379 has_path
381 $g->has_path($a, $b, $c, ..., $x, $y, $z)
382 Return true if the graph has all the edges $a-$b, $b-$c, ...,
384 $x-$y, $y-$z, false otherwise.
385 delete_path
387 $g->delete_path($a, $b, $c, ..., $x, $y, $z)
388 Delete all the edges $a-$b, $b-$c, ..., $x-$y, $y-$z (regardless of
390 whether they exist or not). Returns the graph.
391 add_cycle
393 $g->add_cycle($a, $b, $c, ..., $x, $y, $z)
394 Add the edges $a-$b, $b-$c, ..., $x-$y, $y-$z, and $z-$a to the
396 graph. Returns the graph.
397 has_cycle
399 has_this_cycle
400 $g->has_cycle($a, $b, $c, ..., $x, $y, $z)
401 Return true if the graph has all the edges $a-$b, $b-$c, ...,
403 $x-$y, $y-$z, and $z-$a, false otherwise.
404 NOTE: This does not detect cycles, see "has_a_cycle" and
406 "find_a_cycle".
407 delete_cycle
409 $g->delete_cycle($a, $b, $c, ..., $x, $y, $z)
410 Delete all the edges $a-$b, $b-$c, ..., $x-$y, $y-$z, and $z-$a
412 (regardless of whether they exist or not). Returns the graph.
413 has_a_cycle
415 $g->has_a_cycle
416 Returns true if the graph has a cycle, false if not.
418 find_a_cycle
420 $g->find_a_cycle
421 Returns a cycle if the graph has one (as a list of vertices), an
423 empty list if no cycle can be found.
424 Note that this just returns the vertices of a cycle: not any
426 particular cycle, just the first one it finds. A repeated call
427 might find the same cycle, or it might find a different one, and
428 you cannot call this repeatedly to find all the cycles.
429 Graph Types
431 is_simple_graph
432 $g->is_simple_graph
433 Return true if the graph has no multiedges, false otherwise.
435 is_pseudo_graph
437 $g->is_pseudo_graph
438 Return true if the graph has any multiedges or any self-loops,
440 false otherwise.
441 is_multi_graph
443 $g->is_multi_graph
444 Return true if the graph has any multiedges but no self-loops,
446 false otherwise.
447 is_directed_acyclic_graph
449 is_dag
450 $g->is_directed_acyclic_graph
451 $g->is_dag
452 Return true if the graph is directed and acyclic, false otherwise.
454 is_cyclic
456 $g->is_cyclic
457 Return true if the graph is cyclic (contains at least one cycle).
459 (This is identical to "has_a_cycle".)
460 To find at least one such cycle, see "find_a_cycle".
462 is_acyclic
464 Return true if the graph is acyclic (does not contain any cycles).
465 To find a cycle, use "find_a_cycle".
467 Transitivity
469 is_transitive
470 $g->is_transitive
471 Return true if the graph is transitive, false otherwise.
473 TransitiveClosure_Floyd_Warshall
475 transitive_closure
476 $tcg = $g->TransitiveClosure_Floyd_Warshall
477 Return the transitive closure graph of the graph.
479 transitive_closure_matrix_clear_cache
481 $g->transitive_closure_matrix_clear_cache
482 See "Clearing cached results".
484 You can query the reachability from $u to $v with
486 is_reachable
488 $tcg->is_reachable($u, $v)
489 See Graph::TransitiveClosure for more information about creating and
491 querying transitive closures.
492 With
494 transitive_closure_matrix
496 $tcm = $g->transitive_closure_matrix;
497 you can (create if not existing and) query the transitive closure
499 matrix that underlies the transitive closure graph. See
500 Graph::TransitiveClosure::Matrix for more information.
501 Mutators
503 add_vertices
504 $g->add_vertices('d', 'e', 'f')
505 Add zero or more vertices to the graph. Returns the graph.
507 add_edges
509 $g->add_edges(['d', 'e'], ['f', 'g'])
510 $g->add_edges(qw(d e f g));
511 Add zero or more edges to the graph. The edges are specified as a
513 list of array references, or as a list of vertices where the even
514 (0th, 2nd, 4th, ...) items are start vertices and the odd (1st,
515 3rd, 5th, ...) are the corresponding end vertices. Returns the
516 graph.
517 For a hypergraph, each item in this list must be an array-ref of
519 arguments suitable for "add_edge" - so for undirected, of vertices;
520 for directed, of two array-refs of vertices.
521 rename_vertex
523 $g->rename_vertex('d', 'e')
524 Renames a vertex. It retains all of its edges. Throws exception if
526 doesn't exist.
527 Returns the graph.
529 rename_vertices
531 $g->rename_vertices(sub { uc $_[0] })
532 Calls a function for each vertex-name, renaming it to the return
534 value.
535 Returns the graph.
537 ingest
539 $g->ingest($g2)
540 Ingests all the vertices and edges of the given graph, including
542 attributes. Returns the ingesting graph.
543 Accessors
545 is_directed
546 directed
547 $g->is_directed()
548 $g->directed()
549 Return true if the graph is directed, false otherwise.
551 is_undirected
553 undirected
554 $g->is_undirected()
555 $g->undirected()
556 Return true if the graph is undirected, false otherwise.
558 is_refvertexed
560 is_refvertexed_stringified
561 refvertexed
562 refvertexed_stringified
563 Return true if the graph can handle references (including Perl
564 objects) as vertices.
565 vertices
567 my $V = $g->vertices
568 my @V = $g->vertices
569 In scalar context, return the number of vertices in the graph. In
571 list context, return the vertices, in no particular order.
572 has_vertices
574 $g->has_vertices()
575 Return true if the graph has any vertices, false otherwise.
577 edges
579 my $E = $g->edges
580 my @E = $g->edges
581 In scalar context, return the number of edges in the graph. In
583 list context, return the edges, in no particular order. The edges
584 are returned as anonymous arrays listing the vertices.
585 has_edges
587 $g->has_edges()
588 Return true if the graph has any edges, false otherwise.
590 is_connected
592 $g->is_connected
593 For an undirected graph, return true if the graph is connected,
595 false otherwise. Being connected means that from every vertex it
596 is possible to reach every other vertex.
597 If the graph has been created with a true "unionfind" parameter,
599 the time complexity is (essentially) O(V), otherwise O(V log V).
600 See also "connected_components", "connected_component_by_index",
602 "connected_component_by_vertex", and "same_connected_components",
603 and "biconnectivity".
604 For directed graphs, see "is_strongly_connected" and
606 "is_weakly_connected".
607 connected_components
609 @cc = $g->connected_components()
610 For an undirected graph, returns the vertices of the connected
612 components of the graph as a list of anonymous arrays. The
613 ordering of the anonymous arrays or the ordering of the vertices
614 inside the anonymous arrays (the components) is undefined.
615 For directed graphs, see "strongly_connected_components" and
617 "weakly_connected_components".
618 connected_component_by_vertex
620 $i = $g->connected_component_by_vertex($v)
621 For an undirected graph, return an index identifying the connected
623 component the vertex belongs to, the indexing starting from zero.
624 For the inverse, see "connected_component_by_index".
626 If the graph has been created with a true "unionfind" parameter,
628 the time complexity is (essentially) O(1), otherwise O(V log V).
629 See also "biconnectivity".
631 For directed graphs, see "strongly_connected_component_by_vertex"
633 and "weakly_connected_component_by_vertex".
634 connected_component_by_index
636 @v = $g->connected_component_by_index($i)
637 For an undirected graph, return the vertices of the ith connected
639 component, the indexing starting from zero. The order of vertices
640 is undefined, while the order of the connected components is same
641 as from connected_components().
642 For the inverse, see "connected_component_by_vertex".
644 For directed graphs, see "strongly_connected_component_by_index"
646 and "weakly_connected_component_by_index".
647 same_connected_components
649 $g->same_connected_components($u, $v, ...)
650 For an undirected graph, return true if the vertices are in the
652 same connected component.
653 If the graph has been created with a true "unionfind" parameter,
655 the time complexity is (essentially) O(1), otherwise O(V log V).
656 For directed graphs, see "same_strongly_connected_components" and
658 "same_weakly_connected_components".
659 connected_graph
661 $cg = $g->connected_graph
662 For an undirected graph, return its connected graph.
664 connectivity_clear_cache
666 $g->connectivity_clear_cache
667 See "Clearing cached results".
669 See "Connected Graphs and Their Components" for further discussion.
671 biconnectivity
673 my ($ap, $bc, $br) = $g->biconnectivity
674 For an undirected graph, return the various biconnectivity
676 components of the graph: the articulation points (cut vertices),
677 biconnected components, and bridges.
678 Note: currently only handles connected graphs.
680 is_biconnected
682 $g->is_biconnected
683 For an undirected graph, return true if the graph is biconnected
685 (if it has no articulation points, also known as cut vertices).
686 is_edge_connected
688 $g->is_edge_connected
689 For an undirected graph, return true if the graph is edge-connected
691 (if it has no bridges).
692 Note: more precisely, this would be called is_edge_biconnected,
694 since there is a more general concept of being k-connected.
695 is_edge_separable
697 $g->is_edge_separable
698 For an undirected graph, return true if the graph is edge-separable
700 (if it has bridges).
701 Note: more precisely, this would be called is_edge_biseparable,
703 since there is a more general concept of being k-connected.
704 articulation_points
706 cut_vertices
707 $g->articulation_points
708 For an undirected graph, return the articulation points (cut
710 vertices) of the graph as a list of vertices. The order is
711 undefined.
712 biconnected_components
714 $g->biconnected_components
715 For an undirected graph, return the biconnected components of the
717 graph as a list of anonymous arrays of vertices in the components.
718 The ordering of the anonymous arrays or the ordering of the
719 vertices inside the anonymous arrays (the components) is undefined.
720 Also note that one vertex can belong to more than one biconnected
721 component.
722 biconnected_component_by_vertex
724 $i = $g->biconnected_component_by_index($v)
725 For an undirected graph, return the indices identifying the
727 biconnected components the vertex belongs to, the indexing starting
728 from zero. The order of of the components is undefined.
729 For the inverse, see "connected_component_by_index".
731 For directed graphs, see "strongly_connected_component_by_index"
733 and "weakly_connected_component_by_index".
734 biconnected_component_by_index
736 @v = $g->biconnected_component_by_index($i)
737 For an undirected graph, return the vertices in the ith biconnected
739 component of the graph as an anonymous arrays of vertices in the
740 component. The ordering of the vertices within a component is
741 undefined. Also note that one vertex can belong to more than one
742 biconnected component.
743 same_biconnected_components
745 $g->same_biconnected_components($u, $v, ...)
746 For an undirected graph, return true if the vertices are in the
748 same biconnected component.
749 biconnected_graph
751 $bcg = $g->biconnected_graph
752 For an undirected graph, return its biconnected graph.
754 See "Connected Graphs and Their Components" for further discussion.
756 bridges
758 $g->bridges
759 For an undirected graph, return the bridges of the graph as a list
761 of anonymous arrays of vertices in the bridges. The order of
762 bridges and the order of vertices in them is undefined.
763 biconnectivity_clear_cache
765 $g->biconnectivity_clear_cache
766 See "Clearing cached results".
768 strongly_connected
770 is_strongly_connected
771 $g->is_strongly_connected
772 For a directed graph, return true if the directed graph is strongly
774 connected, false if not.
775 See also "is_weakly_connected".
777 For undirected graphs, see "is_connected", or "is_biconnected".
779 strongly_connected_component_by_vertex
781 $i = $g->strongly_connected_component_by_vertex($v)
782 For a directed graph, return an index identifying the strongly
784 connected component the vertex belongs to, the indexing starting
785 from zero.
786 For the inverse, see "strongly_connected_component_by_index".
788 See also "weakly_connected_component_by_vertex".
790 For undirected graphs, see "connected_components" or
792 "biconnected_components".
793 strongly_connected_component_by_index
795 @v = $g->strongly_connected_component_by_index($i)
796 For a directed graph, return the vertices of the ith connected
798 component, the indexing starting from zero. The order of vertices
799 within a component is undefined, while the order of the connected
800 components is as from strongly_connected_components().
801 For the inverse, see "strongly_connected_component_by_vertex".
803 For undirected graphs, see "weakly_connected_component_by_index".
805 same_strongly_connected_components
807 $g->same_strongly_connected_components($u, $v, ...)
808 For a directed graph, return true if the vertices are in the same
810 strongly connected component.
811 See also "same_weakly_connected_components".
813 For undirected graphs, see "same_connected_components" or
815 "same_biconnected_components".
816 strong_connectivity_clear_cache
818 $g->strong_connectivity_clear_cache
819 See "Clearing cached results".
821 weakly_connected
823 is_weakly_connected
824 $g->is_weakly_connected
825 For a directed graph, return true if the directed graph is weakly
827 connected, false if not.
828 Weakly connected graph is also known as semiconnected graph.
830 See also "is_strongly_connected".
832 For undirected graphs, see "is_connected" or "is_biconnected".
834 weakly_connected_components
836 @wcc = $g->weakly_connected_components()
837 For a directed graph, returns the vertices of the weakly connected
839 components of the graph as a list of anonymous arrays. The
840 ordering of the anonymous arrays or the ordering of the vertices
841 inside the anonymous arrays (the components) is undefined.
842 See also "strongly_connected_components".
844 For undirected graphs, see "connected_components" or
846 "biconnected_components".
847 weakly_connected_component_by_vertex
849 $i = $g->weakly_connected_component_by_vertex($v)
850 For a directed graph, return an index identifying the weakly
852 connected component the vertex belongs to, the indexing starting
853 from zero.
854 For the inverse, see "weakly_connected_component_by_index".
856 For undirected graphs, see "connected_component_by_vertex" and
858 "biconnected_component_by_vertex".
859 weakly_connected_component_by_index
861 @v = $g->weakly_connected_component_by_index($i)
862 For a directed graph, return the vertices of the ith weakly
864 connected component, the indexing starting zero. The order of
865 vertices within a component is undefined, while the order of the
866 weakly connected components is same as from
867 weakly_connected_components().
868 For the inverse, see "weakly_connected_component_by_vertex".
870 For undirected graphs, see connected_component_by_index and
872 biconnected_component_by_index.
873 same_weakly_connected_components
875 $g->same_weakly_connected_components($u, $v, ...)
876 Return true if the vertices are in the same weakly connected
878 component.
879 weakly_connected_graph
881 $wcg = $g->weakly_connected_graph
882 For a directed graph, return its weakly connected graph.
884 For undirected graphs, see "connected_graph" and
886 "biconnected_graph".
887 strongly_connected_components
889 my @scc = $g->strongly_connected_components;
890 For a directed graph, return the strongly connected components as a
892 list of anonymous arrays. The elements in the anonymous arrays are
893 the vertices belonging to the strongly connected component; both
894 the elements and the components are in no particular order.
895 Note that strongly connected components can have single-element
897 components even without self-loops: if a vertex is any of isolated,
898 sink, or a source, the vertex is alone in its own strong component.
899 See also "weakly_connected_components".
901 For undirected graphs, see "connected_components", or see
903 "biconnected_components".
904 strongly_connected_graph
906 my $scg = $g->strongly_connected_graph;
907 See "Connected Graphs and Their Components" for further discussion.
909 Strongly connected graphs are also known as kernel graphs.
911 See also "weakly_connected_graph".
913 For undirected graphs, see "connected_graph", or
915 "biconnected_graph".
916 is_sink_vertex
918 $g->is_sink_vertex($v)
919 Return true if the vertex $v is a sink vertex, false if not. A
921 sink vertex is defined as a vertex with predecessors but no
922 successors: this definition means that isolated vertices are not
923 sink vertices. If you want also isolated vertices, use
924 is_successorless_vertex().
925 is_source_vertex
927 $g->is_source_vertex($v)
928 Return true if the vertex $v is a source vertex, false if not. A
930 source vertex is defined as a vertex with successors but no
931 predecessors: the definition means that isolated vertices are not
932 source vertices. If you want also isolated vertices, use
933 is_predecessorless_vertex().
934 is_successorless_vertex
936 $g->is_successorless_vertex($v)
937 Return true if the vertex $v has no successors (no edges leaving
939 the vertex), false if it has.
940 Isolated vertices will return true: if you do not want this, use
942 is_sink_vertex().
943 is_successorful_vertex
945 $g->is_successorful_vertex($v)
946 Return true if the vertex $v has successors, false if not.
948 is_predecessorless_vertex
950 $g->is_predecessorless_vertex($v)
951 Return true if the vertex $v has no predecessors (no edges entering
953 the vertex), false if it has.
954 Isolated vertices will return true: if you do not want this, use
956 is_source_vertex().
957 is_predecessorful_vertex
959 $g->is_predecessorful_vertex($v)
960 Return true if the vertex $v has predecessors, false if not.
962 is_isolated_vertex
964 $g->is_isolated_vertex($v)
965 Return true if the vertex $v is an isolated vertex: no successors
967 and no predecessors.
968 is_interior_vertex
970 $g->is_interior_vertex($v)
971 Return true if the vertex $v is an interior vertex: both successors
973 and predecessors.
974 is_exterior_vertex
976 $g->is_exterior_vertex($v)
977 Return true if the vertex $v is an exterior vertex: has either no
979 successors or no predecessors, or neither.
980 is_self_loop_vertex
982 $g->is_self_loop_vertex($v)
983 Return true if the vertex $v is a self loop vertex: has an edge
985 from itself to itself.
986 For an undirected hypergraph, only true if an edge has the vertex
988 as its sole participant.
989 sink_vertices
991 @v = $g->sink_vertices()
992 Return the sink vertices of the graph. In scalar context return
994 the number of sink vertices. See "is_sink_vertex" for the
995 definition of a sink vertex.
996 source_vertices
998 @v = $g->source_vertices()
999 Return the source vertices of the graph. In scalar context return
1001 the number of source vertices. See "is_source_vertex" for the
1002 definition of a source vertex.
1003 successorful_vertices
1005 @v = $g->successorful_vertices()
1006 Return the successorful vertices of the graph. In scalar context
1008 return the number of successorful vertices.
1009 successorless_vertices
1011 @v = $g->successorless_vertices()
1012 Return the successorless vertices of the graph. In scalar context
1014 return the number of successorless vertices.
1015 successors
1017 @s = $g->successors($v)
1018 Return the immediate successor vertices of the vertex.
1020 See also "all_successors", "all_neighbours", and "all_reachable".
1022 all_successors
1024 @s = $g->all_successors(@v)
1025 For a directed graph, returns all successor vertices of the
1027 argument vertices, recursively.
1028 For undirected graphs, see "all_neighbours" and "all_reachable".
1030 See also "successors", "successors_by_radius".
1032 successors_by_radius
1034 @s = $g->successors_by_radius(@v, $radius)
1035 For a directed graph, returns all successor vertices of the
1037 argument vertices, recursively.
1038 For undirected graphs, see "all_neighbours" and "all_reachable".
1040 See also "successors", "successors_by_radius".
1042 neighbors
1044 neighbours
1045 @n = $g->neighbours($v)
1046 Return the neighboring/neighbouring vertices. Also known as the
1048 adjacent vertices.
1049 See also "all_neighbours" "all_reachable", and
1051 "neighbours_by_radius".
1052 all_neighbors
1054 all_neighbours
1055 @n = $g->all_neighbours(@v)
1056 Return the neighboring/neighbouring vertices of the argument
1058 vertices, recursively. For a directed graph, recurses up
1059 predecessors and down successors. For an undirected graph, returns
1060 all the vertices reachable from the argument vertices: equivalent
1061 to "all_reachable".
1062 See also "neighbours", "all_reachable", and "neighbours_by_radius".
1064 neighbors_by_radius
1066 neighbours_by_radius
1067 @n = $g->neighbours_by_radius(@v, $radius)
1068 Return the neighboring/neighbouring vertices of the argument
1070 vertices, recursively, out to the given radius.
1071 all_reachable
1073 @r = $g->all_reachable(@v)
1074 Return all the vertices reachable from the argument vertices,
1076 recursively. For a directed graph, equivalent to "all_successors".
1077 For an undirected graph, equivalent to "all_neighbours". The
1078 argument vertices are not included in the results unless there are
1079 explicit self-loops.
1080 See also "neighbours", "all_neighbours", "all_successors", and
1082 "reachable_by_radius".
1083 reachable_by_radius
1085 @r = $g->reachable_by_radius(@v, $radius)
1086 Return all the vertices reachable from the argument vertices,
1088 recursively, out to the given radius.
1089 predecessorful_vertices
1091 @v = $g->predecessorful_vertices()
1092 Return the predecessorful vertices of the graph. In scalar context
1094 return the number of predecessorful vertices.
1095 predecessorless_vertices
1097 @v = $g->predecessorless_vertices()
1098 Return the predecessorless vertices of the graph. In scalar
1100 context return the number of predecessorless vertices.
1101 predecessors
1103 @p = $g->predecessors($v)
1104 Return the immediate predecessor vertices of the vertex.
1106 See also "all_predecessors", "all_neighbours", and "all_reachable".
1108 all_predecessors
1110 @p = $g->all_predecessors(@v)
1111 For a directed graph, returns all predecessor vertices of the
1113 argument vertices, recursively.
1114 For undirected graphs, see "all_neighbours" and "all_reachable".
1116 See also "predecessors", "predecessors_by_radius".
1118 predecessors_by_radius
1120 @p = $g->predecessors_by_radius(@v, $radius)
1121 For a directed graph, returns all predecessor vertices of the
1123 argument vertices, recursively, out to the given radius.
1124 isolated_vertices
1126 @v = $g->isolated_vertices()
1127 Return the isolated vertices of the graph. In scalar context
1129 return the number of isolated vertices. See "is_isolated_vertex"
1130 for the definition of an isolated vertex.
1131 interior_vertices
1133 @v = $g->interior_vertices()
1134 Return the interior vertices of the graph. In scalar context
1136 return the number of interior vertices. See "is_interior_vertex"
1137 for the definition of an interior vertex.
1138 exterior_vertices
1140 @v = $g->exterior_vertices()
1141 Return the exterior vertices of the graph. In scalar context
1143 return the number of exterior vertices. See "is_exterior_vertex"
1144 for the definition of an exterior vertex.
1145 self_loop_vertices
1147 @v = $g->self_loop_vertices()
1148 Return the self-loop vertices of the graph. In scalar context
1150 return the number of self-loop vertices. See "is_self_loop_vertex"
1151 for the definition of a self-loop vertex.
1152 as_hashes
1154 ($nodes, $edges) = $g->as_hashes
1155 Return hash-refs which map vertices to their attributes, and for
1157 edges, a two-level hash mapping the predecessor to its successors,
1158 mapped to the attributes.
1159 If "multivertexed" is true, the vertices hash will have the second-
1161 level values be the multivertex's ID, and the third level will be
1162 attributes as above.
1163 If "multiedged" is true, similar will be true for the edges hash.
1165 For a hypergraph, the edges will instead be an array-ref of hashes
1167 with a key of "attributes", value a hash-ref (if "multiedged", two-
1168 level as above). Then with values of array-refs of vertex-names,
1169 for undirected:
1170 vertices
1172 And directed:
1174 predecessors
1176 successors
1177 Connected Graphs and Their Components
1179 In this discussion connected graph refers to any of connected graphs,
1180 biconnected graphs, and strongly connected graphs.
1181 NOTE: if the vertices of the original graph are Perl objects, (in other
1183 words, references, so you must be using "refvertexed") the vertices of
1184 the connected graph are NOT by default usable as Perl objects because
1185 they are blessed into a package with a rather unusable name.
1186 By default, the vertex names of the connected graph are formed from the
1188 names of the vertices of the original graph by (alphabetically sorting
1189 them and) concatenating their names with "+". The vertex attribute
1190 "subvertices" is also used to store the list (as an array reference) of
1191 the original vertices. To change the 'supercomponent' vertex names and
1192 the whole logic of forming these supercomponents use the
1193 "super_component") option to the method calls:
1194 $g->connected_graph(super_component => sub { ... })
1196 $g->biconnected_graph(super_component => sub { ... })
1197 $g->strongly_connected_graph(super_component => sub { ... })
1198 The subroutine reference gets the 'subcomponents' (the vertices of the
1200 original graph) as arguments, and it is supposed to return the new
1201 supercomponent vertex, the "stringified" form of which is used as the
1202 vertex name.
1203 Degree
1205 A vertex has a degree based on the number of incoming and outgoing
1206 edges. This really makes sense only for directed graphs.
1207 degree
1209 vertex_degree
1210 $d = $g->degree($v)
1211 $d = $g->vertex_degree($v)
1212 For directed graphs: the in-degree minus the out-degree at the
1214 vertex.
1215 For undirected graphs: the number of edges at the vertex
1217 (identical to in_degree(), out_degree()).
1218 in_degree
1220 $d = $g->in_degree($v)
1221 For directed graphs: the number of incoming edges at the vertex.
1223 For undirected graphs: the number of edges at the vertex (identical
1225 to out_degree(), degree(), vertex_degree()).
1226 out_degree
1228 $o = $g->out_degree($v)
1229 For directed graphs: The number of outgoing edges at the vertex.
1231 For undirected graphs: the number of edges at the vertex (identical
1233 to in_degree(), degree(), vertex_degree()).
1234 Related methods are
1236 edges_at
1238 @e = $g->edges_at($v)
1239 The union of edges from, and edges to, the vertex.
1241 edges_from
1243 @e = $g->edges_from($v)
1244 The edges leaving the vertex.
1246 edges_to
1248 @e = $g->edges_to($v)
1249 The edges entering the vertex.
1251 Counted Vertices
1253 Counted vertices are vertices with more than one instance, normally
1254 adding vertices is idempotent. To enable counted vertices on a graph,
1255 give the "countvertexed" parameter a true value
1256 use Graph;
1258 my $g = Graph->new(countvertexed => 1);
1259 To find out how many times the vertex has been added:
1261 get_vertex_count
1263 my $c = $g->get_vertex_count($v);
1264 Return the count of the vertex, or undef if the vertex does not
1266 exist.
1267 Multiedges, Multivertices, Multigraphs
1269 Multiedges are edges with more than one "life", meaning that one has to
1270 delete them as many times as they have been added. Normally adding
1271 edges is idempotent (in other words, adding edges more than once makes
1272 no difference).
1273 There are two kinds or degrees of creating multiedges and
1275 multivertices. The two kinds are mutually exclusive.
1276 The weaker kind is called counted, in which the edge or vertex has a
1278 count on it: add operations increase the count, and delete operations
1279 decrease the count, and once the count goes to zero, the edge or vertex
1280 is deleted. If there are attributes, they all are attached to the same
1281 vertex. You can think of this as the graph elements being refcounted,
1282 or reference counted, if that sounds more familiar.
1283 The stronger kind is called (true) multi, in which the edge or vertex
1285 really has multiple separate identities, so that you can for example
1286 attach different attributes to different instances.
1287 To enable multiedges on a graph:
1289 use Graph;
1291 my $g0 = Graph->new(countedged => 1);
1292 my $g0 = Graph->new(multiedged => 1);
1293 Similarly for vertices
1295 use Graph;
1297 my $g1 = Graph->new(countvertexed => 1);
1298 my $g1 = Graph->new(multivertexed => 1);
1299 You can test for these by
1301 is_countedged
1303 countedged
1304 $g->is_countedged
1305 $g->countedged
1306 Return true if the graph is countedged.
1308 is_countvertexed
1310 countvertexed
1311 $g->is_countvertexed
1312 $g->countvertexed
1313 Return true if the graph is countvertexed.
1315 is_multiedged
1317 multiedged
1318 $g->is_multiedged
1319 $g->multiedged
1320 Return true if the graph is multiedged.
1322 is_multivertexed
1324 multivertexed
1325 $g->is_multivertexed
1326 $g->multivertexed
1327 Return true if the graph is multivertexed.
1329 A multiedged (either the weak kind or the strong kind) graph is a
1331 multigraph, for which you can test with is_multi_graph().
1332 NOTE: The various graph algorithms do not in general work well with
1334 multigraphs (they often assume simple graphs, that is, no multiedges or
1335 loops), and no effort has been made to test the algorithms with
1336 multigraphs.
1337 vertices() and edges() will return the multiple elements: if you want
1339 just the unique elements, use
1340 unique_vertices
1342 unique_edges
1343 @uv = $g->unique_vertices; # unique
1344 @mv = $g->vertices; # possible multiples
1345 @ue = $g->unique_edges;
1346 @me = $g->edges;
1347 If you are using (the stronger kind of) multielements, you should use
1349 the by_id variants:
1350 add_vertex_by_id
1352 has_vertex_by_id
1353 delete_vertex_by_id
1354 add_edge_by_id
1355 has_edge_by_id
1356 delete_edge_by_id
1357 $g->add_vertex_by_id($v, $id)
1359 $g->has_vertex_by_id($v, $id)
1360 $g->delete_vertex_by_id($v, $id)
1361 $g->add_edge_by_id($u, $v, $id)
1363 $g->has_edge_by_id($u, $v, $id)
1364 $g->delete_edge_by_id($u, $v, $id)
1365 These interfaces only apply to multivertices and multiedges. When you
1367 delete the last vertex/edge in a multivertex/edge, the whole
1368 vertex/edge is deleted. You can use add_vertex()/add_edge() on a
1369 multivertex/multiedge graph, in which case an id is generated
1370 automatically. To find out which the generated id was, you need to use
1371 add_vertex_get_id
1373 add_edge_get_id
1374 $idv = $g->add_vertex_get_id($v)
1376 $ide = $g->add_edge_get_id($u, $v)
1377 To return all the ids of vertices/edges in a multivertex/multiedge, use
1379 get_multivertex_ids
1381 get_multiedge_ids
1382 $g->get_multivertex_ids($v)
1384 $g->get_multiedge_ids($u, $v)
1385 The ids are returned in random order.
1387 To find out how many times the edge has been added (this works for
1389 either kind of multiedges):
1390 get_edge_count
1392 my $c = $g->get_edge_count($u, $v);
1393 Return the count (the "countedness") of the edge, or undef if the
1395 edge does not exist.
1396 The following multi-entity utility functions exist, mirroring the non-
1398 multi vertices and edges:
1399 add_weighted_edge_by_id
1401 add_weighted_edges_by_id
1402 add_weighted_path_by_id
1403 add_weighted_vertex_by_id
1404 add_weighted_vertices_by_id
1405 delete_edge_weight_by_id
1406 delete_vertex_weight_by_id
1407 get_edge_weight_by_id
1408 get_vertex_weight_by_id
1409 has_edge_weight_by_id
1410 has_vertex_weight_by_id
1411 set_edge_weight_by_id
1412 set_vertex_weight_by_id
1413 Topological Sort
1415 topological_sort
1416 toposort
1417 my @ts = $g->topological_sort;
1418 Return the vertices of the graph sorted topologically. Note that
1420 there may be several possible topological orderings; one of them is
1421 returned.
1422 If the graph contains a cycle, a fatal error is thrown, you can
1424 either use "eval" to trap that, or supply the "empty_if_cyclic"
1425 argument with a true value
1426 my @ts = $g->topological_sort(empty_if_cyclic => 1);
1428 in which case an empty array is returned if the graph is cyclic.
1430 Minimum Spanning Trees (MST)
1432 Minimum Spanning Trees or MSTs are tree subgraphs derived from an
1433 undirected graph. MSTs "span the graph" (covering all the vertices)
1434 using as lightly weighted (hence the "minimum") edges as possible.
1435 MST_Kruskal
1437 $mstg = $g->MST_Kruskal;
1438 Returns the Kruskal MST of the graph.
1440 MST_Prim
1442 $mstg = $g->MST_Prim(%opt);
1443 Returns the Prim MST of the graph.
1445 You can choose the first vertex with $opt{ first_root }.
1447 MST_Dijkstra
1449 minimum_spanning_tree
1450 $mstg = $g->MST_Dijkstra;
1451 $mstg = $g->minimum_spanning_tree;
1452 Aliases for MST_Prim.
1454 Single-Source Shortest Paths (SSSP)
1456 Single-source shortest paths, also known as Shortest Path Trees (SPTs).
1457 For either a directed or an undirected graph, return a (tree) subgraph
1458 that from a single start vertex (the "single source") travels the
1459 shortest possible paths (the paths with the lightest weights) to all
1460 the other vertices. Note that the SSSP is neither reflexive (the
1461 shortest paths do not include the zero-length path from the source
1462 vertex to the source vertex) nor transitive (the shortest paths do not
1463 include transitive closure paths). If no weight is defined for an
1464 edge, 1 (one) is assumed.
1465 SPT_Dijkstra
1467 $sptg = $g->SPT_Dijkstra($root)
1468 $sptg = $g->SPT_Dijkstra(%opt)
1469 Return as a graph the the single-source shortest paths of the graph
1471 using Dijkstra's algorithm. The graph cannot contain negative
1472 edges (negative edges cause the algorithm to abort with an error
1473 message "Graph::SPT_Dijkstra: edge ... is negative").
1474 You can choose the first vertex of the result with either a single
1476 vertex argument or with $opt{ first_root }, otherwise a random
1477 vertex is chosen.
1478 NOTE: note that all the vertices might not be reachable from the
1480 selected (explicit or random) start vertex.
1481 NOTE: after the first reachable tree from the first start vertex
1483 has been finished, and if there still are unvisited vertices,
1484 SPT_Dijkstra will keep on selecting unvisited vertices.
1485 The next roots (in case the first tree doesn't visit all the
1487 vertices) can be chosen by setting one of the following options to
1488 true: "next_root", "next_alphabetic", "next_numeric",
1489 "next_random".
1490 The "next_root" is the most customizable: the value needs to be a
1492 subroutine reference which will receive the graph and the unvisited
1493 vertices as hash reference. If you want to only visit the first
1494 tree, use "next_root =" sub { undef }>. The rest of these options
1495 are booleans. If none of them are true, a random unvisited vertex
1496 will be selected.
1497 The first start vertex is available as the graph attribute
1499 "SPT_Dijkstra_root").
1500 The result weights of vertices can be retrieved from the result
1502 graph by
1503 my $w = $sptg->get_vertex_attribute($v, 'weight');
1505 The predecessor vertex of a vertex in the result graph can be
1507 retrieved by
1508 my $u = $sptg->get_vertex_attribute($v, 'p');
1510 ("A successor vertex" cannot be retrieved as simply because a
1512 single vertex can have several successors. You can first find the
1513 neighbors() vertices and then remove the predecessor vertex.)
1514 If you want to find the shortest path between two vertices, see
1516 "SP_Dijkstra".
1517 SSSP_Dijkstra
1519 single_source_shortest_paths
1520 Aliases for SPT_Dijkstra.
1521 SP_Dijkstra
1523 @path = $g->SP_Dijkstra($u, $v)
1524 Return the vertices in the shortest path in the graph $g between
1526 the two vertices $u, $v. If no path can be found, an empty list is
1527 returned.
1528 Uses SPT_Dijkstra().
1530 SPT_Dijkstra_clear_cache
1532 $g->SPT_Dijkstra_clear_cache
1533 See "Clearing cached results".
1535 SPT_Bellman_Ford
1537 $sptg = $g->SPT_Bellman_Ford(%opt)
1538 Return as a graph the single-source shortest paths of the graph
1540 using Bellman-Ford's algorithm. The graph can contain negative
1541 edges but not negative cycles (negative cycles cause the algorithm
1542 to abort with an error message "Graph::SPT_Bellman_Ford: negative
1543 cycle exists").
1544 You can choose the start vertex of the result with either a single
1546 vertex argument or with $opt{ first_root }, otherwise a random
1547 vertex is chosen.
1548 NOTE: note that all the vertices might not be reachable from the
1550 selected (explicit or random) start vertex.
1551 The start vertex is available as the graph attribute
1553 "SPT_Bellman_Ford_root").
1554 The result weights of vertices can be retrieved from the result
1556 graph by
1557 my $w = $sptg->get_vertex_attribute($v, 'weight');
1559 The predecessor vertex of a vertex in the result graph can be
1561 retrieved by
1562 my $u = $sptg->get_vertex_attribute($v, 'p');
1564 ("A successor vertex" cannot be retrieved as simply because a
1566 single vertex can have several successors. You can first find the
1567 neighbors() vertices and then remove the predecessor vertex.)
1568 If you want to find the shortest path between two vertices, see
1570 "SP_Bellman_Ford".
1571 SSSP_Bellman_Ford
1573 Alias for SPT_Bellman_Ford.
1574 SP_Bellman_Ford
1576 @path = $g->SP_Bellman_Ford($u, $v)
1577 Return the vertices in the shortest path in the graph $g between
1579 the two vertices $u, $v. If no path can be found, an empty list is
1580 returned.
1581 Uses SPT_Bellman_Ford().
1583 SPT_Bellman_Ford_clear_cache
1585 $g->SPT_Bellman_Ford_clear_cache
1586 See "Clearing cached results".
1588 All-Pairs Shortest Paths (APSP)
1590 For either a directed or an undirected graph, return the APSP object
1591 describing all the possible paths between any two vertices of the
1592 graph. If no weight is defined for an edge, 1 (one) is assumed.
1593 Note that weight of 0 (zero) does not mean do not use this edge, it
1595 means essentially the opposite: an edge that has zero cost, an edge
1596 that makes the vertices the same.
1597 APSP_Floyd_Warshall
1599 all_pairs_shortest_paths
1600 my $apsp = $g->APSP_Floyd_Warshall(...);
1601 Return the all-pairs shortest path object computed from the graph
1603 using the Floyd-Warshall algorithm, of class
1604 Graph::TransitiveClosure.
1605 The length of a path between two vertices is the sum of weight
1607 attribute of the edges along the shortest path between the two
1608 vertices. If no weight attribute name is specified explicitly
1609 $g->APSP_Floyd_Warshall(attribute_name => 'height');
1611 the attribute "weight" is assumed.
1613 If an edge has no defined weight attribute, the value of one is
1615 assumed when getting the attribute.
1616 Once computed, you can query the APSP object with
1618 path_length
1620 my $l = $apsp->path_length($u, $v);
1621 Return the length of the shortest path between the two
1623 vertices.
1624 path_vertices
1626 my @v = $apsp->path_vertices($u, $v);
1627 Return the list of vertices along the shortest path.
1629 path_successor
1631 my $u = $apsp->path_successor($u, $v);
1632 Returns the successor of vertex $u in the all-pairs
1634 shortest path to $v.
1635 all_paths
1637 my @paths = $apsp->all_paths($u, $v);
1638 Return list of array-refs with all the paths from $u to $v.
1640 average_path_length
1642 my $apl = $g->average_path_length; # All vertex pairs.
1643 my $apl = $g->average_path_length($u); # From $u.
1645 my $apl = $g->average_path_length($u, undef); # From $u.
1646 my $apl = $g->average_path_length($u, $v); # From $u to $v.
1648 my $apl = $g->average_path_length(undef, $v); # To $v.
1650 Return the average (shortest) path length over all the non-
1652 zero paths between vertex pairs of the graph's transitive
1653 closure. Depending on the arguments, this can be from a
1654 vertex, between two vertices, or to a vertex. An undefined
1655 (or not-given) vertex will match all.
1656 longest_path
1658 my @lp = $g->longest_path;
1659 my $lp = $g->longest_path;
1660 In scalar context return the longest shortest path length
1662 over all the vertex pairs of the graph. In list context
1663 return the vertices along a longest shortest path. Note
1664 that there might be more than one such path; this interface
1665 returns a random one of them.
1666 NOTE: this returns the longest shortest path, not the
1668 longest path.
1669 diameter
1671 graph_diameter
1672 my $gd = $g->diameter;
1673 The longest path over all the vertex pairs is known as the
1675 graph diameter.
1676 For an unconnected graph, single-vertex, or empty graph,
1678 returns "undef".
1679 shortest_path
1681 my @sp = $g->shortest_path;
1682 my $sp = $g->shortest_path;
1683 In scalar context return the shortest length over all the
1685 vertex pairs of the graph. In list context return the
1686 vertices along a shortest path. Note that there might be
1687 more than one such path; this interface returns a random
1688 one of them.
1689 For an unconnected, single-vertex, or empty graph, returns
1691 "undef" or an empty list.
1692 radius
1694 my $gr = $g->radius;
1695 The shortest longest path over all the vertex pairs is
1697 known as the graph radius. See also "diameter".
1698 For an unconnected, single-vertex, or empty graph, returns
1700 Infinity.
1701 center_vertices
1703 centre_vertices
1704 my @c = $g->center_vertices;
1705 my @c = $g->center_vertices($delta);
1706 The graph center is the set of vertices for which the
1708 vertex eccentricity is equal to the graph radius. The
1709 vertices are returned in random order. By specifying a
1710 delta value you can widen the criterion from strict
1711 equality (handy for non-integer edge weights).
1712 For an unconnected, single-vertex, or empty graph, returns
1714 an empty list.
1715 vertex_eccentricity
1717 my $ve = $g->vertex_eccentricity($v);
1718 The longest path to a vertex is known as the vertex
1720 eccentricity.
1721 If the graph is unconnected, single-vertex, or empty graph,
1723 returns Inf.
1724 You can walk through the matrix of the shortest paths by using
1726 for_shortest_paths
1728 $n = $g->for_shortest_paths($callback)
1729 The number of shortest paths is returned (this should be equal
1731 to V*V). The $callback is a sub reference that receives four
1732 arguments: the transitive closure object from
1733 Graph::TransitiveClosure, the two vertices, and the index to
1734 the current shortest paths (0..V*V-1).
1735 Clearing cached results
1737 For many graph algorithms there are several different but equally valid
1738 results. (Pseudo)Randomness is used internally by the Graph module to
1739 for example pick a random starting vertex, and to select random edges
1740 from a vertex.
1741 For efficiency the computed result is often cached to avoid recomputing
1743 the potentially expensive operation, and this also gives additional
1744 determinism (once a correct result has been computed, the same result
1745 will always be given).
1746 However, sometimes the exact opposite is desirable, and the possible
1748 alternative results are wanted (within the limits of the
1749 pseudorandomness: not all the possible solutions are guaranteed to be
1750 returned, usually only a subset is returned). To undo the caching, the
1751 following methods are available:
1752 • connectivity_clear_cache
1754 Affects "connected_components", "connected_component_by_vertex",
1756 "connected_component_by_index", "same_connected_components",
1757 "connected_graph", "is_connected", "is_weakly_connected",
1758 "weakly_connected_components",
1759 "weakly_connected_component_by_vertex",
1760 "weakly_connected_component_by_index",
1761 "same_weakly_connected_components", "weakly_connected_graph".
1762 • biconnectivity_clear_cache
1764 Affects "biconnected_components",
1766 "biconnected_component_by_vertex",
1767 "biconnected_component_by_index", "is_edge_connected",
1768 "is_edge_separable", "articulation_points", "cut_vertices",
1769 "is_biconnected", "biconnected_graph",
1770 "same_biconnected_components", "bridges".
1771 • strong_connectivity_clear_cache
1773 Affects "strongly_connected_components",
1775 "strongly_connected_component_by_vertex",
1776 "strongly_connected_component_by_index",
1777 "same_strongly_connected_components", "is_strongly_connected",
1778 "strongly_connected", "strongly_connected_graph".
1779 • SPT_Dijkstra_clear_cache
1781 Affects "SPT_Dijkstra", "SSSP_Dijkstra",
1783 "single_source_shortest_paths", "SP_Dijkstra".
1784 • SPT_Bellman_Ford_clear_cache
1786 Affects "SPT_Bellman_Ford", "SSSP_Bellman_Ford", "SP_Bellman_Ford".
1788 Note that any such computed and cached results are of course always
1790 automatically discarded whenever the graph is modified.
1791 Random
1793 You can either ask for random elements of existing graphs or create
1794 random graphs.
1795 random_vertex
1797 my $v = $g->random_vertex;
1798 Return a random vertex of the graph, or undef if there are no
1800 vertices.
1801 random_edge
1803 my $e = $g->random_edge;
1804 Return a random edge of the graph as an array reference having the
1806 vertices as elements, or undef if there are no edges.
1807 random_successor
1809 my $v = $g->random_successor($v);
1810 Return a random successor of the vertex in the graph, or undef if
1812 there are no successors.
1813 random_predecessor
1815 my $u = $g->random_predecessor($v);
1816 Return a random predecessor of the vertex in the graph, or undef if
1818 there are no predecessors.
1819 random_graph
1821 my $g = Graph->random_graph(%opt);
1822 Construct a random graph. The %opt must contain the "vertices"
1824 argument
1825 vertices => vertices_def
1827 where the vertices_def is one of
1829 • an array reference where the elements of the array
1831 reference are the vertices
1832 • a number N in which case the vertices will be integers
1834 0..N-1
1835 The %opt may have either of the argument "edges" or the argument
1837 "edges_fill". Both are used to define how many random edges to add to
1838 the graph; "edges" is an absolute number, while "edges_fill" is a
1839 relative number (relative to the number of edges in a complete graph,
1840 C). The number of edges can be larger than C, but only if the graph is
1841 countedged. The random edges will not include self-loops. If neither
1842 "edges" nor "edges_fill" is specified, an "edges_fill" of 0.5 is
1843 assumed.
1844 If you want repeatable randomness (what is an oxymoron?) you can use
1846 the "random_seed" option:
1847 $g = Graph->random_graph(vertices => 10, random_seed => 1234);
1849 As this uses the standard Perl srand(), the usual caveat applies: use
1851 it sparingly, and consider instead using a single srand() call at the
1852 top level of your application.
1853 The default random distribution of edges is flat, that is, any pair of
1855 vertices is equally likely to appear. To define your own distribution,
1856 use the "random_edge" option:
1857 $g = Graph->random_graph(vertices => 10, random_edge => \&d);
1859 where "d" is a code reference receiving ($g, $u, $v, $p) as parameters,
1861 where the $g is the random graph, $u and $v are the vertices, and the
1862 $p is the probability ([0,1]) for a flat distribution. It must return
1863 a probability ([0,1]) that the vertices $u and $v have an edge between
1864 them. Note that returning one for a particular pair of vertices
1865 doesn't guarantee that the edge will be present in the resulting graph
1866 because the required number of edges might be reached before that
1867 particular pair is tested for the possibility of an edge. Be very
1868 careful to adjust also "edges" or "edges_fill" so that there is a
1869 possibility of the filling process terminating.
1870 NOTE: a known problem with randomness in openbsd pre-perl-5.20 is that
1872 using a seed does not give you deterministic randomness. This affects
1873 any Perl code, not just Graph.
1874 Attributes
1876 You can attach free-form attributes (key-value pairs, in effect a full
1877 Perl hash) to each vertex, edge, and the graph itself.
1878 Note that attaching attributes does slow down some other operations on
1880 the graph by a factor of three to ten. For example adding edge
1881 attributes does slow down anything that walks through all the edges.
1882 For vertex attributes:
1884 set_vertex_attribute
1886 $g->set_vertex_attribute($v, $name, $value)
1887 Set the named vertex attribute.
1889 If the vertex does not exist, the set_...() will create it, and the
1891 other vertex attribute methods will return false or empty.
1892 NOTE: any attributes beginning with an underscore/underline (_) are
1894 reserved for the internal use of the Graph module.
1895 get_vertex_attribute
1897 $value = $g->get_vertex_attribute($v, $name)
1898 Return the named vertex attribute.
1900 has_vertex_attribute
1902 $g->has_vertex_attribute($v, $name)
1903 Return true if the vertex has an attribute, false if not.
1905 delete_vertex_attribute
1907 $g->delete_vertex_attribute($v, $name)
1908 Delete the named vertex attribute.
1910 set_vertex_attributes
1912 $g->set_vertex_attributes($v, $attr)
1913 Set all the attributes of the vertex from the anonymous hash $attr.
1915 NOTE: any attributes beginning with an underscore ("_") are
1917 reserved for the internal use of the Graph module.
1918 get_vertex_attributes
1920 $attr = $g->get_vertex_attributes($v)
1921 Return all the attributes of the vertex as an anonymous hash, or
1923 "undef" if no such vertex.
1924 get_vertex_attribute_names
1926 @name = $g->get_vertex_attribute_names($v)
1927 Return the names of vertex attributes.
1929 get_vertex_attribute_values
1931 @value = $g->get_vertex_attribute_values($v)
1932 Return the values of vertex attributes.
1934 has_vertex_attributes
1936 $g->has_vertex_attributes($v)
1937 Return true if the vertex has any attributes, false if not.
1939 delete_vertex_attributes
1941 $g->delete_vertex_attributes($v)
1942 Delete all the attributes of the named vertex.
1944 If you are using multivertices, use the by_id variants:
1946 set_vertex_attribute_by_id
1948 get_vertex_attribute_by_id
1949 has_vertex_attribute_by_id
1950 delete_vertex_attribute_by_id
1951 set_vertex_attributes_by_id
1952 get_vertex_attributes_by_id
1953 get_vertex_attribute_names_by_id
1954 get_vertex_attribute_values_by_id
1955 has_vertex_attributes_by_id
1956 delete_vertex_attributes_by_id
1957 $g->set_vertex_attribute_by_id($v, $id, $name, $value)
1958 $g->get_vertex_attribute_by_id($v, $id, $name)
1959 $g->has_vertex_attribute_by_id($v, $id, $name)
1960 $g->delete_vertex_attribute_by_id($v, $id, $name)
1961 $g->set_vertex_attributes_by_id($v, $id, $attr)
1962 $g->get_vertex_attributes_by_id($v, $id)
1963 $g->get_vertex_attribute_values_by_id($v, $id)
1964 $g->get_vertex_attribute_names_by_id($v, $id)
1965 $g->has_vertex_attributes_by_id($v, $id)
1966 $g->delete_vertex_attributes_by_id($v, $id)
1967 For edge attributes:
1969 set_edge_attribute
1971 $g->set_edge_attribute($u, $v, $name, $value)
1972 Set the named edge attribute.
1974 If the edge does not exist, the set_...() will create it, and the
1976 other edge attribute methods will return false or empty.
1977 NOTE: any attributes beginning with an underscore ("_") are
1979 reserved for the internal use of the Graph module.
1980 get_edge_attribute
1982 $value = $g->get_edge_attribute($u, $v, $name)
1983 Return the named edge attribute.
1985 has_edge_attribute
1987 $g->has_edge_attribute($u, $v, $name)
1988 Return true if the edge has an attribute, false if not.
1990 delete_edge_attribute
1992 $g->delete_edge_attribute($u, $v, $name)
1993 Delete the named edge attribute.
1995 set_edge_attributes
1997 $g->set_edge_attributes($u, $v, $attr)
1998 Set all the attributes of the edge from the anonymous hash $attr.
2000 NOTE: any attributes beginning with an underscore ("_") are
2002 reserved for the internal use of the Graph module.
2003 get_edge_attributes
2005 $attr = $g->get_edge_attributes($u, $v)
2006 Return all the attributes of the edge as an anonymous hash, or
2008 "undef" if no such edge.
2009 get_edge_attribute_names
2011 @name = $g->get_edge_attribute_names($u, $v)
2012 Return the names of edge attributes.
2014 get_edge_attribute_values
2016 @value = $g->get_edge_attribute_values($u, $v)
2017 Return the values of edge attributes.
2019 has_edge_attributes
2021 $g->has_edge_attributes($u, $v)
2022 Return true if the edge has any attributes, false if not.
2024 delete_edge_attributes
2026 $g->delete_edge_attributes($u, $v)
2027 Delete all the attributes of the named edge.
2029 If you are using multiedges, use the by_id variants:
2031 set_edge_attribute_by_id
2033 get_edge_attribute_by_id
2034 has_edge_attribute_by_id
2035 delete_edge_attribute_by_id
2036 set_edge_attributes_by_id
2037 get_edge_attributes_by_id
2038 get_edge_attribute_names_by_id
2039 get_edge_attribute_values_by_id
2040 has_edge_attributes_by_id
2041 delete_edge_attributes_by_id
2042 $g->set_edge_attribute_by_id($u, $v, $id, $name, $value)
2043 $g->get_edge_attribute_by_id($u, $v, $id, $name)
2044 $g->has_edge_attribute_by_id($u, $v, $id, $name)
2045 $g->delete_edge_attribute_by_id($u, $v, $id, $name)
2046 $g->set_edge_attributes_by_id($u, $v, $id, $attr)
2047 $g->get_edge_attributes_by_id($u, $v, $id)
2048 $g->get_edge_attribute_values_by_id($u, $v, $id)
2049 $g->get_edge_attribute_names_by_id($u, $v, $id)
2050 $g->has_edge_attributes_by_id($u, $v, $id)
2051 $g->delete_edge_attributes_by_id($u, $v, $id)
2052 For graph attributes:
2054 set_graph_attribute
2056 $g->set_graph_attribute($name, $value)
2057 Set the named graph attribute.
2059 NOTE: any attributes beginning with an underscore ("_") are
2061 reserved for the internal use of the Graph module.
2062 get_graph_attribute
2064 $value = $g->get_graph_attribute($name)
2065 Return the named graph attribute.
2067 has_graph_attribute
2069 $g->has_graph_attribute($name)
2070 Return true if the graph has an attribute, false if not.
2072 delete_graph_attribute
2074 $g->delete_graph_attribute($name)
2075 Delete the named graph attribute.
2077 set_graph_attributes
2079 $g->get_graph_attributes($attr)
2080 Set all the attributes of the graph from the anonymous hash $attr.
2082 NOTE: any attributes beginning with an underscore ("_") are
2084 reserved for the internal use of the Graph module.
2085 get_graph_attributes
2087 $attr = $g->get_graph_attributes()
2088 Return all the attributes of the graph as an anonymous hash.
2090 get_graph_attribute_names
2092 @name = $g->get_graph_attribute_names()
2093 Return the names of graph attributes.
2095 get_graph_attribute_values
2097 @value = $g->get_graph_attribute_values()
2098 Return the values of graph attributes.
2100 has_graph_attributes
2102 $g->has_graph_attributes()
2103 Return true if the graph has any attributes, false if not.
2105 delete_graph_attributes
2107 $g->delete_graph_attributes()
2108 Delete all the attributes of the named graph.
2110 Weighted
2112 As convenient shortcuts the following methods add, query, and
2113 manipulate the attribute "weight" with the specified value to the
2114 respective Graph elements.
2115 add_weighted_edge
2117 $g->add_weighted_edge($u, $v, $weight)
2118 add_weighted_edges
2120 $g->add_weighted_edges($u1, $v1, $weight1, ...)
2121 add_weighted_path
2123 $g->add_weighted_path($v1, $weight1, $v2, $weight2, $v3, ...)
2124 add_weighted_vertex
2126 $g->add_weighted_vertex($v, $weight)
2127 add_weighted_vertices
2129 $g->add_weighted_vertices($v1, $weight1, $v2, $weight2, ...)
2130 delete_edge_weight
2132 $g->delete_edge_weight($u, $v)
2133 delete_vertex_weight
2135 $g->delete_vertex_weight($v)
2136 get_edge_weight
2138 $g->get_edge_weight($u, $v)
2139 get_vertex_weight
2141 $g->get_vertex_weight($v)
2142 has_edge_weight
2144 $g->has_edge_weight($u, $v)
2145 has_vertex_weight
2147 $g->has_vertex_weight($v)
2148 set_edge_weight
2150 $g->set_edge_weight($u, $v, $weight)
2151 set_vertex_weight
2153 $g->set_vertex_weight($v, $weight)
2154 Isomorphism
2156 Two graphs being isomorphic means that they are structurally the same
2157 graph, the difference being that the vertices might have been renamed
2158 or substituted. For example in the below example $g0 and $g1 are
2159 isomorphic: the vertices "b c d" have been renamed as "z x y".
2160 $g0 = Graph->new;
2162 $g0->add_edges(qw(a b a c c d));
2163 $g1 = Graph->new;
2164 $g1->add_edges(qw(a x x y a z));
2165 In the general case determining isomorphism is NP-hard, in other words,
2167 really hard (time-consuming), no other ways of solving the problem are
2168 known than brute force check of of all the possibilities (with possible
2169 optimization tricks, of course, but brute force still rules at the end
2170 of the day).
2171 A very rough guess at whether two graphs could be isomorphic is
2173 possible via the method
2174 could_be_isomorphic
2176 $g0->could_be_isomorphic($g1)
2177 If the graphs do not have the same number of vertices and edges, false
2179 is returned. If the distribution of in-degrees and out-degrees at the
2180 vertices of the graphs does not match, false is returned. Otherwise,
2181 true is returned.
2182 What is actually returned is the maximum number of possible isomorphic
2184 graphs between the two graphs, after the above sanity checks have been
2185 conducted. It is basically the product of the factorials of the
2186 absolute values of in-degrees and out-degree pairs at each vertex, with
2187 the isolated vertices ignored (since they could be reshuffled and
2188 renamed arbitrarily). Note that for large graphs the product of these
2189 factorials can overflow the maximum presentable number (the floating
2190 point number) in your computer (in Perl) and you might get for example
2191 Infinity as the result.
2192 Miscellaneous
2194 betweenness
2195 %b = $g->betweenness
2196 Returns a map of vertices to their Freeman's betweennesses:
2198 C_b(v) = \sum_{s \neq v \neq t \in V} \frac{\sigma_{s,t}(v)}{\sigma_{s,t}}
2200 It is described in:
2202 Freeman, A set of measures of centrality based on betweenness, http://arxiv.org/pdf/cond-mat/0309045
2204 and based on the algorithm from:
2206 "A Faster Algorithm for Betweenness Centrality"
2208 clustering_coefficient
2210 $gamma = $g->clustering_coefficient()
2211 ($gamma, %clustering) = $g->clustering_coefficient()
2212 Returns the clustering coefficient gamma as described in
2214 Duncan J. Watts and Steven Strogatz, Collective dynamics of 'small-world' networks, https://web.archive.org/web/20120616204225/http://audiophile.tam.cornell.edu/SS_nature_smallworld.pdf
2216 In scalar context returns just the average gamma, in list context
2218 returns the average gamma and a hash of vertices to clustering
2219 coefficients.
2220 Returns an empty list (and therefore undefined in scalar context)
2222 if the graph has no vertices.
2223 subgraph_by_radius
2225 $s = $g->subgraph_by_radius(@v, $radius);
2226 Returns a subgraph representing the ball of $radius around the
2228 given vertices (breadth-first search).
2229 The "expect" methods can be used to test a graph and croak if the graph
2231 call is not as expected.
2232 expect_acyclic
2234 expect_dag
2235 expect_directed
2236 expect_hyperedged
2237 expect_multiedge
2238 expect_multiedged
2239 expect_multivertex
2240 expect_multivertexed
2241 expect_no_args
2242 expect_non_multiedge
2243 expect_non_multiedged
2244 expect_non_multivertex
2245 expect_non_multivertexed
2246 expect_non_unionfind
2247 expect_undirected
2248 In many algorithms it is useful to have a value representing the
2250 infinity. The Graph provides (and itself uses):
2251 Infinity
2253 (Not exported, use Graph::Infinity explicitly)
2254 Size Requirements
2256 A graph takes up at least 1172 bytes of memory.
2257 A vertex takes up at least 100 bytes of memory.
2259 An edge takes up at least 400 bytes of memory.
2261 (A Perl scalar value takes 16 bytes, or 12 bytes if it's a reference.)
2263 These size approximations are very approximate and optimistic (they are
2265 based on total_size() of Devel::Size). In real life many factors
2266 affect these numbers, for example how Perl is configured. The numbers
2267 are for a 32-bit platform and for Perl 5.8.8.
2268 Roughly, the above numbers mean that in a megabyte of memory you can
2270 fit for example a graph of about 1000 vertices and about 2500 edges.
2271 Hyperedges, hypergraphs
2273 BEWARE: this is a rather thinly tested feature, and the theory is even
2274 less so. Do not expect this to stay as it is (or at all) in future
2275 releases.
2276 NOTE: most usual graph algorithms (and basic concepts) break horribly
2278 (or at least will look funny) with these hyperthingies. Caveat emptor.
2279 Hyperedges are edges that connect a number of vertices different from
2281 the usual two.
2282 Hypergraphs are graphs with hyperedges.
2284 To enable hyperness when constructing Graphs use the "hyperedged"
2286 attribute:
2287 my $h = Graph->new(hyperedged => 1);
2289 To test for hyperness of a graph use the
2291 is_hyperedged
2293 hyperedged
2294 $g->is_hyperedged
2295 $g->hyperedged
2296 Edges in hypergraphs are either directed or undirected, as with simple
2298 graphs. If undirected, the edge is a blob of 0 or more vertices. For
2299 directed, the set of heads and set of tails are also possibly empty. In
2300 general, hypergraphs are simply generalisations of simple-graph ideas,
2301 with some of the arbitrary limitations removed.
2302 For more information on directed hypergraphs, see Directed Hypergraphs
2304 and Applications, Gallo-Longo-Pallottino-Nguyen
2305 <https://doi.org/10.1016/0166-218X%2893%2990045-P>. It defines
2306 hyperarcs (directed edges in a hypergraph) as ordered pairs of subsets
2307 of V, and hyperedges (undirected) as single subsets of V. Since sets
2308 are unordered and elements within them are unique, this implies that
2309 the only valuable use for hypergraphs is where in a given connection
2310 entity (edge or arc), each vertex only appears at most once.
2311 Additionally, how the "hyper" property of edges works may change. The
2312 underpinning notion is that each edge will be considered an entry in an
2313 incidence matrix (dimensions |V| x |E|), with values of either (0,
2314 1=participating) for undirected (hyperedges), or (-1=tail, 0, 1=head)
2315 for directed (hyperarcs) against each vertex.
2316 An extension to this is that to extend directed multigraphs with self-
2318 loops (aka "quivers") to hypergraphs, the incidence-matrix values will
2319 instead be a bitfield, with bit 0 being participation in the tail, and
2320 bit 1 in the head.
2321 DIAGNOSTICS
2323 • Graph::...Map...: arguments X expected Y ...
2324 If you see these (more user-friendly error messages should have
2326 been triggered above and before these) please report any such
2327 occurrences, but in general you should be happy to see these since
2328 it means that an attempt to call something with a wrong number of
2329 arguments was caught in time.
2330 • Graph::add_edge: graph is not hyperedged ...
2332 Maybe you used add_weighted_edge() with only the two vertex
2334 arguments.
2335 • Not an ARRAY reference at lib/Graph.pm ...
2337 One possibility is that you have code based on Graph 0.2xxxx that
2339 assumes Graphs being blessed hash references, possibly also
2340 assuming that certain hash keys are available to use for your own
2341 purposes. In Graph 0.50 none of this is true. Please do not
2342 expect any particular internal implementation of Graphs. Use
2343 inheritance and graph/vertex/edge attributes instead.
2344 Another possibility is that you meant to have objects (blessed
2346 references) as graph vertices, but forgot to use "refvertexed" (see
2347 "refvertexed") when creating the graph.
2348 • Deep recursion on subroutine "Graph::_biconnectivity_dfs" at ...
2350 If you have more than 100 vertices, the recursive algorithm will
2352 trigger Perl's recursion protection. If you set environment
2353 variable "GRAPH_ALLOW_RECURSION" to a true value, this protection
2354 will be disabled, e.g.:
2355 $ GRAPH_ALLOW_RECURSION=1 perl -Ilib util/grand.pl --test=bcc 101
2357
2359 All bad terminology, bugs, and inefficiencies are naturally mine, all
2360 mine, and not the fault of the below.
2361 Thanks to Nathan Goodman and Andras Salamon for bravely betatesting my
2363 pre-0.50 code. If they missed something, that was only because of my
2364 fiendish code.
2365 The following literature for algorithms and some test cases:
2367 • Algorithms in C, Third Edition, Part 5, Graph Algorithms, Robert
2369 Sedgewick, Addison Wesley
2370 • Introduction to Algorithms, First Edition, Cormen-Leiserson-Rivest,
2372 McGraw Hill
2373 • Graphs, Networks and Algorithms, Dieter Jungnickel, Springer
2375
2377 Persistent/Serialized graphs? You want to read/write Graphs? See the
2378 Graph::Reader and Graph::Writer in CPAN.
2379
2381 Jarkko Hietaniemi jhi@iki.fi
2382 Now being maintained by Neil Bowers <neilb@cpan.org>
2384
2386 Copyright (c) 1998-2014 Jarkko Hietaniemi. All rights reserved.
2387 This is free software; you can redistribute it and/or modify it under
2389 the same terms as the Perl 5 programming language system itself.
2390perl v5.36.0 2023-01-20 Graph(3)