반응형
무 방향 그래프에서 모든주기 찾기
무 방향 그래프에서 모든 간단한주기를 찾기위한 작동 알고리즘이 필요합니다. 비용이 기하 급수적 일 수 있고 문제는 NP- 완전이라는 것을 알고 있지만 작은 그래프 (최대 20-30 개의 꼭지점)에서 사용할 것이며주기의 수가 적습니다.
긴 연구 (주로 여기) 후에도 여전히 작동하는 접근 방식이 없습니다. 다음은 내 검색 요약입니다.
무 방향 그래프의주기 ->주기가 있는지 여부 만 감지
무 방향 그래프 내에서 다각형 찾기 -> 매우 좋은 설명이지만 해결책은 없습니다.
유 방향 그래프에서 모든주기 찾기 -> 유 방향 그래프에서만 주기 찾기
부스트 그래프 라이브러리를 사용하여 무 방향 그래프에서주기 감지
내 문제에 접근하는 유일한 답은 다음과 같습니다.
기본 사이클 세트를 찾고 XOR-ing하는 것이 트릭을 할 수있는 것 같습니다. 기본 사이클 세트를 찾는 것은 쉽지만 그래프의 모든 사이클을 얻기 위해 그것들을 결합하는 방법을 이해하지 못합니다.
무 방향 그래프의 경우 표준 접근 방식은 소위주기베이스 (다른 모든주기의 조합을 통해 생성 할 수있는 간단한주기 집합)를 찾는 것입니다. 이것들은 반드시 그래프의 모든 단순한 사이클이 아닙니다. 예를 들어 다음 그래프를 고려하십시오.
A
/ \
B ----- C
\ /
D
여기에는 ABCA, BCDB 및 ABDCA의 세 가지 간단한 사이클이 있습니다. 그러나 이들 각각 2 개를 기초로 삼고 2의 조합으로 3 번째를 얻을 수 있습니다. 이것은 에지 방향을 관찰 할 필요가있어 자유롭게 순환하는 방향 그래프와는 상당한 차이입니다.
무 방향 그래프에 대한주기 기반을 찾기위한 표준 기준 알고리즘은 다음과 같습니다. 스패닝 트리를 만든 다음 트리의 일부가 아닌 각 가장자리에 대해 해당 가장자리와 트리의 일부 가장자리에서주기를 만듭니다. 그렇지 않으면 가장자리가 나무의 일부가되기 때문에 그러한주기가 존재해야합니다.
예를 들어 위의 샘플 그래프에 가능한 스패닝 트리 중 하나는 다음과 같습니다.
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가 모두 0이 아닌지 확인하여 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)로 표시됩니다. 이제 예를 들어 BDCB를 사용하여 XOR ABCA를 수행 할 수 있으며 결과는 정확히 ABDCA 인 (1, 1, 0, 1, 1)입니다. 또는 결과가 (0, 0, 1, 1, 1) 인 XOR ABCA 및 ABDCA를 사용할 수 있습니다. 정확히 BDCB입니다.
주기 기반이 주어지면 2 개 이상의 서로 다른 기본주기의 가능한 모든 조합을 검사하여 모든 단순주기를 찾을 수 있습니다. 절차는 여기에 자세히 설명되어 있습니다. http://dspace.mit.edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdf 페이지 14.
완전성을 위해, 방향성 그래프의 모든 간단한주기를 찾기 위해 알고리즘을 사용하는 것이 가능하고 비효율적이라는 것을 알 수 있습니다. 무 방향 그래프의 모든 에지는 반대 방향으로가는 2 개의 방향성 에지로 대체 될 수 있습니다. 그러면 유 방향 그래프에 대한 알고리즘이 작동합니다. 무시해야하는 무 방향 그래프의 모든 에지에 대해 1 개의 "거짓"2- 노드 사이클이 있으며 무 방향 그래프의 모든 단순 사이클에는 시계 방향 및 시계 반대 방향 버전이 있습니다. 방향성 그래프에서 모든주기를 찾기위한 자바 알고리즘의 오픈 소스 구현은 내가 이미 인용 한 링크에서 찾을 수 있습니다.
다음은 심도 우선 검색을 기반으로 한 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;
}
}
Axel, 당신의 코드를 파이썬으로 번역했습니다. 코드 줄의 약 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()
위의 파이썬 코드에서 적용한이 알고리즘의 매우 절름발이 MATLAB 버전이 있습니다.
function cycleList = searchCycles(edgeMap)
tic
global graph cycles numCycles;
graph = edgeMap;
numCycles = 0;
cycles = {};
for i = 1:size(graph,1)
for j = 1:2
findNewCycles(graph(i,j))
end
end
% print out all found cycles
for i = 1:size(cycles,2)
cycles{i}
end
% return the result
cycleList = cycles;
toc
function findNewCycles(path)
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
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
function inv = invert(path)
inv = rotate_to_smallest(path(end:-1:1));
% rotate cycle path such that it begins with the smallest node
function new_path = rotate_to_smallest(path)
[~,n] = min(path);
new_path = [path(n:end), path(1:n-1)];
function result = isNew(path)
global cycles
result = 1;
for i = 1:size(cycles,2)
if size(path,2) == size(cycles{i},2) && all(path == cycles{i})
result = 0;
break;
end
end
function result = visited(node,path)
result = 0;
if isnan(node) && any(isnan(path))
result = 1;
return
end
for i = 1:size(path,2)
if node == path(i)
result = 1;
break
end
end
다음은 위의 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) );
}
}
@LetterRip 및 @Axel Kemper에서 영감을 얻었습니다. 다음은 더 짧은 Java 버전입니다.
public static int[][] graph =
{
{1, 2}, {2, 3}, {3, 4}, {2, 4},
{3, 5}
};
public static Set<List<Integer>> cycles = new HashSet<>();
static void findNewCycles(ArrayList<Integer> path) {
int start = path.get(0);
int next = -1;
for (int[] edge : graph) {
if (start == edge[0] || start == edge[1]) {
next = (start == edge[0]) ? edge[1] : edge[0];
if (!path.contains(next)) {
ArrayList<Integer> newPath = new ArrayList<>();
newPath.add(next);
newPath.addAll((path));
findNewCycles(newPath);
} else if (path.size() > 2 && next == path.get(path.size() - 1)) {
List<Integer> normalized = new ArrayList<>(path);
Collections.sort(normalized);
cycles.add(normalized);
}
}
}
}
public static void detectCycle() {
for (int i = 0; i < graph.length; i++)
for (int j = 0; j < graph[i].length; j++) {
ArrayList<Integer> path = new ArrayList<>();
path.add(graph[i][j]);
findNewCycles(path);
}
for (List<Integer> c : cycles) {
System.out.println(c);
}
}
위의 파이썬 코드의 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}
예를 들어, 사이클 :을 1-9-3-12-5-10찾을 수 없습니다. 나는 C ++ 버전도 시도했는데, 그것은 분명히 잘못된 매우 큰 (수천만) 수의 사이클을 반환합니다. 아마도주기와 일치하지 않을 것입니다.
죄송합니다. 약간 문제가있어서 더 이상 조사하지 않았습니다. 나는 Nikolay Ognyanov의 게시물을 기반으로 내 자신의 버전을 작성했습니다 (귀하의 게시물에 대단히 감사합니다). 위의 그래프에서 내 버전은 8833 사이클을 반환하며 올바른지 확인하려고합니다. C # 버전은 8397 사이클을 반환합니다.
다음은 파이썬 코드의 노드 버전입니다.
const graph = [[1, 2], [1, 3], [1, 4], [2, 3], [3, 4], [2, 6], [4, 6], [8, 7], [8, 9], [9, 7]]
let cycles = []
function main() {
for (const edge of graph) {
for (const node of edge) {
findNewCycles([node])
}
}
for (cy of cycles) {
console.log(cy.join(','))
}
}
function findNewCycles(path) {
const start_node = path[0]
let next_node = null
let sub = []
// visit each edge and each node of each edge
for (const edge of graph) {
const [node1, node2] = edge
if (edge.includes(start_node)) {
next_node = node1 === start_node ? node2 : node1
}
if (notVisited(next_node, path)) {
// eighbor node not on path yet
sub = [next_node].concat(path)
// explore extended path
findNewCycles(sub)
} else if (path.length > 2 && next_node === path[path.length - 1]) {
// cycle found
const p = rotateToSmallest(path)
const inv = invert(p)
if (isNew(p) && isNew(inv)) {
cycles.push(p)
}
}
}
}
function invert(path) {
return rotateToSmallest([...path].reverse())
}
// rotate cycle path such that it begins with the smallest node
function rotateToSmallest(path) {
const n = path.indexOf(Math.min(...path))
return path.slice(n).concat(path.slice(0, n))
}
function isNew(path) {
const p = JSON.stringify(path)
for (const cycle of cycles) {
if (p === JSON.stringify(cycle)) {
return false
}
}
return true
}
function notVisited(node, path) {
const n = JSON.stringify(node)
for (const p of path) {
if (n === JSON.stringify(p)) {
return false
}
}
return true
}
main()
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
참조 URL : https://stackoverflow.com/questions/12367801/finding-all-cycles-in-undirected-graphs
반응형
'UFO ET IT' 카테고리의 다른 글
| 이미 설치된 hstore 확장으로 새 데이터베이스를 만드는 방법은 무엇입니까? (0) | 2021.01.14 |
|---|---|
| sqlite-INSERT 또는 IGNORE가 작동하도록하는 방법 (0) | 2021.01.14 |
| 쿼리에 대한 sqlalchemy가 있습니다. (0) | 2021.01.13 |
| HttpPost에서 매개 변수를 사용하는 방법 (0) | 2021.01.13 |
| Linux의 변경 사항에 대해 전체 디렉토리 트리를 모니터링하는 방법은 무엇입니까? (0) | 2021.01.13 |