2

Using NetworkX to determine cycles in a graph it seems something is incorrect in the resulting list:

Setup

import networkx as nx

egs = [
    [1, 2],
    [2, 3],
    [2, 4],
    [2, 5],
    [5, 6],
    [5, 7],
    [3, 8],
    [3, 7],
    [4, 9],
    [4, 8],
    [1, 9],
    [1, 6]];
g = nx.Graph(egs)
cyc = nx.cycle_basis(g)

Results:

>>> cyc
[[2, 5, 6, 1], [2, 3, 7, 5], [9, 4, 8, 3, 7, 5, 6, 1], [2, 4, 8, 3]]

[9, 4, 8, 3, 7, 5, 6, 1] is incorrect.

Am I missing a point or this is a bug in NetworkX?

Developer
  • 8,258
  • 8
  • 49
  • 58
  • It is not incorrect; you can traverse that path by following the (undirected) edges `[4, 9], [4, 8], [3, 8], [3, 7], [5, 7], [5, 6], [1, 6], [1, 9]`. Did you mean to use a directed graph? If so, use `ns.DiGraph(egs)` instead. – Arya McCarthy Apr 15 '17 at 17:49
  • @aryamccarthy I was expecting to have another cycle with four nodes not that one. According to manual '''...A basis for cycles of a network is a minimal collection of cycles such that any cycle in the network can be written as a sum of cycles in the basis...'''. However, the missing four node cycle cannot be made by sum of others. – Developer Apr 15 '17 at 17:54
  • Note that, ultimate use here is to find smallest cycles. Probably the term is cordless-cycles. BTW, graph is not directed. And I am so new in graph theory. – Developer Apr 15 '17 at 17:55
  • "Minimal" in this case means that we want as few cycles in the basis as necessary, not as short as possible. All cycles in the graph can be represented as some combination of these; the 4-cycle you're looking for can be formed from the 8-cycle and one of the 4-cycles. – Arya McCarthy Apr 15 '17 at 17:59
  • Perhaps this will help. http://stackoverflow.com/questions/4022662/find-all-chordless-cycles-in-an-undirected-graph – Arya McCarthy Apr 15 '17 at 18:03
  • @aryamccarthy The link is helpful. I had read it already. Since `NetworkX` is so powerful and comprehensive package I said maybe there is already a method there for the purpose mentioned. If there was nothing in the `NetworkX` that can find chordless cycles then I will go to translate the provided C code in the link you provided. This question is of my attempts. – Developer Apr 15 '17 at 18:52

0 Answers0