java - Java中图连通性算法的通用实现

Question

我有一个对象工厂的接口(interface)，它根据给定顶点创建的对象集合创建图形 Function<Object,Vertex>和一个链接 BiPredicate<Vertex,Vertex> .

这个设计允许通过提供这两个函数来指定任意图形连接算法，但就我能够实现它而言，这是以必须循环遍历所有对象对为代价的像这样的输入集合(类 Graph 和 Vertex 在别处定义):

Function<Object,Vertex> maker; // defined by user.
BiPredicate<Vertex,Vertex> linker; // defined by user.

Graph makeGraph( Collection<Object> input ) {
    Graph g = new Graph();
    Collection<Vertex> vertices = input.stream.map( ( Objec t ) -> maker.apply( t ) ).collect( Collectors.toList() );
    for( Vertex ego : vertices ) {
        Collection<Vertex> alters = new ArrayList<>();
        alters.addAll( vertices );
        alters.remove( ego );
        for( Vertex alter : alters ) {
            if( linker.test( ego, alter ) ) {
                g.makeEdge( ego, alter );
            }
        }
    }
}

其实我有两个问题:

1. 有没有比我创建新列表、复制所有内容并从副本中删除 i 的丑陋解决方案更优雅的迭代集合中所有可能对 (i,j) 的方法？

2. 有人能想出一种优化双重迭代的方法吗？现在最好的情况下执行时间是 O( n^2 ) ，因为实现需要接受一个链接函数而不了解它，但也许有办法解决这个问题？例如指定某些参数以指示，例如，在共现网络的链接器测试第一次失败后迭代可能会中断等。

当然，如果有人能想到解决此问题的替代方法，我会很高兴听到。

编辑:

忘记第一个问题，Robert Navado 的 answer让我意识到我错了。

然后为了澄清:我正在寻找一种方法来告诉实现可以在某些条件下优化链接器函数的应用(例如，在上面提到的共现示例中，“按位置排序并在之后中断第一个阴性结果”)。

Answer 1

好吧，除非你的图中有未链接的顶点并且你的图是稀疏的，否则我建议存储边而不是顶点。然而，单链接团中的最大边数是 V*(V-1)。因此，在更坏的情况下，您将需要 O(V^2) 次迭代来链接您的图形，甚至更多的多图。

至于迭代语法，以下也应该有效:

for(Vertex alter : vertices )
   for(Vertex ego : vertices ){
       //Do the descision
}

看看 JUNG图形操作库。它可能已过时，但您可以查看它们的数据结构以获取灵感。