Finding all non overlapping cycles in an undirected graph

Question

I need to find all simple non overlapping cycles on undirected graph. To find all existing cycles I made an Objective-C version of the algorithm that I found here:

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 algorithm works fine (even if it is not very efficient) and it finds all the possible cycles from the graph on the attached picture (please see picture below):

A-B-H-G-F-D-E-A (valid)

B-C-I-H-B (valid)

G-H-I-L-K-G (valid)

F-G-K-J-F (valid)

F-G-H-I-L-K-J-F (invalid)

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

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

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

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

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

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

B-C-I-L-K-G-H-B (invalid)

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

However when I run the above algorithm I want to end up with only those cycles that I highlighted with coloured polygons on the left hand side example. What I don't want are the cycles like the one on the right hand side example.

My first thought was that overlapping cycle will be a cycle that includes all the points from any other cycles, but this is not always true. Can someone point me into the right direction? Is it possible to modify the above algorithm so it finds only non-overlapping cycles or if not what should I do after finding all cycles to filter them?

Answer 1

There isn't enough information just in the undirected graph itself to determine which cycles are which. For example, consider that the following 2 diagrams yield identical undirected graphs:

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

But for the diagram on the left, you want the cycles ABDCA and CDFEC, while for the diagram on the right, you want the cycles ABDCA and EFDBACE. Thus the undirected graph inferred from the diagram isn't enough -- you need to somehow incorporate spatial information from the original diagram.

Answer 2

I'm working on this same problem and a lot of your comments were helpful, especially the comment that all edges will have an area on each side. Thus you could say that each edge has a "left area" and a "right area".

You can add all graph edges to a queue in any order. Peek at the first edge, pick its vertex closer to your origin. Move to the neighbor that is the most counter-clockwise. continue this until you have reached your starting vertex. All of these edges bound your first area. I would give it a unique ID and assign it to a "left area" property of those edges.

Peek at the first edge in the queue and check if it has a "left area". If it does check if it has a "right area" if it does not proceed in a clockwise manner and find the right area. If it has both areas assigned dequeue it and grab the next one.

should be O(e+v) so pretty quick, right?

This is a little bit stream of consciousness but I wanted to get it written down. I'll be writing the algorithm for my actual app and I'll make tweaks as I find problems in it.

Of course I'm open to feedback and suggestions :)

Answer 3

I know this question has been 6 years old yet leaving this answer for someone having the same problem in the future.

Key idea

1. Every edge has exactly two adjacent faces. Actually, every directed edge has exactly one adjacent face.
2. Construct polygons by choosing most counter-clockwise adjacent edge. Then the polygons with counter-clockwise orientation will be non-overlapping cycle of the graph.

Algorithm overview

1. For every edges on the graph, find two polygons containing the edge. One for each direction of the edge.
2. Filter the polygons whose orientation is counter-clockwise.

The resulting polygons are all of non-overlapping cycles in the given graph.

Finding a polygon containing the given edge in a graph

Basically it's choosing the next edge by most counter-clockwise from the current edge until a cycle is created or it hits dead end.

If the end of the cycle equals to the start of the given edge, then the polygon contains the given edge. Else the polygon doesn't contain the given edge, so ignore it.

I'm just posting the entire code of this function. Read it through and I hope you get the idea.

