Storing bidirectional weighted edges in a directed graph

[jpfairbanks]

Over on the StingerGraphs.jl repo, there has been some discussion of the fact that Stinger optimizes bidirectional edges in directed graphs. stingergraph/StingerGraphs.jl#41.

What happens is that when storing an edge i->j we want to have the "back edge" so that we can get the in-neighbors of j. This means that stinger stores 2 copies of i->j one with i and one with j. When the reciprocal edge is inserted j->i stinger replaces the back edge with the reciprocal edge so that there are only 2 edges in the graph. This is fine unless the edge weight for i->j does not equal the edge weight for j->i in which case you cannot access the "in edge weights" efficiently. Namely in order to find the edge weights for all edges coming in to j, you have to explore the edge lists of all in neighbors of j. Which is slow.

This is a problem for applications of STINGER which need weighted directed edges, where the edge weights are not symmetric and the in-edge weights are needed.

There appear to be two solutions,

1. Keep 4 edges around for handling this case.
2. Keep the back edge weights externally from the stinger structure

Does anyone have a 3rd solution that is more clever?

cc: @rohitvarkey @ehein6 @davidediger @edward-kao