java—这看起来像是一种在图中查找没有出边界的顶点的有效方法吗(jgraptht)?

bwleehnv  于 2021-07-12  发布在  Java
关注(0)|答案(1)|浏览(387)

我使用jgrapht在内存图中保存大约150000个顶点。这是一个有向图,每个顶点都有{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() {
            // ..
        }
    }

这也许是一种天真的尝试。我很想知道有没有更好、更地道、更有效的方法来做这件事。

abithluo

abithluo1#

我不太确定代码中发生了什么,但以下内容可以正常工作:

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 包裹。

相关问题