这看起来像是一种在图(JGrapthT)中找到没有传出边的顶点的有效方法吗

Question

我使用JGraphT在内存图中保持大约150000个(或大约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() {
// ..
}
}

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

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