题 在无向图中查找所有无弦循环


如何找到所有 无弦循环 在无向图中?

例如,给出图表

0 --- 1
|     | \
|     |  \
4 --- 3 - 2

算法应该返回1-2-3和0-1-3-4,但绝不会返回0-1-2-3-4。


(注意: [1] 这个问题不一样了 平面图中的小循环发现 因为图表不一定是平面的。 [2] 我读过这篇论文 使用排除原则生成所有循环,无弦循环和哈密顿循环 但我不明白他们在做什么:)。 [3] 我努力了 CYPATH 但是程序只给出了计数,readme.txt中的算法EnumChordlessPath有很大的拼写错误,而且C代码很乱。 [4] 我不是想找到一套任意的 基金会周期。循环基础可以有和弦。)


27
2017-10-26 10:12


起源


@aioobe:没有约束,但那就是 太 效率低下。 - kennytm
发布付费墙背后的纸张链接并没什么好处。 - Beta
@Beta:有时确实如此 - 对论文的引用很有用,+ ACM并不是一本不起眼的技术期刊。 (虽然我也无法访问它) - Jason S
@Kenny:有不止一种构建循环基础的方法吗?这里似乎有点腥......看起来像无条件的循环形成了基础,但我可能会遗漏一些明显的东西。 - Jason S
@jason:是的。考虑完整的4图,它有4种不同的方式来选择基础(3个三角形)。可以有比基数更多的无弦循环。 - kennytm


答案:


将数字分配给从1到n的节点。

  1. 选择节点编号1.将其命名为“A”。

  2. 枚举来自'A'的成对链接。

  3. 选一个。让我们用B小于C调用相邻节点'B'和'C'。

  4. 如果连接了B和C,则输出循环ABC,返回步骤3并选择另一对。

  5. 如果B和C未连接:

    • 枚举连接到B的所有节点。假设它连接到D,E和F.创建一个向量列表CABD,CABE,CABF。对于以下每一个:
    • 如果最后一个节点连接到除C和B之外的任何内部节点,则丢弃该向量
    • 如果最后一个节点连接到C,则输出并丢弃
    • 如果它没有连接到任何一个,则创建一个新的向量列表,追加最后一个节点所连接的所有节点。

    重复,直到你用完向量。

  6. 对所有对重复步骤3-5。

  7. 删除节点1以及指向它的所有链接。选择下一个节点并返回步骤2。

编辑:你可以取消一个嵌套循环。

这似乎是第一眼看到,可能有错误,但你应该明白:

void chordless_cycles(int* adjacency, int dim)
{
    for(int i=0; i<dim-2; i++)
    {
        for(int j=i+1; j<dim-1; j++)
        {
            if(!adjacency[i+j*dim])
                continue;
            list<vector<int> > candidates;
            for(int k=j+1; k<dim; k++)
            {
                if(!adjacency[i+k*dim])
                    continue;
                if(adjacency[j+k*dim])
                {
                    cout << i+1 << " " << j+1 << " " << k+1 << endl;
                    continue;
                }
                vector<int> v;
                v.resize(3);
                v[0]=j;
                v[1]=i;
                v[2]=k;
                candidates.push_back(v);
            }
            while(!candidates.empty())
            {
                vector<int> v = candidates.front();
                candidates.pop_front();
                int k = v.back();
                for(int m=i+1; m<dim; m++)
                {
                    if(find(v.begin(), v.end(), m) != v.end())
                        continue;
                    if(!adjacency[m+k*dim])
                        continue;
                    bool chord = false;
                    int n;
                    for(n=1; n<v.size()-1; n++)
                        if(adjacency[m+v[n]*dim])
                            chord = true;
                    if(chord)
                        continue;
                    if(adjacency[m+j*dim])
                    {
                        for(n=0; n<v.size(); n++)
                            cout<<v[n]+1<<" ";
                        cout<<m+1<<endl;
                        continue;
                    }
                    vector<int> w = v;
                    w.push_back(m);
                    candidates.push_back(w);
                }
            }
        }
    }
}

8
2017-10-26 23:19



