Is finding the largest cycle on a directed graph with 133 Nodes and 737 Edges Computable?

Question

Trying to solve the longest cycle problem for a directed, unweighted graph with 133 nodes and 737 edges. (See also Wikipedia Longest Path Problem).

I tried using the networkx library for Python, but it wasn't able to compute it. Is it worth finding a faster implementation like using DFS in C? It seems to be NP hard which discourages me. I'm not sure if this will take minutes, hours, days, or until the heat death of the universe.

Tried using NetworkX to find the cycles but unable to compute within an hour.

Here is the set of edges of the graph:

[
    (77, 158), (158, 84), (158, 164), (158, 2294), (328, 41), (328, 2005), 
    (328, 36), (328, 167), (328, 62), (328, 23), (41, 278), (41, 2229), 
    (41, 103), (41, 113), (41, 2335), (356, 2751), (356, 258), (356, 275), 
    (356, 2294), (356, 135), (356, 158), (356, 77), (2751, 202), (2751, 
    2005), (2751, 167), (2751, 328), (2751, 62), (2751, 36), (2226, 2429), 
    (2226, 242), (2226, 5), (2226, 2229), (2429, 2247), (2429, 242), 
    (2429, 2348), (249, 2638), (249, 2226), (249, 2348), (249, 98), (249, 
    2229), (249, 242), (2638, 166), (2638, 68), (2638, 2429), (2638, 
    2226), (2638, 2229), (2440, 166), (2440, 326), (166, 62), (166, 167), 
    (166, 113), (166, 2335), (238, 62), (238, 2459), (238, 96), (238, 57), 
    (62, 2440), (62, 2439), (2633, 2050), (2633, 221), (2633, 2006), 
    (2633, 57), (2633, 99), (2633, 333), (2633, 96), (2633, 142), (2633, 
    238), (2050, 2459), (2050, 2117), (2050, 41), (2050, 2309), (221, 
    277), (221, 2711), (221, 259), (221, 183), (221, 258), (221, 150), 
    (221, 2390), (277, 259), (277, 239), (277, 201), (277, 197), (197, 
    2117), (197, 9), (197, 239), (197, 2641), (197, 251), (197, 66), 
    (2117, 2006), (2117, 2459), (2117, 2084), (142, 2348), (142, 238), 
    (142, 2579), (142, 166), (142, 8), (2348, 2638), (2348, 2393), (213, 
    2509), (213, 195), (213, 2), (213, 2117), (213, 77), (213, 135), (213, 
    84), (213, 120), (213, 164), (213, 127), (2509, 2226), (2509, 135), 
    (2509, 120), (2509, 158), (2509, 356), (2509, 77), (2509, 84), (135, 
    166), (135, 38), (135, 127), (135, 164), (135, 158), (135, 77), (135, 
    275), (295, 259), (295, 2032), (295, 324), (259, 103), (259, 2335), 
    (127, 2711), (127, 2006), (127, 275), (127, 356), (127, 164), (2711, 
    2050), (2711, 193), (2711, 2117), (2711, 2649), (150, 218), (150, 77), 
    (150, 258), (150, 2390), (150, 103), (150, 259), (150, 154), (218, 
    113), (218, 58), (84, 356), (84, 98), (84, 127), (2628, 38), (2628, 
    2567), (2628, 201), (2628, 2305), (2628, 197), (2628, 2306), (2628, 
    277), (2628, 2641), (2628, 251), (2628, 239), (2628, 66), (38, 25), 
    (152, 151), (152, 2641), (152, 41), (152, 52), (152, 259), (152, 154), 
    (152, 153), (151, 295), (151, 58), (151, 235), (151, 2116), (151, 
    252), (151, 218), (153, 2026), (153, 2247), (153, 259), (153, 2390), 
    (153, 150), (153, 221), (153, 258), (153, 154), (2026, 245), (2026, 
    2653), (2026, 2247), (2026, 295), (245, 2534), (245, 2390), (245, 8), 
    (245, 113), (245, 99), (120, 2084), (120, 2429), (120, 2567), (120, 
    127), (120, 84), (120, 77), (120, 164), (2084, 2199), (2084, 193), 
    (2084, 189), (2084, 113), (2084, 2649), (2084, 2006), (164, 103), 
    (164, 218), (164, 84), (103, 97), (103, 152), (130, 36), (130, 62), 
    (130, 41), (130, 120), (130, 2294), (130, 84), (130, 213), (130, 127), 
    (130, 164), (130, 158), (130, 356), (130, 194), (130, 2509), (36, 
    2440), (36, 62), (36, 167), (26, 189), (26, 6), (26, 38), (26, 264), 
    (26, 254), (26, 24), (26, 9), (26, 25), (189, 276), (189, 2006), (189, 
    193), (189, 2117), (189, 2711), (189, 2649), (248, 2636), (248, 242), 
    (248, 235), (248, 2426), (248, 58), (248, 218), (248, 151), (2636, 
    349), (2636, 2393), (2636, 98), (2636, 2229), (2636, 249), (2636, 5), 
    (2636, 2348), (2636, 242), (2636, 2638), (61, 2483), (61, 2579), (61, 
    2309), (61, 142), (61, 2), (61, 238), (61, 57), (61, 2633), (61, 344), 
    (61, 96), (61, 59), (61, 99), (2483, 252), (2483, 265), (2483, 24), 
    (2483, 12), (2483, 26), (2483, 25), (2483, 38), (2483, 254), (201, 
    2638), (201, 2309), (201, 158), (201, 2305), (201, 66), (201, 197), 
    (12, 21), (12, 38), (12, 26), (12, 9), (21, 2649), (21, 62), (21, 
    2440), (21, 2439), (21, 23), (21, 167), (202, 2459), (202, 55), (202, 
    218), (202, 58), (202, 248), (8, 2132), (8, 2579), (8, 252), (8, 2), 
    (8, 145), (2132, 193), (2132, 84), (2132, 202), (2132, 58), (2132, 
    2567), (2132, 2426), (2132, 151), (2132, 218), (145, 2653), (145, 59), 
    (145, 202), (145, 96), (145, 238), (145, 2), (145, 245), (2653, 276), 
    (2653, 98), (2653, 2572), (2653, 326), (2653, 6), (2653, 309), (2653, 
    349), (2653, 2433), (2653, 2032), (2653, 324), (252, 58), (252, 239), 
    (252, 2751), (252, 328), (252, 68), (252, 24), (326, 2229), (326, 
    2026), (326, 2032), (256, 2393), (256, 2026), (256, 326), (256, 2032), 
    (256, 295), (256, 2247), (256, 324), (2393, 36), (2393, 2390), (2393, 
    2638), (2393, 2429), (2393, 2226), (2393, 2229), (195, 2226), (195, 
    2006), (195, 2711), (195, 2459), (195, 2084), (195, 193), (195, 2050), 
    (195, 189), (30, 242), (30, 24), (30, 278), (30, 204), (30, 9), (30, 
    265), (30, 12), (30, 25), (30, 38), (30, 26), (30, 87), (242, 309), 
    (242, 5), (242, 2348), (242, 2638), (2655, 113), (2655, 2306), (2655, 
    248), (2655, 151), (2655, 58), (2655, 235), (2655, 202), (2655, 2567), 
    (2655, 2132), (2655, 2116), (2335, 2572), (2335, 5), (2335, 2006), 
    (2335, 295), (2335, 113), (2335, 252), (2335, 8), (2572, 2655), (2572, 
    2032), (2572, 326), (2572, 309), (2572, 2433), (324, 349), (324, 
    2084), (324, 2247), (324, 290), (324, 2433), (324, 276), (324, 2026), 
    (324, 2572), (349, 2433), (349, 41), (349, 113), (349, 2426), (96, 
    193), (96, 57), (96, 2459), (96, 344), (96, 142), (96, 97), (193, 77), 
    (193, 2309), (193, 2006), (193, 2459), (193, 2050), (57, 254), (57, 
    58), (57, 142), (57, 245), (57, 2579), (254, 21), (254, 9), (254, 
    204), (254, 30), (254, 265), (254, 12), (254, 24), (254, 38), (344, 
    235), (344, 12), (344, 189), (344, 245), (344, 8), (344, 2), (344, 
    145), (235, 2426), (235, 2032), (235, 249), (235, 218), (235, 202), 
    (2579, 2247), (2579, 2429), (2579, 96), (2579, 245), (2579, 238), 
    (2579, 2633), (2579, 228), (2247, 349), (2247, 290), (2247, 295), 
    (2247, 2572), (333, 328), (333, 251), (333, 2433), (333, 238), (333, 
    8), (333, 245), (333, 344), (333, 145), (333, 2), (2567, 249), (2567, 
    2426), (2567, 202), (2567, 248), (2567, 58), (2567, 235), (194, 87), 
    (194, 2032), (194, 2649), (194, 275), (194, 164), (194, 127), (194, 
    2294), (194, 213), (194, 77), (194, 84), (194, 120), (87, 25), (87, 
    153), (87, 252), (87, 2439), (87, 183), (87, 228), (87, 2426), (87, 
    103), (251, 2433), (251, 2636), (251, 277), (251, 201), (251, 66), 
    (251, 2306), (251, 2305), (251, 239), (2433, 309), (2433, 326), (2433, 
    2247), (183, 97), (183, 41), (183, 2509), (183, 258), (183, 152), 
    (183, 103), (97, 2116), (97, 58), (97, 258), (97, 221), (97, 154), 
    (97, 256), (97, 152), (204, 68), (204, 278), (204, 24), (204, 265), 
    (204, 38), (204, 25), (204, 9), (204, 2483), (68, 167), (68, 21), (68, 
    278), (68, 2005), (68, 36), (68, 2440), (68, 2751), (68, 328), (264, 
    2309), (264, 127), (264, 24), (264, 12), (264, 25), (264, 204), (264, 
    2483), (264, 38), (264, 265), (2309, 195), (2309, 2006), (2309, 189), 
    (2309, 2084), (98, 62), (98, 2229), (98, 2393), (98, 5), (98, 2429), 
    (98, 242), (98, 2226), (52, 99), (52, 97), (52, 103), (52, 59), (52, 
    2390), (52, 183), (52, 309), (52, 57), (99, 344), (99, 167), (99, 2), 
    (99, 57), (99, 145), (99, 333), (99, 8), (99, 5), (228, 59), (228, 
    2348), (228, 154), (228, 152), (228, 103), (228, 52), (228, 183), 
    (228, 97), (228, 2390), (228, 153), (59, 221), (59, 150), (59, 259), 
    (59, 153), (2116, 2226), (2116, 59), (2116, 2567), (2116, 218), (2116, 
    2132), (2116, 235), (2116, 2655), (2116, 58), (167, 2638), (2306, 
    142), (2306, 201), (2306, 2641), (2306, 66), (2306, 197), (2306, 239), 
    (2306, 277), (2306, 2305), (2306, 2628), (154, 238), (154, 2335), 
    (154, 52), (154, 349), (154, 103), (154, 183), (2032, 2433), (2032, 
    113), (2390, 2572), (2390, 259), (2390, 258), (2390, 59), (6, 2117), 
    (6, 2348), (6, 309), (6, 2433), (6, 2032), (6, 290), (6, 326), (6, 
    2572), (6, 295), (276, 87), (276, 256), (276, 295), (276, 2026), (276, 
    290), (276, 2247), (2005, 38), (2005, 2440), (2005, 2426), (2005, 
    2439), (2005, 349), (2005, 167), (2005, 36), (2005, 21), (2426, 151), 
    (2426, 202), (2426, 218), (2426, 2116), (265, 275), (265, 36), (265, 
    25), (265, 24), (265, 9), (265, 12), (275, 166), (275, 77), (275, 
    2509), (275, 120), (275, 158), (25, 2439), (25, 12), (25, 24), (2439, 
    249), (2439, 328), (2439, 167), (2439, 2440), (2641, 248), (2641, 
    251), (2641, 277), (2641, 2305), (2641, 66), (2641, 201), (66, 2294), 
    (66, 195), (66, 277), (2294, 2440), (2294, 164), (2294, 77), (2294, 
    2509), (2294, 275), (2294, 135), (2006, 2084), (2006, 2459), (258, 
    295), (258, 59), (2305, 277), (2305, 248), (2305, 150), (2305, 66), 
    (2305, 197), (5, 290), (5, 2393), (5, 2429), (5, 249), (5, 2348), 
    (2649, 113), (2649, 2117), (2649, 2459), (2649, 2309), (2649, 2199), 
    (2649, 2050), (2649, 195), (2229, 166), (2229, 2429), (2229, 2348), 
    (309, 2199), (309, 276), (309, 2032), (309, 290), (309, 326), (2199, 
    9), (2199, 113), (2199, 2711), (2199, 2050), (2199, 2006), (2199, 
    2309), (2199, 2117), (2459, 2199), (2459, 2711), (24, 87), (24, 9), 
    (2, 23), (2, 142), (2, 245), (2, 98), (23, 2711), (23, 2751), (23, 
    2439), (23, 2440), (23, 36), (23, 62), (9, 264), (9, 38), (290, 158), 
    (290, 2050), (290, 256), (290, 295), (290, 2026), (239, 326), (239, 
    66), (239, 2305), (239, 2641), (239, 201), (278, 23), (278, 167), 
    (278, 21), (278, 62), (278, 2439), (278, 2440), (278, 2751), (278, 68),
]

