Algorithms like A* don't work with UndirectedAdaptor #870
Description
The UndirectedAdaptor's implementation of IntoEdges does not faithfully reproduce the set of edges that an equivalently constructed undirected graph would have. The result is that search and traversal algorithms cannot traverse adapted edges whose underlying directed edge points the "wrong way".
This example unit test has a directed linear graph going from node 0 to node 5 in order.
When adapted as an undirected graph, A* cannot find a path from 5 to 0.
static LINEAR_EDGES: [(u32, u32); 5] = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5)];
...
#[test]
pub fn test_undirected_adapter_can_traverse() {
// UNGraph
{
std::eprintln!("Testing with UNGraph");
let og_ungraph = Graph::<(), (), crate::Undirected>::from_edges(LINEAR_EDGES);
assert_eq!(og_ungraph.is_directed(), false);
let mut nodes = og_ungraph.node_identifiers().collect::<Vec<_>>();
nodes.sort();
for i in 0..nodes.len() {
let n = nodes[i];
let edges = og_ungraph.edges(n).collect::<Vec<_>>();
std::eprintln!("edges of {n:?}: {edges:?}");
}
}
{
std::eprintln!("Testing with Graph");
let graph = DiGraph::<(), ()>::from_edges(LINEAR_EDGES);
let mut nodes = graph.node_identifiers().collect::<Vec<_>>();
nodes.sort();
for i in 0..nodes.len() {
let n = nodes[i];
let edges = graph.edges(n).collect::<Vec<_>>();
std::eprintln!("edges of {n:?}: {edges:?}");
}
}
{
std::eprintln!("Testing with adapted Graph");
let graph = DiGraph::<(), ()>::from_edges(LINEAR_EDGES);
let ungraph = UndirectedAdaptor(&graph);
let mut nodes = graph.node_identifiers().collect::<Vec<_>>();
nodes.sort();
for i in 0..nodes.len() {
let n = nodes[i];
let edges = ungraph.edges(n).collect::<Vec<_>>();
std::eprintln!("edges of {n:?}: {edges:?}");
}
}
let graph = DiGraph::<(), ()>::from_edges(LINEAR_EDGES);
let mut nodes = graph.node_identifiers().collect::<Vec<_>>();
nodes.sort();
let ungraph = UndirectedAdaptor(&graph);
let path = astar(&ungraph, nodes[5], |n| n == nodes[0], |_| 1, |_| 0);
let x = path.unwrap(); // Panics
}I've included additional log output which shows the difference in the edges() output between an originally-constructed UnGraph and an adapted Ungraph.
Testing with UNGraph
edges of NodeIndex(0): [EdgeReference { index: EdgeIndex(0), node: [NodeIndex(0), NodeIndex(1)], weight: () }]
edges of NodeIndex(1): [EdgeReference { index: EdgeIndex(1), node: [NodeIndex(1), NodeIndex(2)], weight: () }, EdgeReference { index: EdgeIndex(0), node: [NodeIndex(1), NodeIndex(0)], weight: () }]
edges of NodeIndex(2): [EdgeReference { index: EdgeIndex(2), node: [NodeIndex(2), NodeIndex(3)], weight: () }, EdgeReference { index: EdgeIndex(1), node: [NodeIndex(2), NodeIndex(1)], weight: () }]
edges of NodeIndex(3): [EdgeReference { index: EdgeIndex(3), node: [NodeIndex(3), NodeIndex(4)], weight: () }, EdgeReference { index: EdgeIndex(2), node: [NodeIndex(3), NodeIndex(2)], weight: () }]
edges of NodeIndex(4): [EdgeReference { index: EdgeIndex(4), node: [NodeIndex(4), NodeIndex(5)], weight: () }, EdgeReference { index: EdgeIndex(3), node: [NodeIndex(4), NodeIndex(3)], weight: () }]
edges of NodeIndex(5): [EdgeReference { index: EdgeIndex(4), node: [NodeIndex(5), NodeIndex(4)], weight: () }]
Testing with Graph
edges of NodeIndex(0): [EdgeReference { index: EdgeIndex(0), node: [NodeIndex(0), NodeIndex(1)], weight: () }]
edges of NodeIndex(1): [EdgeReference { index: EdgeIndex(1), node: [NodeIndex(1), NodeIndex(2)], weight: () }]
edges of NodeIndex(2): [EdgeReference { index: EdgeIndex(2), node: [NodeIndex(2), NodeIndex(3)], weight: () }]
edges of NodeIndex(3): [EdgeReference { index: EdgeIndex(3), node: [NodeIndex(3), NodeIndex(4)], weight: () }]
edges of NodeIndex(4): [EdgeReference { index: EdgeIndex(4), node: [NodeIndex(4), NodeIndex(5)], weight: () }]
edges of NodeIndex(5): []
Testing with adapted Graph
edges of NodeIndex(0): [EdgeReference { index: EdgeIndex(0), node: [NodeIndex(0), NodeIndex(1)], weight: () }]
edges of NodeIndex(1): [EdgeReference { index: EdgeIndex(0), node: [NodeIndex(0), NodeIndex(1)], weight: () }, EdgeReference { index: EdgeIndex(1), node: [NodeIndex(1), NodeIndex(2)], weight: () }]
edges of NodeIndex(2): [EdgeReference { index: EdgeIndex(1), node: [NodeIndex(1), NodeIndex(2)], weight: () }, EdgeReference { index: EdgeIndex(2), node: [NodeIndex(2), NodeIndex(3)], weight: () }]
edges of NodeIndex(3): [EdgeReference { index: EdgeIndex(2), node: [NodeIndex(2), NodeIndex(3)], weight: () }, EdgeReference { index: EdgeIndex(3), node: [NodeIndex(3), NodeIndex(4)], weight: () }]
edges of NodeIndex(4): [EdgeReference { index: EdgeIndex(3), node: [NodeIndex(3), NodeIndex(4)], weight: () }, EdgeReference { index: EdgeIndex(4), node: [NodeIndex(4), NodeIndex(5)], weight: () }]
edges of NodeIndex(5): [EdgeReference { index: EdgeIndex(4), node: [NodeIndex(4), NodeIndex(5)], weight: () }]
The originally-constructed UnGraph has each edge referenced twice in each orientation. This allows A* and other algorithms to work successfully. The adapted UnGraph has each edge referenced twice, but in the same orientation two times. This prevents traversal of adapted edges when the underlying direct edge is oriented in such a way that it would prevent traversal.
I've got a fix ready. I'll make a PR.