See caveats below for more informations about orientations and vector calculations.

    static public <N extends Location> Optional<Polygon<N>> findPolygon(EndpointPair<N> edge, Graph<N> graph) {
        if (!edge.isOrdered()) throw new IllegalArgumentException("The starting edge must be ordered.");
        if (!graph.hasEdgeConnecting(edge))
            throw new IllegalArgumentException("The starting edge must be contained in the graph");

        final N start = edge.source();
        final MutableGraph<N> polygonGraph = GraphBuilder.directed()
                .incidentEdgeOrder(ElementOrder.stable())
                .nodeOrder(ElementOrder.insertion())
                .build();

        // Set the first edge of the polygon.
        N source = start;
        N target = edge.adjacentNode(source);

        // Start adding edges to polygonGraph.
        // Until a cycle is created.
        while (true) {
            // Check if a cycle is created.
            if (polygonGraph.nodes().contains(target)) {
                // Connect the last edge.
                polygonGraph.putEdge(source, target);
                break;
            }

            // Connect the edge.
            polygonGraph.putEdge(source, target);

            // Find the most counter-clockwise adjacent vertex from the target.
            // Then that vertex is the target of the next edge and the target of the current edge is the source of
            // the next edge.
            Vector base = source.toVector().clone().subtract(target.toVector());
            final N finalTarget = target;
            Map<N, Double> angles = graph.adjacentNodes(target).stream().collect(Collectors.toMap(
                    Function.identity(),
                    node -> {
                        Vector u = node.toVector().clone().subtract(finalTarget.toVector());
                        return Vectors.fullAngle(base, u);
                    }
            ));

            List<N> adjacentNodes = graph.adjacentNodes(target).stream().filter(not(source::equals)).toList();

            // Dead end. Failed to create a polygon. Exit.
            if (adjacentNodes.isEmpty()) break;

            source = target;
            target = Collections.max(adjacentNodes, Comparator.comparingDouble(angles::get));
        }

        // The created polygon doesn't contain the starting edge.
        if (!target.equals(start)) {
            return Optional.empty();
        }

        return Optional.of(new Polygon<>(polygonGraph));
    }

Identifying the orientation of a polygon

https://www.baeldung.com/cs/list-polygon-points-clockwise

A polygon is counter-clockwise iff its area > 0.

Optimization

The time complexity of the algorithm is O(E^2). (I think)

But you can apply dynamic programming method and it reduces to O(E) (I think)

The idea is that for every directed edge there exists only one matching polygon.

So when you find a polygon, cache every edges of that polygon and you won't have to find that polygon for that edges again.

// This is a pseudo-code

Map<Edge, Polygon> cache = new HashMap<>();

// If the edge is in cache, skip the polygon search.
if (cache.containsKey(edge)) continue;
    
// When you have found a polygon, cache the edges.
polygon.edges().forEach(edge -> {
    cache.put(edge, polygon);
});

You can also pre-determine if a given edge can construct a polygon by looking at the neighbors of the edge. If any one of the degree of the vertices of the edge is less than 2, meaning that the edge is not connected to other neighbors at both side, it cannot construct a polygon. So you can skip the polygon search for this edge.

Caveats

Orientations

About the orientation and the related things, although I wrote this article after choose to use counter-clockwise, it seems that it doesn't matter which side you pick to use as long as be consistent for:

1. The orientation of the polygon ( counter-clockwise / clockwise)
2. Which adjacent edge to pick to be the next edge of the polygon ( most counter-clockwise / least counter-clockwise ) (or in other words, least clockwise / most clockwise)

Once you choose one of them to be one thing then the other option is automatically determined in order to the algorithm work.

Angle of two edges

You need to convert edges to vectors in order to calculate the angle between them.

Keep in mind that the tail of the vectors have to be the vertex of the angle.

So, if you're getting the angle between Edge(AB) and Edge(BC) then you have to calculate the angle between u = A - B and w = C - B.

Angle of two vectors

Some APIs define the range of the function for getting angle between two vectors as [-PI/2, PI/2].

But you need it to be [0, 2PI] so, you have to convert it.

You can make it [-PI, PI] by using atan2 function.

https://math.stackexchange.com/questions/878785/how-to-find-an-angle-in-range0-360-between-2-vectors

And then add 2 * PI then take mod 2 * PI.

public class Vectors {
    static public double fullAngle(@NotNull Vector v, @NotNull Vector u) {
        return (Math.atan2(v.det(u), v.dot(u)) + 2 * Math.PI) % (2 * Math.PI);
    }
}