I'm looking for an algorithm that returns ALL simple cycles of fixed length L in a directed and undirected graph.

In my research, I came across similar questions such as:

https://stackoverflow.com/questions/546655/finding-all-cycles-in-a-directed-graph https://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph

whose answers suggest the use of Johnson's algorithm for directed graphs. However, I cannot find anything clear about finding all cycles in an undirected graph and, most importantly, cycles of FIXED LENGTH L both in directed and undirected graphs.

My question comes from the need of finding the cycles incrementally, so that for large graphs I can stop early without biblical runtimes.

CodePudding user response：

I would run the usual cycle finding algorithm and add a filter that passes only cycles of the required length.

Cycle finding algorithm:

 - Run Depth First Search modified 
       to check for back edge ( Dijkstra )
       whenever a previously visited node is popped from the stack

Here is my C code implementing this

    /// @brief Depth first search, finding cycles in directed graph
    /// @param start name of start vertex
    /// @return vector of vectors, each with the vertices in a cycle

std::vector<std::vector<vertex_t>>
cGraph::dfs_cycle_finder(const std::string &start)
{
    std::vector<std::vector<vertex_t>> ret;

    // track visited vertices
    std::vector<bool> visited(vVertexName.size(), false);

    // vertices waiting to be processed
    std::stack<vertex_t> wait;

    // start at the beginning
    wait.push(index(start));

    // continue until no more vertices need processing
    while (!wait.empty())
    {
        vertex_t v = wait.top();
        wait.pop();
        int vi = v;
        if (!visited[vi])
        {
            visited[vi] = true;

            for (vertex_t w : adjacentOut(v))
            {
                if (!visited[w])
                {
                    wait.push(w);
                }
                else
                {
                    // previously visited node, check for ancestor
                    auto cycle = path(w, v);
                    if (cycle.size() > 0)
                    {
                        // found a cycle
                        cycle.push_back(w);
                        ret.push_back(cycle);
                    }
                }
            }
        }
    }
    return ret;
}

The code for the complete application is at https://github.com/JamesBremner/graphCycler

The application can handle graph with thousands of edges in seconds. ( Here is a detailed discussion of the performance of my C DFS code on a graph of 3 million links https://github.com/JamesBremner/PathFinder3/wiki/Performance )

( I would be happy to modify this application to your particular requirements for a small fee. )

CodePudding user response：

If you have generators (or coroutines, or continuations), then this can be accomplished straightforwardly with recursion. In Python:

def find_cycles_recursive(graph, L, cycle):
    successors = graph[cycle[-1]]
    if len(cycle) == L:
        if cycle[0] in successors:
            yield cycle
    elif len(cycle) < L:
        for v in successors:
            if v in cycle:
                continue
            yield from find_cycles_recursive(graph, L, cycle   [v])


def find_cycles(graph, L):
    for v in graph:
        yield from find_cycles_recursive(graph, L, [v])


print(list(find_cycles({0: {1, 2}, 1: {0, 2, 3}, 2: {0, 1, 3}, 3: {1, 2}}, 3)))

You can optimize by changing the condition v in cycle to v <= cycle[0] or v in cycle. For undirected graphs, you can also filter out the graphs where cycle[1] > cycle[-1] at the end.

If you’re working in a language with impoverished control flow primitives, then you need to use data structures to simulate the missing ones. Here this amounts to keeping a stack of iterators. (In general, you need to “defunctionalize the continuation”.)

def find_cycles2(graph, L):
    for v, neighbors in graph.items():
        cycle = [v]
        stack = [iter(neighbors)]
        while stack:
            try:
                if len(cycle) == L:
                    if cycle[0] in graph[cycle[-1]]:
                        print(cycle)
                    del cycle[-1]
                    del stack[-1]
                elif len(cycle) < L:
                    v = next(stack[-1])
                    if v <= cycle[0] or v in cycle:
                        continue
                    cycle.append(v)
                    stack.append(iter(graph[v]))
            except StopIteration:
                del cycle[-1]
                del stack[-1]


find_cycles2({0: {1, 2}, 1: {0, 2, 3}, 2: {0, 1, 3}, 3: {1, 2}}, 3)