Repository: networkx/networkx
Pull request: DOC: Add example for self loop multidigraph in contraction
Add an example to explain for multidigraphs while contracting nodes with self loops in the original graph.

An example to resolve https://github.com/networkx/networkx/issues/6739

@Diarmuid-ODonoghue do you think this accurately covers the case?

Problem statement:
contracted_nodes() duplicates edges
<!-- If you have a general question about NetworkX, please use the discussions tab to create a new discussion -->

<!--- Provide a general summary of the issue in the Title above -->

### Current Behavior
Under some circumstances `contracted_nodes()` duplicates edges within a graph. Primarily its self edges that seem to be the source of the problem.


<!--- Tell us what happens instead of the expected behavior -->
I was using `contracted_nodes()` to merge nodes in a graph, when I noticed a pathological case where one of the merge nodes was not in the graph. 
~~Surprisingly, the problem seems to arise only when the additional parameter `copy=False)` is used. In my minimal example at least, setting `copy=True)` generates different results,~~

### Expected Behavior

<!--- Tell us what should happen -->
I expected this to either leave the edge unchanged or possibly even delete the edge. The graph should only have 1 edge after merging - definitely not 2 edges!
~~I would also expect the same number of edges to result when `copy=False)` and `copy=True)` are used.~~

### Steps to Reproduce

<!--- Provide a minimal example that reproduces the bug -->
```
G1 = nx.MultiDiGraph()
G1.add_edge(1, 1)
nx.contracted_nodes(G1, 2, 1, self_loops=False, copy=False)
G1.number_of_edges() # returns 2 but should be 1
```
The problem seems to occur with `self_loops=False` and also with `self_loops=True`. 

### Environment

<!--- Please provide details about your local environment -->

Python version:
NetworkX version: 3.0. (I did a quick test and the problem seems to persist in v3.1).

### Additional context
Currently using Python 3.10 and the PyCharm editor.

<!--- Add any other context about the problem here, screenshots, etc. -->

Hints from issue discussion:
Yeah this one is tricky. It is a directed graph and when you add a self loop to a directed graph it kind of breaks some of the assumptions. Like in the following example it will duplicate the edge `(1, 1)` when we try to go through `out_edges` and `in_edges` of a directed graph.

``` python
In [1]: import networkx as nx

In [2]: G = nx.DiGraph()

In [3]: G.add_edge(1, 1)

In [4]: G.out_edges()
Out[4]: OutEdgeView([(1, 1)])

In [5]: G.in_edges()
Out[5]: InEdgeView([(1, 1)])

In [6]: G.number_of_edges()
Out[6]: 1
```

I'm not sure what should be the right answer here. @dschult maybe?

PS: this will break even for `copy=True`. 
``` python
>>> nx.contracted_nodes(G1, 2, 1, copy=True).number_of_edges()
2
```
The self-loops argument refers to whether self-loops should be added when two connected nodes are contracted (see the docs for that parameter). It does not relate to self-loops in the original graph.

The return value with `copy=True` and `copy=False` should match. If they don't, that's definitely a bug.

The doubling of self-loops from the original graph is a "feature" or a "bug" depending on how you look at it. The edge interacts with the node in 2 ways: incoming and outgoing.  So, the new graph shows both of those interactions and thus two edges. If you want to track which is which you will need a MultiDiGraph and you'll need to look at the keys of the resulting edges. That is a "feature", not a "bug".  But if you don't want both of these edges, then you'll need to either remove one (or both) of the resulting self-loop edges, or you could use a DiGraph instead of a MultiDiGraph.  That's the extra work required ("bug"-like behavior) for people who don't want to track both in and out directions of self-loops on a contracted node. 

The reported "bug" is, in my view, a "feature" for some users, even though it requires clean up for those users who don't want the extra information. 

If there is a difference between `copy=True` and `copy=False` then we will need to fix that. A simple example would help a lot.


 
Example G1 shows edge duplication when `copy=False`, but G2 with `copy=True `seems to work correctly.
```
G1 = nx.MultiDiGraph()
G1.add_edge(1, 1)
nx.contracted_nodes(G1, 2, 1, self_loops=False, copy=False)
count1 = G1.number_of_edges()  # 2 edges
lis1 = list(G1.edges(data=True))  # [(2, 2, {}), (2, 2, {})]  # ERROR Edge Duplication

G2 = nx.MultiDiGraph()
G2.add_edge(1, 1)
nx.contracted_nodes(G2, 2, 1, self_loops=False, copy=True)
count2 = G2.number_of_edges()  # 1 edge
lis2 = list(G2.edges(data=True))  # [(1, 1, {})]    # correct behaviour
```
The error appears to grow linearly so if G1 has 3 edges between nodes (1,1), then `nx.contracted_nodes(G1, 2, 1, self_loops=False, copy=False)` has 6 edges. 
Labelling of nodes also seems to be inconsistent between `copy=False` and `copy=True` (`self_loops `seems to have no impact here). When `copy=False` the new nodes seem to have the expected label, but not when `copy=True`.
From the documentation: "_The right node v will be merged into the node u, so only u will appear in the returned graph_." I hope this detail helps :-) 
```
G1 = nx.MultiDiGraph()  # NetworkX Error on contracted_nodes()
G1.add_edge(1, 1)
G1.add_edge(1, 1)
nx.contracted_nodes(G1, 2, 1, self_loops=True, copy=False)
lis1 = list(G1.edges(data=True))  # [(2, 2, {}), (2, 2, {}), (2, 2, {}), (2, 2, {})]

G2 = nx.MultiDiGraph()
G2.add_edge(1, 1)
G2.add_edge(1, 1)
nx.contracted_nodes(G2, 2, 1, self_loops=True, copy=True)
count2 = G2.number_of_edges() # 1 edge
lis2 = list(G2.edges(data=True))  # [(1, 1, {}), (1, 1, {})]
```
When `copy=True` you should look at the return value of `nx.contracted_nodes` for the results. In those examples, you aren't capturing the return value, so it disappears.  Testing G2 will not show any changes because the changes are being done in the copy of G2, not in G2 itself.

