My input is a graph G, written as an adjacency list (each row of G starts with a vertex and all further values are the vertices adjacent to it). There are 200 vertices in total.
I'm trying to contract the graph randomly, until only two vertices are left (part of the Karger algorithm).
My issue is that after several iterations, v2's index can't be found in G. It appears that my code merging v2 into v1 doesn't work, as the same vertex is picked multiple times as v2, but I've no idea why.
removed = []
n = len(G) # number of vertices in G
while n > 2:
# Randomly choosing two vertices (and their index)
iv1 = random.randint(0, n - 1)
v1 = G[iv1][0]
v2 = random.choice(G[iv1][1:])
iv2 = None
for index, sublist in enumerate(G):
if sublist[0] is v2:
iv2 = index
# Debug code
removed.append(v2)
if iv2 is None:
print("===")
print("removed=", removed)
print("len set=", len(set(removed)), " len list=", len(removed))
print("G[iv1]=", G[iv1])
print("v1=", v1, " iv1=", iv1, " v2=", v2, " iv2=", iv2, "n=", n)
print("===")
break
# Graph Contraction (v1 and v2 merged, v1 becomes the merged vertex)
G[iv2].remove(v1) # Removing self-loops
G[iv1] += G[iv2][1:] # Vertices adjacent to v2 now adjacent to v1 (1/2)
G[iv1].remove(v2) # Removing self-loops
del G[iv2]
n -= 1
for i in range(n):
if G[i][0] is not v1:
G[i] = [v1 if vert is v2 else vert for vert in G[i]] # (2/2)
return len(G[0])
Here's an output example :
===
removed= [91, 98, 173, 23, 169, 179, 85, 54, 89, 110, 180, 2, 37, 17, 73, 43, 77, 34, 66, 19, 51, 178, 61, 99, 26, 52, 162, 111, 22, 149, 57, 118, 120, 30, 4, 28, 5, 27, 147, 188, 75, 136, 32, 40, 156, 145, 70, 138, 36, 12, 41, 140, 55, 152, 105, 60, 81, 64, 142, 45, 7, 148, 164, 49, 183, 165, 78, 74, 158, 160, 24, 146, 141, 182, 97, 116, 86, 96, 177, 186, 65, 135, 76, 9, 108, 3, 88, 151, 115, 42, 167, 185, 8, 190, 189, 175, 194, 184, 153, 196, 126, 195, 197, 107, 58, 6, 104, 117, 56, 199, 82, 168, 130, 29, 87, 121, 109, 90, 18, 132, 163, 198, 125, 13, 21, 154, 103, 72, 174, 187, 171, 80, 161, 191, 150, 137, 106, 79, 192, 1, 50, 155, 159, 35, 172, 176, 139, 20, 63, 38, 84, 119, 69, 94, 68, 193, 10, 95, 130]
len set= 158 len list= 159
G[iv1]= [123, 92, 92, 92, 129, 92, 11, 92, 92, 92, 92, 33, 47, 92, 92, 129, 92, 92, 92, 92, 69, 69, 33, 92, 129, 13, 128, 134, 92, 69, 92, 134, 92, 13, 114, 47, 13, 13, 128, 44, 134, 33, 123, 44, 181, 69, 33, 92, 16, 69, 134, 33, 157, 44, 83, 47, 181, 33, 92, 44, 92, 92, 181, 134, 129, 170, 92, 47, 129, 47, 44, 16, 181, 92, 44, 134, 157, 92, 11, 33, 181, 33, 92, 48, 92, 33, 13, 134, 130, 47, 92, 69, 92, 92, 134, 134, 92, 47, 123, 69, 92, 129, 130, 92, 114, 69, 69, 92, 44, 129, 157, 123, 92, 44, 134, 13, 11, 47, 13, 47, 92, 181, 134, 123, 47, 128, 92, 181, 92, 44, 48, 123, 134, 69, 33, 92, 129, 33, 123, 16, 130, 33, 92, 44, 92, 13, 44, 92, 157, 129, 114, 181, 47, 69, 92, 92]
v1= 123 iv1= 27 v2= 130 iv2= None n= 42
===