Answer 1

The graph size is challenging for finding the largest cycle.

A first observation was that a few vertices only have incoming edges, or only outgoing edges, and so they could never be part of a cycle. So I decided to eliminate these from the graph in a first phase in the algorithm: this can have a cascading effect so that other nodes also become isolated in that way.

It turned out 9 vertices and 79 edges could be removed in that first phase.

Then I made several attempts to find (long) cycles

• Using networkx
• Using DFS, repeatedly extending one path
• Using DFS, repeatedly selecting edges and see if chains join together...
• Using different heuristic functions for deciding which edge to add to the selection
• Translating it to a SAT problem and have a SAT solver work on it

This looked dim: running for an hour or so did not yield conclusive results.

After playing more with some heuristics, the DFS approach eventually gave me a cycle for all nodes (those not removed in the first phase), i.e. a Hamiltonian cycle on the cleaned graph. It didn't feel right to go for the heuristic that by trial and error made it work, so then I thought of applying randomness in the DFS approach, and to automatically abort and retry when some time slice expired. A bit based on Monte Carlo sampling.

This gave satisfying results: although the time needed can vary between one second or several minutes, it would really be bad luck if it took more than 5 minutes to find a Hamiltonian cycle in this graph.

So here is the code that I eventually ended up with. Granted, it doesn't find the largest cycle when there would not have been a Hamiltonian cycle, as the below algorithm cannot exclude that a still larger cycle than found would exist.

