Richard Rubalcava - 2 months ago 30

Python Question

Code:

`def bipartite(G):`

open_list = [1]

colors = {}

color_counter = 0

# assign a color to the first node being visited

colors[1] = 0

while open_list:

# up the counter here so that all neighbors get the same color

color_counter += 1

# use first elem for bfs

current_neighbors = G[open_list[0]]

current_color = color_counter % 2

# prints used for debugging

print open_list

print "The current color is: %s" % (current_color,)

for neighbor in current_neighbors:

if neighbor not in colors:

open_list.append(neighbor)

colors[neighbor] = current_color

# print used for debugging

print "parent is: %s, child is: %s, %s's color is: %s" \

% (open_list[0], neighbor, neighbor, colors[neighbor])

# print used for debugging

else: print "parent is: %s, child is: %s, already colored: %s" \

% (open_list[0], neighbor, colors[neighbor])

open_list.pop(0)

# now, return array of values that has one of the two colors

zeros_array = []

ones_array = []

for key in colors.keys():

if colors[key] == 0:

zeros_array.append(key)

else:

ones_array.append(key)

if len(set(zeros_array) & set(ones_array)) == 0:

return zeros_array

else:

return None

Here's the graph I'm using:

`{1: {2: 1, 4: 1}, 2: {1: 1, 3: 1, 5: 1}, 3: {8: 1, 2: 1}, 4: {1: 1}, 5: {2: 1, 6: 1}, 6: {5: 1}, 8: {3: 1}}`

I drew it out and the graph can be visualized as a tree with 1 as the root, and branches off to nodes 2 and 4, where 4 is a leaf, but 2 keeps going. I'm using a color counter to color neighbors the same color (either 0 or 1). 2 and 4 are given the same color, then the algorithm correctly gives 3 and 5 the opposite color of their parent 2, but when returning one level up to check 4, the color counter is incremented, so by the time it gets to 8, 8 gets the wrong color.

I'm stuck at how to best fix this.

Answer

You should choose the color in depending on the your current vertex color, something like `colors[neighbor] = (colors[open_list[0]] + 1) % 2`

Also, `len(set(zeros_array) & set(ones_array)) == 0`

will always be `true`

, so you aren't checking is bipartite has gone well. You could check it in else branch of `if neighbor not in colors:`

: just assert that your neighbour has different color with current vertex.