Repository: networkx/networkx

Issue:
steiner_tree should accept MultiGraph
I'm using `steiner_tree` on a road network which may have multiple edges between nodes. 

It looks like `steiner_tree` will fail if passed a `MultiGraph`:
- as a next-to-last step, edges are generated as `(u, v)` tuples pairwise [here](https://github.com/networkx/networkx/blob/master/networkx/algorithms/approximation/steinertree.py#L87)
- before being passed to `G.edge_subgraph` which raises a `ValueError` from `nx.filter.show_multiedges`

This should reproduce the issue:

```python
import networkx as nx
import networkx.algorithms.approximation as nxa

def test_simple_steiner_tree():
    G = nx.Graph()
    G.add_weighted_edges_from([
        (1, 2, 1),
        (2, 3, 1),
        (3, 4, 1),
        (3, 5, 1)
    ])
    terminal_nodes = [2, 4, 5]
    expected_edges = [
        (2, 3),
        (3, 4),
        (3, 5)
    ]
    T = nxa.steiner_tree(G, terminal_nodes)
    assert list(T.edges) == expected_edges

def test_multi_steiner_tree():
    G = nx.MultiGraph()
    G.add_weighted_edges_from([
        (1, 2, 1),
        (2, 3, 1),
        (2, 3, 999),
        (3, 4, 1),
        (3, 5, 1)
    ])
    terminal_nodes = [2, 4, 5]
    expected_edges = [
        (2, 3, 0),
        (3, 4, 0),  # first edge has weight one
        (3, 5, 0)
    ]
    T = nxa.steiner_tree(G, terminal_nodes)

test_simple_steiner_tree()  # passes
test_multi_steiner_tree()  # throws ValueError 
```

The quick fix might be to add `@not_implemented_for('multigraph')`. 

For my current purposes, the following does the trick to handle the `MultiGraph` case:

```python
# get unique links pairwise (u, v)
links = set(chain.from_iterable(
    pairwise(d['path'])
    for u, v, d in mst_edges
))

# for each link in the chain
multi_edges = []
for u, v in links:    
    # consider each edge  between the pair of nodes,
    # keeping track of the one with the minimum weight
    # (there may be a better way - convenience functions/accessors?)
    num_edges = G.number_of_edges(u, v)
    min_k = 0
    min_weight = None
    for k in range(num_edges):
        curr_weight = G.edges[u, v, k][weight]
        if min_weight is None:
            min_weight = curr_weight
        elif curr_weight < min_weight:
            min_weight = curr_weight
            min_k = k
    multi_edges.append((u, v, min_k))

# create subgraph from multi edges - list of (u, v, k)
T = G.edge_subgraph(multi_edges)
```


Discussion:

Patch:
diff --git a/networkx/algorithms/approximation/steinertree.py b/networkx/algorithms/approximation/steinertree.py
index 7f91b63de..b1e248862 100644
--- a/networkx/algorithms/approximation/steinertree.py
+++ b/networkx/algorithms/approximation/steinertree.py
@@ -46,11 +46,23 @@ def metric_closure(G, weight="weight"):
     return M
 
 
-@not_implemented_for("multigraph")
 @not_implemented_for("directed")
 def steiner_tree(G, terminal_nodes, weight="weight"):
     """ Return an approximation to the minimum Steiner tree of a graph.
 
+    The minimum Steiner tree of `G` w.r.t a set of `terminal_nodes`
+    is a tree within `G` that spans those nodes and has minimum size
+    (sum of edge weights) among all such trees.
+
+    The minimum Steiner tree can be approximated by computing the minimum
+    spanning tree of the subgraph of the metric closure of *G* induced by the
+    terminal nodes, where the metric closure of *G* is the complete graph in
+    which each edge is weighted by the shortest path distance between the
+    nodes in *G* .
+    This algorithm produces a tree whose weight is within a (2 - (2 / t))
+    factor of the weight of the optimal Steiner tree where *t* is number of
+    terminal nodes.
+
     Parameters
     ----------
     G : NetworkX graph
@@ -67,24 +79,26 @@ def steiner_tree(G, terminal_nodes, weight="weight"):
 
     Notes
     -----
-    Steiner tree can be approximated by computing the minimum spanning
-    tree of the subgraph of the metric closure of the graph induced by the
-    terminal nodes, where the metric closure of *G* is the complete graph in
-    which each edge is weighted by the shortest path distance between the
-    nodes in *G* .
-    This algorithm produces a tree whose weight is within a (2 - (2 / t))
-    factor of the weight of the optimal Steiner tree where *t* is number of
-    terminal nodes.
+    For multigraphs, the edge between two nodes with minimum weight is the
+    edge put into the Steiner tree.
 
+
+    References
+    ----------
+    .. [1] Steiner_tree_problem on Wikipedia.
+       https://en.wikipedia.org/wiki/Steiner_tree_problem
     """
-    # M is the subgraph of the metric closure induced by the terminal nodes of
-    # G.
+    # H is the subgraph induced by terminal_nodes in the metric closure M of G.
     M = metric_closure(G, weight=weight)
-    # Use the 'distance' attribute of each edge provided by the metric closure
-    # graph.
     H = M.subgraph(terminal_nodes)
+    # Use the 'distance' attribute of each edge provided by M.
     mst_edges = nx.minimum_spanning_edges(H, weight="distance", data=True)
     # Create an iterator over each edge in each shortest path; repeats are okay
     edges = chain.from_iterable(pairwise(d["path"]) for u, v, d in mst_edges)
+    # For multigraph we should add the minimal weight edge keys
+    if G.is_multigraph():
+        edges = (
+            (u, v, min(G[u][v], key=lambda k: G[u][v][k][weight])) for u, v in edges
+        )
     T = G.edge_subgraph(edges)
     return T
diff --git a/networkx/drawing/nx_agraph.py b/networkx/drawing/nx_agraph.py
index 6932ac6ed..4589b0d5d 100644
--- a/networkx/drawing/nx_agraph.py
+++ b/networkx/drawing/nx_agraph.py
@@ -38,8 +38,9 @@ def from_agraph(A, create_using=None):
     A : PyGraphviz AGraph
       A graph created with PyGraphviz
 
-    create_using : NetworkX graph constructor, optional (default=nx.Graph)
+    create_using : NetworkX graph constructor, optional (default=None)
        Graph type to create. If graph instance, then cleared before populated.
+       If `None`, then the appropriate Graph type is inferred from `A`.
 
     Examples
     --------
@@ -145,26 +146,26 @@ def to_agraph(N):
     # add nodes
     for n, nodedata in N.nodes(data=True):
         A.add_node(n)
-        if nodedata is not None:
-            a = A.get_node(n)
-            a.attr.update({k: str(v) for k, v in nodedata.items()})
+        # Add node data
+        a = A.get_node(n)
+        a.attr.update({k: str(v) for k, v in nodedata.items()})
 
     # loop over edges
     if N.is_multigraph():
         for u, v, key, edgedata in N.edges(data=True, keys=True):
             str_edgedata = {k: str(v) for k, v in edgedata.items() if k != "key"}
             A.add_edge(u, v, key=str(key))
-            if edgedata is not None:
-                a = A.get_edge(u, v)
-                a.attr.update(str_edgedata)
+            # Add edge data
+            a = A.get_edge(u, v)
+            a.attr.update(str_edgedata)
 
     else:
         for u, v, edgedata in N.edges(data=True):
             str_edgedata = {k: str(v) for k, v in edgedata.items()}
             A.add_edge(u, v)
-            if edgedata is not None:
-                a = A.get_edge(u, v)
-                a.attr.update(str_edgedata)
+            # Add edge data
+            a = A.get_edge(u, v)
+            a.attr.update(str_edgedata)
 
     return A
 
@@ -250,7 +251,9 @@ def pygraphviz_layout(G, prog="neato", root=None, args=""):
     args : string, optional
       Extra arguments to Graphviz layout program
 
-    Returns : dictionary
+    Returns
+    -------
+    node_pos : dict
       Dictionary of x, y, positions keyed by node.
 
     Examples
@@ -265,11 +268,11 @@ def pygraphviz_layout(G, prog="neato", root=None, args=""):
     representation and GraphViz could treat them as the same node.
     The layout may assign both nodes a single location. See Issue #1568
     If this occurs in your case, consider relabeling the nodes just
-    for the layout computation using something similar to:
+    for the layout computation using something similar to::
 
-        H = nx.convert_node_labels_to_integers(G, label_attribute='node_label')
-        H_layout = nx.nx_agraph.pygraphviz_layout(G, prog='dot')
-        G_layout = {H.nodes[n]['node_label']: p for n, p in H_layout.items()}
+        >>> H = nx.convert_node_labels_to_integers(G, label_attribute='node_label')
+        >>> H_layout = nx.nx_agraph.pygraphviz_layout(G, prog='dot')
+        >>> G_layout = {H.nodes[n]['node_label']: p for n, p in H_layout.items()}
 
     """
     try:
diff --git a/networkx/relabel.py b/networkx/relabel.py
index 737b5af3d..26f50d241 100644
--- a/networkx/relabel.py
+++ b/networkx/relabel.py
@@ -13,7 +13,7 @@ def relabel_nodes(G, mapping, copy=True):
 
     mapping : dictionary
        A dictionary with the old labels as keys and new labels as values.
-       A partial mapping is allowed.
+       A partial mapping is allowed. Mapping 2 nodes to a single node is allowed.
 
     copy : bool (optional, default=True)
        If True return a copy, or if False relabel the nodes in place.
@@ -64,6 +64,27 @@ def relabel_nodes(G, mapping, copy=True):
     >>> list(H)
     [0, 1, 4]
 
+    In a multigraph, relabeling two or more nodes to the same new node
+    will retain all edges, but may change the edge keys in the process:
+
+    >>> G = nx.MultiGraph()
+    >>> G.add_edge(0, 1, value="a")  # returns the key for this edge
+    0
+    >>> G.add_edge(0, 2, value="b")
+    0
+    >>> G.add_edge(0, 3, value="c")
+    0
+    >>> mapping = {1: 4, 2: 4, 3: 4}
+    >>> H = nx.relabel_nodes(G, mapping, copy=True)
+    >>> print(H[0])
+    {4: {0: {'value': 'a'}, 1: {'value': 'b'}, 2: {'value': 'c'}}}
+
+    This works for in-place relabeling too:
+
+    >>> G = nx.relabel_nodes(G, mapping, copy=False)
+    >>> print(G[0])
+    {4: {0: {'value': 'a'}, 1: {'value': 'b'}, 2: {'value': 'c'}}}
+
     Notes
     -----
     Only the nodes specified in the mapping will be relabeled.
@@ -77,6 +98,13 @@ def relabel_nodes(G, mapping, copy=True):
     graph is not possible in-place and an exception is raised.
     In that case, use copy=True.
 
+    If a relabel operation on a multigraph would cause two or more
+    edges to have the same source, target and key, the second edge must
+    be assigned a new key to retain all edges. The new key is set
+    to the lowest non-negative integer not already used as a key
+    for edges between these two nodes. Note that this means non-numeric
+    keys may be replaced by numeric keys.
+
     See Also
     --------
     convert_node_labels_to_integers
@@ -136,6 +164,15 @@ def _relabel_inplace(G, mapping):
                     (new if old == source else source, new, key, data)
                     for (source, _, key, data) in G.in_edges(old, data=True, keys=True)
                 ]
+            # Ensure new edges won't overwrite existing ones
+            seen = set()
+            for i, (source, target, key, data) in enumerate(new_edges):
+                if (target in G[source] and key in G[source][target]):
+                    new_key = 0 if not isinstance(key, (int, float)) else key
+                    while (new_key in G[source][target] or (target, new_key) in seen):
+                        new_key += 1
+                    new_edges[i] = (source, target, new_key, data)
+                    seen.add((target, new_key))
         else:
             new_edges = [
                 (new, new if old == target else target, data)
@@ -156,10 +193,25 @@ def _relabel_copy(G, mapping):
     H.add_nodes_from(mapping.get(n, n) for n in G)
     H._node.update((mapping.get(n, n), d.copy()) for n, d in G.nodes.items())
     if G.is_multigraph():
-        H.add_edges_from(
+        new_edges = [
             (mapping.get(n1, n1), mapping.get(n2, n2), k, d.copy())
             for (n1, n2, k, d) in G.edges(keys=True, data=True)
-        )
+        ]
+
+        # check for conflicting edge-keys
+        undirected = not G.is_directed()
+        seen_edges = set()
+        for i, (source, target, key, data) in enumerate(new_edges):
+            while (source, target, key) in seen_edges:
+                if not isinstance(key, (int, float)):
+                    key = 0
+                key += 1
+            seen_edges.add((source, target, key))
+            if undirected:
+                seen_edges.add((target, source, key))
+            new_edges[i] = (source, target, key, data)
+
+        H.add_edges_from(new_edges)
     else:
         H.add_edges_from(
             (mapping.get(n1, n1), mapping.get(n2, n2), d.copy())


Test patch:
diff --git a/networkx/algorithms/approximation/tests/test_steinertree.py b/networkx/algorithms/approximation/tests/test_steinertree.py
index 93b0af48f..7fe291927 100644
--- a/networkx/algorithms/approximation/tests/test_steinertree.py
+++ b/networkx/algorithms/approximation/tests/test_steinertree.py
@@ -63,22 +63,21 @@ class TestSteinerTree:
         assert_edges_equal(list(S.edges(data=True)), expected_steiner_tree)
 
     def test_multigraph_steiner_tree(self):
-        with pytest.raises(nx.NetworkXNotImplemented):
-            G = nx.MultiGraph()
-            G.add_edges_from(
-                [
-                    (1, 2, 0, {"weight": 1}),
-                    (2, 3, 0, {"weight": 999}),
-                    (2, 3, 1, {"weight": 1}),
-                    (3, 4, 0, {"weight": 1}),
-                    (3, 5, 0, {"weight": 1}),
-                ]
-            )
-            terminal_nodes = [2, 4, 5]
-            expected_edges = [
-                (2, 3, 1, {"weight": 1}),  # edge with key 1 has lower weight
+        G = nx.MultiGraph()
+        G.add_edges_from(
+            [
+                (1, 2, 0, {"weight": 1}),
+                (2, 3, 0, {"weight": 999}),
+                (2, 3, 1, {"weight": 1}),
                 (3, 4, 0, {"weight": 1}),
                 (3, 5, 0, {"weight": 1}),
             ]
-            # not implemented
-            T = steiner_tree(G, terminal_nodes)
+        )
+        terminal_nodes = [2, 4, 5]
+        expected_edges = [
+            (2, 3, 1, {"weight": 1}),  # edge with key 1 has lower weight
+            (3, 4, 0, {"weight": 1}),
+            (3, 5, 0, {"weight": 1}),
+        ]
+        T = steiner_tree(G, terminal_nodes)
+        assert_edges_equal(T.edges(data=True, keys=True), expected_edges)
diff --git a/networkx/drawing/tests/test_agraph.py b/networkx/drawing/tests/test_agraph.py
index b55e88763..8f1cae3ea 100644
--- a/networkx/drawing/tests/test_agraph.py
+++ b/networkx/drawing/tests/test_agraph.py
@@ -51,6 +51,27 @@ class TestAGraph:
         H = nx.nx_agraph.from_agraph(A)
         assert G.name == "test"
 
+    @pytest.mark.parametrize(
+        "graph_class", (nx.Graph, nx.DiGraph, nx.MultiGraph, nx.MultiDiGraph,)
+    )
+    def test_from_agraph_create_using(self, graph_class):
+        G = nx.path_graph(3)
+        A = nx.nx_agraph.to_agraph(G)
+        H = nx.nx_agraph.from_agraph(A, create_using=graph_class)
+        assert isinstance(H, graph_class)
+
+    def test_from_agraph_named_edges(self):
+        # Create an AGraph from an existing (non-multi) Graph
+        G = nx.Graph()
+        G.add_nodes_from([0, 1])
+        A = nx.nx_agraph.to_agraph(G)
+        # Add edge (+ name, given by key) to the AGraph
+        A.add_edge(0, 1, key="foo")
+        # Verify a.name roundtrips out to 'key' in from_agraph
+        H = nx.nx_agraph.from_agraph(A)
+        assert isinstance(H, nx.Graph)
+        assert ("0", "1", {"key": "foo"}) in H.edges(data=True)
+
     def test_undirected(self):
         self.agraph_checks(nx.Graph())
 
@@ -63,17 +84,68 @@ class TestAGraph:
     def test_multi_directed(self):
         self.agraph_checks(nx.MultiDiGraph())
 
+    def test_to_agraph_with_nodedata(self):
+        G = nx.Graph()
+        G.add_node(1, color="red")
+        A = nx.nx_agraph.to_agraph(G)
+        assert dict(A.nodes()[0].attr) == {"color": "red"}
+
+    @pytest.mark.parametrize("graph_class", (nx.Graph, nx.MultiGraph))
+    def test_to_agraph_with_edgedata(self, graph_class):
+        G = graph_class()
+        G.add_nodes_from([0, 1])
+        G.add_edge(0, 1, color="yellow")
+        A = nx.nx_agraph.to_agraph(G)
+        assert dict(A.edges()[0].attr) == {"color": "yellow"}
+
+    def test_view_pygraphviz_path(self, tmp_path):
+        G = nx.complete_graph(3)
+        input_path = str(tmp_path / "graph.png")
+        out_path, A = nx.nx_agraph.view_pygraphviz(G, path=input_path)
+        assert out_path == input_path
+        # Ensure file is not empty
+        with open(input_path, "rb") as fh:
+            data = fh.read()
+        assert len(data) > 0
+
+    def test_view_pygraphviz_file_suffix(self, tmp_path):
+        G = nx.complete_graph(3)
+        path, A = nx.nx_agraph.view_pygraphviz(G, suffix=1)
+        assert path[-6:] == "_1.png"
+
     def test_view_pygraphviz(self):
         G = nx.Graph()  # "An empty graph cannot be drawn."
         pytest.raises(nx.NetworkXException, nx.nx_agraph.view_pygraphviz, G)
         G = nx.barbell_graph(4, 6)
         nx.nx_agraph.view_pygraphviz(G)
 
-    def test_view_pygraphviz_edgelable(self):
+    def test_view_pygraphviz_edgelabel(self):
         G = nx.Graph()
         G.add_edge(1, 2, weight=7)
         G.add_edge(2, 3, weight=8)
-        nx.nx_agraph.view_pygraphviz(G, edgelabel="weight")
+        path, A = nx.nx_agraph.view_pygraphviz(G, edgelabel="weight")
+        for edge in A.edges():
+            assert edge.attr["weight"] in ("7", "8")
+
+    def test_view_pygraphviz_callable_edgelabel(self):
+        G = nx.complete_graph(3)
+
+        def foo_label(data):
+            return "foo"
+
+        path, A = nx.nx_agraph.view_pygraphviz(G, edgelabel=foo_label)
+        for edge in A.edges():
+            assert edge.attr["label"] == "foo"
+
+    def test_view_pygraphviz_multigraph_edgelabels(self):
+        G = nx.MultiGraph()
+        G.add_edge(0, 1, key=0, name="left_fork")
+        G.add_edge(0, 1, key=1, name="right_fork")
+        path, A = nx.nx_agraph.view_pygraphviz(G, edgelabel="name")
+        edges = A.edges()
+        assert len(edges) == 2
+        for edge in edges:
+            assert edge.attr["label"].strip() in ("left_fork", "right_fork")
 
     def test_graph_with_reserved_keywords(self):
         # test attribute/keyword clash case for #1582
@@ -86,7 +158,31 @@ class TestAGraph:
         G.edges[("A", "B")]["v"] = "keyword"
         A = nx.nx_agraph.to_agraph(G)
 
-    def test_round_trip(self):
+    def test_view_pygraphviz_no_added_attrs_to_input(self):
+        G = nx.complete_graph(2)
+        path, A = nx.nx_agraph.view_pygraphviz(G)
+        assert G.graph == {}
+
+    @pytest.mark.xfail(reason="known bug in clean_attrs")
+    def test_view_pygraphviz_leaves_input_graph_unmodified(self):
+        G = nx.complete_graph(2)
+        # Add entries to graph dict that to_agraph handles specially
+        G.graph["node"] = {"width": "0.80"}
+        G.graph["edge"] = {"fontsize": "14"}
+        path, A = nx.nx_agraph.view_pygraphviz(G)
+        assert G.graph == {"node": {"width": "0.80"}, "edge": {"fontsize": "14"}}
+
+    def test_graph_with_AGraph_attrs(self):
+        G = nx.complete_graph(2)
+        # Add entries to graph dict that to_agraph handles specially
+        G.graph["node"] = {"width": "0.80"}
+        G.graph["edge"] = {"fontsize": "14"}
+        path, A = nx.nx_agraph.view_pygraphviz(G)
+        # Ensure user-specified values are not lost
+        assert dict(A.node_attr)["width"] == "0.80"
+        assert dict(A.edge_attr)["fontsize"] == "14"
+
+    def test_round_trip_empty_graph(self):
         G = nx.Graph()
         A = nx.nx_agraph.to_agraph(G)
         H = nx.nx_agraph.from_agraph(A)
@@ -99,6 +195,32 @@ class TestAGraph:
         G.graph["edge"] = {}
         assert_graphs_equal(G, HH)
 
+    @pytest.mark.xfail(reason="integer->string node conversion in round trip")
+    def test_round_trip_integer_nodes(self):
+        G = nx.complete_graph(3)
+        A = nx.nx_agraph.to_agraph(G)
+        H = nx.nx_agraph.from_agraph(A)
+        assert_graphs_equal(G, H)
+
+    def test_graphviz_alias(self):
+        G = self.build_graph(nx.Graph())
+        pos_graphviz = nx.nx_agraph.graphviz_layout(G)
+        pos_pygraphviz = nx.nx_agraph.pygraphviz_layout(G)
+        assert pos_graphviz == pos_pygraphviz
+
+    @pytest.mark.parametrize("root", range(5))
+    def test_pygraphviz_layout_root(self, root):
+        # NOTE: test depends on layout prog being deterministic
+        G = nx.complete_graph(5)
+        A = nx.nx_agraph.to_agraph(G)
+        # Get layout with root arg is not None
+        pygv_layout = nx.nx_agraph.pygraphviz_layout(G, prog="circo", root=root)
+        # Equivalent layout directly on AGraph
+        A.layout(args=f"-Groot={root}", prog="circo")
+        # Parse AGraph layout
+        a1_pos = tuple(float(v) for v in dict(A.get_node("1").attr)["pos"].split(","))
+        assert pygv_layout[1] == a1_pos
+
     def test_2d_layout(self):
         G = nx.Graph()
         G = self.build_graph(G)
diff --git a/networkx/tests/test_relabel.py b/networkx/tests/test_relabel.py
index 9b8ad2998..909904bc9 100644
--- a/networkx/tests/test_relabel.py
+++ b/networkx/tests/test_relabel.py
@@ -183,3 +183,109 @@ class TestRelabel:
         G = nx.MultiDiGraph([(1, 1)])
         G = nx.relabel_nodes(G, {1: 0}, copy=False)
         assert_nodes_equal(G.nodes(), [0])
+
+#    def test_relabel_multidigraph_inout_inplace(self):
+#        pass
+    def test_relabel_multidigraph_inout_merge_nodes(self):
+        for MG in (nx.MultiGraph, nx.MultiDiGraph):
+            for cc in (True, False):
+                G = MG([(0, 4), (1, 4), (4, 2), (4, 3)])
+                G[0][4][0]["value"] = "a"
+                G[1][4][0]["value"] = "b"
+                G[4][2][0]["value"] = "c"
+                G[4][3][0]["value"] = "d"
+                G.add_edge(0, 4, key="x", value="e")
+                G.add_edge(4, 3, key="x", value="f")
+                mapping = {0: 9, 1: 9, 2: 9, 3: 9}
+                H = nx.relabel_nodes(G, mapping, copy=cc)
+                # No ordering on keys enforced
+                assert {"value": "a"} in H[9][4].values()
+                assert {"value": "b"} in H[9][4].values()
+                assert {"value": "c"} in H[4][9].values()
+                assert len(H[4][9]) == 3 if G.is_directed() else 6
+                assert {"value": "d"} in H[4][9].values()
+                assert {"value": "e"} in H[9][4].values()
+                assert {"value": "f"} in H[4][9].values()
+                assert len(H[9][4]) == 3 if G.is_directed() else 6
+
+    def test_relabel_multigraph_merge_inplace(self):
+        G = nx.MultiGraph([(0, 1), (0, 2), (0, 3), (0, 1), (0, 2), (0, 3)])
+        G[0][1][0]["value"] = "a"
+        G[0][2][0]["value"] = "b"
+        G[0][3][0]["value"] = "c"
+        mapping = {1: 4, 2: 4, 3: 4}
+        nx.relabel_nodes(G, mapping, copy=False)
+        # No ordering on keys enforced
+        assert {"value": "a"} in G[0][4].values()
+        assert {"value": "b"} in G[0][4].values()
+        assert {"value": "c"} in G[0][4].values()
+
+    def test_relabel_multidigraph_merge_inplace(self):
+        G = nx.MultiDiGraph([(0, 1), (0, 2), (0, 3)])
+        G[0][1][0]["value"] = "a"
+        G[0][2][0]["value"] = "b"
+        G[0][3][0]["value"] = "c"
+        mapping = {1: 4, 2: 4, 3: 4}
+        nx.relabel_nodes(G, mapping, copy=False)
+        # No ordering on keys enforced
+        assert {"value": "a"} in G[0][4].values()
+        assert {"value": "b"} in G[0][4].values()
+        assert {"value": "c"} in G[0][4].values()
+
+    def test_relabel_multidigraph_inout_copy(self):
+        G = nx.MultiDiGraph([(0, 4), (1, 4), (4, 2), (4, 3)])
+        G[0][4][0]["value"] = "a"
+        G[1][4][0]["value"] = "b"
+        G[4][2][0]["value"] = "c"
+        G[4][3][0]["value"] = "d"
+        G.add_edge(0, 4, key="x", value="e")
+        G.add_edge(4, 3, key="x", value="f")
+        mapping = {0: 9, 1: 9, 2: 9, 3: 9}
+        H = nx.relabel_nodes(G, mapping, copy=True)
+        # No ordering on keys enforced
+        assert {"value": "a"} in H[9][4].values()
+        assert {"value": "b"} in H[9][4].values()
+        assert {"value": "c"} in H[4][9].values()
+        assert len(H[4][9]) == 3
+        assert {"value": "d"} in H[4][9].values()
+        assert {"value": "e"} in H[9][4].values()
+        assert {"value": "f"} in H[4][9].values()
+        assert len(H[9][4]) == 3
+
+    def test_relabel_multigraph_merge_copy(self):
+        G = nx.MultiGraph([(0, 1), (0, 2), (0, 3)])
+        G[0][1][0]["value"] = "a"
+        G[0][2][0]["value"] = "b"
+        G[0][3][0]["value"] = "c"
+        mapping = {1: 4, 2: 4, 3: 4}
+        H = nx.relabel_nodes(G, mapping, copy=True)
+        assert {"value": "a"} in H[0][4].values()
+        assert {"value": "b"} in H[0][4].values()
+        assert {"value": "c"} in H[0][4].values()
+
+    def test_relabel_multidigraph_merge_copy(self):
+        G = nx.MultiDiGraph([(0, 1), (0, 2), (0, 3)])
+        G[0][1][0]["value"] = "a"
+        G[0][2][0]["value"] = "b"
+        G[0][3][0]["value"] = "c"
+        mapping = {1: 4, 2: 4, 3: 4}
+        H = nx.relabel_nodes(G, mapping, copy=True)
+        assert {"value": "a"} in H[0][4].values()
+        assert {"value": "b"} in H[0][4].values()
+        assert {"value": "c"} in H[0][4].values()
+
+    def test_relabel_multigraph_nonnumeric_key(self):
+        for MG in (nx.MultiGraph, nx.MultiDiGraph):
+            for cc in (True, False):
+                G = nx.MultiGraph()
+                G.add_edge(0, 1, key="I", value="a")
+                G.add_edge(0, 2, key="II", value="b")
+                G.add_edge(0, 3, key="II", value="c")
+                mapping = {1: 4, 2: 4, 3: 4}
+                nx.relabel_nodes(G, mapping, copy=False)
+                assert {"value": "a"} in G[0][4].values()
+                assert {"value": "b"} in G[0][4].values()
+                assert {"value": "c"} in G[0][4].values()
+                assert 0 in G[0][4]
+                assert "I" in G[0][4]
+                assert "II" in G[0][4]