Похоже ли это на эффективный способ поиска вершин, не имеющих исходящих ребер в графе (JGrapthT)?

Я использую JGraphT для хранения около 150 000 (или около того) вершин в графе в памяти. Это ориентированный граф, и каждая вершина будет иметь { 0 | 1 } исходящие ребра.

Я хочу найти набор вершин, у которых нет исходящих ребер. Вот что я пытался:

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() {
            // ..
        }
    }

Возможно, это наивная попытка. Я очень хочу знать, есть ли лучший, более идиоматический и более эффективный способ сделать это.


java graph jgrapht
person Nirmalya    schedule 24.04.2021    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Я не совсем уверен, что происходит в коде, но следующее будет работать нормально:

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

Обратите внимание, что для получения всех вершин без исходящих дуг необходимо использовать vertexHasSuccessors(.), а не vertexHasPredecessors(.).

Обратите внимание, что метод vertexHasSuccessors просто вызывает !graph.outgoingEdgesOf(vertex).isEmpty();

Этот подход должен быть эффективным, так как он работает за O(n) времени, где n — количество клиентов. Если вы хотите еще большей производительности, вы можете отслеживать все вершины без исходящей дуги во время построения графа. То есть сохраните набор всех вершин вашего графа, и каждый раз, когда вы добавляете дугу (i,j), удаляйте вершину i из вашего набора. Таким образом, вы всегда можете запросить набор вершин без исходящих дуг за постоянное время.

Наконец, для больших графов вы можете взглянуть на оптимизированные реализации графов в пакете jgrapht-opt.

person Joris Kinable    schedule 24.04.2021
comment
Мой код безнадежно многословен по сравнению с вашим! :-) Я пытаюсь добиться того же, и да, ваш код также говорит мне, каким должен быть обычный способ для подобных задач. Спасибо. Позвольте мне включить это в мою кодовую базу. - person Nirmalya; 25.04.2021
comment
Спасибо также за указание на разницу между преемниками и предшественниками. При написании кода непосредственно на странице SOF я напортачил. Спасибо еще раз. @Joris-kinable - person Nirmalya; 25.04.2021