CM::make "graphs.lib";
# page 556 in CLR
generic package TestAllPairsShortestPaths (AP: All_Pairs_Shortest_Paths
where type Num::Element = Int)
{
my G as graph::GRAPH g = digraph_by_adjacency_list::graph("foo", (), 10) : graph::graph( String, Int, Void )
my _ = apply g.add_node
[(1, "1"),
(2, "2"),
(3, "3"),
(4, "4"),
(5, "5")
]
E = [(1, 2, 3),
(1, 3, 8),
(1, 5,-4),
(2, 4, 1),
(2, 5, 7),
(3, 2, 4),
(4, 1, 2),
(4, 3,-5),
(5, 4, 6)
]
my _ = apply g.add_edge E
# my _ = apply (\\ (i, j, w) => g.add_edge (j, i, w)) E
dist' = [[0, 1,-3, 2,-4],
[3, 0,-4, 1,-1],
[7, 4, 0, 5, 3],
[2,-1,-5, 0,-2],
[8, 5, 1, 6, 0]
]
prior' = [[-1, 3, 4, 5, 1],
[4,-1, 4, 2, 1],
[4, 3,-1, 2, 1],
[4, 3, 4,-1, 1],
[4, 3, 4, 5,-1]
]
fun toList M =
let N = 5
fun f (i, j) = if j > N then [] else rw_matrix::sub (M, i, j) . f (i, j+1)
fun g i = if i > N then [] else f (i, 1) . g (i+1)
in g 1
end
fun test () =
let fun weight (_, _, w) = w
my { dist, prior } = ap::all_pairs_shortest_paths { graph=G, weight=weight }
dist=toList dist
prior=toList prior
in if dist != dist' or prior != prior' then raise exception MATCH
{ dist=dist, prior=pred }
end
}
package test_warshall = TestAllPairsShortestPaths(
floyd_warshals_all_pairs_shortest_path_g (package { type Element = Int
use Int
zero = 0
my ==== : Int * Int -> Bool = op =
inf = 100000000
}))
package test_johnson = TestAllPairsShortestPaths(
johnsons_all_pairs_shortest_paths_g (package { type Element = Int
use Int
zero = 0
my ==== : Int * Int -> Bool = op =
inf = 100000000
}))