find_cycle can't re-find cycle if an edge is removed and re-added?

[Daniel Margul]

Hi all,

I am trying to detect cycles, temporarily remove edges from them, and then add the removed edges back.  Strangely, I am finding that if I perform the following sequence, the cycle that is originally found cannot be found again:

 - Find cycle: found (x --> y), (y --> x)

 - Get edge_data for first edge, to save

 - Remove edge for which edge_data was saved

 - Add edge back, including all saved edge_data

 - Look for a cycle: cannot find (x --> y), (y --> x)

    - Check edge_data for (x --> y) and (y --> x) : these edges still exist

Is there something I should know about add_edge, remove_edge, find_cycle, or DiGraph/edge/node objects that would shed some light?

Best,

Daniel

[Dan Schult]

Perhaps you should open an Issue at https://github.com/networkx/networkx/issues

Especially if you can reproduce this on a fairly small Graph.

It is hard to tell from your description what went wrong -- mostly because using words describes what you think is happening and the code may not match.  When I implement what I think you describe on a DiGraph I am able to find the cycle.

```

>>> import networkx as nx

>>> DG = nx.DiGraph([(1, 6), (6, 4), (4, 5), (5, 9), (9, 3), (3, 8), (8, 1)])

>>> nx.find_cycle(DG)

[(1, 6), (6, 4), (4, 5), (5, 9), (9, 3), (3, 8), (8, 1)]

>>> DG.remove_edge(9, 3)

>>> DG.add_edge(9, 3)

>>> nx.find_cycle(DG)

[(1, 6), (6, 4), (4, 5), (5, 9), (9, 3), (3, 8), (8, 1)]

```

[Daniel Margul]

You make a great point; it was not incredibly useful to share a description without a reproduction.  Below is an example with 200 nodes.

import networkx as nx

# Generate large graph and  look for closest cycle to source node '1'
graph = nx.generators.random_graphs.erdos_renyi_graph(200, 0.01, seed=1, directed=True)
test = nx.find_cycle(graph, source=1)
print(test)

# Confirm the same cycle is found first on same graph with same source node
test = nx.find_cycle(graph, source=1)
print(test)

# Remove & re-add the first edge from the cycle that was found
graph.remove_edge(test[0][0], test[0][1])
graph.add_edge(test[0][0], test[0][1])

# Look for closest cycle to source node '1'
test = nx.find_cycle(graph, source=1)
print(test)

output:

[(11, 0), (0, 14), (14, 30), (30, 77), (77, 132), (132, 44), (44, 6), (6, 48), (48, 32), (32, 71), (71, 11)]

[(11, 0), (0, 14), (14, 30), (30, 77), (77, 132), (132, 44), (44, 6), (6, 48), (48, 32), (32, 71), (71, 11)]

[(39, 54), (54, 2), (2, 67), (67, 104), (104, 12), (12, 85), (85, 107), (107, 11), (11, 184), (184, 50), (50, 39)]

[Dan Schult]

That is helpful ---

Indeed, it is not that the old cycle is *not* found.  It is that *a different* cycle is found.

The `nx.find_cycles` function only ensures that a cycle will be found. Which cycle depends

on the data structure ordering of adjacencies. We use dicts for our data structure.

If you remove an entry from a dict and then replace it, the entry will become the last entry

iterated over.  So the adjacency order of the graph changes when you delete and add an edge.

That's what is causing a different cycle to be reported. You can check that both cycles are there before and after the changes.

```

dd = {i:i for i in range(3)}

print(dd)

del d[1]

d[1]=1

print(dd)

```

There is perhaps a workaround.  Instead of removing and adding the edge back, you can use a `subgraph_view` to hide the edge and the original graph is not changed.  The `subgraph_view` is readonly and fast to create, but slow to report because it has to check each edge to see if it is hidden or not. So it depends what you intend to do with the smaller graph as to whether this is better than copying the graph and deleting an edge.

```

SG = nx.subgraph_view(G, filter_edge=lambda u,v: (u,v) == test[0])

assert not SG.has_edge(*test[0])

```

[Daniel Margul]

Ah!  I had believed my cycle was not found because I iterated over find_cycle() results and broke the loop if the source node is not in it.  But apparently I may need cycle #6001 after rejecting the first 6000.

I really appreciate the workarounds, thank you. 

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/CA%2BXMcTNtJz4DiKze1EkBTkDX1hwZ-AimN3aBTeJBOmD-uMk6hg%40mail.gmail.com.

[Daniel Margul]

Hi again. When you say the subgraph_view is "slow to report," does that mean that a function like find_cycle(filtered_subgraph) will run more slowly than find_cycle(original_graph)? 

[Dan Schult]

Only *very* slightly. Try it on a reasonably sized graph like the example you posted. 

In IPython or JuPyter you can time it with `%timeit nx.find_cycle(G)`

For more in depth timing you can use the `timeit` built-in python library.

I forget if `find_cycles` checks each edge once or multiple times.

Remember that the other obvious option is copying the graph, removing the edge and computing that.

Copying takes time too -- often more time that using the `subgraph_view`.  But "your mileage may vary".

:)