If you have a graph represented as an adjacency list, how can you detect any odd length-ed
cycles in python?
Suppose you have a graph given as input:
A = {
1: [2, 4],
2: [1, 5],
3: [4, 5],
4: [1, 3, 5],
5: [2, 3, 4],
6: []
}
V = {
1: <node>,
2: <node>,
3: <node>,
4: <node>,
5: <node>,
6: <node>
}
A
is a dictionary where the key is a number and the value is a list of numbers, so there is an edge between the key to all of it's values. V
is a dictionary which maps a number to the node instance.
How can you detect if there is an odd length-ed cycle?
From the input above, there actually is one which uses nodes 3, 4, 5
.
Basically how can I get the output to be 3 4 5
?
Thanks
The common way to find a loop in a graph is to use a depth-first search algorithm. In your very case, I would mark each vertex with numbers 1 and 2, so that all neighbouring vertices have different numbers. If once you find, that there are two vertices with same mark, that means you've found a loop of odd length.
Here is my brief implementation (I did not make use of V
dictionaty, assuming A
describes the graph without as is):
import sys
A = {
1: [2, 4],
2: [1, 5],
3: [4, 5],
4: [1, 3, 5],
5: [2, 3, 4],
6: []
}
num_vertices = len(A)
sys.setrecursionlimit(num_vertices + 2)
mark = [None] * (num_vertices + 1)
cur_path = []
def DFS(vertex, cur_mark = 1):
mark[vertex] = cur_mark
global cur_path
cur_path.append(vertex)
for neighbour in A[vertex]:
if not mark[neighbour]:
DFS(neighbour, 3 - cur_mark)
elif mark[neighbour] == cur_mark:
print 'Found a loop of odd length: ', cur_path[cur_path.index(neighbour):]
sys.exit(0)
cur_path = cur_path[:-1]
# Visit all connected components
for vertex in xrange(1, num_vertices + 1):
if not mark[vertex]:
DFS(vertex)
print 'Cycle of odd length not found'