blob: c6ee7facb2a5660f4a40ec6e5bafe1e8579cbdd6 [file] [log] [blame]
use alloc::vec::Vec;
use numi::borrow::Moo;
use petgraph_core::{Edge, GraphStorage};
use petgraph_dino::{DiDinoGraph, EdgeId, NodeId};
use petgraph_utils::{graph, GraphCollection};
use crate::shortest_paths::{
common::tests::{expected, Expect, TestCase},
dijkstra::Dijkstra,
ShortestPath,
};
graph!(
/// Uses the graph from networkx
///
/// <https://github.com/networkx/networkx/blob/main/networkx/algorithms/shortest_paths/tests/test_weighted.py>
factory(networkx) => DiDinoGraph<&'static str, i32>;
[
a: "A",
b: "B",
c: "C",
d: "D",
e: "E",
] as NodeId, [
ab: a -> b: 10,
ac: a -> c: 5,
bd: b -> d: 1,
bc: b -> c: 2,
de: d -> e: 1,
cb: c -> b: 3,
cd: c -> d: 5,
ce: c -> e: 2,
ea: e -> a: 7,
ed: e -> d: 6,
] as EdgeId
);
fn networkx_directed_expect_from(
nodes: &networkx::NodeCollection<NodeId>,
) -> Vec<Expect<NodeId, i32>> {
expected!(nodes; [
a -()> a: 0,
a -(c)> b: 8,
a -()> c: 5,
a -(c, b)> d: 9,
a -(c)> e: 7,
])
}
graph!(
/// Uses a randomly generated graph
factory(random) => DiDinoGraph<&'static str, &'static str>;
[
a: "A",
b: "B",
c: "C",
d: "D",
e: "E",
f: "F",
] as NodeId, [
ab: a -> b: "apple",
bc: b -> c: "cat",
cd: c -> d: "giraffe",
de: d -> e: "is",
ef: e -> f: "banana",
fa: f -> a: "bear",
ad: a -> d: "elephant",
] as EdgeId
);
// TODO: multigraph
#[test]
fn path_from_directed_default_edge_cost() {
let GraphCollection { graph, nodes, .. } = networkx::create();
let expected = networkx_directed_expect_from(&nodes);
let dijkstra = Dijkstra::directed();
TestCase::new(&graph, &dijkstra, &expected).assert_path_from(nodes.a);
}
#[test]
fn distance_from_directed_default_edge_cost() {
let GraphCollection { graph, nodes, .. } = networkx::create();
let expected = networkx_directed_expect_from(&nodes);
let dijkstra = Dijkstra::directed();
TestCase::new(&graph, &dijkstra, &expected).assert_distance_from(nodes.a);
}
fn random_directed_expect_from(
nodes: &random::NodeCollection<NodeId>,
) -> Vec<Expect<NodeId, usize>> {
expected!(nodes; [
a -()> a: 0,
a -()> b: 5,
a -(b)> c: 8,
a -()> d: 8,
a -(d)> e: 10,
a -(d, e)> f: 16,
])
}
fn edge_cost<S>(edge: Edge<S>) -> Moo<'_, usize>
where
S: GraphStorage,
S::EdgeWeight: AsRef<[u8]>,
{
Moo::Owned(edge.weight().as_ref().len())
}
#[test]
fn path_from_directed_custom_edge_cost() {
let GraphCollection { graph, nodes, .. } = random::create();
let dijkstra = Dijkstra::directed().with_edge_cost(edge_cost);
let expected = random_directed_expect_from(&nodes);
TestCase::new(&graph, &dijkstra, &expected).assert_path_from(nodes.a);
}
#[test]
fn distance_from_directed_custom_edge_cost() {
let GraphCollection { graph, nodes, .. } = random::create();
let dijkstra = Dijkstra::directed().with_edge_cost(edge_cost);
let expected = random_directed_expect_from(&nodes);
TestCase::new(&graph, &dijkstra, &expected).assert_distance_from(nodes.a);
}
fn networkx_undirected_expect_from(
nodes: &networkx::NodeCollection<NodeId>,
) -> Vec<Expect<NodeId, i32>> {
expected!(nodes; [
a -()> a: 0,
a -(c)> b: 7,
a -()> c: 5,
a -(e)> d: 8,
a -()> e: 7,
])
}
#[test]
fn path_from_undirected_default_edge_cost() {
let GraphCollection { graph, nodes, .. } = networkx::create();
let dijkstra = Dijkstra::undirected();
let expected = networkx_undirected_expect_from(&nodes);
TestCase::new(&graph, &dijkstra, &expected).assert_path_from(nodes.a);
}
#[test]
fn distance_from_undirected_default_edge_cost() {
let GraphCollection { graph, nodes, .. } = networkx::create();
let dijkstra = Dijkstra::undirected();
let expected = networkx_undirected_expect_from(&nodes);
TestCase::new(&graph, &dijkstra, &expected).assert_distance_from(nodes.a);
}
fn random_undirected_expect_from(
nodes: &random::NodeCollection<NodeId>,
) -> Vec<Expect<NodeId, usize>> {
expected!(nodes; [
a -()> a: 0,
a -()> b: 5,
a -(b)> c: 8,
a -()> d: 8,
a -(f)> e: 10,
a -()> f: 4,
])
}
#[test]
fn path_from_undirected_custom_edge_cost() {
let GraphCollection { graph, nodes, .. } = random::create();
let dijkstra = Dijkstra::undirected().with_edge_cost(edge_cost);
let expected = random_undirected_expect_from(&nodes);
TestCase::new(&graph, &dijkstra, &expected).assert_path_from(nodes.a);
}
#[test]
fn distance_from_undirected_custom_edge_cost() {
let GraphCollection { graph, nodes, .. } = random::create();
let dijkstra = Dijkstra::undirected().with_edge_cost(edge_cost);
let expected = random_undirected_expect_from(&nodes);
TestCase::new(&graph, &dijkstra, &expected).assert_distance_from(nodes.a);
}
#[test]
fn lifetime() {
let GraphCollection { graph, nodes, .. } = networkx::create();
let dijkstra = Dijkstra::directed();
let top3: Vec<_> = dijkstra
.path_from(&graph, nodes.a)
.unwrap()
.take(3)
.collect();
drop(dijkstra);
let top3: Vec<_> = top3
.into_iter()
.map(|route| route.into_cost().into_value())
.collect();
assert_eq!(top3, [0, 5, 7]);
}
// fn non_empty_graph() -> impl Strategy<Value = Graph<(), u8, Directed, u8>> {
// any::<Graph<(), u8, Directed, u8>>()
// .prop_filter("graph is empty", |graph| graph.node_count() > 0)
// }
// #[cfg(not(miri))]
// proptest! {
// #[test]
// fn triangle_inequality(
// graph in non_empty_graph(),
// node in any::<Index>()
// ) { let node = NodeIndex::new(node.index(graph.node_count())); let result = dijkstra(&graph,
// node, None, |edge| *edge.weight() as u32);
//
// // triangle inequality:
// // d(v,u) <= d(v,v2) + d(v2,u)
// for (node, weight) in &result {
// for edge in graph.edges(*node) {
// let next = edge.target();
// let next_weight = *edge.weight() as u32;
//
// if result.contains_key(&next) {
// assert!(result[&next] <= *weight + next_weight);
// }
// }
// }
// }
// }