algorithm to get cycle in graph?

Question

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

Answer 1

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'