3
無向グラフ上の単純な重複していないサイクルをすべて見つける必要があります。アルゴリズムの上無向グラフのすべての重複していないサイクルの検索
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;
}
正常に動作します（それは非常に効率的でない場合であっても）、それがすべて見つかった：私はここで見つけるアルゴリズムのObjective-Cのバージョンが作られた既存のすべてのサイクルを検索するには添付画像上のグラフから可能なサイクル（下図を参照してください）：
ABHGFDEA（有効）
BCIHB（有効）
（有効）FGKJF（有効）
GHILKG
FGHILKJF（無効）
ABCIHGFDEA（無効）（無効）
ABCIHG
ABCILKJFDEA - KJFDEA（無効）
ABHILKGFDEA（無効）
ABHGKJFDEA（無効）
ABCILKGFDEA（無効）
BCILKGHB（無効）
BCILKJFGHB（無効）しかし、私は上記のアルゴリズムを実行したとき、私はのみで終わるしたい
私が色のついたポリゴンで強調表示したサイクルを左側の例に示します。私が望まないのは、右側の例のようなサイクルです。
私が最初に考えたのは、サイクルを重ねることは、他のサイクルからのすべての点を含んサイクルになるということでしたが、これは常に真ではありません。誰かが私を正しい方向に向けることができますか？上記のアルゴリズムを変更して、重複していないサイクルだけを見つけることができますか、またはそれらをフィルタリングするためにすべてのサイクルを見つけた後に何をすべきですか？
私は2つの数字の間に表示される唯一の違いは色です。それらについて有効で無効なものを説明できますか？ – Avi
色はグラフ上のサイクルを表します。したがって、私はそれが（F-G-K-J-F）と（G-H-I-L-K-J-F）と重なり合って除去したいサイクル（F-G-H-I-L-K-J-F）の1つを強調しています。左の写真の色は私が最終的に目指すすべてのサイクルを表しています。 – Guferos
私はその情報を質問に追加すべきだと思います。 – Avi