1Graph(3) User Contributed Perl Documentation Graph(3)
2
6 Graph - graph data structures and algorithms
7
9 use Graph;
10 my $g0 = Graph->new; # A directed graph.
11 use Graph::Directed;
13 my $g1 = Graph::Directed->new; # A directed graph.
14 use Graph::Undirected;
16 my $g2 = Graph::Undirected->new; # An undirected graph.
17 $g->add_edge(...);
19 $g->has_edge(...)
20 $g->delete_edge(...);
21 $g->add_vertex(...);
23 $g->has_vertex(...);
24 $g->delete_vertex(...);
25 $g->vertices(...)
27 $g->edges(...)
28 # And many, many more, see below.
30
32 Non-Description
33 This module is not for drawing or rendering any sort of graphics or
34 images, business, visualization, or otherwise.
35 Description
37 Instead, this module is for creating abstract data structures called
38 graphs, and for doing various operations on those.
39 Perl 5.6.0 minimum
41 The implementation depends on a Perl feature called "weak references"
42 and Perl 5.6.0 was the first to have those.
43 Constructors
45 new Create an empty graph.
46 Graph->new(%options)
48 The options are a hash with option names as the hash keys and the
49 option values as the hash values.
50 The following options are available:
52 · directed
54 A boolean option telling that a directed graph should be
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
66 created. One could also use the "new()" constructor the
67 Graph::Undirected class instead.
68 Note that while often it is possible to think undirected
70 graphs as bidirectional graphs, or as directed graphs with
71 edges going both ways, in this module directed graphs and
72 undirected graphs are two different things that often
73 behave differently.
74 You can test the directness of a graph with
76 $g->is_directed() and $g->is_undirected().
77 · refvertexed
79 If you want to use references (including Perl objects) as
81 vertices.
82 · unionfind
84 If the graph is undirected, you can specify the "unionfind"
86 parameter to use the so-called union-find scheme to speed
87 up the computation of connected components of the graph
88 (see "is_connected", "connected_components",
89 "connected_component_by_vertex",
90 "connected_component_by_index", and
91 "same_connected_components"). If "unionfind" is used,
92 adding edges (and vertices) becomes slower, but
93 connectedness queries become faster. You can test a graph
94 for "union-findness" with
95 has_union_find
97 has_union_find
98 · vertices
100 An array reference of vertices to add.
102 · edges
104 An array reference of array references of edge vertices to
106 add.
107 copy
109 copy_graph
110 my $c = $g->copy_graph;
111 Create a shallow copy of the structure (vertices and edges) of the
113 graph. If you want a deep copy that includes attributes, see
114 "deep_copy". The copy will have the same directedness as the
115 original, and if the original was a "compat02" graph, the copy will
116 be, too.
117 Also the following vertex/edge attributes are copied:
119 refvertexed/hypervertexed/countvertexed/multivertexed
121 hyperedged/countedged/multiedged/omniedged
122 deep_copy
124 deep_copy_graph
125 my $c = $g->deep_copy_graph;
126 Create a deep copy of the graph (vertices, edges, and attributes)
128 of the graph. If you want a shallow copy that does not include
129 attributes, see "copy".
130 Note that copying code references only works with Perls 5.8 or
132 later, and even then only if B::Deparse can reconstruct your code.
133 This functionality uses either Storable or Data::Dumper behind the
134 scenes, depending on which is available (Storable is preferred).
135 undirected_copy
137 undirected_copy_graph
138 my $c = $g->undirected_copy_graph;
139 Create an undirected shallow copy (vertices and edges) of the
141 directed graph so that for any directed edge (u, v) there is an
142 undirected edge (u, v).
143 directed_copy
145 directed_copy_graph
146 my $c = $g->directed_copy_graph;
147 Create a directed shallow copy (vertices and edges) of the
149 undirected graph so that for any undirected edge (u, v) there are
150 two directed edges (u, v) and (v, u).
151 transpose
153 transpose_graph
154 my $t = $g->transpose_graph;
155 Create a directed shallow transposed copy (vertices and edges) of
157 the directed graph so that for any directed edge (u, v) there is a
158 directed edge (v, u).
159 You can also transpose a single edge with
161 transpose_edge
163 $g->transpose_edge($u, $v)
164 complete_graph
166 complete
167 my $c = $g->complete_graph;
168 Create a complete graph that has the same vertices as the original
170 graph. A complete graph has an edge between every pair of
171 vertices.
172 complement_graph
174 complement
175 my $c = $g->complement_graph;
176 Create a complement graph that has the same vertices as the
178 original graph. A complement graph has an edge (u,v) if and only
179 if the original graph does not have edge (u,v).
180 See also "random_graph" for a random constructor.
182 Basics
184 add_vertex
185 $g->add_vertex($v)
186 Add the vertex to the graph. Returns the graph.
188 By default idempotent, but a graph can be created countvertexed.
190 A vertex is also known as a node.
192 Adding "undef" as vertex is not allowed.
194 Note that unless you have isolated vertices (or countvertexed
196 vertices), you do not need to explicitly use "add_vertex" since
197 "add_edge" will implicitly add its vertices.
198 add_edge
200 $g->add_edge($u, $v)
201 Add the edge to the graph. Implicitly first adds the vertices if
203 the graph does not have them. Returns the graph.
204 By default idempotent, but a graph can be created countedged.
206 An edge is also known as an arc.
208 has_vertex
210 $g->has_vertex($v)
211 Return true if the vertex exists in the graph, false otherwise.
213 has_edge
215 $g->has_edge($u, $v)
216 Return true if the edge exists in the graph, false otherwise.
218 delete_vertex
220 $g->delete_vertex($v)
221 Delete the vertex from the graph. Returns the graph, even if the
223 vertex did not exist in the graph.
224 If the graph has been created multivertexed or countvertexed and a
226 vertex has been added multiple times, the vertex will require at
227 least an equal number of deletions to become completely deleted.
228 delete_vertices
230 $g->delete_vertices($v1, $v2, ...)
231 Delete the vertices from the graph. Returns the graph.
233 If the graph has been created multivertexed or countvertexed and a
235 vertex has been added multiple times, the vertex will require at
236 least an equal number of deletions to become completely deleteted.
237 delete_edge
239 $g->delete_edge($u, $v)
240 Delete the edge from the graph. Returns the graph, even if the
242 edge did not exist in the graph.
243 If the graph has been created multivertexed or countedged and an
245 edge has been added multiple times, the edge will require at least
246 an equal number of deletions to become completely deleted.
247 delete_edges
249 $g->delete_edges($u1, $v1, $u2, $v2, ...)
250 Delete the edges from the graph. Returns the graph.
252 If the graph has been created multivertexed or countedged and an
254 edge has been added multiple times, the edge will require at least
255 an equal number of deletions to become completely deleted.
256 Displaying
258 Graphs have stringification overload, so you can do things like
259 print "The graph is $g\n"
261 One-way (directed, unidirected) edges are shown as '-', two-way
263 (undirected, bidirected) edges are shown as '='. If you want to, you
264 can call the stringification via the method
265 stringify
267 Comparing
269 Testing for equality can be done either by the overloaded "eq" operator
270 $g eq "a-b,a-c,d"
272 or by the method
274 eq
276 $g->eq("a-b,a-c,d")
277 The equality testing compares the stringified forms, and therefore it
279 assumes total equality, not isomorphism: all the vertices must be named
280 the same, and they must have identical edges between them.
281 For unequality there are correspondingly the overloaded "ne" operator
283 and the method
284 ne
286 $g->ne("a-b,a-c,d")
287 See also "Isomorphism".
289 Paths and Cycles
291 Paths and cycles are simple extensions of edges: paths are edges
292 starting from where the previous edge ended, and cycles are paths
293 returning back to the start vertex of the first edge.
294 add_path
296 $g->add_path($a, $b, $c, ..., $x, $y, $z)
297 Add the edges $a-$b, $b-$c, ..., $x-$y, $y-$z to the graph.
299 Returns the graph.
300 has_path
302 $g->has_path($a, $b, $c, ..., $x, $y, $z)
303 Return true if the graph has all the edges $a-$b, $b-$c, ...,
305 $x-$y, $y-$z, false otherwise.
306 delete_path
308 $g->delete_path($a, $b, $c, ..., $x, $y, $z)
309 Delete all the edges edges $a-$b, $b-$c, ..., $x-$y, $y-$z
311 (regardless of whether they exist or not). Returns the graph.
312 add_cycle
314 $g->add_cycle($a, $b, $c, ..., $x, $y, $z)
315 Add the edges $a-$b, $b-$c, ..., $x-$y, $y-$z, and $z-$a to the
317 graph. Returns the graph.
318 has_cycle
320 $g->has_cycle($a, $b, $c, ..., $x, $y, $z)
321 Return true if the graph has all the edges $a-$b, $b-$c, ...,
323 $x-$y, $y-$z, and $z-$a, false otherwise.
324 NOTE: This does not detect cycles, see "has_a_cycle" and
326 "find_a_cycle".
327 delete_cycle
329 $g->delete_cycle($a, $b, $c, ..., $x, $y, $z)
330 Delete all the edges edges $a-$b, $b-$c, ..., $x-$y, $y-$z, and
332 $z-$a (regardless of whether they exist or not). Returns the
333 graph.
334 has_a_cycle
336 $g->has_a_cycle
337 Returns true if the graph has a cycle, false if not.
339 find_a_cycle
341 $g->find_a_cycle
342 Returns a cycle if the graph has one (as a list of vertices), an
344 empty list if no cycle can be found.
345 Note that this just returns the vertices of a cycle: not any
347 particular cycle, just the first one it finds. A repeated call
348 might find the same cycle, or it might find a different one, and
349 you cannot call this repeatedly to find all the cycles.
350 Graph Types
352 is_simple_graph
353 $g->is_simple_graph
354 Return true if the graph has no multiedges, false otherwise.
356 is_pseudo_graph
358 $g->is_pseudo_graph
359 Return true if the graph has any multiedges or any self-loops,
361 false otherwise.
362 is_multi_graph
364 $g->is_multi_graph
365 Return true if the graph has any multiedges but no self-loops,
367 false otherwise.
368 is_directed_acyclic_graph
370 is_dag
371 $g->is_directed_acyclic_graph
372 $g->is_dag
373 Return true if the graph is directed and acyclic, false otherwise.
375 is_cyclic
377 $g->is_cyclic
378 Return true if the graph is cyclic (contains at least one cycle).
380 (This is identical to "has_a_cycle".)
381 To find at least that one cycle, see "find_a_cycle".
383 is_acyclic
385 Return true if the graph is acyclic (does not contain any cycles).
386 To find a cycle, use find_a_cycle.
388 Transitivity
390 is_transitive
391 $g->is_transitive
392 Return true if the graph is transitive, false otherwise.
394 TransitiveClosure_Floyd_Warshall
396 transitive_closure
397 $tcg = $g->TransitiveClosure_Floyd_Warshall
398 Return the transitive closure graph of the graph.
400 You can query the reachability from $u to $v with
402 is_reachable
404 $tcg->is_reachable($u, $v)
405 See Graph::TransitiveClosure for more information about creating and
407 querying transitive closures.
408 With
410 transitive_closure_matrix
412 $tcm = $g->transitive_closure_matrix;
413 you can (create if not existing and) query the transitive closure
415 matrix that underlies the transitive closure graph. See
416 Graph::TransitiveClosure::Matrix for more information.
417 Mutators
419 add_vertices
420 $g->add_vertices('d', 'e', 'f')
421 Add zero or more vertices to the graph. Returns the graph.
423 add_edges
425 $g->add_edges(['d', 'e'], ['f', 'g'])
426 $g->add_edges(qw(d e f g));
427 Add zero or more edges to the graph. The edges are specified as a
429 list of array references, or as a list of vertices where the even
430 (0th, 2nd, 4th, ...) items are start vertices and the odd (1st,
431 3rd, 5th, ...) are the corresponding end vertices. Returns the
432 graph.
433 Accessors
435 is_directed
436 directed
437 $g->is_directed()
438 $g->directed()
439 Return true if the graph is directed, false otherwise.
441 is_undirected
443 undirected
444 $g->is_undirected()
445 $g->undirected()
446 Return true if the graph is undirected, false otherwise.
448 is_refvertexed
450 refvertexed
451 Return true if the graph can handle references (including Perl
452 objects) as vertices.
453 vertices
455 my $V = $g->vertices
456 my @V = $g->vertices
457 In scalar context, return the number of vertices in the graph. In
459 list context, return the vertices, in no particular order.
460 has_vertices
462 $g->has_vertices()
463 Return true if the graph has any vertices, false otherwise.
465 edges
467 my $E = $g->edges
468 my @E = $g->edges
469 In scalar context, return the number of edges in the graph. In
471 list context, return the edges, in no particular order. The edges
472 are returned as anonymous arrays listing the vertices.
473 has_edges
475 $g->has_edges()
476 Return true if the graph has any edges, false otherwise.
478 is_connected
480 $g->is_connected
481 For an undirected graph, return true is the graph is connected,
483 false otherwise. Being connected means that from every vertex it
484 is possible to reach every other vertex.
485 If the graph has been created with a true "unionfind" parameter,
487 the time complexity is (essentially) O(V), otherwise O(V log V).
488 See also "connected_components", "connected_component_by_index",
490 "connected_component_by_vertex", and "same_connected_components",
491 and "biconnectivity".
492 For directed graphs, see "is_strongly_connected" and
494 "is_weakly_connected".
495 connected_components
497 @cc = $g->connected_components()
498 For an undirected graph, returns the vertices of the connected
500 components of the graph as a list of anonymous arrays. The
501 ordering of the anonymous arrays or the ordering of the vertices
502 inside the anonymous arrays (the components) is undefined.
503 For directed graphs, see "strongly_connected_components" and
505 "weakly_connected_components".
506 connected_component_by_vertex
508 $i = $g->connected_component_by_vertex($v)
509 For an undirected graph, return an index identifying the connected
511 component the vertex belongs to, the indexing starting from zero.
512 For the inverse, see "connected_component_by_index".
514 If the graph has been created with a true "unionfind" parameter,
516 the time complexity is (essentially) O(1), otherwise O(V log V).
517 See also "biconnectivity".
519 For directed graphs, see "strongly_connected_component_by_vertex"
521 and "weakly_connected_component_by_vertex".
522 connected_component_by_index
524 @v = $g->connected_component_by_index($i)
525 For an undirected graph, return the vertices of the ith connected
527 component, the indexing starting from zero. The order of vertices
528 is undefined, while the order of the connected components is same
529 as from connected_components().
530 For the inverse, see "connected_component_by_vertex".
532 For directed graphs, see "strongly_connected_component_by_index"
534 and "weakly_connected_component_by_index".
535 same_connected_components
537 $g->same_connected_components($u, $v, ...)
538 For an undirected graph, return true if the vertices are in the
540 same connected component.
541 If the graph has been created with a true "unionfind" parameter,
543 the time complexity is (essentially) O(1), otherwise O(V log V).
544 For directed graphs, see "same_strongly_connected_components" and
546 "same_weakly_connected_components".
547 connected_graph
549 $cg = $g->connected_graph
550 For an undirected graph, return its connected graph.
552 connectivity_clear_cache
554 $g->connectivity_clear_cache
555 See "Clearing cached results".
557 See "Connected Graphs and Their Components" for further discussion.
559 biconnectivity
561 my ($ap, $bc, $br) = $g->biconnectivity
562 For an undirected graph, return the various biconnectivity
564 components of the graph: the articulation points (cut vertices),
565 biconnected components, and bridges.
566 Note: currently only handles connected graphs.
568 is_biconnected
570 $g->is_biconnected
571 For an undirected graph, return true if the graph is biconnected
573 (if it has no articulation points, also known as cut vertices).
574 is_edge_connected
576 $g->is_edge_connected
577 For an undirected graph, return true if the graph is edge-connected
579 (if it has no bridges).
580 is_edge_separable
582 $g->is_edge_separable
583 For an undirected graph, return true if the graph is edge-separable
585 (if it has bridges).
586 articulation_points
588 cut_vertices
589 $g->articulation_points
590 For an undirected graph, return the articulation points (cut
592 vertices) of the graph as a list of vertices. The order is
593 undefined.
594 biconnected_components
596 $g->biconnected_components
597 For an undirected graph, return the biconnected components of the
599 graph as a list of anonymous arrays of vertices in the components.
600 The ordering of the anonymous arrays or the ordering of the
601 vertices inside the anonymous arrays (the components) is undefined.
602 Also note that one vertex can belong to more than one biconnected
603 component.
604 biconnected_component_by_vertex
606 $i = $g->biconnected_component_by_index($v)
607 For an undirected graph, return an index identifying the
609 biconnected component the vertex belongs to, the indexing starting
610 from zero.
611 For the inverse, see "connected_component_by_index".
613 For directed graphs, see "strongly_connected_component_by_index"
615 and "weakly_connected_component_by_index".
616 biconnected_component_by_index
618 @v = $g->biconnected_component_by_index($i)
619 For an undirected graph, return the vertices in the ith biconnected
621 component of the graph as an anonymous arrays of vertices in the
622 component. The ordering of the vertices within a component is
623 undefined. Also note that one vertex can belong to more than one
624 biconnected component.
625 same_biconnected_components
627 $g->same_biconnected_components($u, $v, ...)
628 For an undirected graph, return true if the vertices are in the
630 same biconnected component.
631 biconnected_graph
633 $bcg = $g->biconnected_graph
634 For an undirected graph, return its biconnected graph.
636 See "Connected Graphs and Their Components" for further discussion.
638 bridges
640 $g->bridges
641 For an undirected graph, return the bridges of the graph as a list
643 of anonymous arrays of vertices in the bridges. The order of
644 bridges and the order of vertices in them is undefined.
645 biconnectivity_clear_cache
647 $g->biconnectivity_clear_cache
648 See "Clearing cached results".
650 strongly_connected
652 is_strongly_connected
653 $g->is_strongly_connected
654 For a directed graph, return true is the directed graph is strongly
656 connected, false if not.
657 See also "is_weakly_connected".
659 For undirected graphs, see "is_connected", or "is_biconnected".
661 strongly_connected_component_by_vertex
663 $i = $g->strongly_connected_component_by_vertex($v)
664 For a directed graph, return an index identifying the strongly
666 connected component the vertex belongs to, the indexing starting
667 from zero.
668 For the inverse, see "strongly_connected_component_by_index".
670 See also "weakly_connected_component_by_vertex".
672 For undirected graphs, see "connected_components" or
674 "biconnected_components".
675 strongly_connected_component_by_index
677 @v = $g->strongly_connected_component_by_index($i)
678 For a directed graph, return the vertices of the ith connected
680 component, the indexing starting from zero. The order of vertices
681 within a component is undefined, while the order of the connected
682 components is the as from strongly_connected_components().
683 For the inverse, see "strongly_connected_component_by_vertex".
685 For undirected graphs, see "weakly_connected_component_by_index".
687 same_strongly_connected_components
689 $g->same_strongly_connected_components($u, $v, ...)
690 For a directed graph, return true if the vertices are in the same
692 strongly connected component.
693 See also "same_weakly_connected_components".
695 For undirected graphs, see "same_connected_components" or
697 "same_biconnected_components".
698 strong_connectivity_clear_cache
700 $g->strong_connectivity_clear_cache
701 See "Clearing cached results".
703 weakly_connected
705 is_weakly_connected
706 $g->is_weakly_connected
707 For a directed graph, return true is the directed graph is weakly
709 connected, false if not.
710 Weakly connected graph is also known as semiconnected graph.
712 See also "is_strongly_connected".
714 For undirected graphs, see "is_connected" or "is_biconnected".
716 weakly_connected_components
718 @wcc = $g->weakly_connected_components()
719 For a directed graph, returns the vertices of the weakly connected
721 components of the graph as a list of anonymous arrays. The
722 ordering of the anonymous arrays or the ordering of the vertices
723 inside the anonymous arrays (the components) is undefined.
724 See also "strongly_connected_components".
726 For undirected graphs, see "connected_components" or
728 "biconnected_components".
729 weakly_connected_component_by_vertex
731 $i = $g->weakly_connected_component_by_vertex($v)
732 For a directed graph, return an index identifying the weakly
734 connected component the vertex belongs to, the indexing starting
735 from zero.
736 For the inverse, see "weakly_connected_component_by_index".
738 For undirected graphs, see "connected_component_by_vertex" and
740 "biconnected_component_by_vertex".
741 weakly_connected_component_by_index
743 @v = $g->weakly_connected_component_by_index($i)
744 For a directed graph, return the vertices of the ith weakly
746 connected component, the indexing starting zero. The order of
747 vertices within a component is undefined, while the order of the
748 weakly connected components is same as from
749 weakly_connected_components().
750 For the inverse, see "weakly_connected_component_by_vertex".
752 For undirected graphs, see connected_component_by_index and
754 biconnected_component_by_index.
755 same_weakly_connected_components
757 $g->same_weakly_connected_components($u, $v, ...)
758 Return true if the vertices are in the same weakly connected
760 component.
761 weakly_connected_graph
763 $wcg = $g->weakly_connected_graph
764 For a directed graph, return its weakly connected graph.
766 For undirected graphs, see "connected_graph" and
768 "biconnected_graph".
769 strongly_connected_components
771 my @scc = $g->strongly_connected_components;
772 For a directed graph, return the strongly connected components as a
774 list of anonymous arrays. The elements in the anonymous arrays are
775 the vertices belonging to the strongly connected component; both
776 the elements and the components are in no particular order.
777 See also "weakly_connected_components".
779 For undirected graphs, see "connected_components", or see
781 "biconnected_components".
782 strongly_connected_graph
784 my $scg = $g->strongly_connected_graph;
785 See "Connected Graphs and Their Components" for further discussion.
787 Strongly connected graphs are also known as kernel graphs.
789 See also "weakly_connected_graph".
791 For undirected graphs, see "connected_graph", or
793 "biconnected_graph".
794 is_sink_vertex
796 $g->is_sink_vertex($v)
797 Return true if the vertex $v is a sink vertex, false if not. A
799 sink vertex is defined as a vertex with predecessors but no
800 successors: this definition means that isolated vertices are not
801 sink vertices. If you want also isolated vertices, use
802 is_successorless_vertex().
803 is_source_vertex
805 $g->is_source_vertex($v)
806 Return true if the vertex $v is a source vertex, false if not. A
808 source vertex is defined as a vertex with successors but no
809 predecessors: the definition means that isolated vertices are not
810 source vertices. If you want also isolated vertices, use
811 is_predecessorless_vertex().
812 is_successorless_vertex
814 $g->is_successorless_vertex($v)
815 Return true if the vertex $v has no succcessors (no edges leaving
817 the vertex), false if it has.
818 Isolated vertices will return true: if you do not want this, use
820 is_sink_vertex().
821 is_successorful_vertex
823 $g->is_successorful_vertex($v)
824 Return true if the vertex $v has successors, false if not.
826 is_predecessorless_vertex
828 $g->is_predecessorless_vertex($v)
829 Return true if the vertex $v has no predecessors (no edges entering
831 the vertex), false if it has.
832 Isolated vertices will return true: if you do not want this, use
834 is_source_vertex().
835 is_predecessorful_vertex
837 $g->is_predecessorful_vertex($v)
838 Return true if the vertex $v has predecessors, false if not.
840 is_isolated_vertex
842 $g->is_isolated_vertex($v)
843 Return true if the vertex $v is an isolated vertex: no successors
845 and no predecessors.
846 is_interior_vertex
848 $g->is_interior_vertex($v)
849 Return true if the vertex $v is an interior vertex: both successors
851 and predecessors.
852 is_exterior_vertex
854 $g->is_exterior_vertex($v)
855 Return true if the vertex $v is an exterior vertex: has either no
857 successors or no predecessors, or neither.
858 is_self_loop_vertex
860 $g->is_self_loop_vertex($v)
861 Return true if the vertex $v is a self loop vertex: has an edge
863 from itself to itself.
864 sink_vertices
866 @v = $g->sink_vertices()
867 Return the sink vertices of the graph. In scalar context return
869 the number of sink vertices. See "is_sink_vertex" for the
870 definition of a sink vertex.
871 source_vertices
873 @v = $g->source_vertices()
874 Return the source vertices of the graph. In scalar context return
876 the number of source vertices. See "is_source_vertex" for the
877 definition of a source vertex.
878 successorful_vertices
880 @v = $g->successorful_vertices()
881 Return the successorful vertices of the graph. In scalar context
883 return the number of successorful vertices.
884 successorless_vertices
886 @v = $g->successorless_vertices()
887 Return the successorless vertices of the graph. In scalar context
889 return the number of successorless vertices.
890 successors
892 @s = $g->successors($v)
893 Return the immediate successor vertices of the vertex.
895 See also "all_successors", "all_neighbours", and "all_reachable".
897 all_successors
899 @s = $g->all_successors(@v)
900 For a directed graph, returns all successor vertices of the
902 argument vertices, recursively.
903 For undirected graphs, see "all_neighbours" and "all_reachable".
905 See also "successors".
907 neighbors
909 neighbours
910 @n = $g->neighbours($v)
911 Return the neighbo(u)ring vertices. Also known as the adjacent
913 vertices.
914 See also "all_neighbours" and "all_reachable".
916 all_neighbors
918 all_neighbours
919 @n = $g->all_neighbours(@v)
920 Return the neighbo(u)ring vertices of the argument vertices,
922 recursively. For a directed graph, recurses up predecessors and
923 down successors. For an undirected graph, returns all the vertices
924 reachable from the argument vertices.
925 See also "neighbours" and "all_reachable".
927 all_reachable
929 @r = $g->all_reachable(@v)
930 Return all the vertices reachable from of the argument vertices,
932 recursively. For a directed graph, equivalent to "all_successors".
933 For an undirected graph, equivalent to "all_neighbours".
934 See also "neighbours", "all_neighbours", and "all_successors".
936 predecessorful_vertices
938 @v = $g->predecessorful_vertices()
939 Return the predecessorful vertices of the graph. In scalar context
941 return the number of predecessorful vertices.
942 predecessorless_vertices
944 @v = $g->predecessorless_vertices()
945 Return the predecessorless vertices of the graph. In scalar
947 context return the number of predecessorless vertices.
948 predecessors
950 @p = $g->predecessors($v)
951 Return the immediate predecessor vertices of the vertex.
953 See also "all_predecessors", "all_neighbours", and "all_reachable".
955 all_predecessors
957 @p = $g->all_predecessors(@v)
958 For a directed graph, returns all predecessor vertices of the
960 argument vertices, recursively.
961 For undirected graphs, see "all_neighbours" and "all_reachable".
963 See also "predecessors".
965 isolated_vertices
967 @v = $g->isolated_vertices()
968 Return the isolated vertices of the graph. In scalar context
970 return the number of isolated vertices. See "is_isolated_vertex"
971 for the definition of an isolated vertex.
972 interior_vertices
974 @v = $g->interior_vertices()
975 Return the interior vertices of the graph. In scalar context
977 return the number of interior vertices. See "is_interior_vertex"
978 for the definition of an interior vertex.
979 exterior_vertices
981 @v = $g->exterior_vertices()
982 Return the exterior vertices of the graph. In scalar context
984 return the number of exterior vertices. See "is_exterior_vertex"
985 for the definition of an exterior vertex.
986 self_loop_vertices
988 @v = $g->self_loop_vertices()
989 Return the self-loop vertices of the graph. In scalar context
991 return the number of self-loop vertices. See "is_self_loop_vertex"
992 for the definition of a self-loop vertex.
993 Connected Graphs and Their Components
995 In this discussion connected graph refers to any of connected graphs,
996 biconnected graphs, and strongly connected graphs.
997 NOTE: if the vertices of the original graph are Perl objects, (in other
999 words, references, so you must be using "refvertexed") the vertices of
1000 the connected graph are NOT by default usable as Perl objects because
1001 they are blessed into a package with a rather unusable name.
1002 By default, the vertex names of the connected graph are formed from the
1004 names of the vertices of the original graph by (alphabetically sorting
1005 them and) concatenating their names with "+". The vertex attribute
1006 "subvertices" is also used to store the list (as an array reference) of
1007 the original vertices. To change the 'supercomponent' vertex names and
1008 the whole logic of forming these supercomponents use the
1009 "super_component") option to the method calls:
1010 $g->connected_graph(super_component => sub { ... })
1012 $g->biconnected_graph(super_component => sub { ... })
1013 $g->strongly_connected_graph(super_component => sub { ... })
1014 The subroutine reference gets the 'subcomponents' (the vertices of the
1016 original graph) as arguments, and it is supposed to return the new
1017 supercomponent vertex, the "stringified" form of which is used as the
1018 vertex name.
1019 Degree
1021 A vertex has a degree based on the number of incoming and outgoing
1022 edges. This really makes sense only for directed graphs.
1023 degree
1025 vertex_degree
1026 $d = $g->degree($v)
1027 $d = $g->vertex_degree($v)
1028 For directed graphs: the in-degree minus the out-degree at the
1030 vertex.
1031 For undirected graphs: the number of edges at the vertex
1033 (identical to "in_degree()", "out_degree()").
1034 in_degree
1036 $d = $g->in_degree($v)
1037 For directed graphs: the number of incoming edges at the vertex.
1039 For undirected graphs: the number of edges at the vertex (identical
1041 to "out_degree()", "degree()", "vertex_degree()").
1042 out_degree
1044 $o = $g->out_degree($v)
1045 For directed graphs: The number of outgoing edges at the vertex.
1047 For undirected graphs: the number of edges at the vertex (identical
1049 to "in_degree()", "degree()", "vertex_degree()").
1050 average_degree
1052 my $ad = $g->average_degree;
1053 Return the average degree (as in "degree()" or "vertex_degree()")
1055 taken over all vertices.
1056 Related methods are
1058 edges_at
1060 @e = $g->edges_at($v)
1061 The union of edges from and edges to at the vertex.
1063 edges_from
1065 @e = $g->edges_from($v)
1066 The edges leaving the vertex.
1068 edges_to
1070 @e = $g->edges_to($v)
1071 The edges entering the vertex.
1073 See also "average_degree".
1075 Counted Vertices
1077 Counted vertices are vertices with more than one instance, normally
1078 adding vertices is idempotent. To enable counted vertices on a graph,
1079 give the "countvertexed" parameter a true value
1080 use Graph;
1082 my $g = Graph->new(countvertexed => 1);
1083 To find out how many times the vertex has been added:
1085 get_vertex_count
1087 my $c = $g->get_vertex_count($v);
1088 Return the count of the vertex, or undef if the vertex does not
1090 exist.
1091 Multiedges, Multivertices, Multigraphs
1093 Multiedges are edges with more than one "life", meaning that one has to
1094 delete them as many times as they have been added. Normally adding
1095 edges is idempotent (in other words, adding edges more than once makes
1096 no difference).
1097 There are two kinds or degrees of creating multiedges and
1099 multivertices. The two kinds are mutually exclusive.
1100 The weaker kind is called counted, in which the edge or vertex has a
1102 count on it: add operations increase the count, and delete operations
1103 decrease the count, and once the count goes to zero, the edge or vertex
1104 is deleted. If there are attributes, they all are attached to the same
1105 vertex. You can think of this as the graph elements being refcounted,
1106 or reference counted, if that sounds more familiar.
1107 The stronger kind is called (true) multi, in which the edge or vertex
1109 really has multiple separate identities, so that you can for example
1110 attach different attributes to different instances.
1111 To enable multiedges on a graph:
1113 use Graph;
1115 my $g0 = Graph->new(countedged => 1);
1116 my $g0 = Graph->new(multiedged => 1);
1117 Similarly for vertices
1119 use Graph;
1121 my $g1 = Graph->new(countvertexed => 1);
1122 my $g1 = Graph->new(multivertexed => 1);
1123 You can test for these by
1125 is_countedged
1127 countedged
1128 $g->is_countedged
1129 $g->countedged
1130 Return true if the graph is countedged.
1132 is_countvertexed
1134 countvertexed
1135 $g->is_countvertexed
1136 $g->countvertexed
1137 Return true if the graph is countvertexed.
1139 is_multiedged
1141 multiedged
1142 $g->is_multiedged
1143 $g->multiedged
1144 Return true if the graph is multiedged.
1146 is_multivertexed
1148 multivertexed
1149 $g->is_multivertexed
1150 $g->multivertexed
1151 Return true if the graph is multivertexed.
1153 A multiedged (either the weak kind or the strong kind) graph is a
1155 multigraph, for which you can test with "is_multi_graph()".
1156 NOTE: The various graph algorithms do not in general work well with
1158 multigraphs (they often assume simple graphs, that is, no multiedges or
1159 loops), and no effort has been made to test the algorithms with
1160 multigraphs.
1161 vertices() and edges() will return the multiple elements: if you want
1163 just the unique elements, use
1164 unique_vertices
1166 unique_edges
1167 @uv = $g->unique_vertices; # unique
1168 @mv = $g->vertices; # possible multiples
1169 @ue = $g->unique_edges;
1170 @me = $g->edges;
1171 If you are using (the stronger kind of) multielements, you should use
1173 the by_id variants:
1174 add_vertex_by_id
1176 has_vertex_by_id
1177 delete_vertex_by_id
1178 add_edge_by_id
1179 has_edge_by_id
1180 delete_edge_by_id
1181 $g->add_vertex_by_id($v, $id)
1183 $g->has_vertex_by_id($v, $id)
1184 $g->delete_vertex_by_id($v, $id)
1185 $g->add_edge_by_id($u, $v, $id)
1187 $g->has_edge_by_id($u, $v, $id)
1188 $g->delete_edge_by_id($u, $v, $id)
1189 When you delete the last vertex/edge in a multivertex/edge, the whole
1191 vertex/edge is deleted. You can use add_vertex()/add_edge() on a
1192 multivertex/multiedge graph, in which case an id is generated
1193 automatically. To find out which the generated id was, you need to use
1194 add_vertex_get_id
1196 add_edge_get_id
1197 $idv = $g->add_vertex_get_id($v)
1199 $ide = $g->add_edge_get_id($u, $v)
1200 To return all the ids of vertices/edges in a multivertex/multiedge, use
1202 get_multivertex_ids
1204 get_multiedge_ids
1205 $g->get_multivertex_ids($v)
1207 $g->get_multiedge_ids($u, $v)
1208 The ids are returned in random order.
1210 To find out how many times the edge has been added (this works for
1212 either kind of multiedges):
1213 get_edge_count
1215 my $c = $g->get_edge_count($u, $v);
1216 Return the count (the "countedness") of the edge, or undef if the
1218 edge does not exist.
1219 The following multi-entity utility functions exist, mirroring the non-
1221 multi vertices and edges:
1222 add_weighted_edge_by_id
1224 add_weighted_edges_by_id
1225 add_weighted_path_by_id
1226 add_weighted_vertex_by_id
1227 add_weighted_vertices_by_id
1228 delete_edge_weight_by_id
1229 delete_vertex_weight_by_id
1230 get_edge_weight_by_id
1231 get_vertex_weight_by_id
1232 has_edge_weight_by_id
1233 has_vertex_weight_by_id
1234 set_edge_weight_by_id
1235 set_vertex_weight_by_id
1236 Topological Sort
1238 topological_sort
1239 toposort
1240 my @ts = $g->topological_sort;
1241 Return the vertices of the graph sorted topologically. Note that
1243 there may be several possible topological orderings; one of them is
1244 returned.
1245 If the graph contains a cycle, a fatal error is thrown, you can
1247 either use "eval" to trap that, or supply the "empty_if_cyclic"
1248 argument with a true value
1249 my @ts = $g->topological_sort(empty_if_cyclic => 1);
1251 in which case an empty array is returned if the graph is cyclic.
1253 Minimum Spanning Trees (MST)
1255 Minimum Spanning Trees or MSTs are tree subgraphs derived from an
1256 undirected graph. MSTs "span the graph" (covering all the vertices)
1257 using as lightly weighted (hence the "minimum") edges as possible.
1258 MST_Kruskal
1260 $mstg = $g->MST_Kruskal;
1261 Returns the Kruskal MST of the graph.
1263 MST_Prim
1265 $mstg = $g->MST_Prim(%opt);
1266 Returns the Prim MST of the graph.
1268 You can choose the first vertex with $opt{ first_root }.
1270 MST_Dijkstra
1272 minimum_spanning_tree
1273 $mstg = $g->MST_Dijkstra;
1274 $mstg = $g->minimum_spanning_tree;
1275 Aliases for MST_Prim.
1277 Single-Source Shortest Paths (SSSP)
1279 Single-source shortest paths, also known as Shortest Path Trees (SPTs).
1280 For either a directed or an undirected graph, return a (tree) subgraph
1281 that from a single start vertex (the "single source") travels the
1282 shortest possible paths (the paths with the lightest weights) to all
1283 the other vertices. Note that the SSSP is neither reflexive (the
1284 shortest paths do not include the zero-length path from the source
1285 vertex to the source vertex) nor transitive (the shortest paths do not
1286 include transitive closure paths). If no weight is defined for an
1287 edge, 1 (one) is assumed.
1288 SPT_Dijkstra
1290 $sptg = $g->SPT_Dijkstra($root)
1291 $sptg = $g->SPT_Dijkstra(%opt)
1292 Return as a graph the the single-source shortest paths of the graph
1294 using Dijkstra's algorithm. The graph cannot contain negative
1295 edges (negative edges cause the algorithm to abort with an error
1296 message "Graph::SPT_Dijkstra: edge ... is negative").
1297 You can choose the first vertex of the result with either a single
1299 vertex argument or with $opt{ first_root }, otherwise a random
1300 vertex is chosen.
1301 NOTE: note that all the vertices might not be reachable from the
1303 selected (explicit or random) start vertex.
1304 The start vertex is be available as the graph attribute
1306 "SPT_Dijkstra_root").
1307 The result weights of vertices can be retrieved from the result
1309 graph by
1310 my $w = $sptg->get_vertex_attribute($v, 'weight');
1312 The predecessor vertex of a vertex in the result graph can be
1314 retrieved by
1315 my $u = $sptg->get_vertex_attribute($v, 'p');
1317 ("A successor vertex" cannot be retrieved as simply because a
1319 single vertex can have several successors. You can first find the
1320 "neighbors()" vertices and then remove the predecessor vertex.)
1321 If you want to find the shortest path between two vertices, see
1323 "SP_Dijkstra".
1324 SSSP_Dijkstra
1326 single_source_shortest_paths
1327 Aliases for SPT_Dijkstra.
1328 SP_Dijkstra
1330 @path = $g->SP_Dijkstra($u, $v)
1331 Return the vertices in the shortest path in the graph $g between
1333 the two vertices $u, $v. If no path can be found, an empty list is
1334 returned.
1335 Uses SPT_Dijkstra().
1337 SPT_Dijkstra_clear_cache
1339 $g->SPT_Dijkstra_clear_cache
1340 See "Clearing cached results".
1342 SPT_Bellman_Ford
1344 $sptg = $g->SPT_Bellman_Ford(%opt)
1345 Return as a graph the single-source shortest paths of the graph
1347 using Bellman-Ford's algorithm. The graph can contain negative
1348 edges but not negative cycles (negative cycles cause the algorithm
1349 to abort with an error message "Graph::SPT_Bellman_Ford: negative
1350 cycle exists/").
1351 You can choose the start vertex of the result with either a single
1353 vertex argument or with $opt{ first_root }, otherwise a random
1354 vertex is chosen.
1355 NOTE: note that all the vertices might not be reachable from the
1357 selected (explicit or random) start vertex.
1358 The start vertex is be available as the graph attribute
1360 "SPT_Bellman_Ford_root").
1361 The result weights of vertices can be retrieved from the result
1363 graph by
1364 my $w = $sptg->get_vertex_attribute($v, 'weight');
1366 The predecessor vertex of a vertex in the result graph can be
1368 retrieved by
1369 my $u = $sptg->get_vertex_attribute($v, 'p');
1371 ("A successor vertex" cannot be retrieved as simply because a
1373 single vertex can have several successors. You can first find the
1374 "neighbors()" vertices and then remove the predecessor vertex.)
1375 If you want to find the shortes path between two vertices, see
1377 "SP_Bellman_Ford".
1378 SSSP_Bellman_Ford
1380 Alias for SPT_Bellman_Ford.
1381 SP_Bellman_Ford
1383 @path = $g->SP_Bellman_Ford($u, $v)
1384 Return the vertices in the shortest path in the graph $g between
1386 the two vertices $u, $v. If no path can be found, an empty list is
1387 returned.
1388 Uses SPT_Bellman_Ford().
1390 SPT_Bellman_Ford_clear_cache
1392 $g->SPT_Bellman_Ford_clear_cache
1393 See "Clearing cached results".
1395 All-Pairs Shortest Paths (APSP)
1397 For either a directed or an undirected graph, return the APSP object
1398 describing all the possible paths between any two vertices of the
1399 graph. If no weight is defined for an edge, 1 (one) is assumed.
1400 APSP_Floyd_Warshall
1402 all_pairs_shortest_paths
1403 my $apsp = $g->APSP_Floyd_Warshall(...);
1404 Return the all-pairs shortest path object computed from the graph
1406 using Floyd-Warshall's algorithm. The length of a path between two
1407 vertices is the sum of weight attribute of the edges along the
1408 shortest path between the two vertices. If no weight attribute
1409 name is specified explicitly
1410 $g->APSP_Floyd_Warshall(attribute_name => 'height');
1412 the attribute "weight" is assumed.
1414 If an edge has no defined weight attribute, the value of one is
1416 assumed when getting the attribute.
1417 Once computed, you can query the APSP object with
1419 path_length
1421 my $l = $apsp->path_length($u, $v);
1422 Return the length of the shortest path between the two
1424 vertices.
1425 path_vertices
1427 my @v = $apsp->path_vertices($u, $v);
1428 Return the list of vertices along the shortest path.
1430 path_predecessor
1432 my $u = $apsp->path_predecessor($v);
1433 Returns the predecessor of vertex $v in the all-pairs
1435 shortest paths.
1436 average_path_length
1438 my $apl = $g->average_path_length; # All vertex pairs.
1439 my $apl = $g->average_path_length($u); # From $u.
1441 my $apl = $g->average_path_length($u, undef); # From $u.
1442 my $apl = $g->average_path_length($u, $v); # From $u to $v.
1444 my $apl = $g->average_path_length(undef, $v); # To $v.
1446 Return the average (shortest) path length over all the
1448 vertex pairs of the graph, from a vertex, between two
1449 vertices, and to a vertex.
1450 longest_path
1452 my @lp = $g->longest_path;
1453 my $lp = $g->longest_path;
1454 In scalar context return the longest shortest path length
1456 over all the vertex pairs of the graph. In list context
1457 return the vertices along a longest shortest path. Note
1458 that there might be more than one such path; this
1459 interfaces return a random one of them.
1460 diameter
1462 graph_diameter
1463 my $gd = $g->diameter;
1464 The longest path over all the vertex pairs is known as the
1466 graph diameter.
1467 shortest_path
1469 my @sp = $g->shortest_path;
1470 my $sp = $g->shortest_path;
1471 In scalar context return the shortest length over all the
1473 vertex pairs of the graph. In list context return the
1474 vertices along a shortest path. Note that there might be
1475 more than one such path; this interface returns a random
1476 one of them.
1477 radius
1479 my $gr = $g->radius;
1480 The shortest longest path over all the vertex pairs is
1482 known as the graph radius. See also "diameter".
1483 center_vertices
1485 centre_vertices
1486 my @c = $g->center_vertices;
1487 my @c = $g->center_vertices($delta);
1488 The graph center is the set of vertices for which the
1490 vertex eccentricity is equal to the graph radius. The
1491 vertices are returned in random order. By specifying a
1492 delta value you can widen the criterion from strict
1493 equality (handy for non-integer edge weights).
1494 vertex_eccentricity
1496 my $ve = $g->vertex_eccentricity($v);
1497 The longest path to a vertex is known as the vertex
1499 eccentricity. If the graph is unconnected, returns Inf.
1500 You can walk through the matrix of the shortest paths by using
1502 for_shortest_paths
1504 $n = $g->for_shortest_paths($callback)
1505 The number of shortest paths is returned (this should be equal
1507 to V*V). The $callback is a sub reference that receives four
1508 arguments: the transitive closure object from
1509 Graph::TransitiveClosure, the two vertices, and the index to
1510 the current shortest paths (0..V*V-1).
1511 Clearing cached results
1513 For many graph algorithms there are several different but equally valid
1514 results. (Pseudo)Randomness is used internally by the Graph module to
1515 for example pick a random starting vertex, and to select random edges
1516 from a vertex.
1517 For efficiency the computed result is often cached to avoid recomputing
1519 the potentially expensive operation, and this also gives additional
1520 determinism (once a correct result has been computed, the same result
1521 will always be given).
1522 However, sometimes the exact opposite is desireable, and the possible
1524 alternative results are wanted (within the limits of the
1525 pseudorandomness: not all the possible solutions are guaranteed to be
1526 returned, usually only a subset is retuned). To undo the caching, the
1527 following methods are available:
1528 · connectivity_clear_cache
1530 Affects "connected_components", "connected_component_by_vertex",
1532 "connected_component_by_index", "same_connected_components",
1533 "connected_graph", "is_connected", "is_weakly_connected",
1534 "weakly_connected_components",
1535 "weakly_connected_component_by_vertex",
1536 "weakly_connected_component_by_index",
1537 "same_weakly_connected_components", "weakly_connected_graph".
1538 · biconnectivity_clear_cache
1540 Affects "biconnected_components",
1542 "biconnected_component_by_vertex",
1543 "biconnected_component_by_index", "is_edge_connected",
1544 "is_edge_separable", "articulation_points", "cut_vertices",
1545 "is_biconnected", "biconnected_graph",
1546 "same_biconnected_components", "bridges".
1547 · strong_connectivity_clear_cache
1549 Affects "strongly_connected_components",
1551 "strongly_connected_component_by_vertex",
1552 "strongly_connected_component_by_index",
1553 "same_strongly_connected_components", "is_strongly_connected",
1554 "strongly_connected", "strongly_connected_graph".
1555 · SPT_Dijkstra_clear_cache
1557 Affects "SPT_Dijkstra", "SSSP_Dijkstra",
1559 "single_source_shortest_paths", "SP_Dijkstra".
1560 · SPT_Bellman_Ford_clear_cache
1562 Affects "SPT_Bellman_Ford", "SSSP_Bellman_Ford", "SP_Bellman_Ford".
1564 Note that any such computed and cached results are of course always
1566 automatically discarded whenever the graph is modified.
1567 Random
1569 You can either ask for random elements of existing graphs or create
1570 random graphs.
1571 random_vertex
1573 my $v = $g->random_vertex;
1574 Return a random vertex of the graph, or undef if there are no
1576 vertices.
1577 random_edge
1579 my $e = $g->random_edge;
1580 Return a random edge of the graph as an array reference having the
1582 vertices as elements, or undef if there are no edges.
1583 random_successor
1585 my $v = $g->random_successor($v);
1586 Return a random successor of the vertex in the graph, or undef if
1588 there are no successors.
1589 random_predecessor
1591 my $u = $g->random_predecessor($v);
1592 Return a random predecessor of the vertex in the graph, or undef if
1594 there are no predecessors.
1595 random_graph
1597 my $g = Graph->random_graph(%opt);
1598 Construct a random graph. The %opt must contain the "vertices"
1600 argument
1601 vertices => vertices_def
1603 where the vertices_def is one of
1605 · an array reference where the elements of the array
1607 reference are the vertices
1608 · a number N in which case the vertices will be integers
1610 0..N-1
1611 The %opt may have either of the argument "edges" or the argument
1613 "edges_fill". Both are used to define how many random edges to add to
1614 the graph; "edges" is an absolute number, while "edges_fill" is a
1615 relative number (relative to the number of edges in a complete graph,
1616 C). The number of edges can be larger than C, but only if the graph is
1617 countedged. The random edges will not include self-loops. If neither
1618 "edges" nor "edges_fill" is specified, an "edges_fill" of 0.5 is
1619 assumed.
1620 If you want repeatable randomness (what is an oxymoron?) you can use
1622 the "random_seed" option:
1623 $g = Graph->random_graph(vertices => 10, random_seed => 1234);
1625 As this uses the standard Perl srand(), the usual caveat applies: use
1627 it sparingly, and consider instead using a single srand() call at the
1628 top level of your application.
1629 The default random distribution of edges is flat, that is, any pair of
1631 vertices is equally likely to appear. To define your own distribution,
1632 use the "random_edge" option:
1633 $g = Graph->random_graph(vertices => 10, random_edge => \&d);
1635 where "d" is a code reference receiving ($g, $u, $v, $p) as parameters,
1637 where the $g is the random graph, $u and $v are the vertices, and the
1638 $p is the probability ([0,1]) for a flat distribution. It must return
1639 a probability ([0,1]) that the vertices $u and $v have an edge between
1640 them. Note that returning one for a particular pair of vertices
1641 doesn't guarantee that the edge will be present in the resulting graph
1642 because the required number of edges might be reached before that
1643 particular pair is tested for the possibility of an edge. Be very
1644 careful to adjust also "edges" or "edges_fill" so that there is a
1645 possibility of the filling process terminating.
1646 Attributes
1648 You can attach free-form attributes (key-value pairs, in effect a full
1649 Perl hash) to each vertex, edge, and the graph itself.
1650 Note that attaching attributes does slow down some other operations on
1652 the graph by a factor of three to ten. For example adding edge
1653 attributes does slow down anything that walks through all the edges.
1654 For vertex attributes:
1656 set_vertex_attribute
1658 $g->set_vertex_attribute($v, $name, $value)
1659 Set the named vertex attribute.
1661 If the vertex does not exist, the set_...() will create it, and the
1663 other vertex attribute methods will return false or empty.
1664 NOTE: any attributes beginning with an underscore/underline (_) are
1666 reserved for the internal use of the Graph module.
1667 get_vertex_attribute
1669 $value = $g->get_vertex_attribute($v, $name)
1670 Return the named vertex attribute.
1672 has_vertex_attribute
1674 $g->has_vertex_attribute($v, $name)
1675 Return true if the vertex has an attribute, false if not.
1677 delete_vertex_attribute
1679 $g->delete_vertex_attribute($v, $name)
1680 Delete the named vertex attribute.
1682 set_vertex_attributes
1684 $g->set_vertex_attributes($v, $attr)
1685 Set all the attributes of the vertex from the anonymous hash $attr.
1687 NOTE: any attributes beginning with an underscore ("_") are
1689 reserved for the internal use of the Graph module.
1690 get_vertex_attributes
1692 $attr = $g->get_vertex_attributes($v)
1693 Return all the attributes of the vertex as an anonymous hash.
1695 get_vertex_attribute_names
1697 @name = $g->get_vertex_attribute_names($v)
1698 Return the names of vertex attributes.
1700 get_vertex_attribute_values
1702 @value = $g->get_vertex_attribute_values($v)
1703 Return the values of vertex attributes.
1705 has_vertex_attributes
1707 $g->has_vertex_attributes($v)
1708 Return true if the vertex has any attributes, false if not.
1710 delete_vertex_attributes
1712 $g->delete_vertex_attributes($v)
1713 Delete all the attributes of the named vertex.
1715 If you are using multivertices, use the by_id variants:
1717 set_vertex_attribute_by_id
1719 get_vertex_attribute_by_id
1720 has_vertex_attribute_by_id
1721 delete_vertex_attribute_by_id
1722 set_vertex_attributes_by_id
1723 get_vertex_attributes_by_id
1724 get_vertex_attribute_names_by_id
1725 get_vertex_attribute_values_by_id
1726 has_vertex_attributes_by_id
1727 delete_vertex_attributes_by_id
1728 $g->set_vertex_attribute_by_id($v, $id, $name, $value)
1729 $g->get_vertex_attribute_by_id($v, $id, $name)
1730 $g->has_vertex_attribute_by_id($v, $id, $name)
1731 $g->delete_vertex_attribute_by_id($v, $id, $name)
1732 $g->set_vertex_attributes_by_id($v, $id, $attr)
1733 $g->get_vertex_attributes_by_id($v, $id)
1734 $g->get_vertex_attribute_values_by_id($v, $id)
1735 $g->get_vertex_attribute_names_by_id($v, $id)
1736 $g->has_vertex_attributes_by_id($v, $id)
1737 $g->delete_vertex_attributes_by_id($v, $id)
1738 For edge attributes:
1740 set_edge_attribute
1742 $g->set_edge_attribute($u, $v, $name, $value)
1743 Set the named edge attribute.
1745 If the edge does not exist, the set_...() will create it, and the
1747 other edge attribute methods will return false or empty.
1748 NOTE: any attributes beginning with an underscore ("_") are
1750 reserved for the internal use of the Graph module.
1751 get_edge_attribute
1753 $value = $g->get_edge_attribute($u, $v, $name)
1754 Return the named edge attribute.
1756 has_edge_attribute
1758 $g->has_edge_attribute($u, $v, $name)
1759 Return true if the edge has an attribute, false if not.
1761 delete_edge_attribute
1763 $g->delete_edge_attribute($u, $v, $name)
1764 Delete the named edge attribute.
1766 set_edge_attributes
1768 $g->set_edge_attributes($u, $v, $attr)
1769 Set all the attributes of the edge from the anonymous hash $attr.
1771 NOTE: any attributes beginning with an underscore ("_") are
1773 reserved for the internal use of the Graph module.
1774 get_edge_attributes
1776 $attr = $g->get_edge_attributes($u, $v)
1777 Return all the attributes of the edge as an anonymous hash.
1779 get_edge_attribute_names
1781 @name = $g->get_edge_attribute_names($u, $v)
1782 Return the names of edge attributes.
1784 get_edge_attribute_values
1786 @value = $g->get_edge_attribute_values($u, $v)
1787 Return the values of edge attributes.
1789 has_edge_attributes
1791 $g->has_edge_attributes($u, $v)
1792 Return true if the edge has any attributes, false if not.
1794 delete_edge_attributes
1796 $g->delete_edge_attributes($u, $v)
1797 Delete all the attributes of the named edge.
1799 If you are using multiedges, use the by_id variants:
1801 set_edge_attribute_by_id
1803 get_edge_attribute_by_id
1804 has_edge_attribute_by_id
1805 delete_edge_attribute_by_id
1806 set_edge_attributes_by_id
1807 get_edge_attributes_by_id
1808 get_edge_attribute_names_by_id
1809 get_edge_attribute_values_by_id
1810 has_edge_attributes_by_id
1811 delete_edge_attributes_by_id
1812 $g->set_edge_attribute_by_id($u, $v, $id, $name, $value)
1813 $g->get_edge_attribute_by_id($u, $v, $id, $name)
1814 $g->has_edge_attribute_by_id($u, $v, $id, $name)
1815 $g->delete_edge_attribute_by_id($u, $v, $id, $name)
1816 $g->set_edge_attributes_by_id($u, $v, $id, $attr)
1817 $g->get_edge_attributes_by_id($u, $v, $id)
1818 $g->get_edge_attribute_values_by_id($u, $v, $id)
1819 $g->get_edge_attribute_names_by_id($u, $v, $id)
1820 $g->has_edge_attributes_by_id($u, $v, $id)
1821 $g->delete_edge_attributes_by_id($u, $v, $id)
1822 For graph attributes:
1824 set_graph_attribute
1826 $g->set_graph_attribute($name, $value)
1827 Set the named graph attribute.
1829 NOTE: any attributes beginning with an underscore ("_") are
1831 reserved for the internal use of the Graph module.
1832 get_graph_attribute
1834 $value = $g->get_graph_attribute($name)
1835 Return the named graph attribute.
1837 has_graph_attribute
1839 $g->has_graph_attribute($name)
1840 Return true if the graph has an attribute, false if not.
1842 delete_graph_attribute
1844 $g->delete_graph_attribute($name)
1845 Delete the named graph attribute.
1847 set_graph_attributes
1849 $g->get_graph_attributes($attr)
1850 Set all the attributes of the graph from the anonymous hash $attr.
1852 NOTE: any attributes beginning with an underscore ("_") are
1854 reserved for the internal use of the Graph module.
1855 get_graph_attributes
1857 $attr = $g->get_graph_attributes()
1858 Return all the attributes of the graph as an anonymous hash.
1860 get_graph_attribute_names
1862 @name = $g->get_graph_attribute_names()
1863 Return the names of graph attributes.
1865 get_graph_attribute_values
1867 @value = $g->get_graph_attribute_values()
1868 Return the values of graph attributes.
1870 has_graph_attributes
1872 $g->has_graph_attributes()
1873 Return true if the graph has any attributes, false if not.
1875 delete_graph_attributes
1877 $g->delete_graph_attributes()
1878 Delete all the attributes of the named graph.
1880 Weighted
1882 As convenient shortcuts the following methods add, query, and
1883 manipulate the attribute "weight" with the specified value to the
1884 respective Graph elements.
1885 add_weighted_edge
1887 $g->add_weighted_edge($u, $v, $weight)
1888 add_weighted_edges
1890 $g->add_weighted_edges($u1, $v1, $weight1, ...)
1891 add_weighted_path
1893 $g->add_weighted_path($v1, $weight1, $v2, $weight2, $v3, ...)
1894 add_weighted_vertex
1896 $g->add_weighted_vertex($v, $weight)
1897 add_weighted_vertices
1899 $g->add_weighted_vertices($v1, $weight1, $v2, $weight2, ...)
1900 delete_edge_weight
1902 $g->delete_edge_weight($u, $v)
1903 delete_vertex_weight
1905 $g->delete_vertex_weight($v)
1906 get_edge_weight
1908 $g->get_edge_weight($u, $v)
1909 get_vertex_weight
1911 $g->get_vertex_weight($v)
1912 has_edge_weight
1914 $g->has_edge_weight($u, $v)
1915 has_vertex_weight
1917 $g->has_vertex_weight($v)
1918 set_edge_weight
1920 $g->set_edge_weight($u, $v, $weight)
1921 set_vertex_weight
1923 $g->set_vertex_weight($v, $weight)
1924 Isomorphism
1926 Two graphs being isomorphic means that they are structurally the same
1927 graph, the difference being that the vertices might have been renamed
1928 or substituted. For example in the below example $g0 and $g1 are
1929 isomorphic: the vertices "b c d" have been renamed as "z x y".
1930 $g0 = Graph->new;
1932 $g0->add_edges(qw(a b a c c d));
1933 $g1 = Graph->new;
1934 $g1->add_edges(qw(a x x y a z));
1935 In the general case determining isomorphism is NP-hard, in other words,
1937 really hard (time-consuming), no other ways of solving the problem are
1938 known than brute force check of of all the possibilities (with possible
1939 optimization tricks, of course, but brute force still rules at the end
1940 of the day).
1941 A very rough guess at whether two graphs could be isomorphic is
1943 possible via the method
1944 could_be_isomorphic
1946 $g0->could_be_isomorphic($g1)
1947 If the graphs do not have the same number of vertices and edges, false
1949 is returned. If the distribution of in-degrees and out-degrees at the
1950 vertices of the graphs does not match, false is returned. Otherwise,
1951 true is returned.
1952 What is actually returned is the maximum number of possible isomorphic
1954 graphs between the two graphs, after the above sanity checks have been
1955 conducted. It is basically the product of the factorials of the
1956 absolute values of in-degrees and out-degree pairs at each vertex, with
1957 the isolated vertices ignored (since they could be reshuffled and
1958 renamed arbitrarily). Note that for large graphs the product of these
1959 factorials can overflow the maximum presentable number (the floating
1960 point number) in your computer (in Perl) and you might get for example
1961 Infinity as the result.
1962 Miscellaneous
1964 betweenness
1965 %b = $g->betweenness
1966 Returns a map of vertices to their Freeman's betweennesses:
1968 C_b(v) = \sum_{s \neq v \neq t \in V} \frac{\sigma_{s,t}(v)}{\sigma_{s,t}}
1970 It is described in:
1972 Freeman, A set of measures of centrality based on betweenness, http://links.jstor.org/sici?sici=0038-0431(197703)40%3A1%3C35%3AASOMOC%3E2.0.CO%3B2-H
1974 and based on the algorithm from:
1976 "A Faster Algorithm for Betweenness Centrality"
1978 clustering_coefficient
1980 $gamma = $g->clustering_coefficient()
1981 ($gamma, %clustering) = $g->clustering_coefficient()
1982 Returns the clustering coefficient gamma as described in
1984 Duncan J. Watts and Steven Strogatz, Collective dynamics of 'small-world' networks, http://tam.cornell.edu/SS_nature_smallworld.pdf
1986 In scalar context returns just the average gamma, in list context
1988 returns the average gamma and a hash of vertices to clustering
1989 coefficients.
1990 subgraph_by_radius
1992 $s = $g->subgraph_by_radius($n, $radius);
1993 Returns a subgraph representing the ball of $radius around node $n
1995 (breadth-first search).
1996 The "expect" methods can be used to test a graph and croak if the graph
1998 is not as expected.
1999 expect_acyclic
2001 expect_dag
2002 expect_directed
2003 expect_multiedged
2004 expect_multivertexed
2005 expect_non_multiedged
2006 expect_non_multivertexed
2007 expect_undirected
2008 In many algorithms it is useful to have a value representing the
2010 infinity. The Graph provides (and itself uses):
2011 Infinity
2013 (Not exported, use Graph::Infinity explicitly)
2014 Size Requirements
2016 A graph takes up at least 1172 bytes of memory.
2017 A vertex takes up at least 100 bytes of memory.
2019 An edge takes up at least 400 bytes of memory.
2021 (A Perl scalar value takes 16 bytes, or 12 bytes if it's a reference.)
2023 These size approximations are very approximate and optimistic (they are
2025 based on total_size() of Devel::Size). In real life many factors
2026 affect these numbers, for example how Perl is configured. The numbers
2027 are for a 32-bit platform and for Perl 5.8.8.
2028 Roughly, the above numbers mean that in a megabyte of memory you can
2030 fit for example a graph of about 1000 vertices and about 2500 edges.
2031 Hyperedges, hypervertices, hypergraphs
2033 BEWARE: this is a rather thinly tested feature, and the theory is even
2034 less so. Do not expect this to stay as it is (or at all) in future
2035 releases.
2036 NOTE: most usual graph algorithms (and basic concepts) break horribly
2038 (or at least will look funny) with these hyperthingies. Caveat emptor.
2039 Hyperedges are edges that connect a number of vertices different from
2041 the usual two.
2042 Hypervertices are vertices that consist of a number of vertices
2044 different from the usual one.
2045 Note that for hypervertices there is an asymmetry: when adding
2047 hypervertices, the single vertices are also implicitly added.
2048 Hypergraphs are graphs with hyperedges.
2050 To enable hyperness when constructing Graphs use the "hyperedged" and
2052 "hypervertexed" attributes:
2053 my $h = Graph->new(hyperedged => 1, hypervertexed => 1);
2055 To add hypervertexes, either explicitly use more than one vertex (or,
2057 indeed, no vertices) when using add_vertex()
2058 $h->add_vertex("a", "b")
2060 $h->add_vertex()
2061 or implicitly with array references when using add_edge()
2063 $h->add_edge(["a", "b"], "c")
2065 $h->add_edge()
2066 Testing for existence and deletion of hypervertices and hyperedges
2068 works similarly.
2069 To test for hyperness of a graph use the
2071 is_hypervertexed
2073 hypervertexed
2074 $g->is_hypervertexed
2075 $g->hypervertexed
2076 is_hyperedged
2078 hyperedged
2079 $g->is_hyperedged
2080 $g->hyperedged
2081 Since hypervertices consist of more than one vertex:
2083 vertices_at
2085 $g->vertices_at($v)
2086 Return the vertices at the vertex. This may return just the vertex or
2088 also other vertices.
2089 To go with the concept of undirected in normal (non-hyper) graphs,
2091 there is a similar concept of omnidirected (this is my own coinage,
2092 "all-directions") for hypergraphs, and you can naturally test for it by
2093 is_omnidirected
2095 omnidirected
2096 is_omniedged
2097 omniedged
2098 $g->is_omniedged
2099 $g->omniedged
2101 $g->is_omnidirected
2103 $g->omnidirected
2105 Return true if the graph is omnidirected (edges have no direction),
2107 false if not.
2108 You may be wondering why on earth did I make up this new concept, why
2110 didn't the "undirected" work for me? Well, because of this:
2111 $g = Graph->new(hypervertexed => 1, omnivertexed => 1);
2113 That's right, vertices can be omni, too - and that is indeed the
2115 default. You can turn it off and then $g->add_vertex(qw(a b)) no more
2116 means adding also the (hyper)vertex qw(b a). In other words, the
2117 "directivity" is orthogonal to (or independent of) the number of
2118 vertices in the vertex/edge.
2119 is_omnivertexed
2121 omnivertexed
2122 Another oddity that fell out of the implementation is the uniqueness
2124 attribute, that comes naturally in "uniqedged" and "uniqvertexed"
2125 flavours. It does what it sounds like, to unique or not the vertices
2126 participating in edges and vertices (is the hypervertex qw(a b a) the
2127 same as the hypervertex qw(a b), for example). Without too much
2128 explanation:
2129 is_uniqedged
2131 uniqedged
2132 is_uniqvertexed
2133 uniqvertexed
2134 Backward compatibility with Graph 0.2
2136 The Graph 0.2 (and 0.2xxxx) had the following features
2137 · vertices() always sorted the vertex list, which most of the time is
2139 unnecessary and wastes CPU.
2140 · edges() returned a flat list where the begin and end vertices of
2142 the edges were intermingled: every even index had an edge begin
2143 vertex, and every odd index had an edge end vertex. This had the
2144 unfortunate consequence of "scalar(@e = edges)" being twice the
2145 number of edges, and complicating any algorithm walking through the
2146 edges.
2147 · The vertex list returned by edges() was sorted, the primary key
2149 being the edge begin vertices, and the secondary key being the edge
2150 end vertices.
2151 · The attribute API was oddly position dependent and dependent on the
2153 number of arguments. Use ..._graph_attribute(),
2154 ..._vertex_attribute(), ..._edge_attribute() instead.
2155 In future releases of Graph (any release after 0.50) the 0.2xxxx
2157 compatibility will be removed. Upgrade your code now.
2158 If you want to continue using these (mis)features you can use the
2160 "compat02" flag when creating a graph:
2161 my $g = Graph->new(compat02 => 1);
2163 This will change the vertices() and edges() appropriately. This,
2165 however, is not recommended, since it complicates all the code using
2166 vertices() and edges(). Instead it is recommended that the
2167 vertices02() and edges02() methods are used. The corresponding new
2168 style (unsorted, and edges() returning a list of references) methods
2169 are called vertices05() and edges05().
2170 To test whether a graph has the compatibility turned on
2172 is_compat02
2174 compat02
2175 $g->is_compat02
2176 $g->compat02
2177 The following are not backward compatibility methods, strictly
2179 speaking, because they did not exist before.
2180 edges02
2182 Return the edges as a flat list of vertices, elements at even
2183 indices being the start vertices and elements at odd indices being
2184 the end vertices.
2185 edges05
2187 Return the edges as a list of array references, each element
2188 containing the vertices of each edge. (This is not a backward
2189 compatibility interface as such since it did not exist before.)
2190 vertices02
2192 Return the vertices in sorted order.
2193 vertices05
2195 Return the vertices in random order.
2196 For the attributes the recommended way is to use the new API.
2198 Do not expect new methods to work for compat02 graphs.
2200 The following compatibility methods exist:
2202 has_attribute
2204 has_attributes
2205 get_attribute
2206 get_attributes
2207 set_attribute
2208 set_attributes
2209 delete_attribute
2210 delete_attributes
2211 Do not use the above, use the new attribute interfaces instead.
2212 vertices_unsorted
2214 Alias for vertices() (or rather, vertices05()) since the vertices()
2215 now always returns the vertices in an unsorted order. You can also
2216 use the unsorted_vertices import, but only with a true value (false
2217 values will cause an error).
2218 density_limits
2220 my ($sparse, $dense, $complete) = $g->density_limits;
2221 Return the "density limits" used to classify graphs as "sparse" or
2223 "dense". The first limit is C/4 and the second limit is 3C/4,
2224 where C is the number of edges in a complete graph (the last
2225 "limit").
2226 density
2228 my $density = $g->density;
2229 Return the density of the graph, the ratio of the number of edges
2231 to the number of edges in a complete graph.
2232 vertex
2234 my $v = $g->vertex($v);
2235 Return the vertex if the graph has the vertex, undef otherwise.
2237 out_edges
2239 in_edges
2240 edges($v)
2241 This is now called edges_at($v).
2242 DIAGNOSTICS
2244 · Graph::...Map...: arguments X expected Y ...
2245 If you see these (more user-friendly error messages should have
2247 been triggered above and before these) please report any such
2248 occurrences, but in general you should be happy to see these since
2249 it means that an attempt to call something with a wrong number of
2250 arguments was caught in time.
2251 · Graph::add_edge: graph is not hyperedged ...
2253 Maybe you used add_weighted_edge() with only the two vertex
2255 arguments.
2256 · Not an ARRAY reference at lib/Graph.pm ...
2258 One possibility is that you have code based on Graph 0.2xxxx that
2260 assumes Graphs being blessed hash references, possibly also
2261 assuming that certain hash keys are available to use for your own
2262 purposes. In Graph 0.50 none of this is true. Please do not
2263 expect any particular internal implementation of Graphs. Use
2264 inheritance and graph/vertex/edge attributes instead.
2265 Another possibility is that you meant to have objects (blessed
2267 references) as graph vertices, but forgot to use "refvertexed" (see
2268 "refvertexed") when creating the graph.
2269 POSSIBLE FUTURES
2271 A possible future direction is a new graph module written for speed:
2272 this may very possibly mean breaking or limiting some of the APIs or
2273 behaviour as compared with this release of the module.
2274 What definitely won't happen in future releases is carrying over the
2276 Graph 0.2xxxx backward compatibility API.
2277
2279 All bad terminology, bugs, and inefficiencies are naturally mine, all
2280 mine, and not the fault of the below.
2281 Thanks to Nathan Goodman and Andras Salamon for bravely betatesting my
2283 pre-0.50 code. If they missed something, that was only because of my
2284 fiendish code.
2285 The following literature for algorithms and some test cases:
2287 · Algorithms in C, Third Edition, Part 5, Graph Algorithms, Robert
2289 Sedgewick, Addison Wesley
2290 · Introduction to Algorithms, First Edition, Cormen-Leiserson-Rivest,
2292 McGraw Hill
2293 · Graphs, Networks and Algorithms, Dieter Jungnickel, Springer
2295
2297 Persistent/Serialized graphs? You want to read/write Graphs? See the
2298 Graph::Reader and Graph::Writer in CPAN.
2299
2301 Jarkko Hietaniemi jhi@iki.fi
2302
2304 This module is licensed under the same terms as Perl itself.
2305perl v5.12.0 2009-01-17 Graph(3)