Implementation

Here is the Python code:

import random
import time

class Edge:
    def __init__(self, *nodes):
        self.nodes = tuple(nodes)
        self.active = False  # Means it is not really connecting the vertices yet 
        self.chosen = False  # Means it has not yet been selected as part of a cycle attempt
        self.activate()

    def activate(self):  # Make edge really part of the graph
        if self.active:
            raise ValueError("attempting to activate an edge that is already active")
        self.active = True
        self.nodes[0].neighbors[1].append(self)
        self.nodes[1].neighbors[0].append(self)

    def deactivate(self):  # Temporarily remove the edge from the graph
        if not self.active:
            raise ValueError("attempting to deactivate an edge that is not active")
        if self.chosen:
            return []
        self.active = False
        self.nodes[0].neighbors[1].remove(self)
        self.nodes[1].neighbors[0].remove(self)
        removed_edges = [self]
        removed_edges.extend(self.nodes[0].isolate_when_leaf())
        removed_edges.extend(self.nodes[1].isolate_when_leaf())
        return removed_edges  # This is like an undo log so this action can be undone later

    def choose(self):  # Choose this edge as part of our cycle attempt
        if self.chosen:
            raise ValueError("attempting to choose an edge that is already chosen")
        self.chosen = True
        self.deactivated_edges = []
        # Other, alternative edges can no longer be part of the cycle attempt:
        #   temporarily remove them from the graph
        for side, node in enumerate(self.nodes):
            for edge in list(node.neighbors[1-side]):
                if edge != self and edge.active:
                    deactivated = edge.deactivate()
                    if not deactivated:
                        return False
                    self.deactivated_edges.extend(deactivated)
        return True
    
    def unchoose(self):  # Undo the earlier choose action
        if not self.chosen:
            raise ValueError("attempting to unchoose an edge that is not chosen")
        self.chosen = False
        for edge in self.deactivated_edges:
            edge.activate()
        self.deactivated_edges = []

    def get_cycle(self):  # If this edge is on a cycle, return it
        edge = self
        cycle = [self.nodes[0].label]
        while True:
            edges = edge.nodes[1].neighbors[1]
            if not edges:
                return cycle[:1] # No cycle, but can never become one
            edge = edges[0]
            if not edge.chosen:
                return []  # It's not a cycle
            if edge == self:
                return cycle  # It's a cycle
            cycle.append(edge.nodes[0].label)
    
    def __repr__(self):
        return repr(self.nodes)


