Ik heb een werkende algoritme voor het vinden van alle eenvoudige cycli in een ongerichte graaf. Ik weet dat de kosten kunnen exponentieel zijn en het probleem is NP-compleet is, maar ik ga om het te gebruiken in een kleine grafiek (tot 20-30 hoekpunten) en de cycli zijn klein in aantal.
Na een lange onderzoek (voornamelijk hier) Ik heb nog steeds niet over een manier van werken. Hier is een samenvatting van mijn zoektocht:
vinden van alle cycli in een ongerichte graaf
Cycles in een ongerichte graaf – & gt; Alleen detecteert of er een cyclus indien
vinden veelhoeken binnen een ongerichte graaf – & gt; zeer mooie beschrijving, maar geen oplossing
vinden van alle cycli in een gerichte graaf – & gt; vindt cycli alleen gericht grafieken
Detect cycli in ongerichte graaf met behulp boost grafiek bibliotheek
Het enige antwoord dat ik vond dat mijn probleem benadert, is deze:
Zoek alle cycli in de grafiek, redux
Het lijkt erop dat het vinden van een basisset van cycli en XOR-ing hen kon doen de truc. Het vinden van een basisset van cycli is gemakkelijk, maar ik begrijp niet hoe ze te combineren om alle cycli in de grafiek …
te verkrijgen
Antwoord 1, Autoriteit 100%
Voor een ongerichte graaf de standaardbenadering te kijken naar een zogenaamde cyclus basis: een reeks eenvoudige cycli van waaruit men tot combinaties genereren overige cycli. Dit zijn niet noodzakelijkerwijs alle eenvoudige cycli in de grafiek. Denk bijvoorbeeld aan de volgende grafiek:
A
/ \
B ----- C
\ /
D
Er zijn 3 eenvoudige cycli here: A-B-C-A, B-C-D-B en A-B-D-C-A. U kunt evenwel rekening 2 elk van deze als basis en het verkrijgen van het 3 als combinatie van 2. Dit is een wezenlijk verschil met betrekking grafieken waar men niet zo vrij cycli combineren vanwege de noodzaak om randrichting nemen.
De standaard basislijn algoritme voor het vinden van een cyclus basis voor een ongerichte graaf is dit: Bouw een spanning tree en vervolgens voor elke rand die geen deel uitmaakt van de boom build een cyclus van die rand en een aantal randen aan de boom. Dergelijke cyclus moeten bestaan omdat anders de rand zou deel van de boom zijn.
Bijvoorbeeld één van de mogelijke overspanning bomen voor het monster bovenstaande grafiek is:
A
/ \
B C
\
D
De randen 2 niet in de boom zijn B-C en C-D. En de overeenkomstige eenvoudige cycli A-B-C-A en A-B-D-C-A.
U kunt ook de volgende spanning tree te bouwen:
A
/
B ----- C
\
D
En voor deze spanning tree de eenvoudige cycli zou zijn A-B-C-A en B-C-D-B.
De basislijn algoritme kan worden op verschillende manieren verfijnd. Om het beste van mijn kennis de beste verfijning behoort tot Paton (K. Paton, Een algoritme voor het vinden van een fundamentele set van cycli voor een ongerichte lineaire grafiek, Comm. ACM 12 (1969), blz. 514-518.). Een open source implementatie in Java is hier beschikbaar: http://code.google.com/p/niographs/ .
Ik had moeten vermelden hoe je eenvoudige cycli uit de cyclusbasis combineert om nieuwe eenvoudige cycli te vormen. U begint met het opsommen van alle randen van de grafiek in een willekeurige (maar hierna vaststaande) volgorde. Dan representeer je cycli door reeksen van nullen en enen door enen te plaatsen op de posities van randen die bij de cyclus horen en nullen in de posities van randen die geen deel uitmaken van de cyclus. Dan doe je bitsgewijze exclusieve OR (XOR) van de reeksen. De reden dat je XOR doet, is dat je kanten wilt uitsluiten die bij beide cycli horen en zo de gecombineerde cyclus niet eenvoudig maken. U moet ook controleren of de 2 cycli SOMMIGE gemeenschappelijke randen hebben door te controleren of de bitsgewijze EN van de reeksen niet allemaal nullen zijn. Anders is het resultaat van XOR 2 onsamenhangende cycli in plaats van een nieuwe eenvoudige cyclus.
Hier is een voorbeeld van de bovenstaande voorbeeldgrafiek:
We beginnen met het opsommen van de randen: ((AB), (AC), (BC), (BD), (CD)). Dan worden de eenvoudige cycli A-B-C-A, B-D-C-B en A-B-D-C-A weergegeven als (1, 1, 1, 0, 0), (0, 0, 1, 1, 1) en (1, 1, 0, 1, 1). Nu kunnen we bijvoorbeeld XOR A-B-C-A met B-D-C-B en het resultaat is (1, 1, 0, 1, 1) wat precies A-B-D-C-A is. Of we kunnen XOR A-B-C-A en A-B-D-C-A met als resultaat (0, 0, 1, 1, 1). Wat precies B-D-C-B is.
Gegeven een cyclusbasis kun je alle eenvoudige cycli ontdekken door alle mogelijke combinaties van 2 of meer verschillende basiscycli te onderzoeken. De procedure wordt hier in meer detail beschreven: http://dspace.mit. edu/bitstream/handle/1721.1/68106/FTL_R_1982_07.pdfop pagina 14.
Voor de volledigheid merk ik op dat het mogelijk (en inefficiënt) lijkt om algoritmen te gebruiken om alle eenvoudige cycli van een gerichte graaf te vinden. Elke rand van de ongerichte graaf kan worden vervangen door 2 gerichte randen die in tegengestelde richting gaan. Dan zouden algoritmen voor gerichte grafieken moeten werken. Er zal 1 “valse” cyclus met 2 knopen zijn voor elke rand van de ongerichte graaf die moet worden genegeerd en er zal een versie met de klok mee en een versie tegen de klok in zijn van elke eenvoudige cyclus van de ongerichte graaf. Open source-implementatie in Java van algoritmen voor het vinden van alle cycli in een gerichte grafiek is te vinden op de link die ik al aanhaalde.
Antwoord 2, autoriteit 71%
Axel, ik heb je code vertaald naar python. Ongeveer 1/4 van de regels code en duidelijker te lezen.
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()
Antwoord 3, autoriteit 67%
Het volgende is een demo-implementatie in C# (en Java, zie einde van antwoord) op basis van eerst diepte zoeken.
Een buitenste lus scant alle knooppunten van de grafiek en start een zoekopdracht vanaf elk knooppunt. Knooppuntburen (volgens de lijst met randen) worden aan het fietspad toegevoegd. Recursie eindigt als er geen niet-bezochte buren meer kunnen worden toegevoegd. Een nieuwe cyclus wordt gevonden als het pad langer is dan twee knopen en de volgende buur het begin van het pad is. Om dubbele cycli te voorkomen, worden de cycli genormaliseerd door het kleinste knooppunt naar het begin te draaien. Er wordt ook rekening gehouden met cycli in omgekeerde volgorde.
Dit is slechts een naïeve implementatie.
De klassieke krant is: Donald B. Johnson. Het vinden van alle elementaire circuits van een gerichte graaf. SIAM J. Comput., 4(1):77–84, 1975.
Een recent overzicht van moderne algoritmen vindt u hier
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;
}
}
}
De cycli voor de demo-grafiek:
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
Het algoritme gecodeerd in 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;
}
}
Antwoord 4, autoriteit 8%
Hier is slechts een erg flauwe MATLAB-versie van dit algoritme, aangepast van de python-code hierboven, voor iedereen die het ook nodig heeft.
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
Antwoord 5, autoriteit 8%
Hier is een C++-versie van de python-code hierboven:
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) );
}
}
Antwoord 6, autoriteit 8%
Geïnspireerd door @LetterRip en @Axel Kemper
Hier is een kortere versie van 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);
}
}
Antwoord 7, autoriteit 2%
Hier is een vb .net-versie van de python-code hierboven:
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
Einde module
Antwoord 8
Het lijkt erop dat de cycluszoeker hierboven problemen heeft. De C#-versie kan sommige cycli niet vinden. Mijn grafiek is:
{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}
Bijvoorbeeld de cyclus: 1-9-3-12-5-10is niet gevonden.
Ik heb ook de C++ -versie geprobeerd, deze geeft een zeer groot (tientallen miljoenen) aantal cycli terug, wat blijkbaar verkeerd is. Waarschijnlijk komt het niet overeen met de cycli.
Sorry, ik zit een beetje in de knoop en heb verder geen onderzoek gedaan. Ik heb mijn eigen versie geschreven op basis van een bericht van Nikolay Ognyanov (heel erg bedankt voor je bericht). Voor de bovenstaande grafiek retourneert mijn versie 8833 cycli en ik probeer te verifiëren dat deze correct is. De C#-versie retourneert 8397 cycli.
Antwoord 9
Hier is een knooppuntversie van de python-code.
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()
Antwoord 10
Dit is GEEN antwoord!
@Nikolay Ognyano
1. Proberen te begrijpen hoe we de gecombineerde cycli moeten genereren met eenvoudige cycli
Ik probeer te begrijpen wat je noemde
Je moet ook controleren of de 2 cycli SOMMIGE gemeenschappelijke randen hebben door te controleren of de bitsgewijze EN van de reeksen niet allemaal nullen zijn. Anders is het resultaat van XOR 2 onsamenhangende cycli in plaats van een nieuwe eenvoudige cyclus.
Ik zou graag willen weten hoe we moeten omgaan met een grafiek zoals hieronder:
0-----2-----4
| /| /
| / | /
| / | /
| / | /
|/ |/
1-----3
Ervan uitgaande dat de fundamentele/eenvoudige cycli zijn:
0 1 2
1 2 3
2 3 4
Blijkbaar, als ik de volgende bitsgewijze XORen ANDgebruik, zal het de cyclus 0 1 3 4 2missen.
bitset<MAX> ComputeCombinedCycleBits(const vector<bitset<MAX>>& bsets) {
bitset<MAX> bsCombo, bsCommonEdgeCheck; bsCommonEdgeCheck.set();
for (const auto& bs : bsets)
bsCombo ^= bs, bsCommonEdgeCheck &= bs;
if (bsCommonEdgeCheck.none()) bsCombo.reset();
return bsCombo;
}
Ik denk dat het belangrijkste probleem hier is bsCommonEdgeCheck &= bs? Wat moeten we gebruiken als er meer dan 3 eenvoudige cycli zijn om de gecombineerde cyclus samen te stellen?
2. Proberen te begrijpen hoe we de volgorde van de gecombineerde cyclus krijgen
Bijvoorbeeld met de volgende grafiek:
0-----1
|\ /|
| \ / |
| X |
| / \ |
|/ \|
3-----2
Ervan uitgaande dat de fundamentele/eenvoudige cycli zijn:
0 1 2
0 2 3
0 1 3
Nadat we de bitsgewijze XOR hebben gebruikt, zijn we de volgorde van de eenvoudige cycli volledig kwijt, en hoe kunnen we de knoopvolgorde van de gecombineerde cyclus krijgen?
Antwoord 11
De Matlab-versie heeft iets gemist, functie findNewCycles(path) zou moeten zijn:
functie findNewCycles(pad)
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