無向グラフですべての単純なサイクルを見つけるための実用的なアルゴリズムが必要です。コストが指数関数的になる可能性があり、問題が NP 完全であることはわかっていますが、これを小さなグラフ (最大 20 ～ 30 個の頂点) で使用し、サイクル数が少ない場合に使用します。
長い研究 (主にここ) の後、私はまだ実用的なアプローチを持っていません。ここに私の検索の要約があります：
無向グラフの循環-> 循環の有無のみを検出
無向グラフ内のポリゴンの検索-> 非常に良い説明ですが、解決策はありません
有向グラフですべてのサイクルを検索 -> 有向グラフでのみサイクルを検索
ブースト グラフ ライブラリを使用して無向グラフのサイクルを検出する
私の問題に近づく唯一の答えは次のとおりです。
サイクルの基本的なセットを見つけて、それらを XOR することでうまくいくようです。サイクルの基本セットを見つけるのは簡単ですが、グラフ内のすべてのサイクルを取得するためにそれらを組み合わせる方法がわかりません...
無向グラフの場合、標準的なアプローチは、いわゆるサイクル ベース を探すことです。これは、他のすべてのサイクルを組み合わせて生成できる単純なサイクルのセットです。これらは必ずしもグラフ内のすべての単純なサイクルではありません。たとえば、次のグラフを考えてみましょう。
A
/ \
B ----- C
\ /
D
ここには、ABCA、BCDB、ABDCA の 3 つの単純なサイクルがあります。ただし、これらの各 2 をベースとして取り、2 つの組み合わせとして 3 番目を取得することができます。これは、エッジの方向を観察する必要があるため、サイクルを自由に組み合わせることができない有向グラフとは大きく異なります。
無向グラフのサイクルベースを見つけるための標準ベースラインアルゴリズムは次のとおりです。スパニングツリーを構築し、ツリーの一部ではない各エッジに対して、そのエッジとツリー上のいくつかのエッジからサイクルを構築します。このようなサイクルが存在する必要があります。そうしないと、エッジがツリーの一部になってしまうからです。
たとえば、上記のサンプル グラフで考えられるスパニング ツリーの 1 つを次に示します。
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/ で入手できます。
サイクルベースから単純なサイクルを組み合わせて、新しい単純なサイクルを形成する方法について言及する必要がありました。グラフのすべてのエッジを任意の順序 (ただし、今後は固定) でリストすることから始めます。次に、サイクルに属するエッジの位置に 1 を配置し、サイクルの一部ではないエッジの位置に 0 を配置して、0 と 1 のシーケンスでサイクルを表します。次に、シーケンスのビットごとの排他的 OR (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）として表されます。たとえば、ABCA と BDCB の XOR を実行すると、結果は (1, 1, 0, 1, 1) となり、これはまさに ABDCA です。または、ABCA と ABDCA を XOR して結果を (0, 0, 1, 1, 1) にすることもできます。まさにBDCBです。
サイクルベースが与えられた場合、2 つ以上の異なるベースサイクルのすべての可能な組み合わせを調べることで、すべての単純なサイクルを発見できます。この手順については、http: //dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf (14 ページ)で詳しく説明しています。
完全を期すために、有向グラフのすべての単純なサイクルを見つけるためにアルゴリズムを使用することは可能 (かつ非効率的) であるように思われることに注意してください。無向グラフのすべてのエッジは、反対方向に向かう 2 つの有向エッジに置き換えることができます。その後、有向グラフのアルゴリズムが機能するはずです。無向グラフのエッジごとに 1 つの「偽」の 2 ノード サイクルが存在しますが、これは無視する必要があり、無向グラフのすべての単純なサイクルには時計回りと反時計回りのバージョンがあります。有向グラフのすべてのサイクルを見つけるためのアルゴリズムの Java でのオープン ソース実装は、既に引用したリンクにあります。
アクセル、あなたのコードを 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()
以下は、深さ優先検索に基づくC＃（およびJava、回答の最後を参照）でのデモ実装です。
外側のループは、グラフのすべてのノードをスキャンし、すべてのノードから検索を開始します。隣接するノード (エッジのリストに従って) がサイクル パスに追加されます。訪問されていない近隣を追加できない場合、再帰は終了します。パスが 2 つのノードよりも長く、次の隣接ノードがパスの開始点である場合、新しいサイクルが見つかります。サイクルの重複を避けるために、サイクルは最小のノードを最初に回転させることによって正規化されます。逆順のサイクルも考慮されます。
これは単純な実装です。古典的な論文は次のとおりです。ドナルド・B・ジョンソン。有向グラフのすべての基本回路を見つける。サイアム J. コンピューティング、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;
}
}
上記の 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) );
}
}
上記の python コードの vb .net バージョンを次に示します。
Module Module1
' Graph modelled as list of edges
Public graph As Integer(,) = {{{1, 2}, {1, 3}, {1, 4}, {2, 3},
{3, 4}, {2, 6}, {4, 6}, {7, 8},
{8, 9}, {9, 7}}
Public cycles As New List(Of Integer())()
Sub Main()
For i As Integer = 0 To graph.GetLength(0) - 1
For j As Integer = 0 To graph.GetLength(1) - 1
findNewCycles(New Integer() {graph(i, j)})
Next
Next
For Each cy As Integer() In cycles
Dim s As String
s = cy(0)
For i As Integer = 1 To cy.Length - 1
s = s & "," & cy(i)
Next
Console.WriteLine(s)
Debug.Print(s)
Next
End Sub
Private Sub findNewCycles(path As Integer())
Dim n As Integer = path(0)
Dim x As Integer
Dim [sub] As Integer() = New Integer(path.Length) {}
For i As Integer = 0 To graph.GetLength(0) - 1
For y As Integer = 0 To 1
If graph(i, y) = n Then
' edge referes to our current node
x = graph(i, (y + 1) Mod 2)
If Not visited(x, path) Then
' neighbor node not on path yet
[sub](0) = x
Array.Copy(path, 0, [sub], 1, path.Length)
' explore extended path
findNewCycles([sub])
ElseIf (path.Length > 2) AndAlso (x = path(path.Length - 1)) Then
' cycle found
Dim p As Integer() = normalize(path)
Dim inv As Integer() = invert(p)
If isNew(p) AndAlso isNew(inv) Then
cycles.Add(p)
End If
End If
End If
Next
Next
End Sub
Private Function equals(a As Integer(), b As Integer()) As Boolean
Dim ret As Boolean = (a(0) = b(0)) AndAlso (a.Length = b.Length)
Dim i As Integer = 1
While ret AndAlso (i < a.Length)
If a(i) <> b(i) Then
ret = False
End If
i += 1
End While
Return ret
End Function
Private Function invert(path As Integer()) As Integer()
Dim p As Integer() = New Integer(path.Length - 1) {}
For i As Integer = 0 To path.Length - 1
p(i) = path(path.Length - 1 - i)
Next
Return normalize(p)
End Function
' rotate cycle path such that it begins with the smallest node
Private Function normalize(path As Integer()) As Integer()
Dim p As Integer() = New Integer(path.Length - 1) {}
Dim x As Integer = smallest(path)
Dim n As Integer
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
End While
Return p
End Function
Private Function isNew(path As Integer()) As Boolean
Dim ret As Boolean = True
For Each p As Integer() In cycles
If equals(p, path) Then
ret = False
Exit For
End If
Next
Return ret
End Function
Private Function smallest(path As Integer()) As Integer
Dim min As Integer = path(0)
For Each p As Integer In path
If p < min Then
min = p
End If
Next
Return min
End Function
Private Function visited(n As Integer, path As Integer()) As Boolean
Dim ret As Boolean = False
For Each p As Integer In path
If p = n Then
ret = True
Exit For
End If
Next
Return ret
End Function
エンドモジュール
上記のサイクルファインダーにはいくつか問題があるようです。C# バージョンでは、いくつかのサイクルが見つかりません。私のグラフは次のとおりです。
{2,8},{4,8},{5,8},{1,9},{3,9},{4,9},{5,9},{6,9},{1,10},
{4,10},{5,10},{6,10},{7,10},{1,11},{4,11},{6,11},{7,11},
{1,12},{2,12},{3,12},{5,12},{6,12},{2,13},{3,13},{4,13},
{6,13},{7,13},{2,14},{5,14},{7,14}
たとえば、cycle:1-9-3-12-5-10が見つかりません。C++ バージョンも試してみましたが、明らかに間違っている非常に大きな (数千万) サイクル数を返します。おそらく、周期が合っていないのでしょう。
申し訳ありませんが、私は少し危機に瀕しており、これ以上調査していません。Nikolay Ognyanov の投稿に基づいて独自のバージョンを作成しました (投稿ありがとうございます)。上記のグラフでは、私のバージョンは 8833 サイクルを返し、それが正しいことを確認しようとしています。C# バージョンは 8397 サイクルを返します。
Matlab のバージョンには何かがありませんでした。関数 findNewCycles(path) は次のようになります。
関数 findNewCycles(パス)
global graph cycles numCycles;
startNode = path(1);
nextNode = nan;
sub = [];
% visit each edge and each node of each edge
for i = 1:size(graph,1)
node1 = graph(i,1);
node2 = graph(i,2);
if (node1 == startNode) || (node2==startNode) %% this if is required
if node1 == startNode
nextNode = node2;
elseif node2 == startNode
nextNode = node1;
end
if ~(visited(nextNode, path))
% neighbor node not on path yet
sub = nextNode;
sub = [sub path];
% explore extended path
findNewCycles(sub);
elseif size(path,2) > 2 && nextNode == path(end)
% cycle found
p = rotate_to_smallest(path);
inv = invert(p);
if isNew(p) && isNew(inv)
numCycles = numCycles + 1;
cycles{numCycles} = p;
end
end
end
end