CM::make "graphs.lib";
generic package TestShortestPaths (SP: Single_Source_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
[(0, "s"),
(1, "u"),
(2, "v"),
(3, "x"),
(4, "y")
]
E = [(0, 1, 10),
(0, 2, 5),
(1, 2, 2),
(2, 1, 3),
(1, 3, 1),
(2, 3, 9),
(2, 4, 2),
(3, 4, 4),
(4, 3, 6),
(4, 0, 7)
]
my _ = apply g.add_edge E
dist' = [0, 8, 5, 9, 7]
prior' = [-1, 2, 0, 1, 2]
fun test () =
let fun weight (_, _, w) = w
my { dist, prior } = sp::single_source_shortest_paths
{ graph=G, weight=weight, s=0 }
dist'' = rw_vector::fold_backward op . [] dist
prior'' = rw_vector::fold_backward op . [] prior
in if dist' != dist'' or prior' != prior'' then
raise exception MATCH
{ dist=dist, prior=pred }
end
}
package test_dijkstra
=
TestShortestPaths(
dijkstras_single_source_shortest_paths_g (package { use int
type Element = Int
zero = 0
inf = 10000000
my ==== : Int * Int -> Bool = op=
}))
package test_bellman_ford
=
TestShortestPaths(
bellman_fords_single_source_shortest_paths_g (package { use int
type Element = Int
zero = 0
inf = 10000000
my ==== : Int * Int -> Bool = op=
}))