digraph_union fails if merge_edges is set to true

[georgios-ts]

Information

• retworkx version: main
• Python version: Any
• Rust version: Any
• Operating system: Any

What is the current behavior?

If merge_edges arg is set to True, digraph_union returns wrong output. This happens in many cases (e.g graphs with node holes, mismatch edge weights) and this means we need to rework the logic of the function.

What is the expected behavior?

Fix this.

Steps to reproduce the problem

An example where an edge is deleted when it shouldn't since edge weights don't match:

import retworkx as rx

first = rx.PyDiGraph()
nodes = first.add_nodes_from([0, 1])
first.add_edges_from([
   (nodes[0], nodes[1], 'a')
])

second = rx.PyDiGraph()
nodes = second.add_nodes_from([0, 1])
second.add_edges_from([
    (nodes[0], nodes[1], 'b')
])

final = rx.digraph_union(first, second, 
                         merge_nodes=True,
                         merge_edges=True
)
print(final.weighted_edge_list())
---
WeightedEdgeList[(0, 1, a)]

An example with node index hole where an edge is not deleted but it should be removed.

import retworkx as rx

first = rx.PyDiGraph()
nodes = first.add_nodes_from([0, 1])
first.add_edges_from([
   (nodes[0], nodes[1], 'a')
])

second = rx.PyDiGraph()
dummy = second.add_node('dummy')
nodes = second.add_nodes_from([0, 1])
second.add_edges_from([
    (nodes[0], nodes[1], 'a')
])
second.remove_node(dummy)

final = rx.digraph_union(first, second, 
                         merge_nodes=True,
                         merge_edges=True
)
print(final.weighted_edge_list())
---
WeightedEdgeList[(0, 1, a), (0, 1, a)]

[georgios-ts]

Oh, actually i'm a bit confused now. I was ready to push a fix for this but then i realized i am not sure what's the expected output for this function. I was under the impression that merge_edges=True makes sense only if you set merge_nodes=True which in this case means "if two nodes of the second graph are connected by an edge and got merged into nodes of the first graph, do not add an extra edge if the last nodes have an edge with equal weight data". But we have a test case where this assumption does not hold: https://github.com/Qiskit/retworkx/blob/main/tests/digraph/test_union.py#L34

@mtreinish Any input on this?

[mtreinish]

Yeah, I'm not sure exactly what the intent there is, based on that test it looks like it combines the edges if they're between nodes with the same weights and they have the same edge weight. Which seems a bit unexpected, like if the nodes aren't combined how do we know which edge to keep (just the first graph's)?