| Name : perl-Algorithm-Graphs-TransitiveClosure
| |
| Version : 2009110901
| Vendor : obs://build_opensuse_org/devel:languages:perl
|
| Release : 9.63
| Date : 2024-08-05 19:09:44
|
| Group : Development/Libraries/Perl
| Source RPM : perl-Algorithm-Graphs-TransitiveClosure-2009110901-9.63.src.rpm
|
| Size : 0.02 MB
| |
| Packager : (none)
| |
| Summary : Calculate the transitive closure
|
Description :
This is an implementation of the well known _Floyd-Warshall_ algorithm.
[1,2]
The subroutine \'floyd_warshall\' takes a directed graph, and calculates its
transitive closure, which will be returned. The given graph is actually
modified, so be sure to pass a copy of the graph to the routine if you need
to keep the original graph.
The subroutine takes graphs in one of the two following formats:
* floyd_warshall ARRAYREF
The graph _G = (V, E)_ is described with a list of lists, \'$graph\',
representing _V x V_. If there is an edge between vertices \'$i\' and \'$j\'
(or if \'$i == $j\'), then \'$graph -> [$i] -> [$j] == 1\'. For all other pairs
\'($k, $l)\' from _V x V_, \'$graph -> [$k] -> [$l] == 0\'.
The resulting \'$graph\' will have \'$graph -> [$i] -> [$j] == 1\' iff \'$i ==
$j\' or there is a path in _G_ from \'$i\' to \'$j\', and \'$graph -> [$i] ->
[$j] == 0\' otherwise.
* floyd_warshall HASHREF
The graph _G = (V, E)_, with labeled vertices, is described with a hash of
hashes, \'$graph\', representing _V x V_. If there is an edge between
vertices \'$label1\' and \'$label2\' (or if \'$label1 eq $label2\'), then \'$graph
-> {$label1} -> {$label2} == 1\'. For all other pairs \'($label3, $label4)\'
from _V x V_, \'$graph -> {$label3} -> {$label4}\' does not exist.
The resulting \'$graph\' will have \'$graph -> {$label1} -> {$label2} == 1\'
iff \'$label1 eq $label2\' or there is a path in _G_ from \'$label1\' to
\'$label2\', and \'$graph -> {$label1} -> {$label2}\' does not exist otherwise.
|
RPM found in directory: /packages/linux-pbone/ftp5.gwdg.de/pub/opensuse/repositories/devel:/languages:/perl:/CPAN-A/openSUSE_Tumbleweed/noarch |
