forgi 2.0.0 documentation

Contents

Source code for forgi.utilities.graph

from __future__ import print_function

import networkx as nx


[docs]def shortest_cycle(G, v): ''' Calculate one of the shortest cycles which includes the node v. @param G: A networkx graph @param v: The node to include in the cycle ''' lengths = [] for n in G.neighbors(v): G.remove_edge(v, n) try: p = nx.shortest_path(G, v, n) l = nx.shortest_path_length(G, v, n) except nx.exception.NetworkXNoPath: G.add_edge(v, n) continue lengths += [(l, p)] G.add_edge(v, n) if len(lengths) > 0: return min(lengths)[1] else: return []
if __name__ == '__main__': edges = [(1, 2), (2, 3), (2, 5), (1, 4), (4, 5), (1, 3)] G = nx.Graph() G.add_edges_from(edges) print(shortest_cycle(G, 1)) print(shortest_cycle(G, 3)) print(shortest_cycle(G, 4))

Contents