def find_cycle(graph):
if (isinstance(graph, graph_class)):<EOL><INDENT>directed = False<EOL><DEDENT>elif (isinstance(graph, digraph_class)):<EOL><INDENT>directed = True<EOL><DEDENT>else:<EOL><INDENT>raise InvalidGraphType<EOL><DEDENT>def find_cycle_to_ancestor(node, ancestor):<EOL><INDENT>"""<STR_LIT>"""<EOL>path = []<EOL>while (node != ancestor):<EOL><INDENT>if (node is None):<EOL><INDENT>return []<EOL><DEDENT>path.append(node)<EOL>node = spanning_tree[node]<EOL><DEDENT>path.append(node)<EOL>path.reverse()<EOL>return path<EOL><DEDENT>def dfs(node):<EOL><INDENT>"""<STR_LIT>"""<EOL>visited[node] = <NUM_LIT:1><EOL>for each in graph[node]:<EOL><INDENT>if (cycle):<EOL><INDENT>return<EOL><DEDENT>if (each not in visited):<EOL><INDENT>spanning_tree[each] = node<EOL>dfs(each)<EOL><DEDENT>else:<EOL><INDENT>if (directed or spanning_tree[node] != each):<EOL><INDENT>cycle.extend(find_cycle_to_ancestor(node, each))<EOL><DEDENT><DEDENT><DEDENT><DEDENT>recursionlimit = getrecursionlimit()<EOL>setrecursionlimit(max(len(graph.nodes())*<NUM_LIT:2>,recursionlimit))<EOL>visited = {}              <EOL>spanning_tree = {}        <EOL>cycle = []<EOL>for each in graph:<EOL><INDENT>if (each not in visited):<EOL><INDENT>spanning_tree[each] = None<EOL>dfs(each)<EOL>if (cycle):<EOL><INDENT>setrecursionlimit(recursionlimit)<EOL>return cycle<EOL><DEDENT><DEDENT><DEDENT>setrecursionlimit(recursionlimit)<EOL>return []<EOL>
Find a cycle in the given graph.

This function will return a list of nodes which form a cycle in the graph or an empty list if
no cycle exists.

@type graph: graph, digraph
@param graph: Graph.

@rtype: list
@return: List of nodes.