Methods `inOut*` broken for directed graphs

[bbannier]

It looks to me that most of the methods inOutEdges or inOutNeighbors are implemented incorrectly for directed graphs. All these methods use the adjacency matrix to access edges, e.g.,

CXXGraph/include/CXXGraph/Graph/Graph_impl.hpp

Lines 715 to 725 in ae9bc56

	Graph<T>::inOutEdges(shared<const Node<T>> node) const {
	if (cachedAdjMatrix->find(node) == cachedAdjMatrix->end()) {
	return std::unordered_set<shared<const Edge<T>>, edgeHash<T>>();
	}
	auto nodeEdgePairs = cachedAdjMatrix->at(node);
	std::unordered_set<shared<const Edge<T>>, edgeHash<T>> outEdges;
	for (auto pair : nodeEdgePairs) {
	outEdges.insert(pair.second);
	}

This works well-enough for undirected graphs where the adjacency matrix is kept symmetric,

CXXGraph/include/CXXGraph/Graph/Graph_impl.hpp

Lines 94 to 121 in ae9bc56

	} else {
	if (edge->isWeighted().has_value() && edge->isWeighted().value()) {
	auto edge_shared = make_shared<UndirectedWeightedEdge<T>>(
	*dynamic_cast<const UndirectedWeightedEdge<T> *>(edge));
	this->edgeSet.insert(edge_shared);
	std::pair<shared<const Node<T>>, shared<const Edge<T>>> elem = {
	edge_shared->getNodePair().second, edge_shared};
	(*cachedAdjMatrix)[edge_shared->getNodePair().first].push_back(
	std::move(elem));
	std::pair<shared<const Node<T>>, shared<const Edge<T>>> elem1 = {
	edge_shared->getNodePair().first, edge_shared};
	(*cachedAdjMatrix)[edge_shared->getNodePair().second].push_back(
	std::move(elem1));
	} else {
	auto edge_shared = make_shared<UndirectedEdge<T>>(*edge);
	this->edgeSet.insert(edge_shared);
	std::pair<shared<const Node<T>>, shared<const Edge<T>>> elem = {
	edge_shared->getNodePair().second, edge_shared};
	(*cachedAdjMatrix)[edge_shared->getNodePair().first].push_back(
	std::move(elem));
	std::pair<shared<const Node<T>>, shared<const Edge<T>>> elem1 = {
	edge_shared->getNodePair().first, edge_shared};
	(*cachedAdjMatrix)[edge_shared->getNodePair().second].push_back(
	std::move(elem1));
	}
	}

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,

CXXGraph/include/CXXGraph/Graph/Graph_impl.hpp

Lines 76 to 93 in ae9bc56

	if (edge->isWeighted().has_value() && edge->isWeighted().value()) {
	auto edge_shared = make_shared<DirectedWeightedEdge<T>>(
	*dynamic_cast<const DirectedWeightedEdge<T> *>(edge));
	this->edgeSet.insert(edge_shared);
	std::pair<shared<const Node<T>>, shared<const Edge<T>>> elem = {
	edge_shared->getNodePair().second, edge_shared};
	(*cachedAdjMatrix)[edge_shared->getNodePair().first].push_back(
	std::move(elem));
	} else {
	auto edge_shared = make_shared<DirectedEdge<T>>(*edge);
	this->edgeSet.insert(edge_shared);
	std::pair<shared<const Node<T>>, shared<const Edge<T>>> elem = {
	edge_shared->getNodePair().second, edge_shared};
	(*cachedAdjMatrix)[edge_shared->getNodePair().first].push_back(
	std::move(elem));
	}

Originally posted by @bbannier in #405 (comment)

[bbannier]

@ZigRazor, this is a more general issue than #405 and still exists. Can you please reopen?

[bbannier]

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.
}

[ZigRazor]

Yes @bbannier this issue is still open, if you want to contribute to this, i can assign it to you!

[bbannier]

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!

[ZigRazor]

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?