class Node:
    def __init__(self, label):
        self.label = label
        self.neighbors = ([], [])

    def __repr__(self):
        return f"{self.label}({len(self.neighbors[0])},{len(self.neighbors[1])})"

    def isolate_when_leaf(self):  # Remove edges around this vertex when it only has outgoing or only incoming
        if (not self.neighbors[0]) == (not self.neighbors[1]):
            return []  # Not a leaf, or already detached
        removed_edges = []
        for edges in list(self.neighbors):
            if edges and edges[0].chosen:
                return []  # Don't isolate this node. We need to rollback
            for edge in list(edges):
                if edge.active:
                    removed_edges.extend(edge.deactivate())
        return removed_edges


class Graph:
    def __init__(self, edges):
        self.nodes = [
            Node(label)
            for label in {label for edge in edges for label in edge}
        ]
        label_to_node = {node.label: node for node in self.nodes}
        self.edges = [
            Edge(label_to_node[a], label_to_node[b])
            for a, b in edges
        ] 

    def remove_leaves(self):
        removed_edges = []
        for node in self.nodes:
            removed_edges.extend(node.isolate_when_leaf())
        node_count = len(self.nodes)
        self.nodes = [node for node in self.nodes if node.neighbors[0]]
        print(f"Removed {node_count - len(self.nodes)} nodes and {len(removed_edges)} edges")

        
    def hamiltoncycle(self):
        print(f"Start search on a graph with {len(self.nodes)} nodes")
        longest_cycle = []
        deadline = time.time()
        
        def recur(num_edges):
            nonlocal longest_cycle
            # Get list of nodes that still have an incoming and outgoing edge and are not  
            #  joining two already selected edges. 
            nodes = [
                node
                for node in self.nodes
                if node.neighbors[0] and node.neighbors[1] and not (
                        node.neighbors[0][0].chosen and node.neighbors[1][0].chosen)
            ]
            # Select one of those nodes that has least of freedom (either incoming, or outgoing)
            *_, node, side = min((
                (len(node.neighbors[side]), len(node.neighbors[1-side]), i, node, side)
                for i, node in enumerate(nodes) for side, edges in enumerate(node.neighbors)
                if not edges[0].chosen
            ))
            # We have to select one of the edges from the selected node and side (either outgoing/incoming):
            #    Try them in a random order until time slice expires (kinda Monte Carlo). 
            edges = list(node.neighbors[side])
            random.shuffle(edges)
            for edge in edges:
                if edge.choose():
                    cycle = edge.get_cycle()
                    if cycle:
                        if len(cycle) > len(longest_cycle):  # improvement
                            print(f"Found a cycle with {len(cycle)} vertices...")
                            longest_cycle = cycle
                            if len(cycle) == len(self.nodes):
                                return True  # Hamilton cycle found!
                    else:  # Not a cycle yet: add more edges through recursion
                        if recur(num_edges + 1):
                            return True
                edge.unchoose()
                if time.time() > deadline:
                    break

        while len(longest_cycle) < len(self.nodes):
            print("Start from scratch")
            deadline += 10  # Allow 10 seconds for a depth-first search
            longest_cycle = []  # Yes, we really throw away the best result so far ;-)
            recur(0)
        return longest_cycle


