我需要一个工作算法来查找无向图中的所有简单循环.我知道成本可能是指数级的并且问题是NP完全的,但我将在一个小图(最多20-30个顶点)中使用它,并且循环数量很少.
经过长时间的研究(主要是在这里),我仍然没有工作方法.以下是我的搜索摘要:
无向图中的循环 - >仅检测是否存在循环
在无向图中查找多边形 - >非常好的描述,但没有解决方案
在有向图中查找所有循环 - >仅在有向图中查找循环
我发现的唯一一个解决我问题的答案是:
似乎找到一组基本的循环并对它们进行异或可以解决问题.找到一组基本循环很容易,但我不明白如何组合它们以获得图中的所有循环...
Nik*_*nov 43
对于无向图,标准方法是寻找所谓的循环基:一组简单的循环,人们可以通过组合生成所有其他循环.这些不一定是图中的所有简单循环.考虑以下图表:
A
/ \
B ----- C
\ /
D
这里有3个简单的循环:ABCA,BCDB和ABDCA.然而,您可以将这两个中的每一个作为基础,并获得第3个作为2的组合.这与有向图形的实质区别在于,由于需要观察边缘方向,因此无法组合如此自由的周期.
用于查找无向图的循环基础的标准基线算法是:构建生成树,然后对于不是树的一部分的每个边构建从该边创建循环和树上的一些边.必须存在这样的循环,否则边缘将是树的一部分.
例如,上面示例图的一个可能的生成树是:
A
/ \
B C
\
D
不在树中的2个边是BC和CD.相应的简单循环是ABCA和ABDCA.
您还可以构建以下生成树:
A
/
B ----- C
\
D
对于这个生成树,简单的循环将是ABCA和BCDB.
可以以不同方式细化基线算法.据我所知,最佳细化属于Paton(K.Paton,一种用于寻找无向线性图的基本循环集的算法,Comm.ACM 12(1969),pp.514-518.).这里有一个Java开源实现:http://code.google.com/p/niographs/.
我应该已经提到过如何将循环基础中的简单循环组合成新的简单循环.您首先列出图表的所有边缘(但在此后修复).然后通过将0和1的序列放置在属于循环的边缘位置和不属于循环的边缘位置的零的位置来表示循环.然后,您对序列进行按位异或(XOR).您执行XOR的原因是您要排除属于两个循环的边,从而使组合循环不简单.您还需要通过检查序列的按位AND不是全零来检查2个循环是否有一些共同边.否则,XOR的结果将是2个不相交的循环而不是新的简单循环.
以下是上面示例图的示例:
我们首先列出边缘:((AB),(AC),(BC),(BD),(CD)).然后,简单循环ABCA,BDCB和ABDCA表示为(1,1,1,0,0),(0,0,1,1,1)和(1,1,0,1,1).现在我们可以例如XOR ABCA与BDCB,结果是(1,1,0,1,1),这正是ABDCA.或者我们可以XOR ABCA和ABDCA,结果是(0,0,1,1,1).这正是BDCB.
给定循环基础,您可以通过检查2个或更多不同基本循环的所有可能组合来发现所有简单循环.此处详细介绍了该过程:第14页的http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf.
为了完整起见,我会注意到使用算法来查找有向图的所有简单循环似乎是可能的(并且效率低下).无向图的每个边都可以被相反方向的2个有向边代替.那么有向图的算法应该有效.对于无向图的每个边缘将存在1个"假"2节点循环,其将被忽略,并且将存在无向图的每个简单循环的顺时针和逆时针版本.用于查找有向图中所有周期的算法的Java开源实现可以在我已经引用的链接中找到.
Axe*_*per 31
以下是基于深度优先搜索的C#(和Java,请参见答案结尾)的演示实现.
外循环扫描图的所有节点并从每个节点开始搜索.节点邻居(根据边缘列表)被添加到循环路径中.如果不能添加更多未访问的邻居,则递归结束.如果路径长于两个节点并且下一个邻居是路径的开始,则找到新的循环.为避免重复循环,通过将最小节点旋转到开始来对循环进行归一化.反向排序的周期也被考虑在内.
这只是一个天真的实现.经典论文是:Donald B. Johnson.找到有向图的所有基本电路.SIAM J. Comput.,4(1):77-84,1975.
最近对现代算法的调查可以在这里找到
using System;
using System.Collections.Generic;
namespace akCyclesInUndirectedGraphs
{
class Program
{
// Graph modelled as list of edges
static int[,] graph =
{
{1, 2}, {1, 3}, {1, 4}, {2, 3},
{3, 4}, {2, 6}, {4, 6}, {7, 8},
{8, 9}, {9, 7}
};
static List<int[]> cycles = new List<int[]>();
static void Main(string[] args)
{
for (int i = 0; i < graph.GetLength(0); i++)
for (int j = 0; j < graph.GetLength(1); j++)
{
findNewCycles(new int[] {graph[i, j]});
}
foreach (int[] cy in cycles)
{
string s = "" + cy[0];
for (int i = 1; i < cy.Length; i++)
s += "," + cy[i];
Console.WriteLine(s);
}
}
static void findNewCycles(int[] path)
{
int n = path[0];
int x;
int[] sub = new int[path.Length + 1];
for (int i = 0; i < graph.GetLength(0); i++)
for (int y = 0; y <= 1; y++)
if (graph[i, y] == n)
// edge referes to our current node
{
x = graph[i, (y + 1) % 2];
if (!visited(x, path))
// neighbor node not on path yet
{
sub[0] = x;
Array.Copy(path, 0, sub, 1, path.Length);
// explore extended path
findNewCycles(sub);
}
else if ((path.Length > 2) && (x == path[path.Length - 1]))
// cycle found
{
int[] p = normalize(path);
int[] inv = invert(p);
if (isNew(p) && isNew(inv))
cycles.Add(p);
}
}
}
static bool equals(int[] a, int[] b)
{
bool ret = (a[0] == b[0]) && (a.Length == b.Length);
for (int i = 1; ret && (i < a.Length); i++)
if (a[i] != b[i])
{
ret = false;
}
return ret;
}
static int[] invert(int[] path)
{
int[] p = new int[path.Length];
for (int i = 0; i < path.Length; i++)
p[i] = path[path.Length - 1 - i];
return normalize(p);
}
// rotate cycle path such that it begins with the smallest node
static int[] normalize(int[] path)
{
int[] p = new int[path.Length];
int x = smallest(path);
int n;
Array.Copy(path, 0, p, 0, path.Length);
while (p[0] != x)
{
n = p[0];
Array.Copy(p, 1, p, 0, p.Length - 1);
p[p.Length - 1] = n;
}
return p;
}
static bool isNew(int[] path)
{
bool ret = true;
foreach(int[] p in cycles)
if (equals(p, path))
{
ret = false;
break;
}
return ret;
}
static int smallest(int[] path)
{
int min = path[0];
foreach (int p in path)
if (p < min)
min = p;
return min;
}
static bool visited(int n, int[] path)
{
bool ret = false;
foreach (int p in path)
if (p == n)
{
ret = true;
break;
}
return ret;
}
}
}
演示图的周期:
1,3,2
1,4,3,2
1,4,6,2
1,3,4,6,2
1,4,6,2,3
1,4,3
2,6,4,3
7,9,8
用Java编码的算法:
import java.util.ArrayList;
import java.util.List;
public class GraphCycleFinder {
// Graph modeled as list of edges
static int[][] graph =
{
{1, 2}, {1, 3}, {1, 4}, {2, 3},
{3, 4}, {2, 6}, {4, 6}, {7, 8},
{8, 9}, {9, 7}
};
static List<int[]> cycles = new ArrayList<int[]>();
/**
* @param args
*/
public static void main(String[] args) {
for (int i = 0; i < graph.length; i++)
for (int j = 0; j < graph[i].length; j++)
{
findNewCycles(new int[] {graph[i][j]});
}
for (int[] cy : cycles)
{
String s = "" + cy[0];
for (int i = 1; i < cy.length; i++)
{
s += "," + cy[i];
}
o(s);
}
}
static void findNewCycles(int[] path)
{
int n = path[0];
int x;
int[] sub = new int[path.length + 1];
for (int i = 0; i < graph.length; i++)
for (int y = 0; y <= 1; y++)
if (graph[i][y] == n)
// edge refers to our current node
{
x = graph[i][(y + 1) % 2];
if (!visited(x, path))
// neighbor node not on path yet
{
sub[0] = x;
System.arraycopy(path, 0, sub, 1, path.length);
// explore extended path
findNewCycles(sub);
}
else if ((path.length > 2) && (x == path[path.length - 1]))
// cycle found
{
int[] p = normalize(path);
int[] inv = invert(p);
if (isNew(p) && isNew(inv))
{
cycles.add(p);
}
}
}
}
// check of both arrays have same lengths and contents
static Boolean equals(int[] a, int[] b)
{
Boolean ret = (a[0] == b[0]) && (a.length == b.length);
for (int i = 1; ret && (i < a.length); i++)
{
if (a[i] != b[i])
{
ret = false;
}
}
return ret;
}
// create a path array with reversed order
static int[] invert(int[] path)
{
int[] p = new int[path.length];
for (int i = 0; i < path.length; i++)
{
p[i] = path[path.length - 1 - i];
}
return normalize(p);
}
// rotate cycle path such that it begins with the smallest node
static int[] normalize(int[] path)
{
int[] p = new int[path.length];
int x = smallest(path);
int n;
System.arraycopy(path, 0, p, 0, path.length);
while (p[0] != x)
{
n = p[0];
System.arraycopy(p, 1, p, 0, p.length - 1);
p[p.length - 1] = n;
}
return p;
}
// compare path against known cycles
// return true, iff path is not a known cycle
static Boolean isNew(int[] path)
{
Boolean ret = true;
for(int[] p : cycles)
{
if (equals(p, path))
{
ret = false;
break;
}
}
return ret;
}
static void o(String s)
{
System.out.println(s);
}
// return the int of the array which is the smallest
static int smallest(int[] path)
{
int min = path[0];
for (int p : path)
{
if (p < min)
{
min = p;
}
}
return min;
}
// check if vertex n is contained in path
static Boolean visited(int n, int[] path)
{
Boolean ret = false;
for (int p : path)
{
if (p == n)
{
ret = true;
break;
}
}
return ret;
}
}
小智 28
Axel,我已将您的代码翻译为python.大约1/4的代码行和更清晰的阅读.
graph = [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4], [2, 6], [4, 6], [8, 7], [8, 9], [9, 7]]
cycles = []
def main():
global graph
global cycles
for edge in graph:
for node in edge:
findNewCycles([node])
for cy in cycles:
path = [str(node) for node in cy]
s = ",".join(path)
print(s)
def findNewCycles(path):
start_node = path[0]
next_node= None
sub = []
#visit each edge and each node of each edge
for edge in graph:
node1, node2 = edge
if start_node in edge:
if node1 == start_node:
next_node = node2
else:
next_node = node1
if not visited(next_node, path):
# neighbor node not on path yet
sub = [next_node]
sub.extend(path)
# explore extended path
findNewCycles(sub);
elif len(path) > 2 and next_node == path[-1]:
# cycle found
p = rotate_to_smallest(path);
inv = invert(p)
if isNew(p) and isNew(inv):
cycles.append(p)
def invert(path):
return rotate_to_smallest(path[::-1])
# rotate cycle path such that it begins with the smallest node
def rotate_to_smallest(path):
n = path.index(min(path))
return path[n:]+path[:n]
def isNew(path):
return not path in cycles
def visited(node, path):
return node in path
main()
下面是上面 python 代码的 C++ 版本：
std::vector< std::vector<vertex_t> > Graph::findAllCycles()
{
std::vector< std::vector<vertex_t> > cycles;
std::function<void(std::vector<vertex_t>)> findNewCycles = [&]( std::vector<vertex_t> sub_path )
{
auto visisted = []( vertex_t v, const std::vector<vertex_t> & path ){
return std::find(path.begin(),path.end(),v) != path.end();
};
auto rotate_to_smallest = []( std::vector<vertex_t> path ){
std::rotate(path.begin(), std::min_element(path.begin(), path.end()), path.end());
return path;
};
auto invert = [&]( std::vector<vertex_t> path ){
std::reverse(path.begin(),path.end());
return rotate_to_smallest(path);
};
auto isNew = [&cycles]( const std::vector<vertex_t> & path ){
return std::find(cycles.begin(), cycles.end(), path) == cycles.end();
};
vertex_t start_node = sub_path[0];
vertex_t next_node;
// visit each edge and each node of each edge
for(auto edge : edges)
{
if( edge.has(start_node) )
{
vertex_t node1 = edge.v1, node2 = edge.v2;
if(node1 == start_node)
next_node = node2;
else
next_node = node1;
if( !visisted(next_node, sub_path) )
{
// neighbor node not on path yet
std::vector<vertex_t> sub;
sub.push_back(next_node);
sub.insert(sub.end(), sub_path.begin(), sub_path.end());
findNewCycles( sub );
}
else if( sub_path.size() > 2 && next_node == sub_path.back() )
{
// cycle found
auto p = rotate_to_smallest(sub_path);
auto inv = invert(p);
if( isNew(p) && isNew(inv) )
cycles.push_back( p );
}
}
}
};
for(auto edge : edges)
{
findNewCycles( std::vector<vertex_t>(1,edge.v1) );
findNewCycles( std::vector<vertex_t>(1,edge.v2) );
}
}
| 归档时间： |
|
| 查看次数： |
49705 次 |
| 最近记录： |