Last active
November 9, 2018 03:13
-
-
Save yingqiuz/422a600e12637717abd53fc8b51daacf to your computer and use it in GitHub Desktop.
find all cycles at length k
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # requires python3.6 or above | |
| # requires networkx, matplotlib | |
| import numpy as np | |
| import networkx as nx | |
| import matplotlib as plt | |
| def all_cycles_k_recursive(G, source, k, current_node, visited, cycle, allcycles): | |
| """ | |
| """ | |
| # mark current node as visited | |
| visited[current_node] = True | |
| cycle.append(current_node) | |
| if k == 1: | |
| # maximum length achieved | |
| if G[current_node][source] == 1: | |
| print(cycle) | |
| allcycles.append(cycle[:]) | |
| else: | |
| for item in np.nonzero(G[current_node])[0]: | |
| if visited[item] == False: | |
| all_cycles_k_recursive(G, source, k-1, item, visited, cycle, allcycles) | |
| visited[current_node] = False | |
| cycle.pop() # make the current node available | |
| def all_cycles_k(G, source, k): | |
| """ | |
| G: numpy adj array with element i,j == 1 if there's a connection from i to j (transpose of the conventional adj mat) | |
| source: source node, int number | |
| k: length of the cycles, int number | |
| """ | |
| allcycles = [] | |
| visited = [False] * np.max(G.shape) | |
| cycle = [] # current cycle | |
| #cycle.append(source) | |
| all_cycles_k_recursive(G, source, k-1, source, visited, cycle, allcycles) | |
| return allcycles |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment