Re: 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
Report Content as Inappropriate

Re: GraphUnion does not play well with algorithm implementation(s)

H.N. de Ridder
That's quite a viper's nest you've stepped into.

Since the code snippet erroneously assumes that every graph that is not directed must be undirected, my first thought was simply changing the if statement to

if (graph instanceof UndirectedGraph)

Although this correction would be a good idea anyhow, it is not enough: For mixed graphs we need to check for every edge independently whether it is undirected or not and therefore cannot do so by looking at the type of the graph. However, in Jgrapht edges themselves don't have a directed/undirected property: it's the graph that determines this.

So my second thought was introducing a MixedGraph type that stores this knowledge per edge. Thinking where this type should go in the hierachy (common supertype of Directed/UndirectedGraph, common subtype or a sibling?), made me realize what (IMHO) the proper solution would be and what the disadvantages of your suggestion are:

Pushing outGoingEdges/incomingEdges into the Graph interface effectively locks the equivalence undirected == bidirectional in the library at a very basic level. Making MixedGrapUnion implement DirectedGraph also reflects this equivalence. But undirected and birectional need not be equivalent in every situation. They are apparently in your problem frame.  So my suggestion is to solve this issue not by changing jgrapht, but by using what's there to make the code model your problem. And this can be done, I think, by running Floyd-Warshall on a directed view of the mixed graph. Simple, flexible and without difficult changes to jgrapht itself.


----- Reply message -----
From: "Joris Kinable" <[hidden email]>
To: "[hidden email]" <[hidden email]>
Subject: [jgrapht-users] GraphUnion does not play well with algorithm implementation(s)
Date: Wed, Aug 19, 2015 18:57


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]