[jgrapht-users] GraphUnion does not play well with algorithm implementation(s)

[Joris K. <de...@gm...>]

Hi,

I'm encountering some problems with jgrapht's graph union and (at least
one) algorithm implementation. I wanted to hear your opinion about a
possible fix to this issue.


Given two graphs (the actual implementation of V, E is irrelevant):
Graph<V,E> myUndirectedGraph=new SimpleGraph<>(E.class);
Graph<V,E> myDirectedGraph=new SimpleDirectedGraph<>(E.class);

We can now create a mixed graph through the graph union interface (this is
a legal operation!):
Graph<V,E> mixedGraph=new GraphUnion<>(myUndirectedGraph, myDirectedGraph);

So far so good, the mixedGraph works as expected. If I for example query an
edge between vertices i and j, then the mixed graph will only return an
edge if either myUndirectedGraph or myDirectedGraph has an edge/arc (i,j);
an arc (j,i) in myDirectedGraph is never returned.

If we would now plugin the mixedGraph into for example the
FloydWarshallShortestPaths algorithm implementation, we run into runtime
issues. Why? Because of the following code segment:

// initialize matrix, 2
        Set<E> edges = graph.edgeSet();
        for (E edge : edges) {
            V v1 = graph.getEdgeSource(edge);
            V v2 = graph.getEdgeTarget(edge);

            int v_1 = vertices.indexOf(v1);
            int v_2 = vertices.indexOf(v2);

            d[v_1][v_2] = graph.getEdgeWeight(edge);
            if (!(graph instanceof DirectedGraph<?, ?>)) {
                d[v_2][v_1] = graph.getEdgeWeight(edge);
            }
        }

Due to the implementation of the GraphUnion, our mixedGraph is *not* an
instance of DirectedGraph<?,?>, so the algorithm will incorrectly set the
distance d_ij=d_ji, independent of whether arcs (i,j) and (j,i) exist. This
is obviously due to the fact that FloydWarshallShortestPaths thinks we are
dealing with a undirected graph. A possible solution would be:

for(V v1 : graph.vertexSet()){
    int v_1 = vertices.indexOf(v1);
    for(E edge : graph.outgoingEdgesOf(v1)){
        V v2=Graphs.getOppositeVertex(graph, edge, v1);
        int v_2 = vertices.indexOf(v2);
        d[v_1][v_2] = graph.getEdgeWeight(edge);
    }
}

However, the method outgoingEdgesOf(V v) is not accessible through the
interface "Graph", so this won't work.
Furthermore, we cannot use Graph<V,E> mixedGraph2=new
DirectedGraphUnion<>(G g1, G g2) because a DirectedGraphUnion expects 2
*Directed* graphs in its constructor. Hence, the cleanest possible solution
I could come up with is the following:

1. Create a new class MixedGraphUnion which takes an undirected and a
directed graph as input. The MixedGraphUnion is an instance of a
DirectedGraph and implements all methods as expected.
2. Add methods outgoingEdgesOf(V v), incomingEdgesOf(V v), inDegreeOf(V v),
outDegreeOf(V v) to the graph interface. All of these methods make sense,
even in the context of undirected graphs
3. Rewrite the Initialize matrix code in FloydWarshallShortestPaths
implementation as suggested above.

Some of you may ask: why do you want a MixedGraph? Why don't you create a
DirectedGraph and add two arcs (i,j) and (j,i) for each undirected edge?
Unfortunately, as pointed out by some other users, there are applications
where you actually want to distinguish between an edge {i,j} and two
directed arcs (i,j),(j,i) as they may have different meaning. A simple
example commonly arises in street networks: an edge represents a
residential street which may be driven in both directions, an arc
represents a one-way street and two arcs in opposite direction represents a
street consisting of two lanes in opposite direction.

best regards,

Joris Kinable