找到所有chordless周期无向图 [英] Find all chordless cycles in an undirected graph
问题描述
如何找到所有 chordless 的周期中无向图？
How to find all chordless cycles in an undirected graph?
例如，给定的曲线
0 --- 1
| | \
| | \
4 --- 3 - 2
该算法应该返回1-2-3和0-1-3-4，但从来没有0-1-2-3-4。
the algorithm should return 1-2-3 and 0-1-3-4, but never 0-1-2-3-4.
（注： [1] 这个问题是不一样的 小周发现在平面图的因为图形不一定是平面的。 [2] 我已经阅读了本文的Generating所有周期，chordless周期，并与排斥的原理哈密顿周期的但我不'牛逼了解他们在做什么:)。 [3] 我已经试过 CYPATH 但程序只给出了数，算法EnumChordlessPath在readme.txt文件有显著错别字，而C code是一个烂摊子。 [4] 我不是试图找到任意一组的<一个href="http://stackoverflow.com/questions/1607124/algorithms-to-identify-all-the-cycle-bases-in-a-undirected-graph">fundametal周期的。周期的基础上可以有和弦。）
(Note: [1] This question is not the same as small cycle finding in a planar graph because the graph is not necessarily planar. [2] I have read the paper Generating all cycles, chordless cycles, and Hamiltonian cycles with the principle of exclusion but I don't understand what they're doing :). [3] I have tried CYPATH but the program only gives the count, algorithm EnumChordlessPath in readme.txt has significant typos, and the C code is a mess. [4] I am not trying to find an arbitrary set of fundametal cycles. Cycle basis can have chords.)
推荐答案
从1分配号码的节点到n。
Assign numbers to nodes from 1 to n.
-
选择的节点号1叫它'A'。
Pick the node number 1. Call it 'A'.
枚举对链接出来的A。
选择一个。让我们把相邻节点'B'和'C'为B比C。
Pick one. Let's call the adjacent nodes 'B' and 'C' with B less than C.
如果B和C连接，然后输出循环ABC，回到步骤3，并选择一个不同的对。
If B and C are connected, then output the cycle ABC, return to step 3 and pick a different pair.
如果B和C连接不：
- 枚举连接到B的所有节点假设它连接到D，E和F创建矢量公共天线，CABE，CABF列表。对于每一种：
- ，如果最后一个节点被连接到除了C和B的任何内部节点，丢弃矢量
- ，如果最后一个节点被连接到C，输出和丢弃
- ，如果它不连接到任，创建矢量的新的列表，附加的最后一个节点被连接到它的所有节点。
重复操作，直至用完载体。
Repeat until you run out of vectors.
重复步骤3-5，所有对。
Repeat steps 3-5 with all pairs.
删除节点1，而导致这一切的联系。选择下一个节点，回到步骤2。
Remove node 1 and all links that lead to it. Pick the next node and go back to step 2.
编辑：你可以做掉一个嵌套循环。
and you can do away with one nested loop.
这似乎一见钟情的工作，有可能是错误的，但你应该得到的想法：
This seems to work at the first sight, there may be bugs, but you should get the idea:
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);
}
}
}
}
}
这篇关于找到所有chordless周期无向图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
