Commit | Line | Data |
---|---|---|
86530b38 AT |
1 | package Graph::Base; |
2 | ||
3 | use strict; | |
4 | local $^W = 1; | |
5 | ||
6 | use vars qw(@ISA); | |
7 | ||
8 | =head1 NAME | |
9 | ||
10 | Graph::Base - graph base class | |
11 | ||
12 | =head1 SYNOPSIS | |
13 | ||
14 | use Graph::Directed; | |
15 | use Graph::Undirected; | |
16 | ||
17 | $d1 = new Graph; | |
18 | $d2 = new Graph::Directed; | |
19 | $u = new Graph::Undirected; | |
20 | ||
21 | =head1 DESCRIPTION | |
22 | ||
23 | You create new graphs by calling the C<new> constructors of classes | |
24 | C<Graph>, C<Graph::Directed>, and C<Graph::Undirected>. The classes | |
25 | C<Graph> and C<Graph::Directed> are identical. After creating the | |
26 | graph you can modify and explore the graph with following methods. | |
27 | ||
28 | =over 4 | |
29 | ||
30 | =cut | |
31 | ||
32 | require Exporter; | |
33 | @ISA = qw(Exporter); | |
34 | ||
35 | =pod | |
36 | ||
37 | =item new | |
38 | ||
39 | $G = Graph->new(@V) | |
40 | ||
41 | Returns a new graph $G with the optional vertices @V. | |
42 | ||
43 | =cut | |
44 | ||
45 | sub new { | |
46 | my $class = shift; | |
47 | ||
48 | my $G = { }; | |
49 | ||
50 | bless $G, $class; | |
51 | ||
52 | $G->add_vertices(@_) if @_; | |
53 | ||
54 | return $G; | |
55 | } | |
56 | ||
57 | =pod | |
58 | ||
59 | =item add_vertices | |
60 | ||
61 | $G = $G->add_vertices(@v) | |
62 | ||
63 | Adds the vertices to the graph $G, returns the graph. | |
64 | ||
65 | =cut | |
66 | ||
67 | sub add_vertices { | |
68 | my ($G, @v) = @_; | |
69 | ||
70 | @{ $G->{ V } }{ @v } = @v; | |
71 | ||
72 | return $G; | |
73 | } | |
74 | ||
75 | =pod | |
76 | ||
77 | =item add_vertex | |
78 | ||
79 | $G = $G->add_vertex($v) | |
80 | ||
81 | Adds the vertex $v to the graph $G, returns the graph. | |
82 | ||
83 | =cut | |
84 | ||
85 | sub add_vertex { | |
86 | my ($G, $v) = @_; | |
87 | ||
88 | return $G->add_vertices($v); | |
89 | } | |
90 | ||
91 | =pod | |
92 | ||
93 | =item vertices | |
94 | ||
95 | @V = $G->vertices | |
96 | ||
97 | In list context returns the vertices @V of the graph $G. | |
98 | In scalar context returns the number of the vertices. | |
99 | ||
100 | =cut | |
101 | ||
102 | sub vertices { | |
103 | my $G = shift; | |
104 | my @V = exists $G->{ V } ? sort values %{ $G->{ V } } : (); | |
105 | ||
106 | return @V; | |
107 | } | |
108 | ||
109 | =pod | |
110 | ||
111 | =item has_vertices | |
112 | ||
113 | $G->has_vertices(@v) | |
114 | ||
115 | In list context returns a list which contains the vertex | |
116 | of the vertices @v if the vertex exists in the graph $G | |
117 | and undef if it doesn't. In scalar context returns the | |
118 | number of the existing vertices. | |
119 | ||
120 | =cut | |
121 | ||
122 | sub has_vertices { | |
123 | my $G = shift; | |
124 | ||
125 | return wantarray ? | |
126 | map { exists $G->{ V }->{ $_ } ? $_ : undef } @_ : | |
127 | grep { exists $G->{ V }->{ $_ } } @_ ; | |
128 | } | |
129 | ||
130 | =pod | |
131 | ||
132 | =item has_vertex | |
133 | ||
134 | $b = $G->has_vertex($v) | |
135 | ||
136 | Returns true if the vertex $v exists in | |
137 | the graph $G and false if it doesn't. | |
138 | ||
139 | =cut | |
140 | ||
141 | sub has_vertex { | |
142 | my ($G, $v) = @_; | |
143 | ||
144 | return defined $v && exists $G->{ V } && exists $G->{ V }->{ $v }; | |
145 | } | |
146 | ||
147 | =pod | |
148 | ||
149 | =item vertex | |
150 | ||
151 | $v = $G->has_vertex($v) | |
152 | ||
153 | Returns the vertex $v if the vertex exists in the graph $G | |
154 | or undef if it doesn't. | |
155 | ||
156 | =cut | |
157 | ||
158 | sub vertex { | |
159 | my ($G, $v) = @_; | |
160 | ||
161 | return defined $v && $G->{ V }->{ $v }; | |
162 | } | |
163 | ||
164 | =pod | |
165 | ||
166 | =item directed | |
167 | ||
168 | $b = $G->directed($d) | |
169 | ||
170 | Set the directedness of the graph $G to $d or return the | |
171 | current directedness. Directedness defaults to true. | |
172 | ||
173 | =cut | |
174 | ||
175 | sub directed { | |
176 | my ($G, $d) = @_; | |
177 | ||
178 | if (defined $d) { | |
179 | if ($d) { | |
180 | my $o = $G->{ D }; # Old directedness. | |
181 | ||
182 | $G->{ D } = $d; | |
183 | if (not $o) { | |
184 | my @E = $G->edges; | |
185 | ||
186 | while (my ($u, $v) = splice(@E, 0, 2)) { | |
187 | $G->add_edge($v, $u); | |
188 | } | |
189 | } | |
190 | ||
191 | return bless $G, 'Graph::Directed'; # Re-bless. | |
192 | } else { | |
193 | return $G->undirected(not $d); | |
194 | } | |
195 | } | |
196 | ||
197 | return $G->{ D }; | |
198 | } | |
199 | ||
200 | =pod | |
201 | ||
202 | =item undirected | |
203 | ||
204 | $b = $G->undirected($d) | |
205 | ||
206 | Set the undirectedness of the graph $G to $u or return the | |
207 | current undirectedness. Undirectedness defaults to false. | |
208 | ||
209 | =cut | |
210 | ||
211 | sub undirected { | |
212 | my ($G, $u) = @_; | |
213 | ||
214 | $G->{ D } = 1 unless defined $G->{ D }; | |
215 | ||
216 | if (defined $u) { | |
217 | if ($u) { | |
218 | my $o = $G->{ D }; # Old directedness. | |
219 | ||
220 | $G->{ D } = not $u; | |
221 | if ($o) { | |
222 | my @E = $G->edges; | |
223 | my %E; | |
224 | ||
225 | while (my ($u, $v) = splice(@E, 0, 2)) { | |
226 | # Throw away duplicate edges. | |
227 | $G->delete_edge($u, $v) if exists $E{$v}->{$u}; | |
228 | $E{$u}->{$v}++; | |
229 | } | |
230 | } | |
231 | ||
232 | return bless $G, 'Graph::Undirected'; # Re-bless. | |
233 | } else { | |
234 | return $G->directed(not $u); | |
235 | } | |
236 | } | |
237 | ||
238 | return not $G->{ D }; | |
239 | } | |
240 | ||
241 | =pod | |
242 | ||
243 | =item has_edge | |
244 | ||
245 | $b = $G->has_edge($u, $v) | |
246 | ||
247 | Return true if the graph $G has the edge between | |
248 | the vertices $u, $v. | |
249 | ||
250 | =cut | |
251 | ||
252 | sub has_edge { | |
253 | my ($G, $u, $v) = @_; | |
254 | ||
255 | return exists $G->{ Succ }->{ $u }->{ $v } || | |
256 | ($G->undirected && exists $G->{ Succ }->{ $v }->{ $u }); | |
257 | } | |
258 | ||
259 | =pod | |
260 | ||
261 | =item has_edges | |
262 | ||
263 | $G->has_edges($u1, $v1, $u2, $v2, ...) | |
264 | ||
265 | In list context returns a list which contains true for each | |
266 | edge in the graph $G defined by the vertices $u1, $v1, ..., | |
267 | and false for each non-existing edge. In scalar context | |
268 | returns the number of the existing edges. | |
269 | ||
270 | =cut | |
271 | ||
272 | sub has_edges { | |
273 | my $G = shift; | |
274 | my @e; | |
275 | ||
276 | while (my ($u, $v) = splice(@_, 0, 2)) { | |
277 | push @e, $G->has_edge($u, $v); | |
278 | } | |
279 | ||
280 | return wantarray ? @e : grep { $_ } @e; | |
281 | } | |
282 | ||
283 | =pod | |
284 | ||
285 | =item has_path | |
286 | ||
287 | $G->has_path($u, $v, ...) | |
288 | ||
289 | Return true if the graph $G has the cycle defined by | |
290 | the vertices $u, $v, ..., false otherwise. | |
291 | ||
292 | =cut | |
293 | ||
294 | sub has_path { | |
295 | my $G = shift; | |
296 | my $u = shift; | |
297 | ||
298 | while (my $v = shift) { | |
299 | return 0 unless $G->has_edge($u, $v); | |
300 | $u = $v; | |
301 | } | |
302 | ||
303 | return 1; | |
304 | } | |
305 | ||
306 | =pod | |
307 | ||
308 | =item has_cycle | |
309 | ||
310 | $G->has_cycle($u, $v, ...) | |
311 | ||
312 | Return true if the graph $G has the cycle defined by | |
313 | the vertices $u, $v, ...,false otherwise. | |
314 | ||
315 | =cut | |
316 | ||
317 | sub has_cycle { | |
318 | my $G = shift; | |
319 | ||
320 | return $G->has_path(@_, $_[0]); # Just wrap around. | |
321 | } | |
322 | ||
323 | # _union_vertex_set | |
324 | # | |
325 | # $G->_union_vertex_set($u, $v) | |
326 | # | |
327 | # (INTERNAL USE ONLY) | |
328 | # Adds the vertices $u and $v in the graph $G to the same vertex set. | |
329 | # | |
330 | sub _union_vertex_set { | |
331 | my ($G, $u, $v) = @_; | |
332 | ||
333 | my $su = $G->vertex_set( $u ); | |
334 | my $sv = $G->vertex_set( $v ); | |
335 | ||
336 | return if $su eq $sv; | |
337 | ||
338 | my $ru = $G->{ VertexSetRank }->{ $su }; | |
339 | my $rv = $G->{ VertexSetRank }->{ $sv }; | |
340 | ||
341 | if ( $ru < $rv ) { # Union by rank (weight balancing). | |
342 | $G->{ VertexSetParent }->{ $su } = $sv; | |
343 | } else { | |
344 | $G->{ VertexSetParent }->{ $sv } = $su; | |
345 | $G->{ VertexSetRank }->{ $sv }++ if $ru == $rv; | |
346 | } | |
347 | } | |
348 | ||
349 | =pod | |
350 | ||
351 | =item vertex_set | |
352 | ||
353 | $s = $G->vertex_set($v) | |
354 | ||
355 | Returns the vertex set of the vertex $v in the graph $G. | |
356 | A "vertex set" is represented by its parent vertex. | |
357 | ||
358 | =cut | |
359 | ||
360 | sub vertex_set { | |
361 | my ($G, $v) = @_; | |
362 | ||
363 | if ( exists $G->{ VertexSetParent }->{ $v } ) { | |
364 | # Path compression. | |
365 | $G->{ VertexSetParent }->{ $v } = | |
366 | $G->vertex_set( $G->{ VertexSetParent }->{ $v } ) | |
367 | if $v ne $G->{ VertexSetParent }->{ $v }; | |
368 | } else { | |
369 | $G->{ VertexSetParent }->{ $v } = $v; | |
370 | $G->{ VertexSetRank }->{ $v } = 0; | |
371 | } | |
372 | ||
373 | return $G->{ VertexSetParent }->{ $v }; | |
374 | } | |
375 | ||
376 | =pod | |
377 | ||
378 | =item add_edge | |
379 | ||
380 | $G = $G->add_edge($u, $v) | |
381 | ||
382 | Adds the edge defined by the vertices $u, $v, to the graph $G. | |
383 | Also implicitly adds the vertices. Returns the graph. | |
384 | ||
385 | =cut | |
386 | ||
387 | sub add_edge { | |
388 | my ($G, $u, $v) = @_; | |
389 | ||
390 | $G->add_vertex($u); | |
391 | $G->add_vertex($v); | |
392 | $G->_union_vertex_set( $u, $v ); | |
393 | push @{ $G->{ Succ }->{ $u }->{ $v } }, $v; | |
394 | push @{ $G->{ Pred }->{ $v }->{ $u } }, $u; | |
395 | ||
396 | return $G; | |
397 | } | |
398 | ||
399 | =pod | |
400 | ||
401 | =item add_edges | |
402 | ||
403 | $G = $G->add_edges($u1, $v1, $u2, $v2, ...) | |
404 | ||
405 | Adds the edge defined by the vertices $u1, $v1, ..., | |
406 | to the graph $G. Also implicitly adds the vertices. | |
407 | Returns the graph. | |
408 | ||
409 | =cut | |
410 | ||
411 | sub add_edges { | |
412 | my $G = shift; | |
413 | ||
414 | while (my ($u, $v) = splice(@_, 0, 2)) { | |
415 | $G->add_edge($u, $v); | |
416 | } | |
417 | ||
418 | return $G; | |
419 | } | |
420 | ||
421 | =pod | |
422 | ||
423 | =item add_path | |
424 | ||
425 | $G->add_path($u, $v, ...) | |
426 | ||
427 | Adds the path defined by the vertices $u, $v, ..., | |
428 | to the graph $G. Also implicitly adds the vertices. | |
429 | Returns the graph. | |
430 | ||
431 | =cut | |
432 | ||
433 | sub add_path { | |
434 | my $G = shift; | |
435 | my $u = shift; | |
436 | ||
437 | while (my $v = shift) { | |
438 | $G->add_edge($u, $v); | |
439 | $u = $v; | |
440 | } | |
441 | ||
442 | return $G; | |
443 | } | |
444 | ||
445 | =pod | |
446 | ||
447 | =item add_cycle | |
448 | ||
449 | $G = $G->add_cycle($u, $v, ...) | |
450 | ||
451 | Adds the cycle defined by the vertices $u, $v, ..., | |
452 | to the graph $G. Also implicitly adds the vertices. | |
453 | Returns the graph. | |
454 | ||
455 | =cut | |
456 | ||
457 | sub add_cycle { | |
458 | my $G = shift; | |
459 | ||
460 | $G->add_path(@_, $_[0]); # Just wrap around. | |
461 | } | |
462 | ||
463 | # _successors | |
464 | # | |
465 | # @s = $G->_successors($v) | |
466 | # | |
467 | # (INTERNAL USE ONLY, use only on directed graphs) | |
468 | # Returns the successor vertices @s of the vertex | |
469 | # in the graph $G. | |
470 | # | |
471 | sub _successors { | |
472 | my ($G, $v) = @_; | |
473 | ||
474 | my @s = | |
475 | defined $G->{ Succ }->{ $v } ? | |
476 | map { @{ $G->{ Succ }->{ $v }->{ $_ } } } | |
477 | sort keys %{ $G->{ Succ }->{ $v } } : | |
478 | ( ); | |
479 | ||
480 | return @s; | |
481 | } | |
482 | ||
483 | # _predecessors | |
484 | # | |
485 | # @p = $G->_predecessors($v) | |
486 | # | |
487 | # (INTERNAL USE ONLY, use only on directed graphs) | |
488 | # Returns the predecessor vertices @p of the vertex $v | |
489 | # in the graph $G. | |
490 | # | |
491 | sub _predecessors { | |
492 | my ($G, $v) = @_; | |
493 | ||
494 | my @p = | |
495 | defined $G->{ Pred }->{ $v } ? | |
496 | map { @{ $G->{ Pred }->{ $v }->{ $_ } } } | |
497 | sort keys %{ $G->{ Pred }->{ $v } } : | |
498 | ( ); | |
499 | ||
500 | return @p; | |
501 | } | |
502 | ||
503 | =pod | |
504 | ||
505 | =item neighbors | |
506 | ||
507 | @n = $G->neighbors($v) | |
508 | ||
509 | Returns the neighbor vertices of the vertex in the graph. | |
510 | (Also 'neighbours' works.) | |
511 | ||
512 | =cut | |
513 | ||
514 | sub neighbors { | |
515 | my ($G, $v) = @_; | |
516 | ||
517 | my @n = ($G->_successors($v), $G->_predecessors($v)); | |
518 | ||
519 | return @n; | |
520 | } | |
521 | ||
522 | use vars '*neighbours'; | |
523 | *neighbours = \&neighbors; # Keep both sides of the Atlantic happy. | |
524 | ||
525 | =pod | |
526 | ||
527 | =item successors | |
528 | ||
529 | @s = $G->successors($v) | |
530 | ||
531 | Returns the successor vertices of the vertex in the graph. | |
532 | ||
533 | =cut | |
534 | ||
535 | sub successors { | |
536 | my ($G, $v) = @_; | |
537 | ||
538 | return $G->directed ? $G->_successors($v) : $G->neighbors($v); | |
539 | } | |
540 | ||
541 | =pod | |
542 | ||
543 | =item predecessors | |
544 | ||
545 | @p = $G->predecessors($v) | |
546 | ||
547 | Returns the predecessor vertices of the vertex in the graph. | |
548 | ||
549 | =cut | |
550 | ||
551 | sub predecessors { | |
552 | my ($G, $v) = @_; | |
553 | ||
554 | return $G->directed ? $G->_predecessors($v) : $G->neighbors($v); | |
555 | } | |
556 | ||
557 | =pod | |
558 | ||
559 | =item out_edges | |
560 | ||
561 | @e = $G->out_edges($v) | |
562 | ||
563 | Returns the edges leading out of the vertex $v in the graph $G. | |
564 | In list context returns the edges as ($start_vertex, $end_vertex) | |
565 | pairs. In scalar context returns the number of the edges. | |
566 | ||
567 | =cut | |
568 | ||
569 | sub out_edges { | |
570 | my ($G, $v) = @_; | |
571 | ||
572 | return () unless $G->has_vertex($v); | |
573 | ||
574 | my @e = $G->_edges($v, undef); | |
575 | ||
576 | return wantarray ? @e : @e / 2; | |
577 | } | |
578 | ||
579 | =pod | |
580 | ||
581 | =item in_edges | |
582 | ||
583 | @e = $G->in_edges($v) | |
584 | ||
585 | Returns the edges leading into the vertex $v in the graph $G. | |
586 | In list context returns the edges as ($start_vertex, $end_vertex) | |
587 | pairs; in scalar context returns the number of the edges. | |
588 | ||
589 | =cut | |
590 | ||
591 | sub in_edges { | |
592 | my ($G, $v) = @_; | |
593 | ||
594 | return () unless $G->has_vertex($v); | |
595 | ||
596 | my @e = $G->_edges(undef, $v); | |
597 | ||
598 | return wantarray ? @e : @e / 2; | |
599 | } | |
600 | ||
601 | =pod | |
602 | ||
603 | =item edges | |
604 | ||
605 | @e = $G->edges($u, $v) | |
606 | ||
607 | Returns the edges between the vertices $u and $v, or if $v | |
608 | is undefined, the edges leading into or out of the vertex $u, | |
609 | or if $u is undefined, returns all the edges, of the graph $G. | |
610 | In list context returns the edges as a list of | |
611 | $start_vertex, $end_vertex pairs; in scalar context | |
612 | returns the number of the edges. | |
613 | ||
614 | =cut | |
615 | ||
616 | sub edges { | |
617 | my ($G, $u, $v) = @_; | |
618 | ||
619 | return () if defined $v and not $G->has_vertex($v); | |
620 | ||
621 | my @e = | |
622 | defined $u ? | |
623 | ( defined $v ? | |
624 | $G->_edges($u, $v) : | |
625 | ($G->in_edges($u), $G->out_edges($u)) ) : | |
626 | $G->_edges; | |
627 | ||
628 | return wantarray ? @e : @e / 2; | |
629 | } | |
630 | ||
631 | =pod | |
632 | ||
633 | =item delete_edge | |
634 | ||
635 | $G = $G->delete_edge($u, $v) | |
636 | ||
637 | Deletes an edge defined by the vertices $u, $v from the graph $G. | |
638 | Note that the edge need not actually exist. | |
639 | Returns the graph. | |
640 | ||
641 | =cut | |
642 | ||
643 | sub delete_edge { | |
644 | my ($G, $u, $v) = @_; | |
645 | ||
646 | pop @{ $G->{ Succ }->{ $u }->{ $v } }; | |
647 | pop @{ $G->{ Pred }->{ $v }->{ $u } }; | |
648 | ||
649 | delete $G->{ Succ }->{ $u }->{ $v } | |
650 | unless @{ $G->{ Succ }->{ $u }->{ $v } }; | |
651 | delete $G->{ Pred }->{ $v }->{ $u } | |
652 | unless @{ $G->{ Pred }->{ $v }->{ $u } }; | |
653 | ||
654 | delete $G->{ Succ }->{ $u } | |
655 | unless keys %{ $G->{ Succ }->{ $u } }; | |
656 | delete $G->{ Pred }->{ $v } | |
657 | unless keys %{ $G->{ Pred }->{ $v } }; | |
658 | ||
659 | return $G; | |
660 | } | |
661 | ||
662 | =pod | |
663 | ||
664 | =item delete_edges | |
665 | ||
666 | $G = $G->delete_edges($u1, $v1, $u2, $v2, ..) | |
667 | ||
668 | Deletes edges defined by the vertices $u1, $v1, ..., | |
669 | from the graph $G. | |
670 | Note that the edges need not actually exist. | |
671 | Returns the graph. | |
672 | ||
673 | =cut | |
674 | ||
675 | sub delete_edges { | |
676 | my $G = shift; | |
677 | ||
678 | while (my ($u, $v) = splice(@_, 0, 2)) { | |
679 | if (defined $v) { | |
680 | $G->delete_edge($u, $v); | |
681 | } else { | |
682 | my @e = $G->edges($u); | |
683 | ||
684 | while (($u, $v) = splice(@e, 0, 2)) { | |
685 | $G->delete_edge($u, $v); | |
686 | } | |
687 | } | |
688 | } | |
689 | ||
690 | return $G; | |
691 | } | |
692 | ||
693 | =pod | |
694 | ||
695 | =item delete_path | |
696 | ||
697 | $G = $G->delete_path($u, $v, ...) | |
698 | ||
699 | Deletes a path defined by the vertices $u, $v, ..., from the graph $G. | |
700 | Note that the path need not actually exist. Returns the graph. | |
701 | ||
702 | =cut | |
703 | ||
704 | sub delete_path { | |
705 | my $G = shift; | |
706 | my $u = shift; | |
707 | ||
708 | while (my $v = shift) { | |
709 | $G->delete_edge($u, $v); | |
710 | $u = $v; | |
711 | } | |
712 | ||
713 | return $G; | |
714 | } | |
715 | ||
716 | =pod | |
717 | ||
718 | =item delete_cycle | |
719 | ||
720 | $G = $G->delete_cycle($u, $v, ...) | |
721 | ||
722 | Deletes a cycle defined by the vertices $u, $v, ..., from the graph $G. | |
723 | Note that the cycle need not actually exist. Returns the graph. | |
724 | ||
725 | =cut | |
726 | ||
727 | sub delete_cycle { | |
728 | my $G = shift; | |
729 | ||
730 | $G->delete_path(@_, $_[0]); # Just wrap around. | |
731 | } | |
732 | ||
733 | =pod | |
734 | ||
735 | =item delete_vertex | |
736 | ||
737 | $G = $G->delete_vertex($v) | |
738 | ||
739 | Deletes the vertex $v and all its edges from the graph $G. | |
740 | Note that the vertex need not actually exist. | |
741 | Returns the graph. | |
742 | ||
743 | =cut | |
744 | ||
745 | sub delete_vertex { | |
746 | my ($G, $v) = @_; | |
747 | ||
748 | $G->delete_edges($v); | |
749 | ||
750 | delete $G->{ V }->{ $v }; | |
751 | ||
752 | return $G; | |
753 | } | |
754 | ||
755 | =pod | |
756 | ||
757 | =item delete_vertices | |
758 | ||
759 | $G = $G->delete_vertices(@v) | |
760 | ||
761 | Deletes the vertices @v and all their edges from the graph $G. | |
762 | Note that the vertices need not actually exist. | |
763 | Returns the graph. | |
764 | ||
765 | =cut | |
766 | ||
767 | sub delete_vertices { | |
768 | my $G = shift; | |
769 | ||
770 | foreach my $v (@_) { | |
771 | $G->delete_vertex($v); | |
772 | } | |
773 | ||
774 | return $G; | |
775 | } | |
776 | ||
777 | =pod | |
778 | ||
779 | =item in_degree | |
780 | ||
781 | $d = $G->in_degree($v) | |
782 | ||
783 | Returns the in-degree of the vertex $v in the graph $G, | |
784 | or, if $v is undefined, the total in-degree of all the | |
785 | vertices of the graph, or undef if the vertex doesn't | |
786 | exist in the graph. | |
787 | ||
788 | =cut | |
789 | ||
790 | sub in_degree { | |
791 | my ($G, $v) = @_; | |
792 | ||
793 | return undef unless $G->has_vertex($v); | |
794 | ||
795 | if ($G->directed) { | |
796 | if (defined $v) { | |
797 | return scalar $G->in_edges($v); | |
798 | } else { | |
799 | my $in = 0; | |
800 | ||
801 | foreach my $v ($G->vertices) { | |
802 | $in += $G->in_degree($v); | |
803 | } | |
804 | ||
805 | return $in; | |
806 | } | |
807 | } else { | |
808 | return scalar $G->edges($v); | |
809 | } | |
810 | } | |
811 | ||
812 | =pod | |
813 | ||
814 | =item out_degree | |
815 | ||
816 | $d = $G->out_degree($v) | |
817 | ||
818 | Returns the out-degree of the vertex $v in the graph $G, | |
819 | or, if $v is undefined, the total out-degree of all the | |
820 | vertices of the graph, of undef if the vertex doesn't | |
821 | exist in the graph. | |
822 | ||
823 | =cut | |
824 | ||
825 | sub out_degree { | |
826 | my ($G, $v) = @_; | |
827 | ||
828 | return undef unless $G->has_vertex($v); | |
829 | ||
830 | if ($G->directed) { | |
831 | if (defined $v) { | |
832 | return scalar $G->out_edges($v); | |
833 | } else { | |
834 | my $out = 0; | |
835 | ||
836 | foreach my $v ($G->vertices) { | |
837 | $out += $G->out_degree($v); | |
838 | } | |
839 | ||
840 | return $out; | |
841 | } | |
842 | } else { | |
843 | return scalar $G->edges($v); | |
844 | } | |
845 | } | |
846 | ||
847 | =pod | |
848 | ||
849 | =item degree | |
850 | ||
851 | $d = $G->degree($v) | |
852 | ||
853 | Returns the degree of the vertex $v in the graph $G | |
854 | or, if $v is undefined, the total degree of all the | |
855 | vertices of the graph, or undef if the vertex $v | |
856 | doesn't exist in the graph. | |
857 | ||
858 | =cut | |
859 | ||
860 | sub degree { | |
861 | my ($G, $v) = @_; | |
862 | ||
863 | if (defined $v) { | |
864 | return undef unless $G->has_vertex($v); | |
865 | ||
866 | if ($G->directed) { | |
867 | return $G->in_degree($v) - $G->out_degree($v); | |
868 | } else { | |
869 | return $G->edges($v); | |
870 | } | |
871 | } else { | |
872 | if ($G->directed) { | |
873 | return 0; | |
874 | } else { | |
875 | my $deg = 0; | |
876 | ||
877 | foreach my $v ($G->vertices) { | |
878 | $deg += $G->degree($v); | |
879 | } | |
880 | ||
881 | return $deg; | |
882 | } | |
883 | } | |
884 | } | |
885 | ||
886 | =pod | |
887 | ||
888 | =item average_degree | |
889 | ||
890 | $d = $G->average_degree | |
891 | ||
892 | Returns the average degree of the vertices of the graph $G. | |
893 | ||
894 | =cut | |
895 | ||
896 | sub average_degree { | |
897 | my $G = shift; | |
898 | my $V = $G->vertices; | |
899 | ||
900 | return $V ? $G->degree / $V : 0; | |
901 | } | |
902 | ||
903 | =pod | |
904 | ||
905 | =item is_source_vertex | |
906 | ||
907 | $b = $G->is_source_vertex($v) | |
908 | ||
909 | Returns true if the vertex $v is a source vertex of the graph $G. | |
910 | ||
911 | =cut | |
912 | ||
913 | sub is_source_vertex { | |
914 | my ($G, $v) = @_; | |
915 | ||
916 | $G->in_degree($v) == 0 && $G->out_degree($v) > 0; | |
917 | } | |
918 | ||
919 | =pod | |
920 | ||
921 | =item is_sink_vertex | |
922 | ||
923 | $b = $G->is_sink_vertex($v) | |
924 | ||
925 | Returns true if the vertex $v is a sink vertex of the graph $G. | |
926 | ||
927 | =cut | |
928 | ||
929 | sub is_sink_vertex { | |
930 | my ($G, $v) = @_; | |
931 | ||
932 | $G->in_degree($v) > 0 && $G->out_degree($v) == 0; | |
933 | } | |
934 | ||
935 | =pod | |
936 | ||
937 | =item is_isolated_vertex | |
938 | ||
939 | $b = $G->is_isolated_vertex($v) | |
940 | ||
941 | Returns true if the vertex $v is a isolated vertex of the graph $G. | |
942 | ||
943 | =cut | |
944 | ||
945 | sub is_isolated_vertex { | |
946 | my ($G, $v) = @_; | |
947 | ||
948 | $G->in_degree($v) == 0 && $G->out_degree($v) == 0; | |
949 | } | |
950 | ||
951 | =pod | |
952 | ||
953 | =item is_exterior_vertex | |
954 | ||
955 | $b = $G->is_exterior_vertex($v) | |
956 | ||
957 | Returns true if the vertex $v is a exterior vertex of the graph $G. | |
958 | ||
959 | =cut | |
960 | ||
961 | sub is_exterior_vertex { | |
962 | my ($G, $v) = @_; | |
963 | ||
964 | $G->in_degree($v) == 0 xor $G->out_degree($v) == 0; | |
965 | } | |
966 | ||
967 | =pod | |
968 | ||
969 | =item is_interior_vertex | |
970 | ||
971 | $b = $G->is_interior_vertex($v) | |
972 | ||
973 | Returns true if the vertex $v is a interior vertex of the graph $G. | |
974 | ||
975 | =cut | |
976 | ||
977 | sub is_interior_vertex { | |
978 | my ($G, $v) = @_; | |
979 | ||
980 | $G->in_degree($v) && $G->out_degree($v); | |
981 | } | |
982 | ||
983 | =pod | |
984 | ||
985 | =item is_self_loop_vertex | |
986 | ||
987 | $b = $G->is_self_loop_vertex($v) | |
988 | ||
989 | Returns true if the vertex $v is a self-loop vertex of the graph $G. | |
990 | ||
991 | =cut | |
992 | ||
993 | sub is_self_loop_vertex { | |
994 | my ($G, $v) = @_; | |
995 | ||
996 | exists $G->{ Succ }->{ $v }->{ $v }; | |
997 | } | |
998 | ||
999 | =pod | |
1000 | ||
1001 | =item source_vertices | |
1002 | ||
1003 | @s = $G->source_vertices | |
1004 | ||
1005 | Returns the source vertices @s of the graph $G. | |
1006 | ||
1007 | =cut | |
1008 | ||
1009 | sub source_vertices { | |
1010 | my $G = shift; | |
1011 | ||
1012 | return grep { $G->is_source_vertex($_) } $G->vertices; | |
1013 | } | |
1014 | ||
1015 | =pod | |
1016 | ||
1017 | =item sink_vertices | |
1018 | ||
1019 | @s = $G->sink_vertices | |
1020 | ||
1021 | Returns the sink vertices @s of the graph $G. | |
1022 | ||
1023 | =cut | |
1024 | ||
1025 | sub sink_vertices { | |
1026 | my $G = shift; | |
1027 | ||
1028 | return grep { $G->is_sink_vertex($_) } $G->vertices; | |
1029 | } | |
1030 | ||
1031 | =pod | |
1032 | ||
1033 | =item isolated_vertices | |
1034 | ||
1035 | @i = $G->isolated_vertices | |
1036 | ||
1037 | Returns the isolated vertices @i of the graph $G. | |
1038 | ||
1039 | =cut | |
1040 | ||
1041 | sub isolated_vertices { | |
1042 | my $G = shift; | |
1043 | ||
1044 | return grep { $G->is_isolated_vertex($_) } $G->vertices; | |
1045 | } | |
1046 | ||
1047 | =pod | |
1048 | ||
1049 | =item exterior_vertices | |
1050 | ||
1051 | @e = $G->exterior_vertices | |
1052 | ||
1053 | Returns the exterior vertices @e of the graph $G. | |
1054 | ||
1055 | =cut | |
1056 | ||
1057 | sub exterior_vertices { | |
1058 | my $G = shift; | |
1059 | ||
1060 | return grep { $G->is_exterior_vertex($_) } $G->vertices; | |
1061 | } | |
1062 | ||
1063 | =pod | |
1064 | ||
1065 | =item interior_vertices | |
1066 | ||
1067 | @i = $G->interior_vertices | |
1068 | ||
1069 | Returns the interior vertices @i of the graph $G. | |
1070 | ||
1071 | =cut | |
1072 | ||
1073 | sub interior_vertices { | |
1074 | my $G = shift; | |
1075 | ||
1076 | return grep { $G->is_interior_vertex($_) } $G->vertices; | |
1077 | } | |
1078 | ||
1079 | =pod | |
1080 | ||
1081 | =item self_loop_vertices | |
1082 | ||
1083 | @s = $G->self_loop_vertices | |
1084 | ||
1085 | Returns the self-loop vertices @s of the graph $G. | |
1086 | ||
1087 | =cut | |
1088 | ||
1089 | sub self_loop_vertices { | |
1090 | my $G = shift; | |
1091 | ||
1092 | return grep { $G->is_self_loop_vertex($_) } $G->vertices; | |
1093 | } | |
1094 | ||
1095 | =pod | |
1096 | ||
1097 | =item density_limits | |
1098 | ||
1099 | ($sparse, $dense, $complete) = $G->density_limits | |
1100 | ||
1101 | Returns the density limits for the number of edges | |
1102 | in the graph $G. Note that reaching $complete edges | |
1103 | does not really guarantee completeness because we | |
1104 | can have multigraphs. The limit of sparse is less | |
1105 | than 1/4 of the edges of the complete graph, the | |
1106 | limit of dense is more than 3/4 of the edges of the | |
1107 | complete graph. | |
1108 | ||
1109 | =cut | |
1110 | ||
1111 | sub density_limits { | |
1112 | my $G = shift; | |
1113 | ||
1114 | my $V = $G->vertices; | |
1115 | my $M = $V * ($V - 1); | |
1116 | ||
1117 | $M = $M / 2 if $G->undirected; | |
1118 | ||
1119 | return ($M/4, 3*$M/4, $M); | |
1120 | } | |
1121 | ||
1122 | =pod | |
1123 | ||
1124 | =item density | |
1125 | ||
1126 | $d = $G->density | |
1127 | ||
1128 | Returns the density $d of the graph $G. | |
1129 | ||
1130 | =cut | |
1131 | ||
1132 | sub density { | |
1133 | my $G = shift; | |
1134 | my ($sparse, $dense, $complete) = $G->density_limits; | |
1135 | ||
1136 | return $complete ? $G->edges / $complete : 0; | |
1137 | } | |
1138 | ||
1139 | =pod | |
1140 | ||
1141 | =item is_sparse | |
1142 | ||
1143 | $d = $G->is_sparse | |
1144 | ||
1145 | Returns true if the graph $G is sparse. | |
1146 | ||
1147 | =cut | |
1148 | ||
1149 | sub is_sparse { | |
1150 | my $G = shift; | |
1151 | my ($sparse, $dense, $complete) = $G->density_limits; | |
1152 | ||
1153 | return $complete ? $G->edges / $complete <= $dense : 1; | |
1154 | } | |
1155 | ||
1156 | =pod | |
1157 | ||
1158 | =item is_dense | |
1159 | ||
1160 | $d = $G->is_dense | |
1161 | ||
1162 | Returns true if the graph $G is dense. | |
1163 | ||
1164 | =cut | |
1165 | ||
1166 | sub is_dense { | |
1167 | my $G = shift; | |
1168 | my ($sparse, $dense, $complete) = $G->density_limits; | |
1169 | ||
1170 | return $complete ? $G->edges / $complete >= $dense : 0; | |
1171 | } | |
1172 | ||
1173 | =pod | |
1174 | ||
1175 | =item complete | |
1176 | ||
1177 | $C = $G->complete; | |
1178 | ||
1179 | Returns a new complete graph $C corresponding to the graph $G. | |
1180 | ||
1181 | =cut | |
1182 | ||
1183 | sub complete { | |
1184 | my $G = shift; | |
1185 | my $C = (ref $G)->new; | |
1186 | my @V = $G->vertices; | |
1187 | ||
1188 | if ($G->directed) { | |
1189 | foreach my $u (@V) { | |
1190 | foreach my $v (@V) { | |
1191 | $C->add_edge($u, $v) unless $u eq $v; | |
1192 | } | |
1193 | } | |
1194 | } else { | |
1195 | my %E; | |
1196 | ||
1197 | foreach my $u (@V) { | |
1198 | foreach my $v (@V) { | |
1199 | next if $u eq $v or $E{$u}->{$v} || $E{$v}->{$u}; | |
1200 | $C->add_edge($u, $v); | |
1201 | $E{$u}->{$v}++; | |
1202 | $E{$v}->{$u}++; | |
1203 | } | |
1204 | } | |
1205 | } | |
1206 | ||
1207 | $C->directed($G->directed); | |
1208 | ||
1209 | return $C; | |
1210 | } | |
1211 | ||
1212 | =pod | |
1213 | ||
1214 | =item complement | |
1215 | ||
1216 | $C = $G->complement; | |
1217 | ||
1218 | Returns a new complement graph $C corresponding to the graph $G. | |
1219 | ||
1220 | =cut | |
1221 | ||
1222 | sub complement { | |
1223 | my $G = shift; | |
1224 | my $C = $G->complete; | |
1225 | ||
1226 | if (my @E = $G->edges) { | |
1227 | while (my ($u, $v) = splice(@E, 0, 2)) { | |
1228 | $C->delete_edge($u, $v); | |
1229 | } | |
1230 | } | |
1231 | ||
1232 | return $C; | |
1233 | } | |
1234 | ||
1235 | =pod | |
1236 | ||
1237 | =item copy | |
1238 | ||
1239 | $C = $G->copy; | |
1240 | ||
1241 | Returns a new graph $C corresponding to the graph $G. | |
1242 | ||
1243 | =cut | |
1244 | ||
1245 | sub copy { | |
1246 | my $G = shift; | |
1247 | my $C = (ref $G)->new($G->vertices); | |
1248 | ||
1249 | if (my @E = $G->edges) { | |
1250 | while (my ($u, $v) = splice(@E, 0, 2)) { | |
1251 | $C->add_edge($u, $v); | |
1252 | } | |
1253 | } | |
1254 | ||
1255 | $C->directed($G->directed); | |
1256 | ||
1257 | return $C; | |
1258 | } | |
1259 | ||
1260 | =pod | |
1261 | ||
1262 | =item transpose | |
1263 | ||
1264 | $T = $G->transpose; | |
1265 | ||
1266 | Returns a new transpose graph $T corresponding to the graph $G. | |
1267 | ||
1268 | =cut | |
1269 | ||
1270 | sub transpose { | |
1271 | my $G = shift; | |
1272 | ||
1273 | return $G->copy if $G->undirected; | |
1274 | ||
1275 | my $T = (ref $G)->new($G->vertices); | |
1276 | ||
1277 | if (my @E = $G->edges) { | |
1278 | while (my ($u, $v) = splice(@E, 0, 2)) { | |
1279 | $T->add_edge($v, $u); | |
1280 | } | |
1281 | } | |
1282 | ||
1283 | return $T; | |
1284 | } | |
1285 | ||
1286 | # _stringify | |
1287 | # | |
1288 | # $s = $G->_stringify($connector, $separator) | |
1289 | # | |
1290 | # (INTERNAL USE ONLY) | |
1291 | # Returns a string representation of the graph $G. | |
1292 | # The edges are represented by $connector and edges/isolated | |
1293 | # vertices are represented by $separator. | |
1294 | # | |
1295 | sub _stringify { | |
1296 | my ($G, $connector, $separator) = @_; | |
1297 | my @E = $G->edges; | |
1298 | my @e = map { [ $_ ] } $G->isolated_vertices; | |
1299 | ||
1300 | while (my ($u, $v) = splice(@E, 0, 2)) { | |
1301 | push @e, [$u, $v]; | |
1302 | } | |
1303 | ||
1304 | return join($separator, | |
1305 | map { @$_ == 2 ? | |
1306 | join($connector, $_->[0], $_->[1]) : | |
1307 | $_->[0] } | |
1308 | sort { $a->[0] cmp $b->[0] || @$a <=> @$b } @e); | |
1309 | } | |
1310 | ||
1311 | =pod | |
1312 | ||
1313 | =item set_attribute | |
1314 | ||
1315 | $G->set_attribute($attribute, $value) | |
1316 | $G->set_attribute($attribute, $v, $value) | |
1317 | $G->set_attribute($attribute, $u, $v, $value) | |
1318 | ||
1319 | Sets the $attribute of graph/vertex/edge to $value | |
1320 | but only if the vertex/edge already exists. Returns | |
1321 | true if the attribute is set successfully, false if not. | |
1322 | ||
1323 | =cut | |
1324 | ||
1325 | sub set_attribute { | |
1326 | my $G = shift; | |
1327 | my $attribute = shift; | |
1328 | my $value = pop; | |
1329 | my ($u, $v) = @_; | |
1330 | ||
1331 | if (defined $u) { | |
1332 | return 0 unless $G->has_vertex($u); | |
1333 | if (defined $v) { | |
1334 | return 0 unless $G->has_edge($u, $v); | |
1335 | $G->{ Attr }->{ E }->{ $u }->{ $v }->{ $attribute } = $value; | |
1336 | $G->{ Attr }->{ E }->{ $v }->{ $u }->{ $attribute } = $value | |
1337 | if $G->undirected; | |
1338 | } else { | |
1339 | $G->{ Attr }->{ V }->{ $u }->{ $attribute } = $value; | |
1340 | } | |
1341 | } else { | |
1342 | $G->{ Attr }->{ G }->{ $attribute } = $value; | |
1343 | } | |
1344 | ||
1345 | return 1; | |
1346 | } | |
1347 | ||
1348 | =pod | |
1349 | ||
1350 | =item get_attribute | |
1351 | ||
1352 | $value = $G->get_attribute($attribute) | |
1353 | $value = $G->get_attribute($attribute, $v) | |
1354 | $value = $G->get_attribute($attribute, $u, $v) | |
1355 | ||
1356 | Returns the $value of $attribute of graph/vertex/edge. | |
1357 | ||
1358 | =cut | |
1359 | ||
1360 | sub get_attribute { | |
1361 | my $G = shift; | |
1362 | my $attribute = shift; | |
1363 | my ($u, $v) = @_; | |
1364 | ||
1365 | if (defined $u) { | |
1366 | if (defined $v) { | |
1367 | return undef | |
1368 | unless exists $G->{ Attr }->{ E }; | |
1369 | ||
1370 | my $E = $G->{ Attr }->{ E }; | |
1371 | ||
1372 | if ( $G->directed ) { | |
1373 | return $E->{ $u }->{ $v }->{ $attribute }; | |
1374 | } else { | |
1375 | return undef | |
1376 | unless exists $G->{ Attr }->{ E }; | |
1377 | ||
1378 | return $E->{ $u }->{ $v }->{ $attribute } | |
1379 | if exists $E->{ $u }->{ $v }->{ $attribute }; | |
1380 | ||
1381 | return $E->{ $v }->{ $u }->{ $attribute }; | |
1382 | } | |
1383 | } else { | |
1384 | return $G->{ Attr }->{ V }->{ $u }->{ $attribute }; | |
1385 | } | |
1386 | } else { | |
1387 | return $G->{ Attr }->{ G }->{ $attribute }; | |
1388 | } | |
1389 | } | |
1390 | ||
1391 | =pod | |
1392 | ||
1393 | =item has_attribute | |
1394 | ||
1395 | $value = $G->has_attribute($attribute) | |
1396 | $value = $G->has_attribute($attribute, $v) | |
1397 | $value = $G->has_attribute($attribute, $u, $v) | |
1398 | ||
1399 | Returns the $value of $attribute of graph/vertex/edge. | |
1400 | ||
1401 | =cut | |
1402 | ||
1403 | sub has_attribute { | |
1404 | my $G = shift; | |
1405 | my $attribute = shift; | |
1406 | my ($u, $v) = @_; | |
1407 | ||
1408 | if (defined $u) { | |
1409 | if (defined $v) { | |
1410 | return undef | |
1411 | unless exists $G->{ Attr }->{ E }; | |
1412 | ||
1413 | my $E = $G->{ Attr }->{ E }; | |
1414 | ||
1415 | if ( $G->directed ) { | |
1416 | return exists $E->{ $u }->{ $v }->{ $attribute }; | |
1417 | } else { | |
1418 | return exists $E->{ $u }->{ $v }->{ $attribute } or | |
1419 | exists $E->{ $v }->{ $u }->{ $attribute }; | |
1420 | } | |
1421 | } else { | |
1422 | exists $G->{ Attr }->{ V }->{ $u }->{ $attribute }; | |
1423 | } | |
1424 | } else { | |
1425 | exists $G->{ Attr } && | |
1426 | exists $G->{ Attr }->{ G }->{ $attribute }; | |
1427 | } | |
1428 | } | |
1429 | ||
1430 | =pod | |
1431 | ||
1432 | =item get_attributes | |
1433 | ||
1434 | %attributes = $G->get_attributes() | |
1435 | %attributes = $G->get_attributes($v) | |
1436 | %attributes = $G->get_attributes($u, $v) | |
1437 | ||
1438 | Returns as a hash all the attribute names and values | |
1439 | of graph/vertex/edge. | |
1440 | ||
1441 | =cut | |
1442 | ||
1443 | sub get_attributes { | |
1444 | my $G = shift; | |
1445 | my ($u, $v) = @_; | |
1446 | ||
1447 | return ( ) unless exists $G->{ Attr }; | |
1448 | if (defined $u) { | |
1449 | if (defined $v) { | |
1450 | return exists $G->{ Attr }->{ E } && | |
1451 | exists $G->{ Attr }->{ E }->{ $u } && | |
1452 | exists $G->{ Attr }->{ E }->{ $u }->{ $v } ? | |
1453 | %{ $G->{ Attr }->{ E }->{ $u }->{ $v } } : | |
1454 | ( ); | |
1455 | } else { | |
1456 | return exists $G->{ Attr }->{ V } && | |
1457 | exists $G->{ Attr }->{ V }->{ $u } ? | |
1458 | %{ $G->{ Attr }->{ V }->{ $u } } : ( ); | |
1459 | } | |
1460 | } else { | |
1461 | return exists $G->{ Attr }->{ G } ? | |
1462 | %{ $G->{ Attr }->{ G } } : ( ); | |
1463 | } | |
1464 | } | |
1465 | ||
1466 | =pod | |
1467 | ||
1468 | =item delete_attribute | |
1469 | ||
1470 | $G->delete_attribute($attribute) | |
1471 | $G->delete_attribute($attribute, $v) | |
1472 | $G->delete_attribute($attribute, $u, $v) | |
1473 | ||
1474 | Deletes the $attribute of graph/vertex/edge. | |
1475 | ||
1476 | =cut | |
1477 | ||
1478 | sub delete_attribute { | |
1479 | my $G = shift; | |
1480 | my $attribute = shift; | |
1481 | my ($u, $v) = @_; | |
1482 | ||
1483 | if (defined $u) { | |
1484 | if (defined $v) { | |
1485 | return undef | |
1486 | unless exists $G->{ Attr }->{ E }; | |
1487 | ||
1488 | my $E = $G->{ Attr }->{ E }; | |
1489 | ||
1490 | if ( $G->directed ) { | |
1491 | delete $E->{ $u }->{ $v }->{ $attribute }; | |
1492 | } else { | |
1493 | delete $E->{ $v }->{ $u }->{ $attribute }; | |
1494 | delete $E->{ $v }->{ $u }->{ $attribute }; | |
1495 | } | |
1496 | } else { | |
1497 | delete $G->{ Attr }->{ V }->{ $u }->{ $attribute }; | |
1498 | } | |
1499 | } else { | |
1500 | delete $G->{ Attr }->{ G }->{ $attribute }; | |
1501 | } | |
1502 | } | |
1503 | ||
1504 | =pod | |
1505 | ||
1506 | =item delete_attributes | |
1507 | ||
1508 | $G->delete_attributes() | |
1509 | $G->delete_attributes($v) | |
1510 | $G->delete_attributes($u, $v) | |
1511 | ||
1512 | Deletes all the attributes of graph/vertex/edge. | |
1513 | ||
1514 | =cut | |
1515 | ||
1516 | sub delete_attributes { | |
1517 | my $G = shift; | |
1518 | my ($u, $v) = @_; | |
1519 | ||
1520 | if (defined $u) { | |
1521 | if (defined $v) { | |
1522 | delete $G->{ Attr }->{ E }->{ $u }->{ $v }; | |
1523 | } else { | |
1524 | delete $G->{ Attr }->{ V }->{ $u }; | |
1525 | } | |
1526 | } else { | |
1527 | delete $G->{ Attr }->{ G }; | |
1528 | } | |
1529 | } | |
1530 | ||
1531 | =pod | |
1532 | ||
1533 | =item add_weighted_edge | |
1534 | ||
1535 | $G->add_weighted_edge($u, $w, $v, $a) | |
1536 | ||
1537 | Adds in the graph $G an edge from vertex $u to vertex $v | |
1538 | and the edge attribute 'weight' set to $w. | |
1539 | ||
1540 | =cut | |
1541 | ||
1542 | sub add_weighted_edge { | |
1543 | my ($G, $u, $w, $v, $a) = @_; | |
1544 | ||
1545 | $G->add_edge($u, $v); | |
1546 | $G->set_attribute('weight', $u, $v, $w); | |
1547 | } | |
1548 | ||
1549 | =pod | |
1550 | ||
1551 | =item add_weighted_edges | |
1552 | ||
1553 | $G->add_weighted_edges($u1, $w1, $v1, $u2, $w2, $v2, ...) | |
1554 | ||
1555 | Adds in the graph $G the weighted edges. | |
1556 | ||
1557 | =cut | |
1558 | ||
1559 | sub add_weighted_edges { | |
1560 | my $G = shift; | |
1561 | ||
1562 | while (my ($u, $w, $v) = splice(@_, 0, 3)) { | |
1563 | $G->add_weighted_edge($u, $w, $v); | |
1564 | } | |
1565 | } | |
1566 | ||
1567 | =pod | |
1568 | ||
1569 | =item add_weighted_path | |
1570 | ||
1571 | $G->add_weighted_path($v1, $w1, $v2, $w2, ..., $wnm1, $vn) | |
1572 | ||
1573 | Adds in the graph $G the n edges defined by the path $v1 ... $vn | |
1574 | with the n-1 'weight' attributes $w1 ... $wnm1 | |
1575 | ||
1576 | =cut | |
1577 | ||
1578 | sub add_weighted_path { | |
1579 | my $G = shift; | |
1580 | my $u = shift; | |
1581 | ||
1582 | while (my ($w, $v) = splice(@_, 0, 2)) { | |
1583 | $G->add_weighted_edge($u, $w, $v); | |
1584 | $u = $v; | |
1585 | } | |
1586 | } | |
1587 | ||
1588 | =pod | |
1589 | ||
1590 | =item MST_Kruskal | |
1591 | ||
1592 | $MST = $G->MST_Kruskal; | |
1593 | ||
1594 | Returns Kruskal's Minimum Spanning Tree (as a graph) of | |
1595 | the graph $G based on the 'weight' attributes of the edges. | |
1596 | (Needs the ->vertex_set() method.) | |
1597 | ||
1598 | =cut | |
1599 | ||
1600 | sub MST_Kruskal { | |
1601 | my $G = shift; | |
1602 | my $MST = (ref $G)->new; | |
1603 | my @E = $G->edges; | |
1604 | my (@W, $u, $v, $w); | |
1605 | ||
1606 | while (($u, $v) = splice(@E, 0, 2)) { | |
1607 | $w = $G->get_attribute('weight', $u, $v); | |
1608 | next unless defined $w; # undef weight == infinitely heavy | |
1609 | push @W, [ $u, $v, $w ]; | |
1610 | } | |
1611 | ||
1612 | $MST->directed( $G->directed ); | |
1613 | ||
1614 | # Sort by weights. | |
1615 | foreach my $e ( sort { $a->[ 2 ] <=> $b->[ 2 ] } @W ) { | |
1616 | ($u, $v, $w) = @$e; | |
1617 | $MST->add_weighted_edge( $u, $w, $v ) | |
1618 | unless $MST->vertex_set( $u ) eq $MST->vertex_set( $v ); | |
1619 | } | |
1620 | ||
1621 | return $MST; | |
1622 | } | |
1623 | ||
1624 | =pod | |
1625 | ||
1626 | =item edge_classify | |
1627 | ||
1628 | @C = $G->edge_classify(%param) | |
1629 | ||
1630 | Returns the edge classification as a list where each element | |
1631 | is a triplet [$u, $v, $class] the $u, $v being the vertices | |
1632 | of an edge and $class being the class. The %param can be | |
1633 | used to control the search. | |
1634 | ||
1635 | =cut | |
1636 | ||
1637 | sub edge_classify { | |
1638 | my $G = shift; | |
1639 | ||
1640 | my $unseen_successor = | |
1641 | sub { | |
1642 | my ($u, $v, $T) = @_; | |
1643 | ||
1644 | # Freshly seen successors make for tree edges. | |
1645 | push @{ $T->{ edge_class_list } }, | |
1646 | [ $u, $v, 'tree' ]; | |
1647 | }; | |
1648 | my $seen_successor = | |
1649 | sub { | |
1650 | my ($u, $v, $T) = @_; | |
1651 | ||
1652 | my $class; | |
1653 | ||
1654 | if ( $T->{ G }->directed ) { | |
1655 | $class = 'cross'; # Default for directed non-tree edges. | |
1656 | ||
1657 | unless ( exists $T->{ vertex_finished }->{ $v } ) { | |
1658 | $class = 'back'; | |
1659 | } elsif ( $T->{ vertex_found }->{ $u } < | |
1660 | $T->{ vertex_found }->{ $v }) { | |
1661 | $class = 'forward'; | |
1662 | } | |
1663 | } else { | |
1664 | # No cross nor forward edges in | |
1665 | # an undirected graph, by definition. | |
1666 | $class = 'back'; | |
1667 | } | |
1668 | ||
1669 | push @{ $T->{ edge_class_list } }, [ $u, $v, $class ]; | |
1670 | }; | |
1671 | use Graph::DFS; | |
1672 | my $d = | |
1673 | Graph::DFS-> | |
1674 | new( $G, | |
1675 | unseen_successor => $unseen_successor, | |
1676 | seen_successor => $seen_successor, | |
1677 | @_); | |
1678 | ||
1679 | $d->preorder; | |
1680 | ||
1681 | return @{ $d->{ edge_class_list } }; | |
1682 | } | |
1683 | ||
1684 | =pod | |
1685 | ||
1686 | =item toposort | |
1687 | ||
1688 | @toposort = $G->toposort | |
1689 | ||
1690 | Returns the vertices of the graph $G sorted topologically. | |
1691 | ||
1692 | =cut | |
1693 | ||
1694 | sub toposort { | |
1695 | my $G = shift; | |
1696 | my $d = Graph::DFS->new($G); | |
1697 | ||
1698 | reverse $d->postorder; # That's it. | |
1699 | } | |
1700 | ||
1701 | # _strongly_connected | |
1702 | # | |
1703 | # $s = $G->_strongly_connected | |
1704 | # | |
1705 | # (INTERNAL USE ONLY) | |
1706 | # Returns a graph traversal object that can be used for | |
1707 | # strong connection computations. | |
1708 | # | |
1709 | sub _strongly_connected { | |
1710 | my $G = shift; | |
1711 | my $T = $G->transpose; | |
1712 | ||
1713 | Graph::DFS-> | |
1714 | new($T, | |
1715 | # Pick the potential roots in their DFS postorder. | |
1716 | strong_root_order => [ reverse Graph::DFS->new($G)->postorder ], | |
1717 | get_next_root => | |
1718 | sub { | |
1719 | my ($T, %param) = @_; | |
1720 | ||
1721 | while (my $root = | |
1722 | shift @{ $param{ strong_root_order } }) { | |
1723 | return $root if exists $T->{ pool }->{ $root }; | |
1724 | } | |
1725 | } | |
1726 | ); | |
1727 | } | |
1728 | ||
1729 | =pod | |
1730 | ||
1731 | =item strongly_connected_components | |
1732 | ||
1733 | @S = $G->strongly_connected_components | |
1734 | ||
1735 | Returns the strongly connected components @S of the graph $G | |
1736 | as a list of anonymous lists of vertices, each anonymous list | |
1737 | containing the vertices belonging to one strongly connected | |
1738 | component. | |
1739 | ||
1740 | =cut | |
1741 | ||
1742 | sub strongly_connected_components { | |
1743 | my $G = shift; | |
1744 | my $T = $G->_strongly_connected; | |
1745 | my %R = $T->_vertex_roots; | |
1746 | my @C; | |
1747 | ||
1748 | # Clump together vertices having identical root vertices. | |
1749 | while (my ($v, $r) = each %R) { push @{ $C[ $r ] }, $v } | |
1750 | ||
1751 | return @C; | |
1752 | } | |
1753 | ||
1754 | =pod | |
1755 | ||
1756 | =item strongly_connected_graph | |
1757 | ||
1758 | $T = $G->strongly_connected_graph | |
1759 | ||
1760 | Returns the strongly connected graph $T of the graph $G. | |
1761 | The names of the strongly connected components are | |
1762 | formed from their constituent vertices by concatenating | |
1763 | their names by '+'-characters: "a" and "b" --> "a+b". | |
1764 | ||
1765 | =cut | |
1766 | ||
1767 | sub strongly_connected_graph { | |
1768 | my $G = shift; | |
1769 | my $C = (ref $G)->new; | |
1770 | my $T = $G->_strongly_connected; | |
1771 | my %R = $T->_vertex_roots; | |
1772 | my @C; # We're not calling the strongly_connected_components() | |
1773 | # method because we will need also the %R. | |
1774 | ||
1775 | # Create the strongly connected components. | |
1776 | while (my ($v, $r) = each %R) { push @{ $C[$r] }, $v } | |
1777 | foreach my $c (@C) { $c = join("+", @$c) } | |
1778 | ||
1779 | $C->directed( $G->directed ); | |
1780 | ||
1781 | my @E = $G->edges; | |
1782 | ||
1783 | # Copy the edges between strongly connected components. | |
1784 | my $edge_cnt = 0; | |
1785 | my %n; | |
1786 | while (my ($u, $v) = splice(@E, 0, 2)) { | |
1787 | if ($R{ $u } != $R{ $v }) { | |
1788 | $C->add_edge( $C[ $R{ $u } ], $C[ $R{ $v } ] ); | |
1789 | $edge_cnt++; | |
1790 | } elsif ($edge_cnt == 0) { | |
1791 | $n{ $u } = ''; | |
1792 | } | |
1793 | } | |
1794 | if ($edge_cnt == 0) { | |
1795 | $C->add_vertex(join("+", keys %n)); | |
1796 | } | |
1797 | ||
1798 | return $C; | |
1799 | } | |
1800 | ||
1801 | =pod | |
1802 | ||
1803 | =item APSP_Floyd_Warshall | |
1804 | ||
1805 | $APSP = $G->APSP_Floyd_Warshall | |
1806 | ||
1807 | Returns the All-pairs Shortest Paths graph of the graph $G | |
1808 | computed using the Floyd-Warshall algorithm and the attribute | |
1809 | 'weight' on the edges. | |
1810 | The returned graph has an edge for each shortest path. | |
1811 | An edge has attributes "weight" and "path"; for the length of | |
1812 | the shortest path and for the path (an anonymous list) itself. | |
1813 | ||
1814 | =cut | |
1815 | ||
1816 | sub APSP_Floyd_Warshall { | |
1817 | my $G = shift; | |
1818 | ||
1819 | my @V = $G->vertices; | |
1820 | my @E = $G->edges; | |
1821 | my (%V2I, @I2V); | |
1822 | my (@P, @W); | |
1823 | ||
1824 | # Compute the vertex <-> index mappings. | |
1825 | @V2I{ @V } = 0..$#V; | |
1826 | @I2V[ 0..$#V ] = @V; | |
1827 | ||
1828 | # Initialize the predecessor matrix @P and the weight matrix @W. | |
1829 | # (The graph is converted into adjacency-matrix representation.) | |
1830 | # (The matrix is a list of lists.) | |
1831 | foreach my $i ( 0..$#V ) { $W[ $i ][ $i ] = 0 } | |
1832 | while ( my ($u, $v) = splice(@E, 0, 2) ) { | |
1833 | my ( $ui, $vi ) = ( $V2I{ $u }, $V2I{ $v } ); | |
1834 | $P[ $ui ][ $vi ] = $ui unless $ui == $vi; | |
1835 | $W[ $ui ][ $vi ] = $G->get_attribute( 'weight', $u, $v ); | |
1836 | } | |
1837 | ||
1838 | # Do the O(N**3) loop. | |
1839 | for ( my $k = 0; $k < @V; $k++ ) { | |
1840 | my (@nP, @nW); # new @P, new @W | |
1841 | ||
1842 | for ( my $i = 0; $i < @V; $i++ ) { | |
1843 | for ( my $j = 0; $j < @V; $j++ ) { | |
1844 | my $w_ij = $W[ $i ][ $j ]; | |
1845 | my $w_ik_kj = $W[ $i ][ $k ] + $W[ $k ][ $j ] | |
1846 | if defined $W[ $i ][ $k ] and | |
1847 | defined $W[ $k ][ $j ]; | |
1848 | ||
1849 | # Choose the minimum of w_ij and w_ik_kj. | |
1850 | if ( defined $w_ij ) { | |
1851 | if ( defined $w_ik_kj ) { | |
1852 | if ( $w_ij <= $w_ik_kj ) { | |
1853 | $nP[ $i ][ $j ] = $P[ $i ][ $j ]; | |
1854 | $nW[ $i ][ $j ] = $w_ij; | |
1855 | } else { | |
1856 | $nP[ $i ][ $j ] = $P[ $k ][ $j ]; | |
1857 | $nW[ $i ][ $j ] = $w_ik_kj; | |
1858 | } | |
1859 | } else { | |
1860 | $nP[ $i ][ $j ] = $P[ $i ][ $j ]; | |
1861 | $nW[ $i ][ $j ] = $w_ij; | |
1862 | } | |
1863 | } elsif ( defined $w_ik_kj ) { | |
1864 | $nP[ $i ][ $j ] = $P[ $k ][ $j ]; | |
1865 | $nW[ $i ][ $j ] = $w_ik_kj; | |
1866 | } | |
1867 | } | |
1868 | } | |
1869 | ||
1870 | @P = @nP; @W = @nW; # Update the predecessors and weights. | |
1871 | } | |
1872 | ||
1873 | # Now construct the APSP graph. | |
1874 | ||
1875 | my $APSP = (ref $G)->new; | |
1876 | ||
1877 | $APSP->directed( $G->directed ); # Copy the directedness. | |
1878 | ||
1879 | # Convert the adjacency-matrix representation | |
1880 | # into a Graph (adjacency-list representation). | |
1881 | for ( my $i = 0; $i < @V; $i++ ) { | |
1882 | my $iv = $I2V[ $i ]; | |
1883 | ||
1884 | for ( my $j = 0; $j < @V; $j++ ) { | |
1885 | if ( $i == $j ) { | |
1886 | $APSP->add_weighted_edge( $iv, 0, $iv ); | |
1887 | $APSP->set_attribute("path", $iv, $iv, [ $iv ]); | |
1888 | next; | |
1889 | } | |
1890 | next unless defined $W[ $i ][ $j ]; | |
1891 | ||
1892 | my $jv = $I2V[ $j ]; | |
1893 | ||
1894 | $APSP->add_weighted_edge( $iv, $W[ $i ][ $j ], $jv ); | |
1895 | ||
1896 | my @path = ( $jv ); | |
1897 | if ( $P[ $i ][ $j ] != $i ) { | |
1898 | my $k = $P[ $i ][ $j ]; # Walk back the path. | |
1899 | ||
1900 | while ( $k != $i ) { | |
1901 | push @path, $I2V[ $k ]; | |
1902 | $k = $P[ $i ][ $k ]; # Keep walking. | |
1903 | } | |
1904 | } | |
1905 | $APSP->set_attribute( "path", $iv, $jv, [ $iv, reverse @path ] ); | |
1906 | } | |
1907 | } | |
1908 | ||
1909 | return $APSP; | |
1910 | } | |
1911 | ||
1912 | =pod | |
1913 | ||
1914 | =item TransitiveClosure_Floyd_Warshall | |
1915 | ||
1916 | $TransitiveClosure = $G->TransitiveClosure_Floyd_Warshall | |
1917 | ||
1918 | Returns the Transitive Closure graph of the graph $G computed | |
1919 | using the Floyd-Warshall algorithm. | |
1920 | The resulting graph has an edge between each *ordered* pair of | |
1921 | vertices in which the second vertex is reachable from the first. | |
1922 | ||
1923 | =cut | |
1924 | ||
1925 | sub TransitiveClosure_Floyd_Warshall { | |
1926 | my $G = shift; | |
1927 | ||
1928 | my @V = $G->vertices; | |
1929 | my @E = $G->edges; | |
1930 | my (%V2I, @I2V); | |
1931 | my @C = ( '' ) x @V; | |
1932 | ||
1933 | # Compute the vertex <-> index mappings. | |
1934 | @V2I{ @V } = 0..$#V; | |
1935 | @I2V[ 0..$#V ] = @V; | |
1936 | ||
1937 | # Initialize the closure matrix @C. | |
1938 | # (The graph is converted into adjacency-matrix representation.) | |
1939 | # (The matrix is a bit matrix. Well, a list of bit vectors.) | |
1940 | foreach my $i ( 0..$#V ) { vec( $C[ $i ], $i, 1 ) = 1 } | |
1941 | while ( my ($u, $v) = splice(@E, 0, 2) ) { | |
1942 | vec( $C[ $V2I{ $u } ], $V2I{ $v }, 1 ) = 1 | |
1943 | } | |
1944 | ||
1945 | # Do the O(N**3) loop. | |
1946 | for ( my $k = 0; $k < @V; $k++ ) { | |
1947 | my @nC = ( '' ) x @V; # new @C | |
1948 | ||
1949 | for ( my $i = 0; $i < @V; $i++ ) { | |
1950 | for ( my $j = 0; $j < @V; $j++ ) { | |
1951 | vec( $nC[ $i ], $j, 1 ) = | |
1952 | vec( $C[ $i ], $j, 1 ) | | |
1953 | vec( $C[ $i ], $k, 1 ) & vec( $C[ $k ], $j, 1 ); | |
1954 | } | |
1955 | } | |
1956 | ||
1957 | @C = @nC; # Update the closure. | |
1958 | } | |
1959 | ||
1960 | # Now construct the TransitiveClosure graph. | |
1961 | ||
1962 | my $TransitiveClosure = (ref $G)->new; | |
1963 | ||
1964 | $TransitiveClosure->directed( $G->directed ); | |
1965 | ||
1966 | # Convert the (closure-)adjacency-matrix representation | |
1967 | # into a Graph (adjacency-list representation). | |
1968 | for ( my $i = 0; $i < @V; $i++ ) { | |
1969 | for ( my $j = 0; $j < @V; $j++ ) { | |
1970 | $TransitiveClosure->add_edge( $I2V[ $i ], $I2V[ $j ] ) | |
1971 | if vec( $C[ $i ], $j, 1 ); | |
1972 | } | |
1973 | } | |
1974 | ||
1975 | return $TransitiveClosure; | |
1976 | } | |
1977 | ||
1978 | =pod | |
1979 | ||
1980 | =item articulation points | |
1981 | ||
1982 | @A = $G->articulation_points(%param) | |
1983 | ||
1984 | Returns the articulation points (vertices) @A of the graph $G. | |
1985 | The %param can be used to control the search. | |
1986 | ||
1987 | =cut | |
1988 | ||
1989 | sub articulation_points { | |
1990 | my $G = shift; | |
1991 | my $articulate = | |
1992 | sub { | |
1993 | my ( $u, $T ) = @_; | |
1994 | ||
1995 | my $ap = $T->{ vertex_found }->{ $u }; | |
1996 | ||
1997 | my @S = @{ $T->{ active_list } }; # Current stack. | |
1998 | ||
1999 | $T->{ articulation_point }->{ $u } = $ap | |
2000 | unless exists $T->{ articulation_point }->{ $u }; | |
2001 | ||
2002 | # Walk back the stack marking the active DFS branch | |
2003 | # (below $u) as belonging to the articulation point $ap. | |
2004 | for ( my $i = 1; $i < @S; $i++ ) { | |
2005 | my $v = $S[ -$i ]; | |
2006 | ||
2007 | last if $v eq $u; | |
2008 | ||
2009 | $T->{ articulation_point }->{ $v } = $ap | |
2010 | if not exists $T->{ articulation_point }->{ $v } or | |
2011 | $ap < $T->{ articulation_point }->{ $v }; | |
2012 | } | |
2013 | }; | |
2014 | my $unseen_successor = | |
2015 | sub { | |
2016 | my ($u, $v, $T) = @_; | |
2017 | ||
2018 | # We need to know the number of children for root vertices. | |
2019 | $T->{ articulation_children }->{ $u }++; | |
2020 | }; | |
2021 | my $seen_successor = | |
2022 | sub { | |
2023 | my ($u, $v, $T) = @_; | |
2024 | ||
2025 | # If the $v is still active, articulate it. | |
2026 | $articulate->( $v, $T ) if exists $T->{ active_pool }->{ $v }; | |
2027 | }; | |
2028 | my $d = | |
2029 | Graph::DFS->new($G, | |
2030 | articulate => $articulate, | |
2031 | unseen_successor => $unseen_successor, | |
2032 | seen_successor => $seen_successor, | |
2033 | ); | |
2034 | ||
2035 | $d->preorder; | |
2036 | ||
2037 | # Now we need to find (the indices of) unique articulation points | |
2038 | # and map them back to vertices. | |
2039 | ||
2040 | my (%ap, @vf); | |
2041 | ||
2042 | foreach my $v ( $G->vertices ) { | |
2043 | $ap{ $d->{ articulation_point }->{ $v } } = $v; | |
2044 | $vf[ $d->{ vertex_found }->{ $v } ] = $v; | |
2045 | } | |
2046 | ||
2047 | %ap = map { ( $vf[ $_ ], $_ ) } keys %ap; | |
2048 | ||
2049 | # DFS tree roots are articulation points only | |
2050 | # iff they have more than one children. | |
2051 | foreach my $r ( $d->roots ) { | |
2052 | delete $ap{ $r } if $d->{ articulation_children }->{ $r } < 2; | |
2053 | } | |
2054 | ||
2055 | keys %ap; | |
2056 | } | |
2057 | ||
2058 | =pod | |
2059 | ||
2060 | =item is_biconnected | |
2061 | ||
2062 | $b = $G->is_biconnected | |
2063 | ||
2064 | Returns true is the graph $G is biconnected | |
2065 | (has no articulation points), false otherwise. | |
2066 | ||
2067 | =cut | |
2068 | ||
2069 | sub is_biconnected { | |
2070 | my $G = shift; | |
2071 | ||
2072 | return $G->articulation_points == 0; | |
2073 | } | |
2074 | ||
2075 | =pod | |
2076 | ||
2077 | =item largest_out_degree | |
2078 | ||
2079 | $v = $G->largest_out_degree( @V ) | |
2080 | ||
2081 | Selects the vertex $v from the vertices @V having | |
2082 | the largest out degree in the graph $G. | |
2083 | ||
2084 | =cut | |
2085 | ||
2086 | sub largest_out_degree { | |
2087 | my $G = shift; | |
2088 | my $L = shift; | |
2089 | my $O = $G->out_degree($L); | |
2090 | ||
2091 | for my $e (@_) { | |
2092 | my $o = $G->out_degree($e); | |
2093 | if ($o > $O) { | |
2094 | $L = $e; | |
2095 | $O = $o; | |
2096 | } | |
2097 | } | |
2098 | ||
2099 | return $L; | |
2100 | } | |
2101 | ||
2102 | # _heap_init | |
2103 | # | |
2104 | # $G->_heap_init($heap, $u, \%in_heap, \%weight, \%parent) | |
2105 | # | |
2106 | # (INTERNAL USE ONLY) | |
2107 | # Initializes the $heap with the vertex $u as the initial | |
2108 | # vertex, its weight being zero, and marking all vertices | |
2109 | # of the graph $G to be $in_heap, | |
2110 | # | |
2111 | sub _heap_init { | |
2112 | my ($G, $heap, $u, $in_heap, $W, $P) = @_; | |
2113 | ||
2114 | use Graph::HeapElem; | |
2115 | ||
2116 | foreach my $v ( $G->vertices ) { | |
2117 | my $e = Graph::HeapElem->new( $v, $W, $P ); | |
2118 | $heap->add( $e ); | |
2119 | $in_heap->{ $v } = $e; | |
2120 | } | |
2121 | ||
2122 | $W->{ $u } = 0; | |
2123 | } | |
2124 | ||
2125 | =pod | |
2126 | ||
2127 | =item MST_Prim | |
2128 | ||
2129 | $MST = $G->MST_Prim($u) | |
2130 | ||
2131 | Returns Prim's Minimum Spanning Tree (as a graph) of | |
2132 | the graph $G based on the 'weight' attributes of the edges. | |
2133 | The optional start vertex is $u, if none is given, a hopefully | |
2134 | good one (a vertex with a large out degree) is chosen. | |
2135 | ||
2136 | =cut | |
2137 | ||
2138 | sub MST_Prim { | |
2139 | my ( $G, $u ) = @_; | |
2140 | my $MST = (ref $G)->new; | |
2141 | ||
2142 | $u = $G->largest_out_degree( $G->vertices ) unless defined $u; | |
2143 | ||
2144 | use Heap::Fibonacci; | |
2145 | my $heap = Heap::Fibonacci->new; | |
2146 | my ( %in_heap, %weight, %parent ); | |
2147 | ||
2148 | $G->_heap_init( $heap, $u, \%in_heap, \%weight, \%parent ); | |
2149 | ||
2150 | # Walk the edges at the current BFS front | |
2151 | # in the order of their increasing weight. | |
2152 | while ( defined $heap->minimum ) { | |
2153 | $u = $heap->extract_minimum; | |
2154 | delete $in_heap{ $u->vertex }; | |
2155 | ||
2156 | # Now extend the BFS front. | |
2157 | ||
2158 | foreach my $v ( $G->successors( $u->vertex ) ) { | |
2159 | if ( defined( $v = $in_heap{ $v } ) ) { | |
2160 | my $nw = $G->get_attribute( 'weight', | |
2161 | $u->vertex, $v->vertex ); | |
2162 | my $ow = $v->weight; | |
2163 | ||
2164 | if ( not defined $ow or $nw < $ow ) { | |
2165 | $v->weight( $nw ); | |
2166 | $v->parent( $u->vertex ); | |
2167 | $heap->decrease_key( $v ); | |
2168 | } | |
2169 | } | |
2170 | } | |
2171 | } | |
2172 | ||
2173 | foreach my $v ( $G->vertices ) { | |
2174 | $MST->add_weighted_edge( $v, $weight{ $v }, $parent{ $v } ) | |
2175 | if defined $parent{ $v }; | |
2176 | } | |
2177 | ||
2178 | return $MST; | |
2179 | } | |
2180 | ||
2181 | # _SSSP_construct | |
2182 | # | |
2183 | # $SSSP = $G->_SSSP_construct( $s, $W, $P ); | |
2184 | # | |
2185 | # (INTERNAL USE ONLY) | |
2186 | # Return the SSSP($s) graph of graph $G based on the computed | |
2187 | # anonymous hashes for weights and parents: $W and $P. | |
2188 | # The vertices of the graph will have two attributes: "weight", | |
2189 | # which tells the length of the shortest single-source path, | |
2190 | # and "path", which is an anymous list containing the path. | |
2191 | # | |
2192 | sub _SSSP_construct { | |
2193 | my ($G, $s, $W, $P ) = @_; | |
2194 | my $SSSP = (ref $G)->new; | |
2195 | ||
2196 | foreach my $u ( $G->vertices ) { | |
2197 | $SSSP->add_vertex( $u ); | |
2198 | ||
2199 | $SSSP->set_attribute( "weight", $u, $W->{ $u } || 0 ); | |
2200 | ||
2201 | my @path = ( $u ); | |
2202 | if ( defined $P->{ $u } ) { | |
2203 | $SSSP->add_edge($P->{ $u }, $u ); | |
2204 | $SSSP->set_attribute( "weight", $P->{ $u }, $u, $G->get_attribute("weight",$P->{ $u }, $u) || 0 ); | |
2205 | push @path, $P->{ $u }; | |
2206 | if ( $P->{ $u } ne $s ) { | |
2207 | my $v = $P->{ $u }; | |
2208 | ||
2209 | while ( defined $v && exists $P->{ $v } && $v ne $s ) { | |
2210 | push @path, $P->{ $v }; | |
2211 | $v = $P->{ $v }; | |
2212 | } | |
2213 | } | |
2214 | } | |
2215 | $SSSP->set_attribute( "path", $u, [ reverse @path ] ); | |
2216 | } | |
2217 | ||
2218 | return $SSSP; | |
2219 | } | |
2220 | ||
2221 | =pod | |
2222 | ||
2223 | =item SSSP_Dijkstra | |
2224 | ||
2225 | $SSSP = $G->SSSP_Dijkstra($s) | |
2226 | ||
2227 | Returns the Single-source Shortest Paths (as a graph) | |
2228 | of the graph $G starting from the vertex $s using Dijktra's | |
2229 | SSSP algorithm. | |
2230 | ||
2231 | =cut | |
2232 | ||
2233 | sub SSSP_Dijkstra { | |
2234 | my ( $G, $s ) = @_; | |
2235 | ||
2236 | use Heap::Fibonacci; | |
2237 | my $heap = Heap::Fibonacci->new; | |
2238 | my ( %in_heap, %weight, %parent ); | |
2239 | ||
2240 | # The other weights are by default undef (infinite). | |
2241 | $weight{ $s } = 0; | |
2242 | ||
2243 | $G->_heap_init($heap, $s, \%in_heap, \%weight, \%parent ); | |
2244 | ||
2245 | # Walk the edges at the current BFS front | |
2246 | # in the order of their increasing weight. | |
2247 | while ( defined $heap->minimum ) { | |
2248 | my $u = $heap->extract_minimum; | |
2249 | delete $in_heap{ $u->vertex }; | |
2250 | ||
2251 | # Now extend the BFS front. | |
2252 | my $uw = $u->weight; | |
2253 | ||
2254 | foreach my $v ( $G->successors( $u->vertex ) ) { | |
2255 | if ( defined( $v = $in_heap{ $v } ) ) { | |
2256 | my $ow = $v->weight; | |
2257 | my $nw = | |
2258 | $G->get_attribute( 'weight', $u->vertex, $v->vertex ) + | |
2259 | ($uw || 0); # The || 0 helps for undefined $uw. | |
2260 | ||
2261 | # Relax the edge $u - $v. | |
2262 | if ( not defined $ow or $ow > $nw ) { | |
2263 | $v->weight( $nw ); | |
2264 | $v->parent( $u->vertex ); | |
2265 | $heap->decrease_key( $v ); | |
2266 | } | |
2267 | } | |
2268 | } | |
2269 | } | |
2270 | ||
2271 | return $G->_SSSP_construct( $s, \%weight, \%parent ); | |
2272 | } | |
2273 | ||
2274 | =pod | |
2275 | ||
2276 | =item SSSP_Bellman_Ford | |
2277 | ||
2278 | $SSSP = $G->SSSP_Bellman_Ford($s) | |
2279 | ||
2280 | Returns the Single-source Shortest Paths (as a graph) | |
2281 | of the graph $G starting from the vertex $s using Bellman-Ford | |
2282 | SSSP algorithm. If there are one or more negatively weighted | |
2283 | cycles, returns undef. | |
2284 | ||
2285 | =cut | |
2286 | ||
2287 | sub SSSP_Bellman_Ford { | |
2288 | my ( $G, $s ) = @_; | |
2289 | my ( %weight, %parent ); | |
2290 | ||
2291 | $weight{ $s } = 0; | |
2292 | ||
2293 | my $V = $G->vertices; | |
2294 | my @E = $G->edges; | |
2295 | ||
2296 | foreach ( 1..$V ) { # |V|-1 times (*not* |V| times) | |
2297 | my @C = @E; # Copy. | |
2298 | ||
2299 | while (my ($u, $v) = splice(@C, 0, 2)) { | |
2300 | my $ow = $weight{ $v }; | |
2301 | my $nw = $G->get_attribute( 'weight', $u, $v ); | |
2302 | ||
2303 | $nw += $weight{ $u } if defined $weight{ $u }; | |
2304 | # Relax the edge $u - $w. | |
2305 | if ( not defined $ow or $ow > $nw ) { | |
2306 | $weight{ $v } = $nw; | |
2307 | $parent{ $v } = $u; | |
2308 | } | |
2309 | } | |
2310 | } | |
2311 | ||
2312 | my $negative; | |
2313 | ||
2314 | # Warn about detected negative cycles. | |
2315 | while (my ($u, $v) = splice(@E, 0, 2)) { | |
2316 | if ( $weight{ $v } > | |
2317 | $weight{ $u } + $G->get_attribute( 'weight', $u, $v ) ) { | |
2318 | warn "SSSP_Bellman_Ford: negative cycle $u $v\n"; | |
2319 | $negative++; | |
2320 | } | |
2321 | } | |
2322 | ||
2323 | # Bail out if found negative cycles. | |
2324 | return undef if $negative; | |
2325 | ||
2326 | # Otherwise return the SSSP graph. | |
2327 | return $G->_SSSP_construct( $s, \%weight, \%parent ); | |
2328 | } | |
2329 | ||
2330 | =pod | |
2331 | ||
2332 | =item SSSP_DAG | |
2333 | ||
2334 | $SSSP = $G->SSSP_DAG($s) | |
2335 | ||
2336 | Returns the Single-source Shortest Paths (as a graph) | |
2337 | of the DAG $G starting from vertex $s. | |
2338 | ||
2339 | =cut | |
2340 | ||
2341 | sub SSSP_DAG { | |
2342 | my ( $G, $s ) = @_; | |
2343 | my $SSSP = (ref $G)->new; | |
2344 | ||
2345 | my ( %weight, %parent ); | |
2346 | ||
2347 | $weight{ $s } = 0; | |
2348 | ||
2349 | # Because by definition there can be no cycles | |
2350 | # we can freely explore each successor of each vertex. | |
2351 | foreach my $u ( $G->toposort ) { | |
2352 | foreach my $v ( $G->successors( $u ) ) { | |
2353 | my $ow = $weight{ $v }; | |
2354 | my $nw = $G->get_attribute( 'weight', $u, $v ); | |
2355 | ||
2356 | $nw += $weight{ $u } if defined $weight{ $u }; | |
2357 | ||
2358 | # Relax the edge $u - $v. | |
2359 | if ( not defined $ow or $ow > $nw ) { | |
2360 | $weight{ $v } = $nw; | |
2361 | $parent{ $v } = $u; | |
2362 | } | |
2363 | } | |
2364 | } | |
2365 | ||
2366 | return $G->_SSSP_construct( $s, \%weight, \%parent ); | |
2367 | } | |
2368 | ||
2369 | =pod | |
2370 | ||
2371 | =item add_capacity_edge | |
2372 | ||
2373 | $G->add_capacity_edge($u, $w, $v, $a) | |
2374 | ||
2375 | Adds in the graph $G an edge from vertex $u to vertex $v | |
2376 | and the edge attribute 'capacity' set to $w. | |
2377 | ||
2378 | =cut | |
2379 | ||
2380 | sub add_capacity_edge { | |
2381 | my ($G, $u, $w, $v, $a) = @_; | |
2382 | ||
2383 | $G->add_edge($u, $v); | |
2384 | $G->set_attribute('capacity', $u, $v, $w); | |
2385 | } | |
2386 | ||
2387 | =pod | |
2388 | ||
2389 | =item add_capacity_edges | |
2390 | ||
2391 | $G->add_capacity_edges($u1, $w1, $v1, $u2, $w2, $v2, ...) | |
2392 | ||
2393 | Adds in the graph $G the capacity edges. | |
2394 | ||
2395 | =cut | |
2396 | ||
2397 | sub add_capacity_edges { | |
2398 | my $G = shift; | |
2399 | ||
2400 | while (my ($u, $w, $v) = splice(@_, 0, 3)) { | |
2401 | $G->add_capacity_edge($u, $w, $v); | |
2402 | } | |
2403 | } | |
2404 | ||
2405 | =pod | |
2406 | ||
2407 | =item add_capacity_path | |
2408 | ||
2409 | $G->add_capacity_path($v1, $w1, $v2, $w2, ..., $wnm1, $vn) | |
2410 | ||
2411 | Adds in the graph $G the n edges defined by the path $v1 ... $vn | |
2412 | with the n-1 'capacity' attributes $w1 ... $wnm1 | |
2413 | ||
2414 | =cut | |
2415 | ||
2416 | sub add_capacity_path { | |
2417 | my $G = shift; | |
2418 | my $u = shift; | |
2419 | ||
2420 | while (my ($w, $v) = splice(@_, 0, 2)) { | |
2421 | $G->add_capacity_edge($u, $w, $v); | |
2422 | $u = $v; | |
2423 | } | |
2424 | } | |
2425 | ||
2426 | =pod | |
2427 | ||
2428 | =item Flow_Ford_Fulkerson | |
2429 | ||
2430 | $F = $G->Flow_Ford_Fulkerson($S) | |
2431 | ||
2432 | Returns the (maximal) flow network of the flow network $G, | |
2433 | parametrized by the state $S. The $G must have 'capacity' | |
2434 | attributes on its edges. $S->{ source } must contain the | |
2435 | source vertex and $S->{ sink } the sink vertex, and | |
2436 | most importantly $S->{ next_augmenting_path } must contain | |
2437 | an anonymous subroutine which takes $F and $S as arguments | |
2438 | and returns the next potential augmenting path. | |
2439 | Flow_Ford_Fulkerson will do the augmenting. | |
2440 | The result graph $F will have 'flow' and (residual) 'capacity' | |
2441 | attributes on its edges. | |
2442 | ||
2443 | =cut | |
2444 | ||
2445 | sub Flow_Ford_Fulkerson { | |
2446 | my ( $G, $S ) = @_; | |
2447 | ||
2448 | my $F = (ref $G)->new; # The flow network. | |
2449 | my @E = $G->edges; | |
2450 | my ( $u, $v ); | |
2451 | ||
2452 | # Copy the edges and the capacities, zero the flows. | |
2453 | while (($u, $v) = splice(@E, 0, 2)) { | |
2454 | $F->add_edge( $u, $v ); | |
2455 | $F->set_attribute( 'capacity', $u, $v, | |
2456 | $G->get_attribute( 'capacity', $u, $v ) || 0 ); | |
2457 | $F->set_attribute( 'flow', $u, $v, 0 ); | |
2458 | } | |
2459 | ||
2460 | # Walk the augmenting paths. | |
2461 | while ( my $ap = $S->{ next_augmenting_path }->( $F, $S ) ) { | |
2462 | my @aps = @$ap; # augmenting path segments | |
2463 | my $apr; # augmenting path residual capacity | |
2464 | my $psr; # path segment residual capacity | |
2465 | ||
2466 | # Find the minimum capacity of the path. | |
2467 | for ( $u = shift @aps; @aps; $u = $v ) { | |
2468 | $v = shift @aps; | |
2469 | $psr = $F->get_attribute( 'capacity', $u, $v ) - | |
2470 | $F->get_attribute( 'flow', $u, $v ); | |
2471 | $apr = $psr | |
2472 | if $psr >= 0 and ( not defined $apr or $psr < $apr ); | |
2473 | } | |
2474 | ||
2475 | if ( $apr > 0 ) { # Augment the path. | |
2476 | for ( @aps = @$ap, $u = shift @aps; @aps; $u = $v ) { | |
2477 | $v = shift @aps; | |
2478 | $F->set_attribute( 'flow', | |
2479 | $u, $v, | |
2480 | $F->get_attribute( 'flow', $u, $v ) + | |
2481 | $apr ); | |
2482 | } | |
2483 | } | |
2484 | } | |
2485 | ||
2486 | return $F; | |
2487 | } | |
2488 | ||
2489 | =pod | |
2490 | ||
2491 | =item Flow_Edmonds_Karp | |
2492 | ||
2493 | $F = $G->Flow_Edmonds_Karp($source, $sink) | |
2494 | ||
2495 | Return the maximal flow network of the graph $G built | |
2496 | using the Edmonds-Karp version of Ford-Fulkerson. | |
2497 | The input graph $G must have 'capacity' attributes on | |
2498 | its edges; resulting flow graph will have 'capacity' and 'flow' | |
2499 | attributes on its edges. | |
2500 | ||
2501 | =cut | |
2502 | ||
2503 | sub Flow_Edmonds_Karp { | |
2504 | my ( $G, $source, $sink ) = @_; | |
2505 | ||
2506 | my $S; | |
2507 | ||
2508 | $S->{ source } = $source; | |
2509 | $S->{ sink } = $sink; | |
2510 | $S->{ next_augmenting_path } = | |
2511 | sub { | |
2512 | my ( $F, $S ) = @_; | |
2513 | ||
2514 | my $source = $S->{ source }; | |
2515 | my $sink = $S->{ sink }; | |
2516 | ||
2517 | # Initialize our "todo" heap. | |
2518 | unless ( exists $S->{ todo } ) { | |
2519 | # The first element is a hash recording the vertices | |
2520 | # seen so far, the rest are the path from the source. | |
2521 | push @{ $S->{ todo } }, | |
2522 | [ { $source => 1 }, $source ]; | |
2523 | } | |
2524 | ||
2525 | while ( @{ $S->{ todo } } ) { | |
2526 | # $ap: The next augmenting path. | |
2527 | my $ap = shift @{ $S->{ todo } }; | |
2528 | my $sv = shift @$ap; # The seen vertices. | |
2529 | my $v = $ap->[ -1 ]; # The last vertex of path. | |
2530 | ||
2531 | if ( $v eq $sink ) { | |
2532 | return $ap; | |
2533 | } else { | |
2534 | foreach my $s ( $G->successors( $v ) ) { | |
2535 | unless ( exists $sv->{ $s } ) { | |
2536 | push @{ $S->{ todo } }, | |
2537 | [ { %$sv, $s => 1 }, @$ap, $s ]; | |
2538 | } | |
2539 | } | |
2540 | } | |
2541 | } | |
2542 | }; | |
2543 | ||
2544 | return $G->Flow_Ford_Fulkerson( $S ); | |
2545 | } | |
2546 | ||
2547 | use overload 'eq' => \&eq; | |
2548 | ||
2549 | =pod | |
2550 | ||
2551 | =item eq | |
2552 | ||
2553 | $G->eq($H) | |
2554 | ||
2555 | Return true if the graphs (actually, their string representations) | |
2556 | are identical. This means really identical: they must have identical | |
2557 | vertex names and identical edges between the vertices, and they must | |
2558 | be similarly directed. (Just isomorphism isn't enough.) | |
2559 | ||
2560 | =cut | |
2561 | ||
2562 | sub eq { | |
2563 | my ($G, $H) = @_; | |
2564 | ||
2565 | return ref $H ? $G->stringify eq $H->stringify : $G->stringify eq $H; | |
2566 | } | |
2567 | ||
2568 | =pod | |
2569 | ||
2570 | =back | |
2571 | ||
2572 | =head1 COPYRIGHT | |
2573 | ||
2574 | Copyright 1999, O'Reilly & Associates. | |
2575 | ||
2576 | This code is distributed under the same copyright terms as Perl itself. | |
2577 | ||
2578 | =cut | |
2579 | ||
2580 | 1; |