Fedaykin1200
Reputation: 23
Is finding the largest cycle on a directed graph with 133 Nodes and 737 Edges Computable?
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),
]
Upvotes: 2
Views: 125
Answers (1)
trincot
Reputation: 350300
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.
Upvotes: 3
Related Questions
- Why DFS and not BFS for finding cycle in graphs
- Finding a cycle in a DFS directed graph
- Directed Graph Structure in networkx with two edges between two nodes
- networkx python, directed/undirected graph, inconsistent nodes and edges?
- Finding consecutive edges linking certain nodes in graph
- Finding the longest cycle in a directed graph using DFS
- Finding a cycle in a directed graph using BFS or DFS
- maximum number of cycles in a directed graph with verices=|V| and edges =|E|
- Output the nodes in a cycle existing in a directed graph