复活老人:)对于“如果最后一个节点连接到除C和B之外的任何内部节点,丢弃向量”,内部节点是什么意思?不幸的是我无法真正阅读你的代码。它是内部节点的纯粹定义,即带有子节点的内部节点,还是指“向量中的节点”?我遵循的最后一个,但如果它只是'一个内部节点' - 它怎么可能 不 如果形状不是三角形,那么连接? - Jelle Veraa


@aioobe有一个观点。只需找到所有周期,然后排除非无弦的周期。这可能效率太低,但可以在此过程中修剪搜索空间以降低效率低下。这是一个通用算法:

void printChordlessCycles( ChordlessCycle path) {

  System.out.println( path.toString() );
  for( Node n : path.lastNode().neighbors() ) {

    if( path.canAdd( n) ) {

      path.add( n);
      printChordlessCycles( path);
      path.remove( n);
    }
  }
}

Graph g = loadGraph(...);
ChordlessCycle p = new ChordlessCycle();
for( Node n : g.getNodes()) {
  p.add(n);
  printChordlessCycles( p);
  p.remove( n);
}

class ChordlessCycle {
   private CountedSet<Node> connected_nodes;
   private List<Node> path;

   ...

   public void add( Node n) {
     for( Node neighbor : n.getNeighbors() ) {
       connected_nodes.increment( neighbor);
     }
     path.add( n);
   }

   public void remove( Node n) {
     for( Node neighbor : n.getNeighbors() ) {
       connected_nodes.decrement( neighbor);
     }
     path.remove( n);
   }

   public boolean canAdd( Node n) {
     return (connected_nodes.getCount( n) == 0);
   }
}

4
2017-10-26 22:41





这个怎么样。首先,将问题减少到找到通过给定顶点A的所有无弦循环。一旦找到所有这些,您可以从图中删除A,并用另一个点重复,直到没有任何剩余。

如何找到通过顶点A的所有无弦循环?给定允许顶点列表,将其减少到找到从B到A的所有无弦路径,并搜索广度优先或深度优先。请注意,当迭代从B可到达的顶点(在一个步骤中)时,当您选择其中一个顶点时,必须从允许顶点列表中删除所有其他顶点(当B = A时要特别小心,以免消除三个 - 路径)。


1
2017-10-26 23:58





只是一个想法:

假设您在示例图上枚举循环,并且从节点0开始。

如果您对每个给定边进行广度优先搜索,例如0 - 1,你在1处达到一个分叉。那么首先达到0的循环是无弦的,其余的不是并且可以被消除......至少我认为是这种情况。

你能用这样的方法吗?或者有一个反例吗?


1
2017-10-27 12:20





找到所有周期。

无弦循环的定义是一组点,其中不存在这些点的子集循环。因此,一旦你有所有周期问题就是简单地消除具有子集周期的周期。

为了提高效率,对于您找到的每个循环,循环遍历所有现有循环并验证它不是另一个循环的子集,反之亦然,如果是,则消除较大的循环。

除此之外,只有困难在于弄清楚如何编写一个算法来确定一个集合是否是另一个集合的子集。


1
2017-10-28 09:27



这是一个好主意,但我的直觉是它可能会遭受大型图形的组合爆炸。请参阅完整图表中的周期数: mathworld.wolfram.com/CompleteGraph.html。对于完整的图形K16,循环数是1904975488436,但是无弦循环的数量是3个顶点循环的数量=(16 * 15 * 14)/(3 * 2 * 1)= 560。 - Jason S
这是不可避免的。我没有方便的证据,但我几乎可以保证你必须在你找到所有无弦循环之前迭代它们。但是,在找到所有组合之后,不是让每个循环都检查所有其他循环,而是在获得它们时消除它们,这意味着减少第二次传递的内存和工作量。换句话说,图K16的时间将是O(1904975488436 * 560)而不是O(1904975488436 ^ 2)。 - Neil
“但我几乎可以保证你必须在你找到所有无弦周期之前迭代它们。”我不同意;如果您正在进行图表的广度优先遍历,并且您发现无弦循环,则会立即消除搜索空间的大部分。 - Jason S
你意识到这有点像说如果你找到一个解决旅行商问题的半合适解决方案,你可能距离最佳解决方案不远,因此你可以通过查看类似的解决方案来消除大部分搜索空间。这是一个不幸的现实,你必须检查所有可能性,即图中所有点的幂集。 - Neil