这看起来像是一种查找图中没有出边的顶点的有效方法 (JGraphT) 吗？

Question

我正在使用 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() {
            // ..
        }
    }

这或许，是一种幼稚的尝试。我很想知道是否有更好、更惯用和更有效的方法来做到这一点。

Answer 1

我不太确定代码中发生了什么，但以下代码可以正常工作：

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 包中的优化图实现。

这看起来像是一种查找图中没有出边的顶点的有效方法 (JGraphT) 吗？

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

java

graph

jgrapht