GraphUnion does not play well with algorithm implementation(s)

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view

GraphUnion does not play well with algorithm implementation(s)

Joris Kinable

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


jgrapht-users mailing list
[hidden email]