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 undirected_copy
159 undirected_copy_graph
160 my $c = $g->undirected_copy_graph;
161 Create an undirected shallow copy (vertices and edges) of the
163 directed graph so that for any directed edge (u, v) there is an
164 undirected edge (u, v).
165 undirected_copy_clear_cache
167 @path = $g->undirected_copy_clear_cache;
168 See "Clearing cached results".
170 directed_copy
172 directed_copy_graph
173 my $c = $g->directed_copy_graph;
174 Create a directed shallow copy (vertices and edges) of the
176 undirected graph so that for any undirected edge (u, v) there are
177 two directed edges (u, v) and (v, u).
178 transpose
180 transpose_graph
181 my $t = $g->transpose_graph;
182 Create a directed shallow transposed copy (vertices and edges) of
184 the directed graph so that for any directed edge (u, v) there is a
185 directed edge (v, u).
186 You can also transpose a single edge with
188 transpose_edge
190 $g->transpose_edge($u, $v)
191 complete_graph
193 complete
194 my $c = $g->complete_graph;
195 Create a complete graph that has the same vertices as the original
197 graph. A complete graph has an edge between every pair of
198 vertices.
199 complement_graph
201 complement
202 my $c = $g->complement_graph;
203 Create a complement graph that has the same vertices as the
205 original graph. A complement graph has an edge (u,v) if and only
206 if the original graph does not have edge (u,v).
207 subgraph
209 my $c = $g->subgraph(\@src, \@dst);
210 my $c = $g->subgraph(\@src);
211 Creates a subgraph of a given graph. The created subgraph has the
213 same graph properties (directedness, and so forth) as the original
214 graph, but none of the attributes (graph, vertex, or edge).
215 A vertex is added to the subgraph if it is in the original graph.
217 An edge is added to the subgraph if there is an edge in the
219 original graph that starts from the "src" set of vertices and ends
220 in the "dst" set of vertices.
221 You can leave out "dst" in which case "dst" is assumed to be the
223 same: this is called a vertex-induced subgraph.
224 See also "random_graph" for a random constructor.
226 Basics
228 add_vertex
229 $g->add_vertex($v)
230 Add the vertex to the graph. Returns the graph.
232 By default idempotent, but a graph can be created countvertexed.
234 A vertex is also known as a node.
236 Adding "undef" as vertex is not allowed.
238 Note that unless you have isolated vertices (or countvertexed
240 vertices), you do not need to explicitly use "add_vertex" since
241 "add_edge" will implicitly add its vertices.
242 add_edge
244 $g->add_edge($u, $v)
245 Add the edge to the graph. Implicitly first adds the vertices if
247 the graph does not have them. Returns the graph.
248 By default idempotent, but a graph can be created countedged.
250 An edge is also known as an arc.
252 For a hypergraph, the interface is different: if undirected, give a
254 list of one or more vertices. If directed, give a list of two
255 array-refs of vertices. As conceptually these are sets, the
256 ordering of the contents is not important.
257 has_vertex
259 $g->has_vertex($v)
260 Return true if the vertex exists in the graph, false otherwise.
262 has_edge
264 $g->has_edge($u, $v)
265 Return true if the edge exists in the graph, false otherwise.
267 any_edge
269 $g->any_edge($u, $v)
270 Return true if any edge in the graph connects the first vertex to
272 the second, false otherwise. Note this is a different question from
273 "has_edge". It will give the same result as checking the first
274 vertex's "successors" to see if any match the second one, but in a
275 more efficient way.
276 delete_vertex
278 $g->delete_vertex($v)
279 Delete the vertex from the graph. Returns the graph, even if the
281 vertex did not exist in the graph.
282 If the graph has been created multivertexed or countvertexed and a
284 vertex has been added multiple times, the vertex will require at
285 least an equal number of deletions to become completely deleted.
286 delete_vertices
288 $g->delete_vertices($v1, $v2, ...)
289 Delete the vertices from the graph. Returns the graph, even if
291 none of the vertices existed in the graph.
292 If the graph has been created multivertexed or countvertexed and a
294 vertex has been added multiple times, the vertex will require at
295 least an equal number of deletions to become completely deleted.
296 delete_edge
298 $g->delete_edge($u, $v)
299 Delete the edge from the graph. Returns the graph, even if the
301 edge did not exist in the graph.
302 If the graph has been created multiedged or countedged and an edge
304 has been added multiple times, the edge will require at least an
305 equal number of deletions to become completely deleted.
306 delete_edges
308 $g->delete_edges($u1, $v1, $u2, $v2, ...)
309 Delete the edges from the graph. Returns the graph, even if none
311 of the edges existed in the graph.
312 If the graph has been created multiedged or countedged and an edge
314 has been added multiple times, the edge will require at least an
315 equal number of deletions to become completely deleted.
316 Displaying
318 Graphs have stringification overload, so you can do things like
319 print "The graph is $g\n"
321 One-way (directed, unidirected) edges are shown as '-', two-way
323 (undirected, bidirected) edges are shown as '='. If you want to, you
324 can call the stringification via the method
325 stringify
327 Boolean
329 Graphs have boolifying overload, so you can do things like
330 if ($g) { print "The graph is: $g\n" }
332 which works even if the graph is empty. In fact, the boolify always
334 returns true. If you want to test for example for vertices, test for
335 vertices.
336 boolify
338 Comparing
340 Testing for equality can be done either by the overloaded "eq" operator
341 $g eq "a-b,a-c,d"
343 or by the method
345 eq
347 $g->eq("a-b,a-c,d")
348 The equality testing compares the stringified forms, and therefore it
350 assumes total equality, not isomorphism: all the vertices must be named
351 the same, and they must have identical edges between them.
352 For unequality there are correspondingly the overloaded "ne" operator
354 and the method
355 ne
357 $g->ne("a-b,a-c,d")
358 See also "Isomorphism".
360 Paths and Cycles
362 Paths and cycles are simple extensions of edges: paths are edges
363 starting from where the previous edge ended, and cycles are paths
364 returning back to the start vertex of the first edge.
365 add_path
367 $g->add_path($a, $b, $c, ..., $x, $y, $z)
368 Add the edges $a-$b, $b-$c, ..., $x-$y, $y-$z to the graph.
370 Returns the graph.
371 has_path
373 $g->has_path($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, false otherwise.
377 delete_path
379 $g->delete_path($a, $b, $c, ..., $x, $y, $z)
380 Delete all the edges $a-$b, $b-$c, ..., $x-$y, $y-$z (regardless of
382 whether they exist or not). Returns the graph.
383 add_cycle
385 $g->add_cycle($a, $b, $c, ..., $x, $y, $z)
386 Add the edges $a-$b, $b-$c, ..., $x-$y, $y-$z, and $z-$a to the
388 graph. Returns the graph.
389 has_cycle
391 has_this_cycle
392 $g->has_cycle($a, $b, $c, ..., $x, $y, $z)
393 Return true if the graph has all the edges $a-$b, $b-$c, ...,
395 $x-$y, $y-$z, and $z-$a, false otherwise.
396 NOTE: This does not detect cycles, see "has_a_cycle" and
398 "find_a_cycle".
399 delete_cycle
401 $g->delete_cycle($a, $b, $c, ..., $x, $y, $z)
402 Delete all the edges $a-$b, $b-$c, ..., $x-$y, $y-$z, and $z-$a
404 (regardless of whether they exist or not). Returns the graph.
405 has_a_cycle
407 $g->has_a_cycle
408 Returns true if the graph has a cycle, false if not.
410 find_a_cycle
412 $g->find_a_cycle
413 Returns a cycle if the graph has one (as a list of vertices), an
415 empty list if no cycle can be found.
416 Note that this just returns the vertices of a cycle: not any
418 particular cycle, just the first one it finds. A repeated call
419 might find the same cycle, or it might find a different one, and
420 you cannot call this repeatedly to find all the cycles.
421 Graph Types
423 is_simple_graph
424 $g->is_simple_graph
425 Return true if the graph has no multiedges, false otherwise.
427 is_pseudo_graph
429 $g->is_pseudo_graph
430 Return true if the graph has any multiedges or any self-loops,
432 false otherwise.
433 is_multi_graph
435 $g->is_multi_graph
436 Return true if the graph has any multiedges but no self-loops,
438 false otherwise.
439 is_directed_acyclic_graph
441 is_dag
442 $g->is_directed_acyclic_graph
443 $g->is_dag
444 Return true if the graph is directed and acyclic, false otherwise.
446 is_cyclic
448 $g->is_cyclic
449 Return true if the graph is cyclic (contains at least one cycle).
451 (This is identical to "has_a_cycle".)
452 To find at least one such cycle, see "find_a_cycle".
454 is_acyclic
456 Return true if the graph is acyclic (does not contain any cycles).
457 To find a cycle, use "find_a_cycle".
459 Transitivity
461 is_transitive
462 $g->is_transitive
463 Return true if the graph is transitive, false otherwise.
465 TransitiveClosure_Floyd_Warshall
467 transitive_closure
468 $tcg = $g->TransitiveClosure_Floyd_Warshall
469 Return the transitive closure graph of the graph.
471 transitive_closure_matrix_clear_cache
473 $g->transitive_closure_matrix_clear_cache
474 See "Clearing cached results".
476 You can query the reachability from $u to $v with
478 is_reachable
480 $tcg->is_reachable($u, $v)
481 See Graph::TransitiveClosure for more information about creating and
483 querying transitive closures.
484 With
486 transitive_closure_matrix
488 $tcm = $g->transitive_closure_matrix;
489 you can (create if not existing and) query the transitive closure
491 matrix that underlies the transitive closure graph. See
492 Graph::TransitiveClosure::Matrix for more information.
493 Mutators
495 add_vertices
496 $g->add_vertices('d', 'e', 'f')
497 Add zero or more vertices to the graph. Returns the graph.
499 add_edges
501 $g->add_edges(['d', 'e'], ['f', 'g'])
502 $g->add_edges(qw(d e f g));
503 Add zero or more edges to the graph. The edges are specified as a
505 list of array references, or as a list of vertices where the even
506 (0th, 2nd, 4th, ...) items are start vertices and the odd (1st,
507 3rd, 5th, ...) are the corresponding end vertices. Returns the
508 graph.
509 For a hypergraph, each item in this list must be an array-ref of
511 arguments suitable for "add_edge" - so for undirected, of vertices;
512 for directed, of two array-refs of vertices.
513 rename_vertex
515 $g->rename_vertex('d', 'e')
516 Renames a vertex. It retains all of its edges. Throws exception if
518 doesn't exist.
519 Returns the graph.
521 rename_vertices
523 $g->rename_vertices(sub { uc $_[0] })
524 Calls a function for each vertex-name, renaming it to the return
526 value.
527 Returns the graph.
529 ingest
531 $g->ingest($g2)
532 Ingests all the vertices and edges of the given graph, including
534 attributes. Returns the ingesting graph.
535 Accessors
537 is_directed
538 directed
539 $g->is_directed()
540 $g->directed()
541 Return true if the graph is directed, false otherwise.
543 is_undirected
545 undirected
546 $g->is_undirected()
547 $g->undirected()
548 Return true if the graph is undirected, false otherwise.
550 is_refvertexed
552 is_refvertexed_stringified
553 refvertexed
554 refvertexed_stringified
555 Return true if the graph can handle references (including Perl
556 objects) as vertices.
557 vertices
559 my $V = $g->vertices
560 my @V = $g->vertices
561 In scalar context, return the number of vertices in the graph. In
563 list context, return the vertices, in no particular order.
564 has_vertices
566 $g->has_vertices()
567 Return true if the graph has any vertices, false otherwise.
569 edges
571 my $E = $g->edges
572 my @E = $g->edges
573 In scalar context, return the number of edges in the graph. In
575 list context, return the edges, in no particular order. The edges
576 are returned as anonymous arrays listing the vertices.
577 has_edges
579 $g->has_edges()
580 Return true if the graph has any edges, false otherwise.
582 is_connected
584 $g->is_connected
585 For an undirected graph, return true if the graph is connected,
587 false otherwise. Being connected means that from every vertex it
588 is possible to reach every other vertex.
589 If the graph has been created with a true "unionfind" parameter,
591 the time complexity is (essentially) O(V), otherwise O(V log V).
592 See also "connected_components", "connected_component_by_index",
594 "connected_component_by_vertex", and "same_connected_components",
595 and "biconnectivity".
596 For directed graphs, see "is_strongly_connected" and
598 "is_weakly_connected".
599 connected_components
601 @cc = $g->connected_components()
602 For an undirected graph, returns the vertices of the connected
604 components of the graph as a list of anonymous arrays. The
605 ordering of the anonymous arrays or the ordering of the vertices
606 inside the anonymous arrays (the components) is undefined.
607 For directed graphs, see "strongly_connected_components" and
609 "weakly_connected_components".
610 connected_component_by_vertex
612 $i = $g->connected_component_by_vertex($v)
613 For an undirected graph, return an index identifying the connected
615 component the vertex belongs to, the indexing starting from zero.
616 For the inverse, see "connected_component_by_index".
618 If the graph has been created with a true "unionfind" parameter,
620 the time complexity is (essentially) O(1), otherwise O(V log V).
621 See also "biconnectivity".
623 For directed graphs, see "strongly_connected_component_by_vertex"
625 and "weakly_connected_component_by_vertex".
626 connected_component_by_index
628 @v = $g->connected_component_by_index($i)
629 For an undirected graph, return the vertices of the ith connected
631 component, the indexing starting from zero. The order of vertices
632 is undefined, while the order of the connected components is same
633 as from connected_components().
634 For the inverse, see "connected_component_by_vertex".
636 For directed graphs, see "strongly_connected_component_by_index"
638 and "weakly_connected_component_by_index".
639 same_connected_components
641 $g->same_connected_components($u, $v, ...)
642 For an undirected graph, return true if the vertices are in the
644 same connected component.
645 If the graph has been created with a true "unionfind" parameter,
647 the time complexity is (essentially) O(1), otherwise O(V log V).
648 For directed graphs, see "same_strongly_connected_components" and
650 "same_weakly_connected_components".
651 connected_graph
653 $cg = $g->connected_graph
654 For an undirected graph, return its connected graph.
656 connectivity_clear_cache
658 $g->connectivity_clear_cache
659 See "Clearing cached results".
661 See "Connected Graphs and Their Components" for further discussion.
663 biconnectivity
665 my ($ap, $bc, $br) = $g->biconnectivity
666 For an undirected graph, return the various biconnectivity
668 components of the graph: the articulation points (cut vertices),
669 biconnected components, and bridges.
670 Note: currently only handles connected graphs.
672 is_biconnected
674 $g->is_biconnected
675 For an undirected graph, return true if the graph is biconnected
677 (if it has no articulation points, also known as cut vertices).
678 is_edge_connected
680 $g->is_edge_connected
681 For an undirected graph, return true if the graph is edge-connected
683 (if it has no bridges).
684 Note: more precisely, this would be called is_edge_biconnected,
686 since there is a more general concept of being k-connected.
687 is_edge_separable
689 $g->is_edge_separable
690 For an undirected graph, return true if the graph is edge-separable
692 (if it has bridges).
693 Note: more precisely, this would be called is_edge_biseparable,
695 since there is a more general concept of being k-connected.
696 articulation_points
698 cut_vertices
699 $g->articulation_points
700 For an undirected graph, return the articulation points (cut
702 vertices) of the graph as a list of vertices. The order is
703 undefined.
704 biconnected_components
706 $g->biconnected_components
707 For an undirected graph, return the biconnected components of the
709 graph as a list of anonymous arrays of vertices in the components.
710 The ordering of the anonymous arrays or the ordering of the
711 vertices inside the anonymous arrays (the components) is undefined.
712 Also note that one vertex can belong to more than one biconnected
713 component.
714 biconnected_component_by_vertex
716 $i = $g->biconnected_component_by_index($v)
717 For an undirected graph, return the indices identifying the
719 biconnected components the vertex belongs to, the indexing starting
720 from zero. The order of of the components is undefined.
721 For the inverse, see "connected_component_by_index".
723 For directed graphs, see "strongly_connected_component_by_index"
725 and "weakly_connected_component_by_index".
726 biconnected_component_by_index
728 @v = $g->biconnected_component_by_index($i)
729 For an undirected graph, return the vertices in the ith biconnected
731 component of the graph as an anonymous arrays of vertices in the
732 component. The ordering of the vertices within a component is
733 undefined. Also note that one vertex can belong to more than one
734 biconnected component.
735 same_biconnected_components
737 $g->same_biconnected_components($u, $v, ...)
738 For an undirected graph, return true if the vertices are in the
740 same biconnected component.
741 biconnected_graph
743 $bcg = $g->biconnected_graph
744 For an undirected graph, return its biconnected graph.
746 See "Connected Graphs and Their Components" for further discussion.
748 bridges
750 $g->bridges
751 For an undirected graph, return the bridges of the graph as a list
753 of anonymous arrays of vertices in the bridges. The order of
754 bridges and the order of vertices in them is undefined.
755 biconnectivity_clear_cache
757 $g->biconnectivity_clear_cache
758 See "Clearing cached results".
760 strongly_connected
762 is_strongly_connected
763 $g->is_strongly_connected
764 For a directed graph, return true is the directed graph is strongly
766 connected, false if not.
767 See also "is_weakly_connected".
769 For undirected graphs, see "is_connected", or "is_biconnected".
771 strongly_connected_component_by_vertex
773 $i = $g->strongly_connected_component_by_vertex($v)
774 For a directed graph, return an index identifying the strongly
776 connected component the vertex belongs to, the indexing starting
777 from zero.
778 For the inverse, see "strongly_connected_component_by_index".
780 See also "weakly_connected_component_by_vertex".
782 For undirected graphs, see "connected_components" or
784 "biconnected_components".
785 strongly_connected_component_by_index
787 @v = $g->strongly_connected_component_by_index($i)
788 For a directed graph, return the vertices of the ith connected
790 component, the indexing starting from zero. The order of vertices
791 within a component is undefined, while the order of the connected
792 components is as from strongly_connected_components().
793 For the inverse, see "strongly_connected_component_by_vertex".
795 For undirected graphs, see "weakly_connected_component_by_index".
797 same_strongly_connected_components
799 $g->same_strongly_connected_components($u, $v, ...)
800 For a directed graph, return true if the vertices are in the same
802 strongly connected component.
803 See also "same_weakly_connected_components".
805 For undirected graphs, see "same_connected_components" or
807 "same_biconnected_components".
808 strong_connectivity_clear_cache
810 $g->strong_connectivity_clear_cache
811 See "Clearing cached results".
813 weakly_connected
815 is_weakly_connected
816 $g->is_weakly_connected
817 For a directed graph, return true is the directed graph is weakly
819 connected, false if not.
820 Weakly connected graph is also known as semiconnected graph.
822 See also "is_strongly_connected".
824 For undirected graphs, see "is_connected" or "is_biconnected".
826 weakly_connected_components
828 @wcc = $g->weakly_connected_components()
829 For a directed graph, returns the vertices of the weakly connected
831 components of the graph as a list of anonymous arrays. The
832 ordering of the anonymous arrays or the ordering of the vertices
833 inside the anonymous arrays (the components) is undefined.
834 See also "strongly_connected_components".
836 For undirected graphs, see "connected_components" or
838 "biconnected_components".
839 weakly_connected_component_by_vertex
841 $i = $g->weakly_connected_component_by_vertex($v)
842 For a directed graph, return an index identifying the weakly
844 connected component the vertex belongs to, the indexing starting
845 from zero.
846 For the inverse, see "weakly_connected_component_by_index".
848 For undirected graphs, see "connected_component_by_vertex" and
850 "biconnected_component_by_vertex".
851 weakly_connected_component_by_index
853 @v = $g->weakly_connected_component_by_index($i)
854 For a directed graph, return the vertices of the ith weakly
856 connected component, the indexing starting zero. The order of
857 vertices within a component is undefined, while the order of the
858 weakly connected components is same as from
859 weakly_connected_components().
860 For the inverse, see "weakly_connected_component_by_vertex".
862 For undirected graphs, see connected_component_by_index and
864 biconnected_component_by_index.
865 same_weakly_connected_components
867 $g->same_weakly_connected_components($u, $v, ...)
868 Return true if the vertices are in the same weakly connected
870 component.
871 weakly_connected_graph
873 $wcg = $g->weakly_connected_graph
874 For a directed graph, return its weakly connected graph.
876 For undirected graphs, see "connected_graph" and
878 "biconnected_graph".
879 strongly_connected_components
881 my @scc = $g->strongly_connected_components;
882 For a directed graph, return the strongly connected components as a
884 list of anonymous arrays. The elements in the anonymous arrays are
885 the vertices belonging to the strongly connected component; both
886 the elements and the components are in no particular order.
887 Note that strongly connected components can have single-element
889 components even without self-loops: if a vertex is any of isolated,
890 sink, or a source, the vertex is alone in its own strong component.
891 See also "weakly_connected_components".
893 For undirected graphs, see "connected_components", or see
895 "biconnected_components".
896 strongly_connected_graph
898 my $scg = $g->strongly_connected_graph;
899 See "Connected Graphs and Their Components" for further discussion.
901 Strongly connected graphs are also known as kernel graphs.
903 See also "weakly_connected_graph".
905 For undirected graphs, see "connected_graph", or
907 "biconnected_graph".
908 is_sink_vertex
910 $g->is_sink_vertex($v)
911 Return true if the vertex $v is a sink vertex, false if not. A
913 sink vertex is defined as a vertex with predecessors but no
914 successors: this definition means that isolated vertices are not
915 sink vertices. If you want also isolated vertices, use
916 is_successorless_vertex().
917 is_source_vertex
919 $g->is_source_vertex($v)
920 Return true if the vertex $v is a source vertex, false if not. A
922 source vertex is defined as a vertex with successors but no
923 predecessors: the definition means that isolated vertices are not
924 source vertices. If you want also isolated vertices, use
925 is_predecessorless_vertex().
926 is_successorless_vertex
928 $g->is_successorless_vertex($v)
929 Return true if the vertex $v has no successors (no edges leaving
931 the vertex), false if it has.
932 Isolated vertices will return true: if you do not want this, use
934 is_sink_vertex().
935 is_successorful_vertex
937 $g->is_successorful_vertex($v)
938 Return true if the vertex $v has successors, false if not.
940 is_predecessorless_vertex
942 $g->is_predecessorless_vertex($v)
943 Return true if the vertex $v has no predecessors (no edges entering
945 the vertex), false if it has.
946 Isolated vertices will return true: if you do not want this, use
948 is_source_vertex().
949 is_predecessorful_vertex
951 $g->is_predecessorful_vertex($v)
952 Return true if the vertex $v has predecessors, false if not.
954 is_isolated_vertex
956 $g->is_isolated_vertex($v)
957 Return true if the vertex $v is an isolated vertex: no successors
959 and no predecessors.
960 is_interior_vertex
962 $g->is_interior_vertex($v)
963 Return true if the vertex $v is an interior vertex: both successors
965 and predecessors.
966 is_exterior_vertex
968 $g->is_exterior_vertex($v)
969 Return true if the vertex $v is an exterior vertex: has either no
971 successors or no predecessors, or neither.
972 is_self_loop_vertex
974 $g->is_self_loop_vertex($v)
975 Return true if the vertex $v is a self loop vertex: has an edge
977 from itself to itself.
978 sink_vertices
980 @v = $g->sink_vertices()
981 Return the sink vertices of the graph. In scalar context return
983 the number of sink vertices. See "is_sink_vertex" for the
984 definition of a sink vertex.
985 source_vertices
987 @v = $g->source_vertices()
988 Return the source vertices of the graph. In scalar context return
990 the number of source vertices. See "is_source_vertex" for the
991 definition of a source vertex.
992 successorful_vertices
994 @v = $g->successorful_vertices()
995 Return the successorful vertices of the graph. In scalar context
997 return the number of successorful vertices.
998 successorless_vertices
1000 @v = $g->successorless_vertices()
1001 Return the successorless vertices of the graph. In scalar context
1003 return the number of successorless vertices.
1004 successors
1006 @s = $g->successors($v)
1007 Return the immediate successor vertices of the vertex.
1009 See also "all_successors", "all_neighbours", and "all_reachable".
1011 all_successors
1013 @s = $g->all_successors(@v)
1014 For a directed graph, returns all successor vertices of the
1016 argument vertices, recursively.
1017 For undirected graphs, see "all_neighbours" and "all_reachable".
1019 See also "successors", "successors_by_radius".
1021 successors_by_radius
1023 @s = $g->successors_by_radius(@v, $radius)
1024 For a directed graph, returns all successor vertices of the
1026 argument vertices, recursively.
1027 For undirected graphs, see "all_neighbours" and "all_reachable".
1029 See also "successors", "successors_by_radius".
1031 neighbors
1033 neighbours
1034 @n = $g->neighbours($v)
1035 Return the neighboring/neighbouring vertices. Also known as the
1037 adjacent vertices.
1038 See also "all_neighbours" "all_reachable", and
1040 "neighbours_by_radius".
1041 all_neighbors
1043 all_neighbours
1044 @n = $g->all_neighbours(@v)
1045 Return the neighboring/neighbouring vertices of the argument
1047 vertices, recursively. For a directed graph, recurses up
1048 predecessors and down successors. For an undirected graph, returns
1049 all the vertices reachable from the argument vertices: equivalent
1050 to "all_reachable".
1051 See also "neighbours", "all_reachable", and "neighbours_by_radius".
1053 neighbors_by_radius
1055 neighbours_by_radius
1056 @n = $g->neighbours_by_radius(@v, $radius)
1057 Return the neighboring/neighbouring vertices of the argument
1059 vertices, recursively, out to the given radius.
1060 all_reachable
1062 @r = $g->all_reachable(@v)
1063 Return all the vertices reachable from the argument vertices,
1065 recursively. For a directed graph, equivalent to "all_successors".
1066 For an undirected graph, equivalent to "all_neighbours". The
1067 argument vertices are not included in the results unless there are
1068 explicit self-loops.
1069 See also "neighbours", "all_neighbours", "all_successors", and
1071 "reachable_by_radius".
1072 reachable_by_radius
1074 @r = $g->reachable_by_radius(@v, $radius)
1075 Return all the vertices reachable from the argument vertices,
1077 recursively, out to the given radius.
1078 predecessorful_vertices
1080 @v = $g->predecessorful_vertices()
1081 Return the predecessorful vertices of the graph. In scalar context
1083 return the number of predecessorful vertices.
1084 predecessorless_vertices
1086 @v = $g->predecessorless_vertices()
1087 Return the predecessorless vertices of the graph. In scalar
1089 context return the number of predecessorless vertices.
1090 predecessors
1092 @p = $g->predecessors($v)
1093 Return the immediate predecessor vertices of the vertex.
1095 See also "all_predecessors", "all_neighbours", and "all_reachable".
1097 all_predecessors
1099 @p = $g->all_predecessors(@v)
1100 For a directed graph, returns all predecessor vertices of the
1102 argument vertices, recursively.
1103 For undirected graphs, see "all_neighbours" and "all_reachable".
1105 See also "predecessors", "predecessors_by_radius".
1107 predecessors_by_radius
1109 @p = $g->predecessors_by_radius(@v, $radius)
1110 For a directed graph, returns all predecessor vertices of the
1112 argument vertices, recursively, out to the given radius.
1113 isolated_vertices
1115 @v = $g->isolated_vertices()
1116 Return the isolated vertices of the graph. In scalar context
1118 return the number of isolated vertices. See "is_isolated_vertex"
1119 for the definition of an isolated vertex.
1120 interior_vertices
1122 @v = $g->interior_vertices()
1123 Return the interior vertices of the graph. In scalar context
1125 return the number of interior vertices. See "is_interior_vertex"
1126 for the definition of an interior vertex.
1127 exterior_vertices
1129 @v = $g->exterior_vertices()
1130 Return the exterior vertices of the graph. In scalar context
1132 return the number of exterior vertices. See "is_exterior_vertex"
1133 for the definition of an exterior vertex.
1134 self_loop_vertices
1136 @v = $g->self_loop_vertices()
1137 Return the self-loop vertices of the graph. In scalar context
1139 return the number of self-loop vertices. See "is_self_loop_vertex"
1140 for the definition of a self-loop vertex.
1141 as_hashes
1143 ($nodes, $edges) = $g->as_hashes
1144 Return hash-refs which map vertices to their attributes, and for
1146 edges, a two-level hash mapping the predecessor to its successors,
1147 mapped to the attributes.
1148 If "multivertexed" is true, the vertices hash will have the second-
1150 level values be the multivertex's ID, and the third level will be
1151 attributes as above.
1152 If "multiedged" is true, similar will be true for the edges hash.
1154 For a hypergraph, the edges will instead be an array-ref of hashes
1156 with a key of "attributes", value a hash-ref (if "multiedged", two-
1157 level as above). Then with values of array-refs of vertex-names,
1158 for undirected:
1159 vertices
1161 Connected Graphs and Their Components
1163 In this discussion connected graph refers to any of connected graphs,
1164 biconnected graphs, and strongly connected graphs.
1165 NOTE: if the vertices of the original graph are Perl objects, (in other
1167 words, references, so you must be using "refvertexed") the vertices of
1168 the connected graph are NOT by default usable as Perl objects because
1169 they are blessed into a package with a rather unusable name.
1170 By default, the vertex names of the connected graph are formed from the
1172 names of the vertices of the original graph by (alphabetically sorting
1173 them and) concatenating their names with "+". The vertex attribute
1174 "subvertices" is also used to store the list (as an array reference) of
1175 the original vertices. To change the 'supercomponent' vertex names and
1176 the whole logic of forming these supercomponents use the
1177 "super_component") option to the method calls:
1178 $g->connected_graph(super_component => sub { ... })
1180 $g->biconnected_graph(super_component => sub { ... })
1181 $g->strongly_connected_graph(super_component => sub { ... })
1182 The subroutine reference gets the 'subcomponents' (the vertices of the
1184 original graph) as arguments, and it is supposed to return the new
1185 supercomponent vertex, the "stringified" form of which is used as the
1186 vertex name.
1187 Degree
1189 A vertex has a degree based on the number of incoming and outgoing
1190 edges. This really makes sense only for directed graphs.
1191 degree
1193 vertex_degree
1194 $d = $g->degree($v)
1195 $d = $g->vertex_degree($v)
1196 For directed graphs: the in-degree minus the out-degree at the
1198 vertex.
1199 For undirected graphs: the number of edges at the vertex
1201 (identical to "in_degree()", "out_degree()").
1202 in_degree
1204 $d = $g->in_degree($v)
1205 For directed graphs: the number of incoming edges at the vertex.
1207 For undirected graphs: the number of edges at the vertex (identical
1209 to "out_degree()", "degree()", "vertex_degree()").
1210 out_degree
1212 $o = $g->out_degree($v)
1213 For directed graphs: The number of outgoing edges at the vertex.
1215 For undirected graphs: the number of edges at the vertex (identical
1217 to "in_degree()", "degree()", "vertex_degree()").
1218 average_degree
1220 my $ad = $g->average_degree;
1221 Return the average degree (as in "degree()" or "vertex_degree()")
1223 taken over all vertices.
1224 Related methods are
1226 edges_at
1228 @e = $g->edges_at($v)
1229 The union of edges from, and edges to, the vertex.
1231 edges_from
1233 @e = $g->edges_from($v)
1234 The edges leaving the vertex.
1236 edges_to
1238 @e = $g->edges_to($v)
1239 The edges entering the vertex.
1241 See also "average_degree".
1243 Counted Vertices
1245 Counted vertices are vertices with more than one instance, normally
1246 adding vertices is idempotent. To enable counted vertices on a graph,
1247 give the "countvertexed" parameter a true value
1248 use Graph;
1250 my $g = Graph->new(countvertexed => 1);
1251 To find out how many times the vertex has been added:
1253 get_vertex_count
1255 my $c = $g->get_vertex_count($v);
1256 Return the count of the vertex, or undef if the vertex does not
1258 exist.
1259 Multiedges, Multivertices, Multigraphs
1261 Multiedges are edges with more than one "life", meaning that one has to
1262 delete them as many times as they have been added. Normally adding
1263 edges is idempotent (in other words, adding edges more than once makes
1264 no difference).
1265 There are two kinds or degrees of creating multiedges and
1267 multivertices. The two kinds are mutually exclusive.
1268 The weaker kind is called counted, in which the edge or vertex has a
1270 count on it: add operations increase the count, and delete operations
1271 decrease the count, and once the count goes to zero, the edge or vertex
1272 is deleted. If there are attributes, they all are attached to the same
1273 vertex. You can think of this as the graph elements being refcounted,
1274 or reference counted, if that sounds more familiar.
1275 The stronger kind is called (true) multi, in which the edge or vertex
1277 really has multiple separate identities, so that you can for example
1278 attach different attributes to different instances.
1279 To enable multiedges on a graph:
1281 use Graph;
1283 my $g0 = Graph->new(countedged => 1);
1284 my $g0 = Graph->new(multiedged => 1);
1285 Similarly for vertices
1287 use Graph;
1289 my $g1 = Graph->new(countvertexed => 1);
1290 my $g1 = Graph->new(multivertexed => 1);
1291 You can test for these by
1293 is_countedged
1295 countedged
1296 $g->is_countedged
1297 $g->countedged
1298 Return true if the graph is countedged.
1300 is_countvertexed
1302 countvertexed
1303 $g->is_countvertexed
1304 $g->countvertexed
1305 Return true if the graph is countvertexed.
1307 is_multiedged
1309 multiedged
1310 $g->is_multiedged
1311 $g->multiedged
1312 Return true if the graph is multiedged.
1314 is_multivertexed
1316 multivertexed
1317 $g->is_multivertexed
1318 $g->multivertexed
1319 Return true if the graph is multivertexed.
1321 A multiedged (either the weak kind or the strong kind) graph is a
1323 multigraph, for which you can test with "is_multi_graph()".
1324 NOTE: The various graph algorithms do not in general work well with
1326 multigraphs (they often assume simple graphs, that is, no multiedges or
1327 loops), and no effort has been made to test the algorithms with
1328 multigraphs.
1329 vertices() and edges() will return the multiple elements: if you want
1331 just the unique elements, use
1332 unique_vertices
1334 unique_edges
1335 @uv = $g->unique_vertices; # unique
1336 @mv = $g->vertices; # possible multiples
1337 @ue = $g->unique_edges;
1338 @me = $g->edges;
1339 If you are using (the stronger kind of) multielements, you should use
1341 the by_id variants:
1342 add_vertex_by_id
1344 has_vertex_by_id
1345 delete_vertex_by_id
1346 add_edge_by_id
1347 has_edge_by_id
1348 delete_edge_by_id
1349 $g->add_vertex_by_id($v, $id)
1351 $g->has_vertex_by_id($v, $id)
1352 $g->delete_vertex_by_id($v, $id)
1353 $g->add_edge_by_id($u, $v, $id)
1355 $g->has_edge_by_id($u, $v, $id)
1356 $g->delete_edge_by_id($u, $v, $id)
1357 These interfaces only apply to multivertices and multiedges. When you
1359 delete the last vertex/edge in a multivertex/edge, the whole
1360 vertex/edge is deleted. You can use add_vertex()/add_edge() on a
1361 multivertex/multiedge graph, in which case an id is generated
1362 automatically. To find out which the generated id was, you need to use
1363 add_vertex_get_id
1365 add_edge_get_id
1366 $idv = $g->add_vertex_get_id($v)
1368 $ide = $g->add_edge_get_id($u, $v)
1369 To return all the ids of vertices/edges in a multivertex/multiedge, use
1371 get_multivertex_ids
1373 get_multiedge_ids
1374 $g->get_multivertex_ids($v)
1376 $g->get_multiedge_ids($u, $v)
1377 The ids are returned in random order.
1379 To find out how many times the edge has been added (this works for
1381 either kind of multiedges):
1382 get_edge_count
1384 my $c = $g->get_edge_count($u, $v);
1385 Return the count (the "countedness") of the edge, or undef if the
1387 edge does not exist.
1388 The following multi-entity utility functions exist, mirroring the non-
1390 multi vertices and edges:
1391 add_weighted_edge_by_id
1393 add_weighted_edges_by_id
1394 add_weighted_path_by_id
1395 add_weighted_vertex_by_id
1396 add_weighted_vertices_by_id
1397 delete_edge_weight_by_id
1398 delete_vertex_weight_by_id
1399 get_edge_weight_by_id
1400 get_vertex_weight_by_id
1401 has_edge_weight_by_id
1402 has_vertex_weight_by_id
1403 set_edge_weight_by_id
1404 set_vertex_weight_by_id
1405 Topological Sort
1407 topological_sort
1408 toposort
1409 my @ts = $g->topological_sort;
1410 Return the vertices of the graph sorted topologically. Note that
1412 there may be several possible topological orderings; one of them is
1413 returned.
1414 If the graph contains a cycle, a fatal error is thrown, you can
1416 either use "eval" to trap that, or supply the "empty_if_cyclic"
1417 argument with a true value
1418 my @ts = $g->topological_sort(empty_if_cyclic => 1);
1420 in which case an empty array is returned if the graph is cyclic.
1422 Minimum Spanning Trees (MST)
1424 Minimum Spanning Trees or MSTs are tree subgraphs derived from an
1425 undirected graph. MSTs "span the graph" (covering all the vertices)
1426 using as lightly weighted (hence the "minimum") edges as possible.
1427 MST_Kruskal
1429 $mstg = $g->MST_Kruskal;
1430 Returns the Kruskal MST of the graph.
1432 MST_Prim
1434 $mstg = $g->MST_Prim(%opt);
1435 Returns the Prim MST of the graph.
1437 You can choose the first vertex with $opt{ first_root }.
1439 MST_Dijkstra
1441 minimum_spanning_tree
1442 $mstg = $g->MST_Dijkstra;
1443 $mstg = $g->minimum_spanning_tree;
1444 Aliases for MST_Prim.
1446 Single-Source Shortest Paths (SSSP)
1448 Single-source shortest paths, also known as Shortest Path Trees (SPTs).
1449 For either a directed or an undirected graph, return a (tree) subgraph
1450 that from a single start vertex (the "single source") travels the
1451 shortest possible paths (the paths with the lightest weights) to all
1452 the other vertices. Note that the SSSP is neither reflexive (the
1453 shortest paths do not include the zero-length path from the source
1454 vertex to the source vertex) nor transitive (the shortest paths do not
1455 include transitive closure paths). If no weight is defined for an
1456 edge, 1 (one) is assumed.
1457 SPT_Dijkstra
1459 $sptg = $g->SPT_Dijkstra($root)
1460 $sptg = $g->SPT_Dijkstra(%opt)
1461 Return as a graph the the single-source shortest paths of the graph
1463 using Dijkstra's algorithm. The graph cannot contain negative
1464 edges (negative edges cause the algorithm to abort with an error
1465 message "Graph::SPT_Dijkstra: edge ... is negative").
1466 You can choose the first vertex of the result with either a single
1468 vertex argument or with $opt{ first_root }, otherwise a random
1469 vertex is chosen.
1470 NOTE: note that all the vertices might not be reachable from the
1472 selected (explicit or random) start vertex.
1473 NOTE: after the first reachable tree from the first start vertex
1475 has been finished, and if there still are unvisited vertices,
1476 SPT_Dijkstra will keep on selecting unvisited vertices.
1477 The next roots (in case the first tree doesn't visit all the
1479 vertices) can be chosen by setting one of the following options to
1480 true: "next_root", "next_alphabetic", "next_numeric",
1481 "next_random".
1482 The "next_root" is the most customizable: the value needs to be a
1484 subroutine reference which will receive the graph and the unvisited
1485 vertices as hash reference. If you want to only visit the first
1486 tree, use "next_root =" sub { undef }>. The rest of these options
1487 are booleans. If none of them are true, a random unvisited vertex
1488 will be selected.
1489 The first start vertex is available as the graph attribute
1491 "SPT_Dijkstra_root").
1492 The result weights of vertices can be retrieved from the result
1494 graph by
1495 my $w = $sptg->get_vertex_attribute($v, 'weight');
1497 The predecessor vertex of a vertex in the result graph can be
1499 retrieved by
1500 my $u = $sptg->get_vertex_attribute($v, 'p');
1502 ("A successor vertex" cannot be retrieved as simply because a
1504 single vertex can have several successors. You can first find the
1505 "neighbors()" vertices and then remove the predecessor vertex.)
1506 If you want to find the shortest path between two vertices, see
1508 "SP_Dijkstra".
1509 SSSP_Dijkstra
1511 single_source_shortest_paths
1512 Aliases for SPT_Dijkstra.
1513 SP_Dijkstra
1515 @path = $g->SP_Dijkstra($u, $v)
1516 Return the vertices in the shortest path in the graph $g between
1518 the two vertices $u, $v. If no path can be found, an empty list is
1519 returned.
1520 Uses SPT_Dijkstra().
1522 SPT_Dijkstra_clear_cache
1524 $g->SPT_Dijkstra_clear_cache
1525 See "Clearing cached results".
1527 SPT_Bellman_Ford
1529 $sptg = $g->SPT_Bellman_Ford(%opt)
1530 Return as a graph the single-source shortest paths of the graph
1532 using Bellman-Ford's algorithm. The graph can contain negative
1533 edges but not negative cycles (negative cycles cause the algorithm
1534 to abort with an error message "Graph::SPT_Bellman_Ford: negative
1535 cycle exists").
1536 You can choose the start vertex of the result with either a single
1538 vertex argument or with $opt{ first_root }, otherwise a random
1539 vertex is chosen.
1540 NOTE: note that all the vertices might not be reachable from the
1542 selected (explicit or random) start vertex.
1543 The start vertex is available as the graph attribute
1545 "SPT_Bellman_Ford_root").
1546 The result weights of vertices can be retrieved from the result
1548 graph by
1549 my $w = $sptg->get_vertex_attribute($v, 'weight');
1551 The predecessor vertex of a vertex in the result graph can be
1553 retrieved by
1554 my $u = $sptg->get_vertex_attribute($v, 'p');
1556 ("A successor vertex" cannot be retrieved as simply because a
1558 single vertex can have several successors. You can first find the
1559 "neighbors()" vertices and then remove the predecessor vertex.)
1560 If you want to find the shortest path between two vertices, see
1562 "SP_Bellman_Ford".
1563 SSSP_Bellman_Ford
1565 Alias for SPT_Bellman_Ford.
1566 SP_Bellman_Ford
1568 @path = $g->SP_Bellman_Ford($u, $v)
1569 Return the vertices in the shortest path in the graph $g between
1571 the two vertices $u, $v. If no path can be found, an empty list is
1572 returned.
1573 Uses SPT_Bellman_Ford().
1575 SPT_Bellman_Ford_clear_cache
1577 $g->SPT_Bellman_Ford_clear_cache
1578 See "Clearing cached results".
1580 All-Pairs Shortest Paths (APSP)
1582 For either a directed or an undirected graph, return the APSP object
1583 describing all the possible paths between any two vertices of the
1584 graph. If no weight is defined for an edge, 1 (one) is assumed.
1585 Note that weight of 0 (zero) does not mean do not use this edge, it
1587 means essentially the opposite: an edge that has zero cost, an edge
1588 that makes the vertices the same.
1589 APSP_Floyd_Warshall
1591 all_pairs_shortest_paths
1592 my $apsp = $g->APSP_Floyd_Warshall(...);
1593 Return the all-pairs shortest path object computed from the graph
1595 using the Floyd-Warshall algorithm, of class
1596 Graph::TransitiveClosure.
1597 The length of a path between two vertices is the sum of weight
1599 attribute of the edges along the shortest path between the two
1600 vertices. If no weight attribute name is specified explicitly
1601 $g->APSP_Floyd_Warshall(attribute_name => 'height');
1603 the attribute "weight" is assumed.
1605 If an edge has no defined weight attribute, the value of one is
1607 assumed when getting the attribute.
1608 Once computed, you can query the APSP object with
1610 path_length
1612 my $l = $apsp->path_length($u, $v);
1613 Return the length of the shortest path between the two
1615 vertices.
1616 path_vertices
1618 my @v = $apsp->path_vertices($u, $v);
1619 Return the list of vertices along the shortest path.
1621 path_successor
1623 my $u = $apsp->path_successor($u, $v);
1624 Returns the successor of vertex $u in the all-pairs
1626 shortest path to $v.
1627 all_paths
1629 my @paths = $apsp->all_paths($u, $v);
1630 Return list of array-refs with all the paths from $u to $v.
1632 average_path_length
1634 my $apl = $g->average_path_length; # All vertex pairs.
1635 my $apl = $g->average_path_length($u); # From $u.
1637 my $apl = $g->average_path_length($u, undef); # From $u.
1638 my $apl = $g->average_path_length($u, $v); # From $u to $v.
1640 my $apl = $g->average_path_length(undef, $v); # To $v.
1642 Return the average (shortest) path length over all the non-
1644 zero paths between vertex pairs of the graph's transitive
1645 closure. Depending on the arguments, this can be from a
1646 vertex, between two vertices, or to a vertex. An undefined
1647 (or not-given) vertex will match all.
1648 longest_path
1650 my @lp = $g->longest_path;
1651 my $lp = $g->longest_path;
1652 In scalar context return the longest shortest path length
1654 over all the vertex pairs of the graph. In list context
1655 return the vertices along a longest shortest path. Note
1656 that there might be more than one such path; this interface
1657 returns a random one of them.
1658 NOTE: this returns the longest shortest path, not the
1660 longest path.
1661 diameter
1663 graph_diameter
1664 my $gd = $g->diameter;
1665 The longest path over all the vertex pairs is known as the
1667 graph diameter.
1668 For an unconnected graph, single-vertex, or empty graph,
1670 returns "undef".
1671 shortest_path
1673 my @sp = $g->shortest_path;
1674 my $sp = $g->shortest_path;
1675 In scalar context return the shortest length over all the
1677 vertex pairs of the graph. In list context return the
1678 vertices along a shortest path. Note that there might be
1679 more than one such path; this interface returns a random
1680 one of them.
1681 For an unconnected, single-vertex, or empty graph, returns
1683 "undef" or an empty list.
1684 radius
1686 my $gr = $g->radius;
1687 The shortest longest path over all the vertex pairs is
1689 known as the graph radius. See also "diameter".
1690 For an unconnected, single-vertex, or empty graph, returns
1692 Infinity.
1693 center_vertices
1695 centre_vertices
1696 my @c = $g->center_vertices;
1697 my @c = $g->center_vertices($delta);
1698 The graph center is the set of vertices for which the
1700 vertex eccentricity is equal to the graph radius. The
1701 vertices are returned in random order. By specifying a
1702 delta value you can widen the criterion from strict
1703 equality (handy for non-integer edge weights).
1704 For an unconnected, single-vertex, or empty graph, returns
1706 an empty list.
1707 vertex_eccentricity
1709 my $ve = $g->vertex_eccentricity($v);
1710 The longest path to a vertex is known as the vertex
1712 eccentricity.
1713 If the graph is unconnected, single-vertex, or empty graph,
1715 returns Inf.
1716 You can walk through the matrix of the shortest paths by using
1718 for_shortest_paths
1720 $n = $g->for_shortest_paths($callback)
1721 The number of shortest paths is returned (this should be equal
1723 to V*V). The $callback is a sub reference that receives four
1724 arguments: the transitive closure object from
1725 Graph::TransitiveClosure, the two vertices, and the index to
1726 the current shortest paths (0..V*V-1).
1727 Clearing cached results
1729 For many graph algorithms there are several different but equally valid
1730 results. (Pseudo)Randomness is used internally by the Graph module to
1731 for example pick a random starting vertex, and to select random edges
1732 from a vertex.
1733 For efficiency the computed result is often cached to avoid recomputing
1735 the potentially expensive operation, and this also gives additional
1736 determinism (once a correct result has been computed, the same result
1737 will always be given).
1738 However, sometimes the exact opposite is desirable, and the possible
1740 alternative results are wanted (within the limits of the
1741 pseudorandomness: not all the possible solutions are guaranteed to be
1742 returned, usually only a subset is returned). To undo the caching, the
1743 following methods are available:
1744 • connectivity_clear_cache
1746 Affects "connected_components", "connected_component_by_vertex",
1748 "connected_component_by_index", "same_connected_components",
1749 "connected_graph", "is_connected", "is_weakly_connected",
1750 "weakly_connected_components",
1751 "weakly_connected_component_by_vertex",
1752 "weakly_connected_component_by_index",
1753 "same_weakly_connected_components", "weakly_connected_graph".
1754 • biconnectivity_clear_cache
1756 Affects "biconnected_components",
1758 "biconnected_component_by_vertex",
1759 "biconnected_component_by_index", "is_edge_connected",
1760 "is_edge_separable", "articulation_points", "cut_vertices",
1761 "is_biconnected", "biconnected_graph",
1762 "same_biconnected_components", "bridges".
1763 • strong_connectivity_clear_cache
1765 Affects "strongly_connected_components",
1767 "strongly_connected_component_by_vertex",
1768 "strongly_connected_component_by_index",
1769 "same_strongly_connected_components", "is_strongly_connected",
1770 "strongly_connected", "strongly_connected_graph".
1771 • SPT_Dijkstra_clear_cache
1773 Affects "SPT_Dijkstra", "SSSP_Dijkstra",
1775 "single_source_shortest_paths", "SP_Dijkstra".
1776 • SPT_Bellman_Ford_clear_cache
1778 Affects "SPT_Bellman_Ford", "SSSP_Bellman_Ford", "SP_Bellman_Ford".
1780 Note that any such computed and cached results are of course always
1782 automatically discarded whenever the graph is modified.
1783 Random
1785 You can either ask for random elements of existing graphs or create
1786 random graphs.
1787 random_vertex
1789 my $v = $g->random_vertex;
1790 Return a random vertex of the graph, or undef if there are no
1792 vertices.
1793 random_edge
1795 my $e = $g->random_edge;
1796 Return a random edge of the graph as an array reference having the
1798 vertices as elements, or undef if there are no edges.
1799 random_successor
1801 my $v = $g->random_successor($v);
1802 Return a random successor of the vertex in the graph, or undef if
1804 there are no successors.
1805 random_predecessor
1807 my $u = $g->random_predecessor($v);
1808 Return a random predecessor of the vertex in the graph, or undef if
1810 there are no predecessors.
1811 random_graph
1813 my $g = Graph->random_graph(%opt);
1814 Construct a random graph. The %opt must contain the "vertices"
1816 argument
1817 vertices => vertices_def
1819 where the vertices_def is one of
1821 • an array reference where the elements of the array
1823 reference are the vertices
1824 • a number N in which case the vertices will be integers
1826 0..N-1
1827 The %opt may have either of the argument "edges" or the argument
1829 "edges_fill". Both are used to define how many random edges to add to
1830 the graph; "edges" is an absolute number, while "edges_fill" is a
1831 relative number (relative to the number of edges in a complete graph,
1832 C). The number of edges can be larger than C, but only if the graph is
1833 countedged. The random edges will not include self-loops. If neither
1834 "edges" nor "edges_fill" is specified, an "edges_fill" of 0.5 is
1835 assumed.
1836 If you want repeatable randomness (what is an oxymoron?) you can use
1838 the "random_seed" option:
1839 $g = Graph->random_graph(vertices => 10, random_seed => 1234);
1841 As this uses the standard Perl srand(), the usual caveat applies: use
1843 it sparingly, and consider instead using a single srand() call at the
1844 top level of your application.
1845 The default random distribution of edges is flat, that is, any pair of
1847 vertices is equally likely to appear. To define your own distribution,
1848 use the "random_edge" option:
1849 $g = Graph->random_graph(vertices => 10, random_edge => \&d);
1851 where "d" is a code reference receiving ($g, $u, $v, $p) as parameters,
1853 where the $g is the random graph, $u and $v are the vertices, and the
1854 $p is the probability ([0,1]) for a flat distribution. It must return
1855 a probability ([0,1]) that the vertices $u and $v have an edge between
1856 them. Note that returning one for a particular pair of vertices
1857 doesn't guarantee that the edge will be present in the resulting graph
1858 because the required number of edges might be reached before that
1859 particular pair is tested for the possibility of an edge. Be very
1860 careful to adjust also "edges" or "edges_fill" so that there is a
1861 possibility of the filling process terminating.
1862 NOTE: a known problem with randomness in openbsd pre-perl-5.20 is that
1864 using a seed does not give you deterministic randomness. This affects
1865 any Perl code, not just Graph.
1866 Attributes
1868 You can attach free-form attributes (key-value pairs, in effect a full
1869 Perl hash) to each vertex, edge, and the graph itself.
1870 Note that attaching attributes does slow down some other operations on
1872 the graph by a factor of three to ten. For example adding edge
1873 attributes does slow down anything that walks through all the edges.
1874 For vertex attributes:
1876 set_vertex_attribute
1878 $g->set_vertex_attribute($v, $name, $value)
1879 Set the named vertex attribute.
1881 If the vertex does not exist, the set_...() will create it, and the
1883 other vertex attribute methods will return false or empty.
1884 NOTE: any attributes beginning with an underscore/underline (_) are
1886 reserved for the internal use of the Graph module.
1887 get_vertex_attribute
1889 $value = $g->get_vertex_attribute($v, $name)
1890 Return the named vertex attribute.
1892 has_vertex_attribute
1894 $g->has_vertex_attribute($v, $name)
1895 Return true if the vertex has an attribute, false if not.
1897 delete_vertex_attribute
1899 $g->delete_vertex_attribute($v, $name)
1900 Delete the named vertex attribute.
1902 set_vertex_attributes
1904 $g->set_vertex_attributes($v, $attr)
1905 Set all the attributes of the vertex from the anonymous hash $attr.
1907 NOTE: any attributes beginning with an underscore ("_") are
1909 reserved for the internal use of the Graph module.
1910 get_vertex_attributes
1912 $attr = $g->get_vertex_attributes($v)
1913 Return all the attributes of the vertex as an anonymous hash, or
1915 "undef" if no such vertex.
1916 get_vertex_attribute_names
1918 @name = $g->get_vertex_attribute_names($v)
1919 Return the names of vertex attributes.
1921 get_vertex_attribute_values
1923 @value = $g->get_vertex_attribute_values($v)
1924 Return the values of vertex attributes.
1926 has_vertex_attributes
1928 $g->has_vertex_attributes($v)
1929 Return true if the vertex has any attributes, false if not.
1931 delete_vertex_attributes
1933 $g->delete_vertex_attributes($v)
1934 Delete all the attributes of the named vertex.
1936 If you are using multivertices, use the by_id variants:
1938 set_vertex_attribute_by_id
1940 get_vertex_attribute_by_id
1941 has_vertex_attribute_by_id
1942 delete_vertex_attribute_by_id
1943 set_vertex_attributes_by_id
1944 get_vertex_attributes_by_id
1945 get_vertex_attribute_names_by_id
1946 get_vertex_attribute_values_by_id
1947 has_vertex_attributes_by_id
1948 delete_vertex_attributes_by_id
1949 $g->set_vertex_attribute_by_id($v, $id, $name, $value)
1950 $g->get_vertex_attribute_by_id($v, $id, $name)
1951 $g->has_vertex_attribute_by_id($v, $id, $name)
1952 $g->delete_vertex_attribute_by_id($v, $id, $name)
1953 $g->set_vertex_attributes_by_id($v, $id, $attr)
1954 $g->get_vertex_attributes_by_id($v, $id)
1955 $g->get_vertex_attribute_values_by_id($v, $id)
1956 $g->get_vertex_attribute_names_by_id($v, $id)
1957 $g->has_vertex_attributes_by_id($v, $id)
1958 $g->delete_vertex_attributes_by_id($v, $id)
1959 For edge attributes:
1961 set_edge_attribute
1963 $g->set_edge_attribute($u, $v, $name, $value)
1964 Set the named edge attribute.
1966 If the edge does not exist, the set_...() will create it, and the
1968 other edge attribute methods will return false or empty.
1969 NOTE: any attributes beginning with an underscore ("_") are
1971 reserved for the internal use of the Graph module.
1972 get_edge_attribute
1974 $value = $g->get_edge_attribute($u, $v, $name)
1975 Return the named edge attribute.
1977 has_edge_attribute
1979 $g->has_edge_attribute($u, $v, $name)
1980 Return true if the edge has an attribute, false if not.
1982 delete_edge_attribute
1984 $g->delete_edge_attribute($u, $v, $name)
1985 Delete the named edge attribute.
1987 set_edge_attributes
1989 $g->set_edge_attributes($u, $v, $attr)
1990 Set all the attributes of the edge from the anonymous hash $attr.
1992 NOTE: any attributes beginning with an underscore ("_") are
1994 reserved for the internal use of the Graph module.
1995 get_edge_attributes
1997 $attr = $g->get_edge_attributes($u, $v)
1998 Return all the attributes of the edge as an anonymous hash, or
2000 "undef" if no such edge.
2001 get_edge_attribute_names
2003 @name = $g->get_edge_attribute_names($u, $v)
2004 Return the names of edge attributes.
2006 get_edge_attribute_values
2008 @value = $g->get_edge_attribute_values($u, $v)
2009 Return the values of edge attributes.
2011 has_edge_attributes
2013 $g->has_edge_attributes($u, $v)
2014 Return true if the edge has any attributes, false if not.
2016 delete_edge_attributes
2018 $g->delete_edge_attributes($u, $v)
2019 Delete all the attributes of the named edge.
2021 If you are using multiedges, use the by_id variants:
2023 set_edge_attribute_by_id
2025 get_edge_attribute_by_id
2026 has_edge_attribute_by_id
2027 delete_edge_attribute_by_id
2028 set_edge_attributes_by_id
2029 get_edge_attributes_by_id
2030 get_edge_attribute_names_by_id
2031 get_edge_attribute_values_by_id
2032 has_edge_attributes_by_id
2033 delete_edge_attributes_by_id
2034 $g->set_edge_attribute_by_id($u, $v, $id, $name, $value)
2035 $g->get_edge_attribute_by_id($u, $v, $id, $name)
2036 $g->has_edge_attribute_by_id($u, $v, $id, $name)
2037 $g->delete_edge_attribute_by_id($u, $v, $id, $name)
2038 $g->set_edge_attributes_by_id($u, $v, $id, $attr)
2039 $g->get_edge_attributes_by_id($u, $v, $id)
2040 $g->get_edge_attribute_values_by_id($u, $v, $id)
2041 $g->get_edge_attribute_names_by_id($u, $v, $id)
2042 $g->has_edge_attributes_by_id($u, $v, $id)
2043 $g->delete_edge_attributes_by_id($u, $v, $id)
2044 For graph attributes:
2046 set_graph_attribute
2048 $g->set_graph_attribute($name, $value)
2049 Set the named graph attribute.
2051 NOTE: any attributes beginning with an underscore ("_") are
2053 reserved for the internal use of the Graph module.
2054 get_graph_attribute
2056 $value = $g->get_graph_attribute($name)
2057 Return the named graph attribute.
2059 has_graph_attribute
2061 $g->has_graph_attribute($name)
2062 Return true if the graph has an attribute, false if not.
2064 delete_graph_attribute
2066 $g->delete_graph_attribute($name)
2067 Delete the named graph attribute.
2069 set_graph_attributes
2071 $g->get_graph_attributes($attr)
2072 Set all the attributes of the graph from the anonymous hash $attr.
2074 NOTE: any attributes beginning with an underscore ("_") are
2076 reserved for the internal use of the Graph module.
2077 get_graph_attributes
2079 $attr = $g->get_graph_attributes()
2080 Return all the attributes of the graph as an anonymous hash.
2082 get_graph_attribute_names
2084 @name = $g->get_graph_attribute_names()
2085 Return the names of graph attributes.
2087 get_graph_attribute_values
2089 @value = $g->get_graph_attribute_values()
2090 Return the values of graph attributes.
2092 has_graph_attributes
2094 $g->has_graph_attributes()
2095 Return true if the graph has any attributes, false if not.
2097 delete_graph_attributes
2099 $g->delete_graph_attributes()
2100 Delete all the attributes of the named graph.
2102 Weighted
2104 As convenient shortcuts the following methods add, query, and
2105 manipulate the attribute "weight" with the specified value to the
2106 respective Graph elements.
2107 add_weighted_edge
2109 $g->add_weighted_edge($u, $v, $weight)
2110 add_weighted_edges
2112 $g->add_weighted_edges($u1, $v1, $weight1, ...)
2113 add_weighted_path
2115 $g->add_weighted_path($v1, $weight1, $v2, $weight2, $v3, ...)
2116 add_weighted_vertex
2118 $g->add_weighted_vertex($v, $weight)
2119 add_weighted_vertices
2121 $g->add_weighted_vertices($v1, $weight1, $v2, $weight2, ...)
2122 delete_edge_weight
2124 $g->delete_edge_weight($u, $v)
2125 delete_vertex_weight
2127 $g->delete_vertex_weight($v)
2128 get_edge_weight
2130 $g->get_edge_weight($u, $v)
2131 get_vertex_weight
2133 $g->get_vertex_weight($v)
2134 has_edge_weight
2136 $g->has_edge_weight($u, $v)
2137 has_vertex_weight
2139 $g->has_vertex_weight($v)
2140 set_edge_weight
2142 $g->set_edge_weight($u, $v, $weight)
2143 set_vertex_weight
2145 $g->set_vertex_weight($v, $weight)
2146 Isomorphism
2148 Two graphs being isomorphic means that they are structurally the same
2149 graph, the difference being that the vertices might have been renamed
2150 or substituted. For example in the below example $g0 and $g1 are
2151 isomorphic: the vertices "b c d" have been renamed as "z x y".
2152 $g0 = Graph->new;
2154 $g0->add_edges(qw(a b a c c d));
2155 $g1 = Graph->new;
2156 $g1->add_edges(qw(a x x y a z));
2157 In the general case determining isomorphism is NP-hard, in other words,
2159 really hard (time-consuming), no other ways of solving the problem are
2160 known than brute force check of of all the possibilities (with possible
2161 optimization tricks, of course, but brute force still rules at the end
2162 of the day).
2163 A very rough guess at whether two graphs could be isomorphic is
2165 possible via the method
2166 could_be_isomorphic
2168 $g0->could_be_isomorphic($g1)
2169 If the graphs do not have the same number of vertices and edges, false
2171 is returned. If the distribution of in-degrees and out-degrees at the
2172 vertices of the graphs does not match, false is returned. Otherwise,
2173 true is returned.
2174 What is actually returned is the maximum number of possible isomorphic
2176 graphs between the two graphs, after the above sanity checks have been
2177 conducted. It is basically the product of the factorials of the
2178 absolute values of in-degrees and out-degree pairs at each vertex, with
2179 the isolated vertices ignored (since they could be reshuffled and
2180 renamed arbitrarily). Note that for large graphs the product of these
2181 factorials can overflow the maximum presentable number (the floating
2182 point number) in your computer (in Perl) and you might get for example
2183 Infinity as the result.
2184 Miscellaneous
2186 betweenness
2187 %b = $g->betweenness
2188 Returns a map of vertices to their Freeman's betweennesses:
2190 C_b(v) = \sum_{s \neq v \neq t \in V} \frac{\sigma_{s,t}(v)}{\sigma_{s,t}}
2192 It is described in:
2194 Freeman, A set of measures of centrality based on betweenness, http://arxiv.org/pdf/cond-mat/0309045
2196 and based on the algorithm from:
2198 "A Faster Algorithm for Betweenness Centrality"
2200 clustering_coefficient
2202 $gamma = $g->clustering_coefficient()
2203 ($gamma, %clustering) = $g->clustering_coefficient()
2204 Returns the clustering coefficient gamma as described in
2206 Duncan J. Watts and Steven Strogatz, Collective dynamics of 'small-world' networks, https://web.archive.org/web/20120616204225/http://audiophile.tam.cornell.edu/SS_nature_smallworld.pdf
2208 In scalar context returns just the average gamma, in list context
2210 returns the average gamma and a hash of vertices to clustering
2211 coefficients.
2212 Returns an empty list (and therefore undefined in scalar context)
2214 if the graph has no vertices.
2215 subgraph_by_radius
2217 $s = $g->subgraph_by_radius(@v, $radius);
2218 Returns a subgraph representing the ball of $radius around the
2220 given vertices (breadth-first search).
2221 The "expect" methods can be used to test a graph and croak if the graph
2223 call is not as expected.
2224 expect_acyclic
2226 expect_dag
2227 expect_directed
2228 expect_hyperedged
2229 expect_multiedge
2230 expect_multiedged
2231 expect_multivertex
2232 expect_multivertexed
2233 expect_no_args
2234 expect_non_multiedge
2235 expect_non_multiedged
2236 expect_non_multivertex
2237 expect_non_multivertexed
2238 expect_non_unionfind
2239 expect_undirected
2240 In many algorithms it is useful to have a value representing the
2242 infinity. The Graph provides (and itself uses):
2243 Infinity
2245 (Not exported, use Graph::Infinity explicitly)
2246 Size Requirements
2248 A graph takes up at least 1172 bytes of memory.
2249 A vertex takes up at least 100 bytes of memory.
2251 An edge takes up at least 400 bytes of memory.
2253 (A Perl scalar value takes 16 bytes, or 12 bytes if it's a reference.)
2255 These size approximations are very approximate and optimistic (they are
2257 based on total_size() of Devel::Size). In real life many factors
2258 affect these numbers, for example how Perl is configured. The numbers
2259 are for a 32-bit platform and for Perl 5.8.8.
2260 Roughly, the above numbers mean that in a megabyte of memory you can
2262 fit for example a graph of about 1000 vertices and about 2500 edges.
2263 Hyperedges, hypergraphs
2265 BEWARE: this is a rather thinly tested feature, and the theory is even
2266 less so. Do not expect this to stay as it is (or at all) in future
2267 releases.
2268 NOTE: most usual graph algorithms (and basic concepts) break horribly
2270 (or at least will look funny) with these hyperthingies. Caveat emptor.
2271 Hyperedges are edges that connect a number of vertices different from
2273 the usual two.
2274 Hypergraphs are graphs with hyperedges.
2276 To enable hyperness when constructing Graphs use the "hyperedged"
2278 attribute:
2279 my $h = Graph->new(hyperedged => 1);
2281 To test for hyperness of a graph use the
2283 is_hyperedged
2285 hyperedged
2286 $g->is_hyperedged
2287 $g->hyperedged
2288 For more information on directed hypergraphs, see Directed Hypergraphs
2290 and Applications
2291 <https://static.aminer.org/pdf/PDF/000/836/884/directed_hypergraphs_and_applications.pdf>.
2292 It defines hyperarcs (directed edges in a hypergraph) as ordered pairs
2293 of subsets of V, and hyperedges (undirected) as single subsets of V.
2294 Since sets are unordered and elements within them are unique, this
2295 implies that the only valuable use for hypergraphs is where in a given
2296 connection entity (edge or arc), each vertex only appears at most once.
2297 Additionally, how the "hyper" property of edges works may change. The
2298 underpinning notion is that each edge will be considered an entry in an
2299 incidence matrix (dimensions |V| x |E|), with values of either (0,
2300 1=participating) for undirected (hyperedges), or (-1=tail, 0, 1=head)
2301 for directed (hyperarcs) against each vertex.
2302 DIAGNOSTICS
2304 • Graph::...Map...: arguments X expected Y ...
2305 If you see these (more user-friendly error messages should have
2307 been triggered above and before these) please report any such
2308 occurrences, but in general you should be happy to see these since
2309 it means that an attempt to call something with a wrong number of
2310 arguments was caught in time.
2311 • Graph::add_edge: graph is not hyperedged ...
2313 Maybe you used add_weighted_edge() with only the two vertex
2315 arguments.
2316 • Not an ARRAY reference at lib/Graph.pm ...
2318 One possibility is that you have code based on Graph 0.2xxxx that
2320 assumes Graphs being blessed hash references, possibly also
2321 assuming that certain hash keys are available to use for your own
2322 purposes. In Graph 0.50 none of this is true. Please do not
2323 expect any particular internal implementation of Graphs. Use
2324 inheritance and graph/vertex/edge attributes instead.
2325 Another possibility is that you meant to have objects (blessed
2327 references) as graph vertices, but forgot to use "refvertexed" (see
2328 "refvertexed") when creating the graph.
2329
2331 All bad terminology, bugs, and inefficiencies are naturally mine, all
2332 mine, and not the fault of the below.
2333 Thanks to Nathan Goodman and Andras Salamon for bravely betatesting my
2335 pre-0.50 code. If they missed something, that was only because of my
2336 fiendish code.
2337 The following literature for algorithms and some test cases:
2339 • Algorithms in C, Third Edition, Part 5, Graph Algorithms, Robert
2341 Sedgewick, Addison Wesley
2342 • Introduction to Algorithms, First Edition, Cormen-Leiserson-Rivest,
2344 McGraw Hill
2345 • Graphs, Networks and Algorithms, Dieter Jungnickel, Springer
2347
2349 Persistent/Serialized graphs? You want to read/write Graphs? See the
2350 Graph::Reader and Graph::Writer in CPAN.
2351
2353 Jarkko Hietaniemi jhi@iki.fi
2354 Now being maintained by Neil Bowers <neilb@cpan.org>
2356
2358 Copyright (c) 1998-2014 Jarkko Hietaniemi. All rights reserved.
2359 This is free software; you can redistribute it and/or modify it under
2361 the same terms as the Perl 5 programming language system itself.
2362perl v5.32.1 2021-01-27 Graph(3)