Longest Simple Cycle Problem

The Longest Simple Cycle problem seeks to find the longest simple cycle in a graph. A simple cycle is a cycle that doesn’t repeat any vertices except the first and last. This problem can appear in various applications like network design and route optimization.

In more accessible terms, imagine a network of cities connected by roads. What is the longest route you can take that visits each city only once and returns to the starting city?

Example Code in Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// Example code assumes that the graph is represented as an adjacency matrix
public class LongestSimpleCycle {
    static int longestCycle(int[][] graph, boolean[] visited, int currNode, int startNode, int length) {
        if (currNode == startNode && length > 0) return length;
        visited[currNode] = true;
        int maxLength = -1;

        for (int i = 0; i < graph.length; i++) {
            if (graph[currNode][i] > 0 && !visited[i]) {
                int cycleLength = longestCycle(graph, visited, i, startNode, length + 1);
                maxLength = Math.max(maxLength, cycleLength);
            }
        }

        visited[currNode] = false;
        return maxLength;
    }

    public static void main(String[] args) {
        int[][] graph = { // your adjacency matrix here };
        boolean[] visited = new boolean[graph.length];
        System.out.println(longestCycle(graph, visited, 0, 0, 0));
    }
}

Example Code in C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int longestCycle(vector<vector<int>> &graph, vector<bool> &visited, int currNode, int startNode, int length) {
    if (currNode == startNode && length > 0) return length;
    visited[currNode] = true;
    int maxLength = -1;

    for (int i = 0; i < graph.size(); ++i) {
        if (graph[currNode][i] > 0 && !visited[i]) {
            int cycleLength = longestCycle(graph, visited, i, startNode, length + 1);
            maxLength = max(maxLength, cycleLength);
        }
    }

    visited[currNode] = false;
    return maxLength;
}

int main() {
    vector<vector<int>> graph;  // Your adjacency matrix here
    vector<bool> visited(graph.size(), false);
    cout << longestCycle(graph, visited, 0, 0, 0) << endl;
}

Example Code in Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
def longest_cycle(graph, visited, curr_node, start_node, length):
    if curr_node == start_node and length > 0:
        return length
    
    visited[curr_node] = True
    max_length = -1

    for i in range(len(graph)):
        if graph[curr_node][i] > 0 and not visited[i]:
            cycle_length = longest_cycle(graph, visited, i, start_node, length + 1)
            max_length = max(max_length, cycle_length)

    visited[curr_node] = False
    return max_length

graph = []  # Your adjacency matrix here
visited = [False for _ in range(len(graph))]
print(longest_cycle(graph, visited, 0, 0, 0))

In all implementations, the algorithm explores all possible cycles starting from each node. It uses a Depth-First Search (DFS) approach to find the longest simple cycle. Note that this is an exponential time solution.