jgrapht

Is there a DAG with weighted edges?

I'd like to create a DAG in order to use the TopologicalOrderIterator and would like to save some weights on the edges. However, a DAG does not allow weighted edges and the TopologicalOrderIterator is not available for a SimpleDirectedWeightedGraph. Am I missing something and this combination should somehow be forbidden or did I just not find the right classes?

Solution

  • Just to correct two wrong statements: (1) a DAG does allow weighted edges and (2) a TopologicalOrderIterator does exist for the SimpleDirectedWeightedGraph.

    Here's an example of using a SimpleDirectedWeightedGraph with the TopologicalOrderIterator:

    //Create a standard directed weighted graph. This graph type allows cycles, so, to maintain the acyclic property,
// it's the users responsibility not to add any arcs that create cycles.
Graph<Integer, DefaultWeightedEdge> graph = GraphTypeBuilder.<Integer,DefaultWeightedEdge> directed().weighted(true).buildGraph();
Graphs.addAllVertices(graph, Arrays.asList(0,1,2,3,4));
Graphs.addEdge(graph, 0,1, 10); //Adds a directed arc from vertex 0 to vertex 1 with weight 10
Graphs.addEdge(graph, 0,2, 11);
Graphs.addEdge(graph, 1,2, 12);
Graphs.addEdge(graph, 2,3, 13);
Graphs.addEdge(graph, 2,4, 14);
TopologicalOrderIterator<Integer, DefaultWeightedEdge> it = new TopologicalOrderIterator<>(graph);
while(it.hasNext()){
    System.out.println(it.next());
}

    Note that in this example, to construct the graph, I used the builder paradigm. Instead of

    Graph<Integer, DefaultWeightedEdge> graph = GraphTypeBuilder.<Integer,DefaultWeightedEdge> directed().weighted(true).buildGraph();

    I could have written:

    Graph<Integer, DefaultWeightedEdge> graph = new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class);

    Alternatively you could use the specialized DirectedAcyclicGraph graph format:

    DirectedAcyclicGraph<Integer, DefaultWeightedEdge> graph = new DirectedAcyclicGraph<>(null, SupplierUtil.createDefaultWeightedEdgeSupplier(),true);
Graphs.addAllVertices(graph, Arrays.asList(0,1,2,3,4));
Graphs.addEdge(graph, 0,1, 10); //Adds a directed arc from vertex 0 to vertex 1 with weight 10
Graphs.addEdge(graph, 0,2, 11);
Graphs.addEdge(graph, 1,2, 12);
Graphs.addEdge(graph, 2,3, 13);
Graphs.addEdge(graph, 2,4, 14);
Iterator<Integer> it = graph.iterator(); //Creates a Topological order iterator
while(it.hasNext()){
    System.out.println(it.next());
}

    Note that the following code would be incorrect:

    DirectedAcyclicGraph<Integer, DefaultWeightedEdge> graph = new DirectedAcyclicGraph<>(DefaultWeightedEdge.class);
Graphs.addAllVertices(graph, Arrays.asList(0,1));
Graphs.addEdge(graph, 0, 1, 10); //Adds a directed arc from vertex 0 to vertex 1 with weight 10

    This creates an unweighted graph and then attempts to add a weighted edge. This would result in the following exception:

    Exception in thread "main" java.lang.UnsupportedOperationException
    at org.jgrapht.graph.BaseIntrusiveEdgesSpecifics.setEdgeWeight(BaseIntrusiveEdgesSpecifics.java:138)

    In order to create a weighted version of the DirectedAcyclicGraph, the correct constructor should be used.