Open bbannier opened 5 months ago
@ZigRazor, this is a more general issue than #405 and still exists. Can you please reopen?
This is still an issue. Below test should pass, but fails:
TEST(Foo, bar) {
// Construct a simple directed graph (1) --> (2) --> (3).
CXXGraph::Graph<int> g;
CXXGraph::Node<int> n1("1", 1);
CXXGraph::Node<int> n2("2", 2);
CXXGraph::Node<int> n3("3", 3);
for (auto &&n : {n1, n2, n3}) {
g.addNode(&n);
}
CXXGraph::DirectedEdge<int> e1(1, {&n1, &n2});
CXXGraph::DirectedEdge<int> e2(2, {&n2, &n3});
for (auto &&e : {e1, e2}) {
g.addEdge(&e);
}
ASSERT_EQ(g.outNeighbors(&n1).size(), 1);
ASSERT_EQ(g.outNeighbors(&n2).size(), 1);
ASSERT_EQ(g.outNeighbors(&n3).size(), 0);
ASSERT_EQ(g.inOutNeighbors(&n1).size(), 1);
ASSERT_EQ(g.inOutNeighbors(&n2).size(), 2); // Fails, value is 1.
ASSERT_EQ(g.inOutNeighbors(&n3).size(), 1); // Fails, value is 0.
}
Yes @bbannier this issue is still open, if you want to contribute to this, i can assign it to you!
Yes @bbannier this issue is still open, if you want to contribute to this, i can assign it to you!
I might be able to fix this one issue, but would be afraid of missing APIs (e.g., what about directed weighted graphs?).
My main motivation was less to rush anyone, but to provide a reproducer. Thanks for bumping the priority!
maybe we need to correct the adjacency matrix use for the directed graph to return the correct result without broke the APIs. What do you think?
It looks to me that most of the methods
inOutEdges
orinOutNeighbors
are implemented incorrectly for directed graphs. All these methods use the adjacency matrix to access edges, e.g., https://github.com/ZigRazor/CXXGraph/blob/ae9bc563ad24f329da55c08a0c71e30ac818937c/include/CXXGraph/Graph/Graph_impl.hpp#L715-L725This works well-enough for undirected graphs where the adjacency matrix is kept symmetric, https://github.com/ZigRazor/CXXGraph/blob/ae9bc563ad24f329da55c08a0c71e30ac818937c/include/CXXGraph/Graph/Graph_impl.hpp#L94-L121
For directed graphs the adjacency matrix is not symmetric which means that it cannot be used as-is to obtain incoming edges for a node, https://github.com/ZigRazor/CXXGraph/blob/ae9bc563ad24f329da55c08a0c71e30ac818937c/include/CXXGraph/Graph/Graph_impl.hpp#L76-L93
Originally posted by @bbannier in https://github.com/ZigRazor/CXXGraph/issues/405#issuecomment-2007179170