Finden aller nicht überlappenden Zyklen in einem ungerichteten Graphen

Question

Ich muss alle einfachen nicht überlappenden Zyklen auf ungerichteten Graphen finden. Um alle bestehenden Zyklen zu finden machte ich eine Objective-C-Version des Algorithmus, die ich hier gefunden:

Finding all cycles in undirected graphs

@interface HSValue : NSObject 
@property (nonatomic, assign) CGPoint point; 
@end 
@implementation HSValue 
@end 


@interface CyclesFinder() 
@property (nonatomic, strong) NSMutableArray <NSArray<HSValue *>*> *cycles; 
@property (nonatomic, strong) NSArray <NSArray<HSValue*>*> *edges; 
@end 

@implementation CyclesFinder 

-(void)findCyclesInGraph:(NSArray <NSArray<HSValue*>*> *)edges { 
    self.edges = edges; 
    for (NSInteger i=0; i < self.edges.count; i++) { 
     for (NSInteger j=0; j < self.edges[i].count; j++) { 
      [self findNewCycles:@[self.edges[i][j]]]; 
     } 
    } 
} 

-(void)findNewCycles:(NSArray <HSValue *> *)path { 

    HSValue *startNode = path[0]; 
    HSValue *nextNode; 
    NSArray <HSValue *> *sub; 

    for (NSInteger i=0; i < self.edges.count; i++) { 
     NSArray <HSValue *> *edge = self.edges[i]; 
     if ([edge containsObject:startNode]) { 
      if ([edge[0] isEqual:startNode]) { 
       nextNode = edge[1]; 
      } 
      else { 
       nextNode = edge[0]; 
      } 
     } 
     else { 
      nextNode = nil; 
     } 

     if (![path containsObject:nextNode] && nextNode) { 
      sub = @[nextNode]; 
      sub = [sub arrayByAddingObjectsFromArray:path]; 
      [self findNewCycles:sub]; 
     } 
     else if (path.count > 2 && [nextNode isEqual:path.lastObject]) { 
      if (![self cycleExist:path]) { 
       [self.cycles addObject:path]; 
       break; 
      } 
     } 
    } 
} 

-(BOOL)cycleExist:(NSArray <HSValue*> *)path { 
    path = [path sortedArrayUsingSelector:@selector(compare:)]; 
    for (NSInteger i=0; i < self.cycles.count; i++) { 
     NSArray <HSValue *> *cycle = [self.cycles[i] sortedArrayUsingSelector:@selector(compare:)]; 
     if ([cycle isEqualToArray:path]) { 
      return TRUE; 
     } 
    } 

    return FALSE; 
} 

Above Algorithmus funktioniert gut (auch wenn es nicht sehr effizient ist) und es findet alle möglich Zyklen aus der grafischen Darstellung auf dem beigefügte Bild (siehe Bild unten):

ABHGFDEA (gültig)

BCIHB (gültig)

GHILKG (gültig)

FGKJF (gültig)

FGHILKJF (ungültig)

ABCIHGFDEA (ungültig)

ABCILKJFDEA (ungültig)

ABCIHG - KJFDEA (ungültig)

ABHILKGFDEA (ungültig)

ABHGKJFDEA (ungültig)

ABCILKGFDEA (ungültig)

BCILKGHB (ungültig)

BCILKJFGHB (ungültig)

jedoch, wenn ich den obigen Algorithmus ausgeführt werden soll ich nur mit, um am Ende diejenigen, Zyklen, die ich mit farbigen Polygonen am linken Beispiel markiert habe. Was ich nicht will, sind die Zyklen wie der auf der rechten Seite Beispiel.

Mein erster Gedanke war, dass Zyklus überlappende wird ein Zyklus, der alle Punkte von allen anderen Zyklen enthält, aber das ist nicht immer wahr. Kann mir jemand in die richtige Richtung zeigen? Ist es möglich, den obigen Algorithmus zu modifizieren, so dass er nur nicht überlappende Zyklen findet oder wenn nicht, was soll ich tun, nachdem ich alle Zyklen gefunden habe, um sie zu filtern?

Answer 1

Es gibt nicht genug Informationen nur im ungerichteten Graph selbst, um festzustellen, welche Zyklen welche sind. Betrachten wir zum Beispiel, dass die folgenden zwei Diagramme identisch ungerichtete Graphen ergeben:

A-----B  E-------------F 
|  |  \   /
C-----D  \ A-----B/
|  |   \|  |/ 
E-----F   C-----D 

Aber für das Diagramm auf der linken Seite, möchten Sie die Zyklen ABDCA und CDFEC, während für das Diagramm auf der rechten Seite, möchten Sie die Zyklen ABDCA und EFDBACE. Daher ist der ungerichtete Graph, der aus dem Diagramm abgeleitet wird, nicht genug - Sie müssen irgendwie räumliche Informationen aus dem ursprünglichen Diagramm einbeziehen.

Answer 2

Ich arbeite an dem gleichen Problem und viele Ihrer Kommentare waren hilfreich, vor allem der Kommentar, dass alle Kanten einen Bereich auf jeder Seite haben werden. Man könnte also sagen, dass jede Kante einen "linken Bereich" und einen "rechten Bereich" hat.

Sie können alle Diagrammkanten zu einer Warteschlange in beliebiger Reihenfolge hinzufügen. Spähen Sie an der ersten Kante, wählen Sie den Scheitelpunkt näher an Ihrem Ursprung. Gehe zum Nachbar, der am meisten gegen den Uhrzeigersinn ist. fahre fort, bis du deinen Startknoten erreicht hast. Alle diese Kanten begrenzen den ersten Bereich. Ich würde es eine eindeutige ID geben und es einer "linken Bereich" Eigenschaft dieser Kanten zuweisen.

Spähen Sie an der ersten Kante in der Warteschlange und prüfen Sie, ob es einen "linken Bereich" hat. Wenn es überprüft, ob es einen "richtigen Bereich" hat, wenn es nicht im Uhrzeigersinn weitergeht und den richtigen Bereich findet. Wenn es beiden Bereichen zugewiesen ist, entschreibe es und schnappe den nächsten.

sollte O (e + v) so ziemlich schnell sein, oder?

Dies ist ein kleiner Strom des Bewusstseins, aber ich wollte es aufgeschrieben bekommen. Ich werde den Algorithmus für meine eigentliche App schreiben und ich werde Verbesserungen vornehmen, wenn ich Probleme darin finde.

Natürlich bin ich offen für Feedback und Anregungen :)