Try something like this:
```python
    G2 = nx.MultiDiGraph() 
    G2.add_edge(1, 1)
    newG2 = nx.contracted_nodes(G2, 2, 1, self_loops=False, copy=True)
    count2 = newG2.number_of_edges()  
    lis2 = list(newG2.edges(data=True)) 
```

Thanks for your reply and you're right, so sorry for the confusion. Hopefully the following helps clarify the issue occurring with `MultiDiGraph()` only.
```
G3 = nx.MultiDiGraph() 
G3.add_edges_from([[1, 1], [1,1], [1,1]]) # 3 edges
nx.contracted_nodes(G3, 2, 1, self_loops=True, copy=False)
list_G3 = list(G3.edges(data=True))  # [(2, 2, {}), (2, 2, {}), (2, 2, {}), (2, 2, {}), (2, 2, {}), (2, 2, {})]
count_G3 = G3.number_of_edges() # 6
```

```
G3b = nx.MultiDiGraph() 
G3b.add_edges_from([[1, 1], [1,1], [1,1]])  # 3 edges
G3d = nx.contracted_nodes(G3b, 2, 1, self_loops=True, copy=True)
list_G3b = list(G3d.edges(data=True))  # [(2, 2, {}), (2, 2, {}), (2, 2, {}), (2, 2, {}), (2, 2, {}), (2, 2, {})]
count_3d = G3d.number_of_edges() # 6
```

I notice that the problem does Not occur if I change `MultiDiGraph()` to `MultiGraph()`. In that situation, the newly modified graphs contain 3 edges each. Thanks again.
Hmmm... I am getting 6 edges for both of these examples...  What version of networkx?
`nx.__version__`
NetworkX v3.1, but I discovered this when using v3.0. Upgrading to 3.1 didn't change the result. Thanks again. 
Can you check your results. You show getting 6 edges, but you only show 4 edges.  
I get 6 edges and they show 6 edges. (This is all for the list_G3b case).
I copied and pasted your code... but the results you show are as comments, so maybe they got copied over incorrectly?

Commit message: DOC: Add example for self loop multidigraph in contraction

Patch to review:
diff --git a/networkx/algorithms/minors/contraction.py b/networkx/algorithms/minors/contraction.py
index ff4df958d60..0acbe099fa6 100644
--- a/networkx/algorithms/minors/contraction.py
+++ b/networkx/algorithms/minors/contraction.py
@@ -497,6 +497,18 @@ def contracted_nodes(G, u, v, self_loops=True, copy=True):
     >>> list(H.edges())
     [(1, 1)]
 
+    In a ``MultiDiGraph`` with a self loop, the in and out edges will
+    be treated separately as edges, so while contracting a node which
+    has a self loop the contraction will add multiple edges:
+
+    >>> G = nx.MultiDiGraph([(1, 2), (2, 2)])
+    >>> H = nx.contracted_nodes(G, 1, 2)
+    >>> list(H.edges()) # edge 1->2, 2->2, 2->2 from the original Graph G
+    [(1, 1), (1, 1), (1, 1)]
+    >>> H = nx.contracted_nodes(G, 1, 2, self_loops=False)
+    >>> list(H.edges()) # edge 2->2, 2->2 from the original Graph G
+    [(1, 1), (1, 1)]
+
     See Also
     --------
     contracted_edge


Code review comments:
diff_hunk: @@ -497,6 +497,18 @@ def contracted_nodes(G, u, v, self_loops=True, copy=True):
     >>> list(H.edges())
     [(1, 1)]
 
+    In a ``MultiDiGraph`` with a self loop, the in and out edges will
+    be treated separately as edges, so while contracting a node which
+    has a self loop the contraction will add multiple edges:
+
+    >>> G = nx.MultiDiGraph([(1, 2), (2, 2)])
+    >>> H = nx.contracted_nodes(G, 1, 2)
+    >>> list(H.edges()) # edge 1->2, 2->2, 2->2 from the original Graph G
+    [(1, 1), (1, 1), (1, 1)]
+    >>> H = nx.contracted_nodes(G, 1, 2, self_loops=False)
+    >>> list(H.edges()) # edge 2->2, 2->2 from the original Graph G
path: networkx/algorithms/minors/contraction.py
text: @user1:
A very pedantic nit, but could help capture the nature of the in/out edge handling in the self-loop case:

```suggestion
    >>> list(H.edges())  # edge 1->2, 2->2, 2<-2 from the original Graph G
    [(1, 1), (1, 1), (1, 1)]
    >>> H = nx.contracted_nodes(G, 1, 2, self_loops=False)
    >>> list(H.edges())  # edge 2->2, 2<-2 from the original Graph G
```