ios - 在无向图中查找所有非重叠循环

Question

我需要在无向图上找到所有简单的非重叠循环。为了找到所有现有的循环，我制作了我在此处找到的算法的 Objective-C 版本:

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;
}

上述算法工作正常(即使它不是很有效)并且它从附图上的图中找到所有可能的循环(请参见下图):

A-B-H-G-F-D-E-A(有效)

B-C-I-H-B(有效)

G-H-I-L-K-G(有效)

F-G-K-J-F(有效)

F-G-H-I-L-K-J-F(无效)

A-B-C-I-H-G-F-D-E-A(无效)

A-B-C-I-L-K-J-F-D-E-A(无效)

A-B-C-I-H-G--K-J-F-D-E-A(无效)

A-B-H-I-L-K-G-F-D-E-A(无效)

A-B-H-G-K-J-F-D-E-A(无效)

A-B-C-I-L-K-G-F-D-E-A(无效)

B-C-I-L-K-G-H-B(无效)

B-C-I-L-K-J-F-G-H-B(无效)

但是，当我运行上述算法时，我只想得到在左侧示例中用彩色多边形突出显示的那些循环。我不想要的是右侧示例中的循环。

我的第一个想法是重叠循环将是一个包含任何其他循环的所有点的循环，但这并不总是正确的。有人能指出我正确的方向吗？是否可以修改上述算法，使其仅找到非重叠循环，或者如果不能，在找到所有循环以过滤它们后我应该做什么？

Answer 1

仅在无向图中本身没有足够的信息来确定哪些循环是哪些。例如，考虑以下 2 个图产生相同的无向图:

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

但对于左图，您需要循环 ABDCA 和 CDFEC，而对于右图，您需要循环 ABDCA 和 EFDBACE。因此，从图表中推断出的无向图是不够的——您需要以某种方式合并来自原始图表的空间信息。