compose() erases some MultiGraph edges

[clbarnes]

If a user wants to compose two multigraphs, it is very likely that they want to use all of the edges present in both. In MultiGraphs, edges which share the same (source, target) pair are not the same. Currently, edges which share the same (source, target, key) tuple are treated the same: as keys are assigned in insertion order by default, rather than having anything to do with the data, the end user just sees that an arbitrary few of their edges have gone missing.

import networkx as nx

a, b = nx.MultiGraph(), nx.MultiGraph()
a.add_path([1,2])
b.add_path([1,2])

nx.compose(a,b).number_of_edges() == a.number_of_edges() + b.number_of_edges()
>>> False

The documentation states that the edge sets are unioned. If this edge set is hashed by (source, target) pair, then the function cannot be advertised as applicable to MultiGraphs, because it collapses all multiedges. If the edge set is hashed by (source, target, key), as it is currently, then there is unexpected and possibly arbitrary behaviour which is not well documented. The edge set should be hashed by a UUID for MultiGraphs (i.e. all edges are distinct), in order to reflect how these classes are actually going to be used.

[dschult]

I can imagine users being confused by this if they use MultiGraphs without setting keys (which many don't). On the other hand, changing it as you suggest could be confusing to users who do pay attention to the edge keys. At the very least a note should be included in the docs.

Perhaps there should be an argument to describe how to treat the edge keys.