javagraphjgrapht

How to find roots and leaves set in jgrapht DirectedAcyclicGraph


My code:

import org.jgrapht.graph.DirectedAcyclicGraph;
// ...
private DirectedAcyclicGraph<String, DefaultEdge> graph = new DirectedAcyclicGraph<>(DefaultEdge.class);
// ...
graph.addVertex("x");
graph.addVertex("y");
// ...
graph.addEdge("x", "y");

After constructing the graph, how can I get a set of all the roots (vertices with no incoming edges) and of all leaves (vertices with no outgoing edges)


Solution

  • The following is working, but doesn't strike me as most efficient.

    // leaves:
    graph.vertexSet().stream()
                    .filter(key -> graph.outgoingEdgesOf(key).size() == 0)
                    .forEach(key -> doLeavesStuff(key));
    
    // roots:
    graph.vertexSet().stream()
                    .filter(key -> graph.incomingEdgesOf(key).size() == 0)
                    .forEach(key -> doRootsStuff(key));