Does this look like an efficient way to find vertices which have no outgoing edges in a graph (JGrapthT)?

I am using JGraphT for holding about 150,000 (or thereabouts) vertices in an in-memory graph. This a directed graph and each vertex is going to have { 0 | 1 } outgoing edges.

I want to find retrieve the set of vertices which have no outgoing edges. Here’s what I have attempted:

import io.vavr.Tuple;
import io.vavr.Tuple2;
import io.vavr.Tuple3;
import io.vavr.control.Option;
import org.jgrapht.Graphs;
import org.jgrapht.graph.SimpleDirectedGraph;
import org.jgrapht.graph.concurrent.AsSynchronizedGraph;

 public Option<io.vavr.collection.Set<Employee>> 
 pickEmployeesWithNoSupervisor(Integer companyID) {
        
       // holdingCompany is of type: SimpleDirectedGraph<Employee,String>
       // edge is a simple string: "reportingTo"
       // Retrieve from a Map, initialized earlier, elsewhere

       var holdingCompany = this.allCompanies.get(companyID);
       if (holdingCompany == null)
                    return (Option.none());
       else {
        
           var vertices = holdingCompany.vertexSet();
           io.vavr.collection.Set<Employee> accumulator = io.vavr.collection.HashSet.empty();
           var allNoReportingToEmployees = 
                io.vavr.collection.HashSet.ofAll(vertices)
                .foldLeft(accumulator,(accu,nextEmp) -> {
                   var hasPredecessors = 
                          Graphs.vertexHasPredecessors(mayBeAKnownCompany,nextEmp);
                   return (!hasPredecessors ? accu.add(nextEmp) : accu) ;
                });
                   
            return Option.some(allNoReportingToEmployees);
          }
     }

     public class Employee {
        private final Integer empID;
      
        public Employee(Integer empID) {
            this.empID = empID;
        }

        @Override
        public boolean equals(Object o) {
           // ..
        }

        @Override
        public int hashCode() {
            // ..
        }
    }

This perhaps, is a naive attempt. I am keen to know if there is any better, more idiomatic and more efficient way of doing this.

Answer

I’m not quite sure what’s going on in the code, but the following would work fine:

Set<Employee> verticesWithoutSucc = myGraph.vertexSet().stream().filter(v -> !Graphs.vertexHasSuccessors(myGraph,v)).collect(Collectors.toSet());

Note that, to get all vertices without outgoing arcs, you must use vertexHasSuccessors(.) as opposed to vertexHasPredecessors(.).

Note that the vertexHasSuccessors method simply invokes !graph.outgoingEdgesOf(vertex).isEmpty();

This approach should be efficient since it runs in O(n) time, where n is the number of customers. If you want even better performance, you could keep track of all the vertices without an outgoing arc during the construction of the graph. That is, keep a set of all the vertices in your graph, and each time you add an arc (i,j), remove vertex i from your set. As such you can always query the set of vertices without outgoing arcs in constant time.

Finally, for large graphs, you could have a look at the optimized graph implementations in the jgrapht-opt package.