edges = [  ... your input comes here ... ]
# Create the data structure
graph = Graph(edges)
# Remove vertices that only have incoming edges or only outgoing edges: 
#   these can never be part of a cycle. Apply this with cascading effect:
graph.remove_leaves()
# Apply main algorithm:
cycle = graph.hamiltoncycle()
# Report the solution:
print(f"Found this cycle of size {len(cycle)}:")
print(cycle)
# Verify the solution:
for edge in zip(cycle, cycle[1:] + [cycle[0]]):
    if edge not in edges:
        print(f"Cycle has an edge that doesn't exist in the graph: {edge}")
        exit(1)
if len(set(cycle)) < len(cycle):
    print("Cycle has duplicates")
    exit(1)
print("Cycle was verified and found OK")

Because of the random nature of this algorithm, the output is different in each run. Here is one output:

Removed 9 nodes and 79 edges
Start search on a graph with 124 nodes
Start from scratch
Found a cycle with 3 vertices...
Found a cycle with 7 vertices...
Found a cycle with 18 vertices...
Found a cycle with 59 vertices...
Found a cycle with 86 vertices...
Start from scratch
Found a cycle with 2 vertices...
Found a cycle with 3 vertices...
Found a cycle with 4 vertices...
Found a cycle with 7 vertices...
Found a cycle with 11 vertices...
Found a cycle with 22 vertices...
Found a cycle with 55 vertices...
Found a cycle with 56 vertices...
Found a cycle with 124 vertices...
Found this cycle of size 124:
[290, 295, 324, 276, 256, 2026, 2653, 6, 2572, 2655, 2306, 2628, 197, 66, 277, 201, 2305, 150, 258, 59, 153, 221, 183, 97, 2116, 2132, 2567, 202, 2459, 2711, 2117, 2006, 2084, 2649, 195, 2050, 2309, 189, 193, 77, 158, 2294, 2509, 135, 164, 84, 127, 356, 2751, 328, 41, 278, 23, 36, 62, 2440, 166, 167, 2638, 68, 2005, 21, 2439, 249, 2226, 242, 309, 2199, 9, 264, 204, 2483, 265, 275, 120, 2429, 2247, 349, 2426, 151, 252, 239, 2641, 248, 235, 2032, 2433, 326, 2229, 2348, 2393, 2390, 259, 103, 152, 52, 57, 2579, 2633, 142, 238, 96, 344, 12, 26, 254, 30, 38, 25, 24, 87, 228, 154, 2335, 8, 145, 2, 245, 99, 333, 251, 2636, 98, 5]
Cycle was verified and found OK

Here the result was found after two iterations of performing a DFS search from scratch. How many are needed will vary.

You can run it on repl.it