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 any sort of graphics, business or other‐
35 wise.
36 Description
38 Instead, this module is for creating abstract data structures called
40 graphs, and for doing various operations on those.
41 Perl 5.6.0 minimum
43 The implementation depends on a Perl feature called "weak references"
45 and Perl 5.6.0 was the first to have those.
46 Constructors
48 new Create an empty graph.
50 Graph->new(%options)
52 The options are a hash with option names as the hash keys and the
53 option values as the hash values.
54 The following options are available:
56 * directed
58 A boolean option telling that a directed graph should be
60 created. Often somewhat redundant because a directed graph
61 is the default for the Graph class or one could simply use
62 the "new()" constructor of the Graph::Directed class.
63 You can test the directness of a graph with
65 $g->is_directed() and $g->is_undirected().
66 * undirected
68 A boolean option telling that an undirected graph should be
70 created. One could also use the "new()" constructor the
71 Graph::Undirected class instead.
72 Note that while often it is possible to think undirected
74 graphs as bidirectional graphs, or as directed graphs with
75 edges going both ways, in this module directed graphs and
76 undirected graphs are two different things that often
77 behave differently.
78 You can test the directness of a graph with
80 $g->is_directed() and $g->is_undirected().
81 * refvertexed
83 If you want to use references (including Perl objects) as
85 vertices.
86 * unionfind
88 If the graph is undirected, you can specify the "unionfind"
90 parameter to use the so-called union-find scheme to speed
91 up the computation of connected components of the graph
92 (see "is_connected", "connected_components", "con‐
93 nected_component_by_vertex", "connected_compo‐
94 nent_by_index", and "same_connected_components"). If
95 "unionfind" is used, adding edges (and vertices) becomes
96 slower, but connectedness queries become faster. You can
97 test a graph for "union-findness" with
98 has_union_find
100 has_union_find
101 * vertices
103 An array reference of vertices to add.
105 * edges
107 An array reference of array references of edge vertices to
109 add.
110 copy
112 copy_graph
113 my $c = $g->copy_graph;
114 Create a shallow copy of the structure (vertices and edges) of the
116 graph. If you want a deep copy that includes attributes, see
117 "deep_copy". The copy will have the same directedness as the orig‐
118 inal.
119 deep_copy
121 deep_copy_graph
122 my $c = $g->deep_copy_graph;
123 Create a deep copy of the graph (vertices, edges, and attributes)
125 of the graph. If you want a shallow copy that does not include
126 attributes, see "copy". (Uses Data::Dumper behind the scenes.
127 Note that copying code references only works with Perls 5.8 or
128 later, and even then only if B::Deparse can reconstruct your code.)
129 undirected_copy
131 undirected_copy_graph
132 my $c = $g->undirected_copy_graph;
133 Create an undirected shallow copy (vertices and edges) of the
135 directed graph so that for any directed edge (u, v) there is an
136 undirected edge (u, v).
137 directed_copy
139 directed_copy_graph
140 my $c = $g->directed_copy_graph;
141 Create a directed shallow copy (vertices and edges) of the undi‐
143 rected graph so that for any undirected edge (u, v) there are two
144 directed edges (u, v) and (v, u).
145 transpose
147 transpose_graph
148 my $t = $g->transpose_graph;
149 Create a directed shallow transposed copy (vertices and edges) of
151 the directed graph so that for any directed edge (u, v) there is a
152 directed edge (v, u).
153 You can also transpose a single edge with
155 transpose_edge
157 $g->transpose_edge($u, $v)
158 complete_graph
160 complete
161 my $c = $g->complete_graph;
162 Create a complete graph that has the same vertices as the original
164 graph. A complete graph has an edge between every pair of ver‐
165 tices.
166 complement_graph
168 complement
169 my $c = $g->complement_graph;
170 Create a complement graph that has the same vertices as the origi‐
172 nal graph. A complement graph has an edge (u,v) if and only if the
173 original graph does not have edge (u,v).
174 See also "random_graph" for a random constructor.
176 Basics
178 add_vertex
180 $g->add_vertex($v)
181 Add the vertex to the graph. Returns the graph.
183 By default idempotent, but a graph can be created countvertexed.
185 A vertex is also known as a node.
187 Adding "undef" as vertex is not allowed.
189 Note that unless you have isolated vertices (or countvertexed ver‐
191 tices), you do not need to explicitly use "add_vertex" since
192 "add_edge" will implicitly add its vertices.
193 add_edge
195 $g->add_edge($u, $v)
196 Add the edge to the graph. Implicitly first adds the vertices if
198 the graph does not have them. Returns the graph.
199 By default idempotent, but a graph can be created countedged.
201 An edge is also known as an arc.
203 has_vertex
205 $g->has_vertex($v)
206 Return true if the vertex exists in the graph, false otherwise.
208 has_edge
210 $g->has_edge($u, $v)
211 Return true if the edge exists in the graph, false otherwise.
213 delete_vertex
215 $g->delete_vertex($v)
216 Delete the vertex from the graph. Returns the graph, even if the
218 vertex did not exist in the graph.
219 If the graph has been created multivertexed or countvertexed and a
221 vertex has been added multiple times, the vertex will require at
222 least an equal number of deletions to become completely deleted.
223 delete_vertices
225 $g->delete_vertices($v1, $v2, ...)
226 Delete the vertices from the graph. Returns the graph.
228 If the graph has been created multivertexed or countvertexed and a
230 vertex has been added multiple times, the vertex will require at
231 least an equal number of deletions to become completely deleteted.
232 delete_edge
234 $g->delete_edge($u, $v)
235 Delete the edge from the graph. Returns the graph, even if the
237 edge did not exist in the graph.
238 If the graph has been created multivertexed or countedged and an
240 edge has been added multiple times, the edge will require at least
241 an equal number of deletions to become completely deleted.
242 delete_edges
244 $g->delete_edges($u1, $v1, $u2, $v2, ...)
245 Delete the edges from the graph. Returns the graph.
247 If the graph has been created multivertexed or countedged and an
249 edge has been added multiple times, the edge will require at least
250 an equal number of deletions to become completely deleted.
251 Displaying
253 Graphs have stringification overload, so you can do things like
255 print "The graph is $g\n"
257 One-way (directed, unidirected) edges are shown as '-', two-way (undi‐
259 rected, bidirected) edges are shown as '='. If you want to, you can
260 call the stringification via the method
261 stringify
263 Comparing
265 Testing for equality can be done either by the overloaded "eq" operator
267 $g eq "a-b,a-c,d"
269 or by the method
271 eq
273 $g->eq("a-b,a-c,d")
274 The equality testing compares the stringified forms, and therefore it
276 assumes total equality, not isomorphism: all the vertices must be named
277 the same, and they must have identical edges between them.
278 For unequality there are correspondingly the overloaded "ne" operator
280 and the method
281 ne
283 $g->ne("a-b,a-c,d")
284 See also "Isomorphism".
286 Paths and Cycles
288 Paths and cycles are simple extensions of edges: paths are edges start‐
290 ing from where the previous edge ended, and cycles are paths returning
291 back to the start vertex of the first edge.
292 add_path
294 $g->add_path($a, $b, $c, ..., $x, $y, $z)
295 Add the edges $a-$b, $b-$c, ..., $x-$y, $y-$z to the graph.
297 Returns the graph.
298 has_path
300 $g->has_path($a, $b, $c, ..., $x, $y, $z)
301 Return true if the graph has all the edges $a-$b, $b-$c, ...,
303 $x-$y, $y-$z, false otherwise.
304 delete_path
306 $g->delete_path($a, $b, $c, ..., $x, $y, $z)
307 Delete all the edges edges $a-$b, $b-$c, ..., $x-$y, $y-$z (regard‐
309 less of whether they exist or not). Returns the graph.
310 add_cycle
312 $g->add_cycle($a, $b, $c, ..., $x, $y, $z)
313 Add the edges $a-$b, $b-$c, ..., $x-$y, $y-$z, and $z-$a to the
315 graph. Returns the graph.
316 has_cycle
318 $g->has_cycle($a, $b, $c, ..., $x, $y, $z)
319 Return true if the graph has all the edges $a-$b, $b-$c, ...,
321 $x-$y, $y-$z, and $z-$a, false otherwise.
322 NOTE: This does not detect cycles, see "has_a_cycle" and
324 "find_a_cycle".
325 delete_cycle
327 $g->delete_cycle($a, $b, $c, ..., $x, $y, $z)
328 Delete all the edges edges $a-$b, $b-$c, ..., $x-$y, $y-$z, and
330 $z-$a (regardless of whether they exist or not). Returns the
331 graph.
332 has_a_cycle
334 $g->has_a_cycle
335 Returns true if the graph has a cycle, false if not.
337 find_a_cycle
339 $g->find_a_cycle
340 Returns a cycle if the graph has one (as a list of vertices), an
342 empty list if no cycle can be found.
343 Note that this just returns the vertices of a cycle: not any par‐
345 ticular cycle, just the first one it finds. A repeated call might
346 find the same cycle, or it might find a different one, and you can‐
347 not call this repeatedly to find all the cycles.
348 Graph Types
350 is_simple_graph
352 $g->is_simple_graph
353 Return true if the graph has no multiedges, false otherwise.
355 is_pseudo_graph
357 $g->is_pseudo_graph
358 Return true if the graph has any multiedges or any self-loops,
360 false otherwise.
361 is_multi_graph
363 $g->is_multi_graph
364 Return true if the graph has any multiedges but no self-loops,
366 false otherwise.
367 is_directed_acyclic_graph
369 is_dag
370 $g->is_directed_acyclic_graph
371 $g->is_dag
372 Return true if the graph is directed and acyclic, false otherwise.
374 is_cyclic
376 $g->is_cyclic
377 Return true if the graph is cyclic (contains at least one cycle).
379 (This is identical to "has_a_cycle".)
380 To find at least that one cycle, see "find_a_cycle".
382 is_acyclic
384 Return true if the graph is acyclic (does not contain any cycles).
385 To find a cycle, use find_a_cycle.
387 Transitivity
389 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 Graph::Transi‐
416 tiveClosure::Matrix for more information.
417 Mutators
419 add_vertices
421 $g->add_vertices('d', 'e', 'f')
422 Add zero or more vertices to the graph.
424 add_edges
426 $g->add_edges(['d', 'e'], ['f', 'g'])
427 $g->add_edges(qw(d e f g));
428 Add zero or more edges to the graph. The edges are specified as a
430 list of array references, or as a list of vertices where the even
431 (0th, 2nd, 4th, ...) items are start vertices and the odd (1st,
432 3rd, 5th, ...) are the corresponding end vertices.
433 Accessors
435 is_directed
437 directed
438 $g->is_directed()
439 $g->directed()
440 Return true if the graph is directed, false otherwise.
442 is_undirected
444 undirected
445 $g->is_undirected()
446 $g->undirected()
447 Return true if the graph is undirected, false otherwise.
449 is_refvertexed
451 refvertexed
452 Return true if the graph can handle references (including Perl
453 objects) as vertices.
454 vertices
456 my $V = $g->vertices
457 my @V = $g->vertices
458 In scalar context, return the number of vertices in the graph. In
460 list context, return the vertices, in no particular order.
461 has_vertices
463 $g->has_vertices()
464 Return true if the graph has any vertices, false otherwise.
466 edges
468 my $E = $g->edges
469 my @E = $g->edges
470 In scalar context, return the number of edges in the graph. In
472 list context, return the edges, in no particular order. The edges
473 are returned as anonymous arrays listing the vertices.
474 has_edges
476 $g->has_edges()
477 Return true if the graph has any edges, false otherwise.
479 is_connected
481 $g->is_connected
482 For an undirected graph, return true is the graph is connected,
484 false otherwise. Being connected means that from every vertex it
485 is possible to reach every other vertex.
486 If the graph has been created with a true "unionfind" parameter,
488 the time complexity is (essentially) O(V), otherwise O(V log V).
489 See also "connected_components", "connected_component_by_index",
491 "connected_component_by_vertex", and "same_connected_components",
492 and "biconnectivity".
493 For directed graphs, see "is_strongly_connected" and
495 "is_weakly_connected".
496 connected_components
498 @cc = $g->connected_components()
499 For an undirected graph, returns the vertices of the connected com‐
501 ponents of the graph as a list of anonymous arrays. The ordering
502 of the anonymous arrays or the ordering of the vertices inside the
503 anonymous arrays (the components) is undefined.
504 For directed graphs, see "strongly_connected_components" and
506 "weakly_connected_components".
507 connected_component_by_vertex
509 $i = $g->connected_component_by_vertex($v)
510 For an undirected graph, return an index identifying the connected
512 component the vertex belongs to, the indexing starting from zero.
513 For the inverse, see "connected_component_by_index".
515 If the graph has been created with a true "unionfind" parameter,
517 the time complexity is (essentially) O(1), otherwise O(V log V).
518 See also "biconnectivity".
520 For directed graphs, see "strongly_connected_component_by_vertex"
522 and "weakly_connected_component_by_vertex".
523 connected_component_by_index
525 @v = $g->connected_component_by_index($i)
526 For an undirected graph, return the vertices of the ith connected
528 component, the indexing starting from zero. The order of vertices
529 is undefined, while the order of the connected components is same
530 as from connected_components().
531 For the inverse, see "connected_component_by_vertex".
533 For directed graphs, see "strongly_connected_component_by_index"
535 and "weakly_connected_component_by_index".
536 same_connected_components
538 $g->same_connected_components($u, $v, ...)
539 For an undirected graph, return true if the vertices are in the
541 same connected component.
542 If the graph has been created with a true "unionfind" parameter,
544 the time complexity is (essentially) O(1), otherwise O(V log V).
545 For directed graphs, see "same_strongly_connected_components" and
547 "same_weakly_connected_components".
548 connected_graph
550 $cg = $g->connected_graph
551 For an undirected graph, return its connected graph.
553 connectivity_clear_cache
555 $g->connectivity_clear_cache
556 See "Clearing cached results".
558 See "Connected Graphs and Their Components" for further discussion.
560 biconnectivity
562 my ($ap, $bc, $br) = $g->biconnectivity
563 For an undirected graph, return the various biconnectivity compo‐
565 nents of the graph: the articulation points (cut vertices), bicon‐
566 nected components, and bridges.
567 Note: currently only handles connected graphs.
569 is_biconnected
571 $g->is_biconnected
572 For an undirected graph, return true if the graph is biconnected
574 (if it has no articulation points, also known as cut vertices).
575 is_edge_connected
577 $g->is_edge_connected
578 For an undirected graph, return true if the graph is edge-connected
580 (if it has no bridges).
581 is_edge_separable
583 $g->is_edge_separable
584 For an undirected graph, return true if the graph is edge-separable
586 (if it has bridges).
587 articulation_points
589 cut_vertices
590 $g->articulation_points
591 For an undirected graph, return the articulation points (cut ver‐
593 tices) of the graph as a list of vertices. The order is 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 ver‐
601 tices 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 bicon‐
609 nected component the vertex belongs to, the indexing starting from
610 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 con‐
666 nected component the vertex belongs to, the indexing starting from
667 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 "bicon‐
674 nected_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 com‐
680 ponent, 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 order‐
722 ing of the anonymous arrays or the ordering of the vertices inside
723 the anonymous arrays (the components) is undefined.
724 See also "strongly_connected_components".
726 For undirected graphs, see "connected_components" or "bicon‐
728 nected_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 con‐
734 nected component the vertex belongs to, the indexing starting from
735 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 con‐
746 nected component, the indexing starting zero. The order of ver‐
747 tices within a component is undefined, while the order of the
748 weakly connected components is same as from weakly_connected_compo‐
749 nents().
750 For the inverse, see "weakly_connected_component_by_vertex".
752 For undirected graphs, see connected_component_by_index and bicon‐
754 nected_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 compo‐
760 nent.
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 "bicon‐
768 nected_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 "bicon‐
781 nected_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 "bicon‐
793 nected_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 succes‐
800 sors: this definition means that isolated vertices are not sink
801 vertices. If you want also isolated vertices, use is_successor‐
802 less_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 prede‐
809 cessors: the definition means that isolated vertices are not source
810 vertices. If you want also isolated vertices, use is_predecessor‐
811 less_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 defini‐
870 tion 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 def‐
877 inition 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 neighbors
897 neighbours
898 Return the neighbo(u)ring vertices. Also known as the adjacent
899 vertices.
900 predecessorful_vertices
902 @v = $g->predecessorful_vertices()
903 Return the predecessorful vertices of the graph. In scalar context
905 return the number of predecessorful vertices.
906 predecessorless_vertices
908 @v = $g->predecessorless_vertices()
909 Return the predecessorless vertices of the graph. In scalar con‐
911 text return the number of predecessorless vertices.
912 predecessors
914 @s = $g->predecessors($v)
915 Return the immediate predecessor vertices of the vertex.
917 isolated_vertices
919 @v = $g->isolated_vertices()
920 Return the isolated vertices of the graph. In scalar context
922 return the number of isolated vertices. See "is_isolated_vertex"
923 for the definition of an isolated vertex.
924 interior_vertices
926 @v = $g->interior_vertices()
927 Return the interior vertices of the graph. In scalar context
929 return the number of interior vertices. See "is_interior_vertex"
930 for the definition of an interior vertex.
931 exterior_vertices
933 @v = $g->exterior_vertices()
934 Return the exterior vertices of the graph. In scalar context
936 return the number of exterior vertices. See "is_exterior_vertex"
937 for the definition of an exterior vertex.
938 self_loop_vertices
940 @v = $g->self_loop_vertices()
941 Return the self-loop vertices of the graph. In scalar context
943 return the number of self-loop vertices. See "is_self_loop_vertex"
944 for the definition of a self-loop vertex.
945 Connected Graphs and Their Components
947 In this discussion connected graph refers to any of connected graphs,
949 biconnected graphs, and strongly connected graphs.
950 NOTE: if the vertices of the original graph are Perl objects, (in other
952 words, references, so you must be using "refvertexed") the vertices of
953 the connected graph are NOT by default usable as Perl objects because
954 they are blessed into a package with a rather unusable name.
955 By default, the vertex names of the connected graph are formed from the
957 names of the vertices of the original graph by (alphabetically sorting
958 them and) concatenating their names with "+". The vertex attribute
959 "subvertices" is also used to store the list (as an array reference) of
960 the original vertices. To change the 'supercomponent' vertex names and
961 the whole logic of forming these supercomponents use the "super_compo‐
962 nent") option to the method calls:
963 $g->connected_graph(super_component => sub { ... })
965 $g->biconnected_graph(super_component => sub { ... })
966 $g->strongly_connected_graph(super_component => sub { ... })
967 The subroutine reference gets the 'subcomponents' (the vertices of the
969 original graph) as arguments, and it is supposed to return the new
970 supercomponent vertex, the "stringified" form of which is used as the
971 vertex name.
972 Degree
974 A vertex has a degree based on the number of incoming and outgoing
976 edges. This really makes sense only for directed graphs.
977 degree
979 vertex_degree
980 $d = $g->degree($v)
981 $d = $g->vertex_degree($v)
982 For directed graphs: the in-degree minus the out-degree at the ver‐
984 tex. For undirected graphs: the number of edges at the vertex.
985 in_degree
987 $d = $g->in_degree($v)
988 The number of incoming edges at the vertex.
990 out_degree
992 $o = $g->out_degree($v)
993 The number of outgoing edges at the vertex.
995 average_degree
997 my $ad = $g->average_degree;
998 Return the average degree taken over all vertices.
1000 Related methods are
1002 edges_at
1004 @e = $g->edges_at($v)
1005 The union of edges from and edges to at the vertex.
1007 edges_from
1009 @e = $g->edges_from($v)
1010 The edges leaving the vertex.
1012 edges_to
1014 @e = $g->edges_to($v)
1015 The edges entering the vertex.
1017 See also "average_degree".
1019 Counted Vertices
1021 Counted vertices are vertices with more than one instance, normally
1023 adding vertices is idempotent. To enable counted vertices on a graph,
1024 give the "countvertexed" parameter a true value
1025 use Graph;
1027 my $g = Graph->new(countvertexed => 1);
1028 To find out how many times the vertex has been added:
1030 get_vertex_count
1032 my $c = $g->get_vertex_count($v);
1033 Return the count of the vertex, or undef if the vertex does not
1035 exist.
1036 Multiedges, Multivertices, Multigraphs
1038 Multiedges are edges with more than one "life", meaning that one has to
1040 delete them as many times as they have been added. Normally adding
1041 edges is idempotent (in other words, adding edges more than once makes
1042 no difference).
1043 There are two kinds or degrees of creating multiedges and multiver‐
1045 tices. The two kinds are mutually exclusive.
1046 The weaker kind is called counted, in which the edge or vertex has a
1048 count on it: add operations increase the count, and delete operations
1049 decrease the count, and once the count goes to zero, the edge or vertex
1050 is deleted. If there are attributes, they all are attached to the same
1051 vertex. You can think of this as the graph elements being refcounted,
1052 or reference counted, if that sounds more familiar.
1053 The stronger kind is called (true) multi, in which the edge or vertex
1055 really has multiple separate identities, so that you can for example
1056 attach different attributes to different instances.
1057 To enable multiedges on a graph:
1059 use Graph;
1061 my $g0 = Graph->new(countedged => 1);
1062 my $g0 = Graph->new(multiedged => 1);
1063 Similarly for vertices
1065 use Graph;
1067 my $g1 = Graph->new(countvertexed => 1);
1068 my $g1 = Graph->new(multivertexed => 1);
1069 You can test for these by
1071 is_countedged
1073 countedged
1074 $g->is_countedged
1075 $g->countedged
1076 Return true if the graph is countedged.
1078 is_countvertexed
1080 countvertexed
1081 $g->is_countvertexed
1082 $g->countvertexed
1083 Return true if the graph is countvertexed.
1085 is_multiedged
1087 multiedged
1088 $g->is_multiedged
1089 $g->multiedged
1090 Return true if the graph is multiedged.
1092 is_multivertexed
1094 multivertexed
1095 $g->is_multivertexed
1096 $g->multivertexed
1097 Return true if the graph is multivertexed.
1099 A multiedged (either the weak kind or the strong kind) graph is a
1101 multigraph, for which you can test with "is_multi_graph()".
1102 NOTE: The various graph algorithms do not in general work well with
1104 multigraphs (they often assume simple graphs, that is, no multiedges or
1105 loops), and no effort has been made to test the algorithms with multi‐
1106 graphs.
1107 vertices() and edges() will return the multiple elements: if you want
1109 just the unique elements, use
1110 unique_vertices
1112 unique_edges
1113 @uv = $g->unique_vertices; # unique
1114 @mv = $g->vertices; # possible multiples
1115 @ue = $g->unique_edges;
1116 @me = $g->edges;
1117 If you are using (the stronger kind of) multielements, you should use
1119 the by_id variants:
1120 add_vertex_by_id
1122 has_vertex_by_id
1123 delete_vertex_by_id
1124 add_edge_by_id
1125 has_edge_by_id
1126 delete_edge_by_id
1127 $g->add_vertex_by_id($v, $id)
1129 $g->has_vertex_by_id($v, $id)
1130 $g->delete_vertex_by_id($v, $id)
1131 $g->add_edge_by_id($u, $v, $id)
1133 $g->has_edge_by_id($u, $v, $id)
1134 $g->delete_edge_by_id($u, $v, $id)
1135 When you delete the last vertex/edge in a multivertex/edge, the whole
1137 vertex/edge is deleted. You can use add_vertex()/add_edge() on a mul‐
1138 tivertex/multiedge graph, in which case an id is generated automati‐
1139 cally. To find out which the generated id was, you need to use
1140 add_vertex_get_id
1142 add_edge_get_id
1143 $idv = $g->add_vertex_get_id($v)
1145 $ide = $g->add_edge_get_id($u, $v)
1146 To return all the ids of vertices/edges in a multivertex/multiedge, use
1148 get_multivertex_ids
1150 get_multiedge_ids
1151 $g->get_multivertex_ids($v)
1153 $g->get_multiedge_ids($u, $v)
1154 The ids are returned in random order.
1156 To find out how many times the edge has been added (this works for
1158 either kind of multiedges):
1159 get_edge_count
1161 my $c = $g->get_edge_count($u, $v);
1162 Return the count (the "countedness") of the edge, or undef if the
1164 edge does not exist.
1165 The following multi-entity utility functions exist, mirroring the non-
1167 multi vertices and edges:
1168 add_weighted_edge_by_id
1170 add_weighted_edges_by_id
1171 add_weighted_path_by_id
1172 add_weighted_vertex_by_id
1173 add_weighted_vertices_by_id
1174 delete_edge_weight_by_id
1175 delete_vertex_weight_by_id
1176 get_edge_weight_by_id
1177 get_vertex_weight_by_id
1178 has_edge_weight_by_id
1179 has_vertex_weight_by_id
1180 set_edge_weight_by_id
1181 set_vertex_weight_by_id
1182 Topological Sort
1184 topological_sort
1186 toposort
1187 my @ts = $g->topological_sort;
1188 Return the vertices of the graph sorted topologically. Note that
1190 there may be several possible topological orderings; one of them is
1191 returned.
1192 If the graph contains a cycle, a fatal error is thrown, you can
1194 either use "eval" to trap that, or supply the "empty_if_cyclic"
1195 argument with a true value
1196 my @ts = $g->topological_sort(empty_if_cyclic => 1);
1198 in which case an empty array is returned if the graph is cyclic.
1200 Minimum Spanning Trees (MST)
1202 Minimum Spanning Trees or MSTs are tree subgraphs derived from an undi‐
1204 rected graph. MSTs "span the graph" (covering all the vertices) using
1205 as lightly weighted (hence the "minimum") edges as possible.
1206 MST_Kruskal
1208 $mstg = $g->MST_Kruskal;
1209 Returns the Kruskal MST of the graph.
1211 MST_Prim
1213 $mstg = $g->MST_Prim(%opt);
1214 Returns the Prim MST of the graph.
1216 You can choose the first vertex with $opt{ first_root }.
1218 MST_Dijkstra
1220 minimum_spanning_tree
1221 $mstg = $g->MST_Dijkstra;
1222 $mstg = $g->minimum_spanning_tree;
1223 Aliases for MST_Prim.
1225 Single-Source Shortest Paths (SSSP)
1227 Single-source shortest paths, also known as Shortest Path Trees (SPTs).
1229 For either a directed or an undirected graph, return a (tree) subgraph
1230 that from a single start vertex (the "single source") travels the
1231 shortest possible paths (the paths with the lightest weights) to all
1232 the other vertices. Note that the SSSP is neither reflexive (the
1233 shortest paths do not include the zero-length path from the source ver‐
1234 tex to the source vertex) nor transitive (the shortest paths do not
1235 include transitive closure paths). If no weight is defined for an
1236 edge, 1 (one) is assumed.
1237 SPT_Dijkstra
1239 $sptg = $g->SPT_Dijkstra($root)
1240 $sptg = $g->SPT_Dijkstra(%opt)
1241 Return as a graph the the single-source shortest paths of the graph
1243 using Dijkstra's algorithm. The graph cannot contain negative
1244 edges (negative edges cause the algorithm to abort with an error
1245 message "Graph::SPT_Dijkstra: edge ... is negative").
1246 You can choose the first vertex of the result with either a single
1248 vertex argument or with $opt{ first_root }, otherwise a random ver‐
1249 tex is chosen.
1250 NOTE: note that all the vertices might not be reachable from the
1252 selected (explicit or random) start vertex.
1253 The start vertex is be available as the graph attribute "SPT_Dijk‐
1255 stra_root").
1256 The result weights of vertices can be retrieved from the result
1258 graph by
1259 my $w = $sptg->get_vertex_attribute($v, 'weight');
1261 The predecessor vertex of a vertex in the result graph can be
1263 retrieved by
1264 my $u = $sptg->get_vertex_attribute($v, 'p');
1266 ("A successor vertex" cannot be retrieved as simply because a sin‐
1268 gle vertex can have several successors. You can first find the
1269 "neighbors()" vertices and then remove the predecessor vertex.)
1270 If you want to find the shortest path between two vertices, see
1272 "SP_Dijkstra".
1273 SSSP_Dijkstra
1275 single_source_shortest_paths
1276 Aliases for SPT_Dijkstra.
1277 SP_Dijkstra
1279 @path = $g->SP_Dijkstra($u, $v)
1280 Return the vertices in the shortest path in the graph $g between
1282 the two vertices $u, $v. If no path can be found, an empty list is
1283 returned.
1284 Uses SPT_Dijkstra().
1286 SPT_Dijkstra_clear_cache
1288 $g->SPT_Dijkstra_clear_cache
1289 See "Clearing cached results".
1291 SPT_Bellman_Ford
1293 $sptg = $g->SPT_Bellman_Ford(%opt)
1294 Return as a graph the single-source shortest paths of the graph
1296 using Bellman-Ford's algorithm. The graph can contain negative
1297 edges but not negative cycles (negative cycles cause the algorithm
1298 to abort with an error message "Graph::SPT_Bellman_Ford: negative
1299 cycle exists/").
1300 You can choose the start vertex of the result with either a single
1302 vertex argument or with $opt{ first_root }, otherwise a random ver‐
1303 tex is chosen.
1304 NOTE: note that all the vertices might not be reachable from the
1306 selected (explicit or random) start vertex.
1307 The start vertex is be available as the graph attribute "SPT_Bell‐
1309 man_Ford_root").
1310 The result weights of vertices can be retrieved from the result
1312 graph by
1313 my $w = $sptg->get_vertex_attribute($v, 'weight');
1315 The predecessor vertex of a vertex in the result graph can be
1317 retrieved by
1318 my $u = $sptg->get_vertex_attribute($v, 'p');
1320 ("A successor vertex" cannot be retrieved as simply because a sin‐
1322 gle vertex can have several successors. You can first find the
1323 "neighbors()" vertices and then remove the predecessor vertex.)
1324 If you want to find the shortes path between two vertices, see
1326 "SP_Bellman_Ford".
1327 SSSP_Bellman_Ford
1329 Alias for SPT_Bellman_Ford.
1330 SP_Bellman_Ford
1332 @path = $g->SP_Bellman_Ford($u, $v)
1333 Return the vertices in the shortest path in the graph $g between
1335 the two vertices $u, $v. If no path can be found, an empty list is
1336 returned.
1337 Uses SPT_Bellman_Ford().
1339 SPT_Bellman_Ford_clear_cache
1341 $g->SPT_Bellman_Ford_clear_cache
1342 See "Clearing cached results".
1344 All-Pairs Shortest Paths (APSP)
1346 For either a directed or an undirected graph, return the APSP object
1348 describing all the possible paths between any two vertices of the
1349 graph. If no weight is defined for an edge, 1 (one) is assumed.
1350 APSP_Floyd_Warshall
1352 all_pairs_shortest_paths
1353 my $apsp = $g->APSP_Floyd_Warshall(...);
1354 Return the all-pairs shortest path object computed from the graph
1356 using Floyd-Warshall's algorithm. The length of a path between two
1357 vertices is the sum of weight attribute of the edges along the
1358 shortest path between the two vertices. If no weight attribute
1359 name is specified explicitly
1360 $g->APSP_Floyd_Warshall(attribute_name => 'height');
1362 the attribute "weight" is assumed.
1364 If an edge has no defined weight attribute, the value of one is
1366 assumed when getting the attribute.
1367 Once computed, you can query the APSP object with
1369 path_length
1371 my $l = $apsp->path_length($u, $v);
1372 Return the length of the shortest path between the two ver‐
1374 tices.
1375 path_vertices
1377 my @v = $apsp->path_vertices($u, $v);
1378 Return the list of vertices along the shortest path.
1380 path_predecessor
1382 my $u = $apsp->path_predecessor($v);
1383 Returns the predecessor of vertex $v in the all-pairs
1385 shortest paths.
1386 average_path_length
1388 my $apl = $g->average_path_length; # All vertex pairs.
1389 my $apl = $g->average_path_length($u); # From $u.
1391 my $apl = $g->average_path_length($u, undef); # From $u.
1392 my $apl = $g->average_path_length($u, $v); # From $u to $v.
1394 my $apl = $g->average_path_length(undef, $v); # To $v.
1396 Return the average (shortest) path length over all the ver‐
1398 tex pairs of the graph, from a vertex, between two ver‐
1399 tices, and to a vertex.
1400 longest_path
1402 my @lp = $g->longest_path;
1403 my $lp = $g->longest_path;
1404 In scalar context return the longest shortest path length
1406 over all the vertex pairs of the graph. In list context
1407 return the vertices along a longest shortest path. Note
1408 that there might be more than one such path; this inter‐
1409 faces return a random one of them.
1410 diameter
1412 graph_diameter
1413 my $gd = $g->diameter;
1414 The longest path over all the vertex pairs is known as the
1416 graph diameter.
1417 shortest_path
1419 my @sp = $g->shortest_path;
1420 my $sp = $g->shortest_path;
1421 In scalar context return the shortest length over all the
1423 vertex pairs of the graph. In list context return the ver‐
1424 tices along a shortest path. Note that there might be more
1425 than one such path; this interface returns a random one of
1426 them.
1427 radius
1429 my $gr = $g->radius;
1430 The shortest longest path over all the vertex pairs is
1432 known as the graph radius. See also "diameter".
1433 center_vertices
1435 centre_vertices
1436 my @c = $g->center_vertices;
1437 my @c = $g->center_vertices($delta);
1438 The graph center is the set of vertices for which the ver‐
1440 tex eccentricity is equal to the graph radius. The ver‐
1441 tices are returned in random order. By specifying a delta
1442 value you can widen the criterion from strict equality
1443 (handy for non-integer edge weights).
1444 vertex_eccentricity
1446 my $ve = $g->vertex_eccentricity($v);
1447 The longest path to a vertex is known as the vertex eccen‐
1449 tricity. If the graph is unconnected, returns Inf.
1450 You can walk through the matrix of the shortest paths by using
1452 for_shortest_paths
1454 $n = $g->for_shortest_paths($callback)
1455 The number of shortest paths is returned (this should be equal
1457 to V*V). The $callback is a sub reference that receives four
1458 arguments: the transitive closure object from Graph::Transi‐
1459 tiveClosure, the two vertices, and the index to the current
1460 shortest paths (0..V*V-1).
1461 Clearing cached results
1463 For many graph algorithms there are several different but equally valid
1465 results. (Pseudo)Randomness is used internally by the Graph module to
1466 for example pick a random starting vertex, and to select random edges
1467 from a vertex.
1468 For efficiency the computed result is often cached to avoid recomputing
1470 the potentially expensive operation, and this also gives additional
1471 determinism (once a correct result has been computed, the same result
1472 will always be given).
1473 However, sometimes the exact opposite is desireable, and the possible
1475 alternative results are wanted (within the limits of the pseudorandom‐
1476 ness: not all the possible solutions are guaranteed to be returned,
1477 usually only a subset is retuned). To undo the caching, the following
1478 methods are available:
1479 · connectivity_clear_cache
1481 Affects "connected_components", "connected_component_by_vertex",
1483 "connected_component_by_index", "same_connected_components", "con‐
1484 nected_graph", "is_connected", "is_weakly_connected", "weakly_con‐
1485 nected_components", "weakly_connected_component_by_vertex",
1486 "weakly_connected_component_by_index", "same_weakly_connected_com‐
1487 ponents", "weakly_connected_graph".
1488 · biconnectivity_clear_cache
1490 Affects "biconnected_components", "biconnected_component_by_ver‐
1492 tex", "biconnected_component_by_index", "is_edge_connected",
1493 "is_edge_separable", "articulation_points", "cut_vertices",
1494 "is_biconnected", "biconnected_graph", "same_biconnected_compo‐
1495 nents", "bridges".
1496 · strong_connectivity_clear_cache
1498 Affects "strongly_connected_components", "strongly_connected_compo‐
1500 nent_by_vertex", "strongly_connected_component_by_index",
1501 "same_strongly_connected_components", "is_strongly_connected",
1502 "strongly_connected", "strongly_connected_graph".
1503 · SPT_Dijkstra_clear_cache
1505 Affects "SPT_Dijkstra", "SSSP_Dijkstra", "single_source_short‐
1507 est_paths", "SP_Dijkstra".
1508 · SPT_Bellman_Ford_clear_cache
1510 Affects "SPT_Bellman_Ford", "SSSP_Bellman_Ford", "SP_Bellman_Ford".
1512 Note that any such computed and cached results are of course always
1514 automatically discarded whenever the graph is modified.
1515 Random
1517 You can either ask for random elements of existing graphs or create
1519 random graphs.
1520 random_vertex
1522 my $v = $g->random_vertex;
1523 Return a random vertex of the graph, or undef if there are no ver‐
1525 tices.
1526 random_edge
1528 my $e = $g->random_edge;
1529 Return a random edge of the graph as an array reference having the
1531 vertices as elements, or undef if there are no edges.
1532 random_successor
1534 my $v = $g->random_successor($v);
1535 Return a random successor of the vertex in the graph, or undef if
1537 there are no successors.
1538 random_predecessor
1540 my $u = $g->random_predecessor($v);
1541 Return a random predecessor of the vertex in the graph, or undef if
1543 there are no predecessors.
1544 random_graph
1546 my $g = Graph->random_graph(%opt);
1547 Construct a random graph. The %opt must contain the "vertices"
1549 argument
1550 vertices => vertices_def
1552 where the vertices_def is one of
1554 * an array reference where the elements of the array refer‐
1556 ence are the vertices
1557 * a number N in which case the vertices will be integers
1559 0..N-1
1560 The %opt may have either of the argument "edges" or the argument
1562 "edges_fill". Both are used to define how many random edges to add to
1563 the graph; "edges" is an absolute number, while "edges_fill" is a rela‐
1564 tive number (relative to the number of edges in a complete graph, C).
1565 The number of edges can be larger than C, but only if the graph is
1566 countedged. The random edges will not include self-loops. If neither
1567 "edges" nor "edges_fill" is specified, an "edges_fill" of 0.5 is
1568 assumed.
1569 If you want repeatable randomness (what is an oxymoron?) you can use
1571 the "random_seed" option:
1572 $g = Graph->random_graph(vertices => 10, random_seed => 1234);
1574 As this uses the standard Perl srand(), the usual caveat applies: use
1576 it sparingly, and consider instead using a single srand() call at the
1577 top level of your application.
1578 The default random distribution of edges is flat, that is, any pair of
1580 vertices is equally likely to appear. To define your own distribution,
1581 use the "random_edge" option:
1582 $g = Graph->random_graph(vertices => 10, random_edge => \&d);
1584 where "d" is a code reference receiving ($g, $u, $v, $p) as parameters,
1586 where the $g is the random graph, $u and $v are the vertices, and the
1587 $p is the probability ([0,1]) for a flat distribution. It must return
1588 a probability ([0,1]) that the vertices $u and $v have an edge between
1589 them. Note that returning one for a particular pair of vertices
1590 doesn't guarantee that the edge will be present in the resulting graph
1591 because the required number of edges might be reached before that par‐
1592 ticular pair is tested for the possibility of an edge. Be very careful
1593 to adjust also "edges" or "edges_fill" so that there is a possibility
1594 of the filling process terminating.
1595 Attributes
1597 You can attach free-form attributes (key-value pairs, in effect a full
1599 Perl hash) to each vertex, edge, and the graph itself.
1600 Note that attaching attributes does slow down some other operations on
1602 the graph by a factor of three to ten. For example adding edge
1603 attributes does slow down anything that walks through all the edges.
1604 For vertex attributes:
1606 set_vertex_attribute
1608 $g->set_vertex_attribute($v, $name, $value)
1609 Set the named vertex attribute.
1611 If the vertex does not exist, the set_...() will create it, and the
1613 other vertex attribute methods will return false or empty.
1614 NOTE: any attributes beginning with an underscore/underline (_) are
1616 reserved for the internal use of the Graph module.
1617 get_vertex_attribute
1619 $value = $g->get_vertex_attribute($v, $name)
1620 Return the named vertex attribute.
1622 has_vertex_attribute
1624 $g->has_vertex_attribute($v, $name)
1625 Return true if the vertex has an attribute, false if not.
1627 delete_vertex_attribute
1629 $g->delete_vertex_attribute($v, $name)
1630 Delete the named vertex attribute.
1632 set_vertex_attributes
1634 $g->set_vertex_attributes($v, $attr)
1635 Set all the attributes of the vertex from the anonymous hash $attr.
1637 NOTE: any attributes beginning with an underscore ("_") are
1639 reserved for the internal use of the Graph module.
1640 get_vertex_attributes
1642 $attr = $g->get_vertex_attributes($v)
1643 Return all the attributes of the vertex as an anonymous hash.
1645 get_vertex_attribute_names
1647 @name = $g->get_vertex_attribute_names($v)
1648 Return the names of vertex attributes.
1650 get_vertex_attribute_values
1652 @value = $g->get_vertex_attribute_values($v)
1653 Return the values of vertex attributes.
1655 has_vertex_attributes
1657 $g->has_vertex_attributes($v)
1658 Return true if the vertex has any attributes, false if not.
1660 delete_vertex_attributes
1662 $g->delete_vertex_attributes($v)
1663 Delete all the attributes of the named vertex.
1665 If you are using multivertices, use the by_id variants:
1667 set_vertex_attribute_by_id
1669 get_vertex_attribute_by_id
1670 has_vertex_attribute_by_id
1671 delete_vertex_attribute_by_id
1672 set_vertex_attributes_by_id
1673 get_vertex_attributes_by_id
1674 get_vertex_attribute_names_by_id
1675 get_vertex_attribute_values_by_id
1676 has_vertex_attributes_by_id
1677 delete_vertex_attributes_by_id
1678 $g->set_vertex_attribute_by_id($v, $id, $name, $value)
1679 $g->get_vertex_attribute_by_id($v, $id, $name)
1680 $g->has_vertex_attribute_by_id($v, $id, $name)
1681 $g->delete_vertex_attribute_by_id($v, $id, $name)
1682 $g->set_vertex_attributes_by_id($v, $id, $attr)
1683 $g->get_vertex_attributes_by_id($v, $id)
1684 $g->get_vertex_attribute_values_by_id($v, $id)
1685 $g->get_vertex_attribute_names_by_id($v, $id)
1686 $g->has_vertex_attributes_by_id($v, $id)
1687 $g->delete_vertex_attributes_by_id($v, $id)
1688 For edge attributes:
1690 set_edge_attribute
1692 $g->set_edge_attribute($u, $v, $name, $value)
1693 Set the named edge attribute.
1695 If the edge does not exist, the set_...() will create it, and the
1697 other edge attribute methods will return false or empty.
1698 NOTE: any attributes beginning with an underscore ("_") are
1700 reserved for the internal use of the Graph module.
1701 get_edge_attribute
1703 $value = $g->get_edge_attribute($u, $v, $name)
1704 Return the named edge attribute.
1706 has_edge_attribute
1708 $g->has_edge_attribute($u, $v, $name)
1709 Return true if the edge has an attribute, false if not.
1711 delete_edge_attribute
1713 $g->delete_edge_attribute($u, $v, $name)
1714 Delete the named edge attribute.
1716 set_edge_attributes
1718 $g->set_edge_attributes($u, $v, $attr)
1719 Set all the attributes of the edge from the anonymous hash $attr.
1721 NOTE: any attributes beginning with an underscore ("_") are
1723 reserved for the internal use of the Graph module.
1724 get_edge_attributes
1726 $attr = $g->get_edge_attributes($u, $v)
1727 Return all the attributes of the edge as an anonymous hash.
1729 get_edge_attribute_names
1731 @name = $g->get_edge_attribute_names($u, $v)
1732 Return the names of edge attributes.
1734 get_edge_attribute_values
1736 @value = $g->get_edge_attribute_values($u, $v)
1737 Return the values of edge attributes.
1739 has_edge_attributes
1741 $g->has_edge_attributes($u, $v)
1742 Return true if the edge has any attributes, false if not.
1744 delete_edge_attributes
1746 $g->delete_edge_attributes($u, $v)
1747 Delete all the attributes of the named edge.
1749 If you are using multiedges, use the by_id variants:
1751 set_edge_attribute_by_id
1753 get_edge_attribute_by_id
1754 has_edge_attribute_by_id
1755 delete_edge_attribute_by_id
1756 set_edge_attributes_by_id
1757 get_edge_attributes_by_id
1758 get_edge_attribute_names_by_id
1759 get_edge_attribute_values_by_id
1760 has_edge_attributes_by_id
1761 delete_edge_attributes_by_id
1762 $g->set_edge_attribute_by_id($u, $v, $id, $name, $value)
1763 $g->get_edge_attribute_by_id($u, $v, $id, $name)
1764 $g->has_edge_attribute_by_id($u, $v, $id, $name)
1765 $g->delete_edge_attribute_by_id($u, $v, $id, $name)
1766 $g->set_edge_attributes_by_id($u, $v, $id, $attr)
1767 $g->get_edge_attributes_by_id($u, $v, $id)
1768 $g->get_edge_attribute_values_by_id($u, $v, $id)
1769 $g->get_edge_attribute_names_by_id($u, $v, $id)
1770 $g->has_edge_attributes_by_id($u, $v, $id)
1771 $g->delete_edge_attributes_by_id($u, $v, $id)
1772 For graph attributes:
1774 set_graph_attribute
1776 $g->set_graph_attribute($name, $value)
1777 Set the named graph attribute.
1779 NOTE: any attributes beginning with an underscore ("_") are
1781 reserved for the internal use of the Graph module.
1782 get_graph_attribute
1784 $value = $g->get_graph_attribute($name)
1785 Return the named graph attribute.
1787 has_graph_attribute
1789 $g->has_graph_attribute($name)
1790 Return true if the graph has an attribute, false if not.
1792 delete_graph_attribute
1794 $g->delete_graph_attribute($name)
1795 Delete the named graph attribute.
1797 set_graph_attributes
1799 $g->get_graph_attributes($attr)
1800 Set all the attributes of the graph from the anonymous hash $attr.
1802 NOTE: any attributes beginning with an underscore ("_") are
1804 reserved for the internal use of the Graph module.
1805 get_graph_attributes
1807 $attr = $g->get_graph_attributes()
1808 Return all the attributes of the graph as an anonymous hash.
1810 get_graph_attribute_names
1812 @name = $g->get_graph_attribute_names()
1813 Return the names of graph attributes.
1815 get_graph_attribute_values
1817 @value = $g->get_graph_attribute_values()
1818 Return the values of graph attributes.
1820 has_graph_attributes
1822 $g->has_graph_attributes()
1823 Return true if the graph has any attributes, false if not.
1825 delete_graph_attributes
1827 $g->delete_graph_attributes()
1828 Delete all the attributes of the named graph.
1830 Weighted
1832 As convenient shortcuts the following methods add, query, and manipu‐
1834 late the attribute "weight" with the specified value to the respective
1835 Graph elements.
1836 add_weighted_edge
1838 $g->add_weighted_edge($u, $v, $weight)
1839 add_weighted_edges
1841 $g->add_weighted_edges($u1, $v1, $weight1, ...)
1842 add_weighted_path
1844 $g->add_weighted_path($v1, $weight1, $v2, $weight2, $v3, ...)
1845 add_weighted_vertex
1847 $g->add_weighted_vertex($v, $weight)
1848 add_weighted_vertices
1850 $g->add_weighted_vertices($v1, $weight1, $v2, $weight2, ...)
1851 delete_edge_weight
1853 $g->delete_edge_weight($u, $v)
1854 delete_vertex_weight
1856 $g->delete_vertex_weight($v)
1857 get_edge_weight
1859 $g->get_edge_weight($u, $v)
1860 get_vertex_weight
1862 $g->get_vertex_weight($v)
1863 has_edge_weight
1865 $g->has_edge_weight($u, $v)
1866 has_vertex_weight
1868 $g->has_vertex_weight($v)
1869 set_edge_weight
1871 $g->set_edge_weight($u, $v, $weight)
1872 set_vertex_weight
1874 $g->set_vertex_weight($v, $weight)
1875 Isomorphism
1877 Two graphs being isomorphic means that they are structurally the same
1879 graph, the difference being that the vertices might have been renamed
1880 or substituted. For example in the below example $g0 and $g1 are iso‐
1881 morphic: the vertices "b c d" have been renamed as "z x y".
1882 $g0 = Graph->new;
1884 $g0->add_edges(qw(a b a c c d));
1885 $g1 = Graph->new;
1886 $g1->add_edges(qw(a x x y a z));
1887 In the general case determining isomorphism is NP-hard, in other words,
1889 really hard (time-consuming), no other ways of solving the problem are
1890 known than brute force check of of all the possibilities (with possible
1891 optimization tricks, of course, but brute force still rules at the end
1892 of the day).
1893 A very rough guess at whether two graphs could be isomorphic is possi‐
1895 ble via the method
1896 could_be_isomorphic
1898 $g0->could_be_isomorphic($g1)
1899 If the graphs do not have the same number of vertices and edges, false
1901 is returned. If the distribution of in-degrees and out-degrees at the
1902 vertices of the graphs does not match, false is returned. Otherwise,
1903 true is returned.
1904 What is actually returned is the maximum number of possible isomorphic
1906 graphs between the two graphs, after the above sanity checks have been
1907 conducted. It is basically the product of the factorials of the abso‐
1908 lute values of in-degrees and out-degree pairs at each vertex, with the
1909 isolated vertices ignored (since they could be reshuffled and renamed
1910 arbitrarily). Note that for large graphs the product of these factori‐
1911 als can overflow the maximum presentable number (the floating point
1912 number) in your computer (in Perl) and you might get for example Infin‐
1913 ity as the result.
1914 Miscellaneous
1916 The "expect" methods can be used to test a graph and croak if the graph
1918 is not as expected.
1919 expect_acyclic
1921 expect_dag
1922 expect_directed
1923 expect_multiedged
1924 expect_multivertexed
1925 expect_non_multiedged
1926 expect_non_multivertexed
1927 expect_undirected
1928 In many algorithms it is useful to have a value representing the infin‐
1930 ity. The Graph provides (and itself uses):
1931 Infinity
1933 (Not exported, use Graph::Infinity explicitly)
1934 Size Requirements
1936 A graph takes up at least 1172 bytes of memory.
1938 A vertex takes up at least 100 bytes of memory.
1940 An edge takes up at least 400 bytes of memory.
1942 (A Perl scalar value takes 16 bytes, or 12 bytes if it's a reference.)
1944 These size approximations are very approximate and optimistic (they are
1946 based on total_size() of Devel::Size). In real life many factors
1947 affect these numbers, for example how Perl is configured. The numbers
1948 are for a 32-bit platform and for Perl 5.8.8.
1949 Roughly, the above numbers mean that in a megabyte of memory you can
1951 fit for example a graph of about 1000 vertices and about 2500 edges.
1952 Hyperedges, hypervertices, hypergraphs
1954 BEWARE: this is a rather thinly tested feature, and the theory is even
1956 less so. Do not expect this to stay as it is (or at all) in future
1957 releases.
1958 NOTE: most usual graph algorithms (and basic concepts) break horribly
1960 (or at least will look funny) with these hyperthingies. Caveat emptor.
1961 Hyperedges are edges that connect a number of vertices different from
1963 the usual two.
1964 Hypervertices are vertices that consist of a number of vertices differ‐
1966 ent from the usual one.
1967 Note that for hypervertices there is an asymmetry: when adding hyper‐
1969 vertices, the single vertices are also implicitly added.
1970 Hypergraphs are graphs with hyperedges.
1972 To enable hyperness when constructing Graphs use the "hyperedged" and
1974 "hypervertexed" attributes:
1975 my $h = Graph->new(hyperedged => 1, hypervertexed => 1);
1977 To add hypervertexes, either explicitly use more than one vertex (or,
1979 indeed, no vertices) when using add_vertex()
1980 $h->add_vertex("a", "b")
1982 $h->add_vertex()
1983 or implicitly with array references when using add_edge()
1985 $h->add_edge(["a", "b"], "c")
1987 $h->add_edge()
1988 Testing for existence and deletion of hypervertices and hyperedges
1990 works similarly.
1991 To test for hyperness of a graph use the
1993 is_hypervertexed
1995 hypervertexed
1996 $g->is_hypervertexed
1997 $g->hypervertexed
1998 is_hyperedged
2000 hyperedged
2001 $g->is_hyperedged
2002 $g->hyperedged
2003 Since hypervertices consist of more than one vertex:
2005 vertices_at
2007 $g->vertices_at($v)
2008 Return the vertices at the vertex. This may return just the vertex or
2010 also other vertices.
2011 To go with the concept of undirected in normal (non-hyper) graphs,
2013 there is a similar concept of omnidirected (this is my own coinage,
2014 "all-directions") for hypergraphs, and you can naturally test for it by
2015 is_omnidirected
2017 omnidirected
2018 is_omniedged
2019 omniedged
2020 $g->is_omniedged
2021 $g->omniedged
2023 $g->is_omnidirected
2025 $g->omnidirected
2027 Return true if the graph is omnidirected (edges have no direction),
2029 false if not.
2030 You may be wondering why on earth did I make up this new concept, why
2032 didn't the "undirected" work for me? Well, because of this:
2033 $g = Graph->new(hypervertexed => 1, omnivertexed => 1);
2035 That's right, vertices can be omni, too - and that is indeed the
2037 default. You can turn it off and then $g->add_vertex(qw(a b)) no more
2038 means adding also the (hyper)vertex qw(b a). In other words, the
2039 "directivity" is orthogonal to (or independent of) the number of ver‐
2040 tices in the vertex/edge.
2041 is_omnivertexed
2043 omnivertexed
2044 Another oddity that fell out of the implementation is the uniqueness
2046 attribute, that comes naturally in "uniqedged" and "uniqvertexed"
2047 flavours. It does what it sounds like, to unique or not the vertices
2048 participating in edges and vertices (is the hypervertex qw(a b a) the
2049 same as the hypervertex qw(a b), for example). Without too much expla‐
2050 nation:
2051 is_uniqedged
2053 uniqedged
2054 is_uniqvertexed
2055 uniqvertexed
2056 Backward compatibility with Graph 0.2
2058 The Graph 0.2 (and 0.2xxxx) had the following features
2060 · vertices() always sorted the vertex list, which most of the time is
2062 unnecessary and wastes CPU.
2063 · edges() returned a flat list where the begin and end vertices of
2065 the edges were intermingled: every even index had an edge begin
2066 vertex, and every odd index had an edge end vertex. This had the
2067 unfortunate consequence of "scalar(@e = edges)" being twice the
2068 number of edges, and complicating any algorithm walking through the
2069 edges.
2070 · The vertex list returned by edges() was sorted, the primary key
2072 being the edge begin vertices, and the secondary key being the edge
2073 end vertices.
2074 · The attribute API was oddly position dependent and dependent on the
2076 number of arguments. Use ..._graph_attribute(), ..._ver‐
2077 tex_attribute(), ..._edge_attribute() instead.
2078 In future releases of Graph (any release after 0.50) the 0.2xxxx com‐
2080 patibility will be removed. Upgrade your code now.
2081 If you want to continue using these (mis)features you can use the "com‐
2083 pat02" flag when creating a graph:
2084 my $g = Graph->new(compat02 => 1);
2086 This will change the vertices() and edges() appropriately. This, how‐
2088 ever, is not recommended, since it complicates all the code using ver‐
2089 tices() and edges(). Instead it is recommended that the vertices02()
2090 and edges02() methods are used. The corresponding new style (unsorted,
2091 and edges() returning a list of references) methods are called ver‐
2092 tices05() and edges05().
2093 To test whether a graph has the compatibility turned on
2095 is_compat02
2097 compat02
2098 $g->is_compat02
2099 $g->compat02
2100 The following are not backward compatibility methods, strictly speak‐
2102 ing, because they did not exist before.
2103 edges02
2105 Return the edges as a flat list of vertices, elements at even
2106 indices being the start vertices and elements at odd indices being
2107 the end vertices.
2108 edges05
2110 Return the edges as a list of array references, each element con‐
2111 taining the vertices of each edge. (This is not a backward compat‐
2112 ibility interface as such since it did not exist before.)
2113 vertices02
2115 Return the vertices in sorted order.
2116 vertices05
2118 Return the vertices in random order.
2119 For the attributes the recommended way is to use the new API.
2121 Do not expect new methods to work for compat02 graphs.
2123 The following compatibility methods exist:
2125 has_attribute
2127 has_attributes
2128 get_attribute
2129 get_attributes
2130 set_attribute
2131 set_attributes
2132 delete_attribute
2133 delete_attributes
2134 Do not use the above, use the new attribute interfaces instead.
2135 vertices_unsorted
2137 Alias for vertices() (or rather, vertices05()) since the vertices()
2138 now always returns the vertices in an unsorted order. You can also
2139 use the unsorted_vertices import, but only with a true value (false
2140 values will cause an error).
2141 density_limits
2143 my ($sparse, $dense, $complete) = $g->density_limits;
2144 Return the "density limits" used to classify graphs as "sparse" or
2146 "dense". The first limit is C/4 and the second limit is 3C/4,
2147 where C is the number of edges in a complete graph (the last
2148 "limit").
2149 density
2151 my $density = $g->density;
2152 Return the density of the graph, the ratio of the number of edges
2154 to the number of edges in a complete graph.
2155 vertex
2157 my $v = $g->vertex($v);
2158 Return the vertex if the graph has the vertex, undef otherwise.
2160 out_edges
2162 in_edges
2163 edges($v)
2164 This is now called edges_at($v).
2165 DIAGNOSTICS
2167 · Graph::...Map...: arguments X expected Y ...
2169 If you see these (more user-friendly error messages should have
2171 been triggered above and before these) please report any such
2172 occurrences, but in general you should be happy to see these since
2173 it means that an attempt to call something with a wrong number of
2174 arguments was caught in time.
2175 · Graph::add_edge: graph is not hyperedged ...
2177 Maybe you used add_weighted_edge() with only the two vertex argu‐
2179 ments.
2180 · Not an ARRAY reference at lib/Graph.pm ...
2182 One possibility is that you have code based on Graph 0.2xxxx that
2184 assumes Graphs being blessed hash references, possibly also assum‐
2185 ing that certain hash keys are available to use for your own pur‐
2186 poses. In Graph 0.50 none of this is true. Please do not expect
2187 any particular internal implementation of Graphs. Use inheritance
2188 and graph/vertex/edge attributes instead.
2189 Another possibility is that you meant to have objects (blessed ref‐
2191 erences) as graph vertices, but forgot to use "refvertexed" (see
2192 "refvertexed") when creating the graph.
2193 POSSIBLE FUTURES
2195 A possible future direction is a new graph module written for speed:
2197 this may very possibly mean breaking or limiting some of the APIs or
2198 behaviour as compared with this release of the module.
2199 What definitely won't happen in future releases is carrying over the
2201 Graph 0.2xxxx backward compatibility API.
2202
2204 All bad terminology, bugs, and inefficiencies are naturally mine, all
2205 mine, and not the fault of the below.
2206 Thanks to Nathan Goodman and Andras Salamon for bravely betatesting my
2208 pre-0.50 code. If they missed something, that was only because of my
2209 fiendish code.
2210 The following literature for algorithms and some test cases:
2212 · Algorithms in C, Third Edition, Part 5, Graph Algorithms, Robert
2214 Sedgewick, Addison Wesley
2215 · Introduction to Algorithms, First Edition, Cormen-Leiserson-Rivest,
2217 McGraw Hill
2218 · Graphs, Networks and Algorithms, Dieter Jungnickel, Springer
2220
2222 Jarkko Hietaniemi jhi@iki.fi
2223
2225 This module is licensed under the same terms as Perl itself.
2226perl v5.8.8 2004-11-08 Graph(3)