Repository: networkx/networkx

Issue:
vf2pp_is_isomorphic returns wrong results
<!-- 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
```
import networkx as nx
g = nx.MultiDiGraph({0: [1, 1, 2, 2, 3], 1: [2, 3, 3], 2: [3]})
h = nx.MultiDiGraph({0: [1, 1, 2, 2, 3], 1: [2, 3, 3], 3: [2]})
print(nx.is_isomorphic(g, h))
print(nx.vf2pp_is_isomorphic(g, h))
```
prints:
```
False
True
```
<!--- Tell us what happens instead of the expected behavior -->

### Expected Behavior
Prints:
```
False
False
```
<!--- Tell us what should happen -->

### Steps to Reproduce
See above.
<!--- Provide a minimal example that reproduces the bug -->

### Environment

<!--- Please provide details about your local environment -->

Python version: 3.11.0
NetworkX version: 3.0rc1

### Additional context

<!--- Add any other context about the problem here, screenshots, etc. -->


Discussion:
reneechebbo: > Fantastic! Thanks very much!!

My pleasure!

Patch:
diff --git a/networkx/algorithms/isomorphism/vf2pp_helpers/feasibility.py b/networkx/algorithms/isomorphism/vf2pp_helpers/feasibility.py
index 90e8fe864..40d19e332 100644
--- a/networkx/algorithms/isomorphism/vf2pp_helpers/feasibility.py
+++ b/networkx/algorithms/isomorphism/vf2pp_helpers/feasibility.py
@@ -232,16 +232,16 @@ def _consistent_PT(u, v, graph_params, state_params):
 
     for predecessor in G1.pred[u]:
         if predecessor in mapping:
-            if G1.number_of_edges(u, predecessor) != G2.number_of_edges(
-                v, mapping[predecessor]
+            if G1.number_of_edges(predecessor, u) != G2.number_of_edges(
+                mapping[predecessor], v
             ):
                 return False
 
     for predecessor in G2.pred[v]:
         if predecessor in reverse_mapping:
             if G1.number_of_edges(
-                u, reverse_mapping[predecessor]
-            ) != G2.number_of_edges(v, predecessor):
+                reverse_mapping[predecessor], u
+            ) != G2.number_of_edges(predecessor, v):
                 return False
 
     return True
diff --git a/networkx/algorithms/lowest_common_ancestors.py b/networkx/algorithms/lowest_common_ancestors.py
index 68aaf7d3f..9c40758f8 100644
--- a/networkx/algorithms/lowest_common_ancestors.py
+++ b/networkx/algorithms/lowest_common_ancestors.py
@@ -14,7 +14,6 @@ __all__ = [
 
 
 @not_implemented_for("undirected")
-@not_implemented_for("multigraph")
 def all_pairs_lowest_common_ancestor(G, pairs=None):
     """Return the lowest common ancestor of all pairs or the provided pairs
 
@@ -112,7 +111,6 @@ def all_pairs_lowest_common_ancestor(G, pairs=None):
 
 
 @not_implemented_for("undirected")
-@not_implemented_for("multigraph")
 def lowest_common_ancestor(G, node1, node2, default=None):
     """Compute the lowest common ancestor of the given pair of nodes.
 
@@ -150,7 +148,6 @@ def lowest_common_ancestor(G, node1, node2, default=None):
 
 
 @not_implemented_for("undirected")
-@not_implemented_for("multigraph")
 def tree_all_pairs_lowest_common_ancestor(G, root=None, pairs=None):
     r"""Yield the lowest common ancestor for sets of pairs in a tree.
 
@@ -237,7 +234,8 @@ def tree_all_pairs_lowest_common_ancestor(G, root=None, pairs=None):
                     msg = "No root specified and tree has multiple sources."
                     raise nx.NetworkXError(msg)
                 root = n
-            elif deg > 1:
+            # checking deg>1 is not sufficient for MultiDiGraphs
+            elif deg > 1 and len(G.pred[n]) > 1:
                 msg = "Tree LCA only defined on trees; use DAG routine."
                 raise nx.NetworkXError(msg)
     if root is None:
diff --git a/networkx/algorithms/simple_paths.py b/networkx/algorithms/simple_paths.py
index 6fb5cfee0..d6baa23b3 100644
--- a/networkx/algorithms/simple_paths.py
+++ b/networkx/algorithms/simple_paths.py
@@ -257,7 +257,7 @@ def _empty_generator():
 
 
 def _all_simple_paths_graph(G, source, targets, cutoff):
-    visited = dict.fromkeys([source])
+    visited = {source: True}
     stack = [iter(G[source])]
     while stack:
         children = stack[-1]
@@ -270,7 +270,7 @@ def _all_simple_paths_graph(G, source, targets, cutoff):
                 continue
             if child in targets:
                 yield list(visited) + [child]
-            visited[child] = None
+            visited[child] = True
             if targets - set(visited.keys()):  # expand stack until find all targets
                 stack.append(iter(G[child]))
             else:
@@ -283,7 +283,7 @@ def _all_simple_paths_graph(G, source, targets, cutoff):
 
 
 def _all_simple_paths_multigraph(G, source, targets, cutoff):
-    visited = dict.fromkeys([source])
+    visited = {source: True}
     stack = [(v for u, v in G.edges(source))]
     while stack:
         children = stack[-1]
@@ -296,7 +296,7 @@ def _all_simple_paths_multigraph(G, source, targets, cutoff):
                 continue
             if child in targets:
                 yield list(visited) + [child]
-            visited[child] = None
+            visited[child] = True
             if targets - set(visited.keys()):
                 stack.append((v for u, v in G.edges(child)))
             else:
diff --git a/networkx/classes/digraph.py b/networkx/classes/digraph.py
index edaf444bf..0d353d934 100644
--- a/networkx/classes/digraph.py
+++ b/networkx/classes/digraph.py
@@ -485,6 +485,16 @@ class DiGraph(Graph):
         --------
         add_node
 
+        Notes
+        -------
+        When adding nodes from an iterator over the graph you are changing,
+        a `RuntimeError` can be raised with message:
+        `RuntimeError: dictionary changed size during iteration`. This
+        happens when the graph's underlying dictionary is modified during
+        iteration. To avoid this error, evaluate the iterator into a separate
+        object, e.g. by using `list(iterator_of_nodes)`, and pass this
+        object to `G.add_nodes_from`.
+
         Examples
         --------
         >>> G = nx.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
@@ -509,6 +519,13 @@ class DiGraph(Graph):
         >>> H.nodes[1]["size"]
         11
 
+        Evaluate an iterator over a graph if using it to modify the same graph
+
+        >>> G = nx.DiGraph([(0, 1), (1, 2), (3, 4)])
+        >>> # wrong way - will raise RuntimeError
+        >>> # G.add_nodes_from(n + 1 for n in G.nodes)
+        >>> # correct way
+        >>> G.add_nodes_from(list(n + 1 for n in G.nodes))
         """
         for n in nodes_for_adding:
             try:
@@ -582,6 +599,16 @@ class DiGraph(Graph):
         --------
         remove_node
 
+        Notes
+        -------
+        When removing nodes from an iterator over the graph you are changing,
+        a `RuntimeError` will be raised with message:
+        `RuntimeError: dictionary changed size during iteration`. This
+        happens when the graph's underlying dictionary is modified during
+        iteration. To avoid this error, evaluate the iterator into a separate
+        object, e.g. by using `list(iterator_of_nodes)`, and pass this
+        object to `G.remove_nodes_from`.
+
         Examples
         --------
         >>> G = nx.path_graph(3)  # or DiGraph, MultiGraph, MultiDiGraph, etc
@@ -592,6 +619,13 @@ class DiGraph(Graph):
         >>> list(G.nodes)
         []
 
+        Evaluate an iterator over a graph if using it to modify the same graph
+
+        >>> G = nx.DiGraph([(0, 1), (1, 2), (3, 4)])
+        >>> # this command will fail, as the graph's dict is modified during iteration
+        >>> # G.remove_nodes_from(n for n in G.nodes if n < 2)
+        >>> # this command will work, since the dictionary underlying graph is not modified
+        >>> G.remove_nodes_from(list(n for n in G.nodes if n < 2))
         """
         for n in nodes:
             try:
@@ -702,6 +736,14 @@ class DiGraph(Graph):
         Edge attributes specified in an ebunch take precedence over
         attributes specified via keyword arguments.
 
+        When adding edges from an iterator over the graph you are changing,
+        a `RuntimeError` can be raised with message:
+        `RuntimeError: dictionary changed size during iteration`. This
+        happens when the graph's underlying dictionary is modified during
+        iteration. To avoid this error, evaluate the iterator into a separate
+        object, e.g. by using `list(iterator_of_edges)`, and pass this
+        object to `G.add_edges_from`.
+
         Examples
         --------
         >>> G = nx.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
@@ -713,6 +755,15 @@ class DiGraph(Graph):
 
         >>> G.add_edges_from([(1, 2), (2, 3)], weight=3)
         >>> G.add_edges_from([(3, 4), (1, 4)], label="WN2898")
+
+        Evaluate an iterator over a graph if using it to modify the same graph
+
+        >>> G = nx.DiGraph([(1, 2), (2, 3), (3, 4)])
+        >>> # Grow graph by one new node, adding edges to all existing nodes.
+        >>> # wrong way - will raise RuntimeError
+        >>> # G.add_edges_from(((5, n) for n in G.nodes))
+        >>> # right way - note that there will be no self-edge for node 5
+        >>> G.add_edges_from(list((5, n) for n in G.nodes))
         """
         for e in ebunch_to_add:
             ne = len(e)
diff --git a/networkx/classes/graph.py b/networkx/classes/graph.py
index 076d1f4c9..67dc57d42 100644
--- a/networkx/classes/graph.py
+++ b/networkx/classes/graph.py
@@ -579,6 +579,16 @@ class Graph:
         --------
         add_node
 
+        Notes
+        -------
+        When adding nodes from an iterator over the graph you are changing,
+        a `RuntimeError` can be raised with message:
+        `RuntimeError: dictionary changed size during iteration`. This
+        happens when the graph's underlying dictionary is modified during
+        iteration. To avoid this error, evaluate the iterator into a separate
+        object, e.g. by using `list(iterator_of_nodes)`, and pass this
+        object to `G.add_nodes_from`.
+
         Examples
         --------
         >>> G = nx.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
@@ -603,6 +613,13 @@ class Graph:
         >>> H.nodes[1]["size"]
         11
 
+        Evaluate an iterator over a graph if using it to modify the same graph
+
+        >>> G = nx.Graph([(0, 1), (1, 2), (3, 4)])
+        >>> # wrong way - will raise RuntimeError
+        >>> # G.add_nodes_from(n + 1 for n in G.nodes)
+        >>> # correct way
+        >>> G.add_nodes_from(list(n + 1 for n in G.nodes))
         """
         for n in nodes_for_adding:
             try:
@@ -674,6 +691,16 @@ class Graph:
         --------
         remove_node
 
+        Notes
+        -------
+        When removing nodes from an iterator over the graph you are changing,
+        a `RuntimeError` will be raised with message:
+        `RuntimeError: dictionary changed size during iteration`. This
+        happens when the graph's underlying dictionary is modified during
+        iteration. To avoid this error, evaluate the iterator into a separate
+        object, e.g. by using `list(iterator_of_nodes)`, and pass this
+        object to `G.remove_nodes_from`.
+
         Examples
         --------
         >>> G = nx.path_graph(3)  # or DiGraph, MultiGraph, MultiDiGraph, etc
@@ -684,6 +711,13 @@ class Graph:
         >>> list(G.nodes)
         []
 
+        Evaluate an iterator over a graph if using it to modify the same graph
+
+        >>> G = nx.Graph([(0, 1), (1, 2), (3, 4)])
+        >>> # this command will fail, as the graph's dict is modified during iteration
+        >>> # G.remove_nodes_from(n for n in G.nodes if n < 2)
+        >>> # this command will work, since the dictionary underlying graph is not modified
+        >>> G.remove_nodes_from(list(n for n in G.nodes if n < 2))
         """
         adj = self._adj
         for n in nodes:
@@ -950,6 +984,14 @@ class Graph:
         Edge attributes specified in an ebunch take precedence over
         attributes specified via keyword arguments.
 
+        When adding edges from an iterator over the graph you are changing,
+        a `RuntimeError` can be raised with message:
+        `RuntimeError: dictionary changed size during iteration`. This
+        happens when the graph's underlying dictionary is modified during
+        iteration. To avoid this error, evaluate the iterator into a separate
+        object, e.g. by using `list(iterator_of_edges)`, and pass this
+        object to `G.add_edges_from`.
+
         Examples
         --------
         >>> G = nx.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
@@ -961,6 +1003,15 @@ class Graph:
 
         >>> G.add_edges_from([(1, 2), (2, 3)], weight=3)
         >>> G.add_edges_from([(3, 4), (1, 4)], label="WN2898")
+
+        Evaluate an iterator over a graph if using it to modify the same graph
+
+        >>> G = nx.Graph([(1, 2), (2, 3), (3, 4)])
+        >>> # Grow graph by one new node, adding edges to all existing nodes.
+        >>> # wrong way - will raise RuntimeError
+        >>> # G.add_edges_from(((5, n) for n in G.nodes))
+        >>> # correct way - note that there will be no self-edge for node 5
+        >>> G.add_edges_from(list((5, n) for n in G.nodes))
         """
         for e in ebunch_to_add:
             ne = len(e)
@@ -1012,10 +1063,28 @@ class Graph:
         the edge data. For MultiGraph/MultiDiGraph, duplicate edges
         are stored.
 
+        When adding edges from an iterator over the graph you are changing,
+        a `RuntimeError` can be raised with message:
+        `RuntimeError: dictionary changed size during iteration`. This
+        happens when the graph's underlying dictionary is modified during
+        iteration. To avoid this error, evaluate the iterator into a separate
+        object, e.g. by using `list(iterator_of_edges)`, and pass this
+        object to `G.add_weighted_edges_from`.
+
         Examples
         --------
         >>> G = nx.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
         >>> G.add_weighted_edges_from([(0, 1, 3.0), (1, 2, 7.5)])
+
+        Evaluate an iterator over edges before passing it
+
+        >>> G = nx.Graph([(1, 2), (2, 3), (3, 4)])
+        >>> weight = 0.1
+        >>> # Grow graph by one new node, adding edges to all existing nodes.
+        >>> # wrong way - will raise RuntimeError
+        >>> # G.add_weighted_edges_from(((5, n, weight) for n in G.nodes))
+        >>> # correct way - note that there will be no self-edge for node 5
+        >>> G.add_weighted_edges_from(list((5, n, weight) for n in G.nodes))
         """
         self.add_edges_from(((u, v, {weight: d}) for u, v, d in ebunch_to_add), **attr)
 
diff --git a/networkx/classes/multigraph.py b/networkx/classes/multigraph.py
index 3d9e69b39..a91e012ef 100644
--- a/networkx/classes/multigraph.py
+++ b/networkx/classes/multigraph.py
@@ -562,6 +562,14 @@ class MultiGraph(Graph):
         This method can be overridden by subclassing the base class and
         providing a custom ``new_edge_key()`` method.
 
+        When adding edges from an iterator over the graph you are changing,
+        a `RuntimeError` can be raised with message:
+        `RuntimeError: dictionary changed size during iteration`. This
+        happens when the graph's underlying dictionary is modified during
+        iteration. To avoid this error, evaluate the iterator into a separate
+        object, e.g. by using `list(iterator_of_edges)`, and pass this
+        object to `G.add_edges_from`.
+
         Examples
         --------
         >>> G = nx.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
@@ -573,6 +581,15 @@ class MultiGraph(Graph):
 
         >>> G.add_edges_from([(1, 2), (2, 3)], weight=3)
         >>> G.add_edges_from([(3, 4), (1, 4)], label="WN2898")
+
+        Evaluate an iterator over a graph if using it to modify the same graph
+
+        >>> G = nx.MultiGraph([(1, 2), (2, 3), (3, 4)])
+        >>> # Grow graph by one new node, adding edges to all existing nodes.
+        >>> # wrong way - will raise RuntimeError
+        >>> # G.add_edges_from(((5, n) for n in G.nodes))
+        >>> # right way - note that there will be no self-edge for node 5
+        >>> assigned_keys = G.add_edges_from(list((5, n) for n in G.nodes))
         """
         keylist = []
         for e in ebunch_to_add:


Test patch:
diff --git a/networkx/algorithms/isomorphism/tests/test_isomorphvf2.py b/networkx/algorithms/isomorphism/tests/test_isomorphvf2.py
index 5d3f41b41..02218526c 100644
--- a/networkx/algorithms/isomorphism/tests/test_isomorphvf2.py
+++ b/networkx/algorithms/isomorphism/tests/test_isomorphvf2.py
@@ -401,3 +401,9 @@ def test_monomorphism_edge_match():
 
     gm = iso.DiGraphMatcher(G, SG, edge_match=iso.categorical_edge_match("label", None))
     assert gm.subgraph_is_monomorphic()
+
+
+def test_isomorphvf2pp_multidigraphs():
+    g = nx.MultiDiGraph({0: [1, 1, 2, 2, 3], 1: [2, 3, 3], 2: [3]})
+    h = nx.MultiDiGraph({0: [1, 1, 2, 2, 3], 1: [2, 3, 3], 3: [2]})
+    assert not (nx.vf2pp_is_isomorphic(g, h))
diff --git a/networkx/algorithms/tests/test_lowest_common_ancestors.py b/networkx/algorithms/tests/test_lowest_common_ancestors.py
index fac31403e..1a8fd03c8 100644
--- a/networkx/algorithms/tests/test_lowest_common_ancestors.py
+++ b/networkx/algorithms/tests/test_lowest_common_ancestors.py
@@ -136,12 +136,6 @@ class TestTreeLCA:
         with pytest.raises(NNI):
             next(all_pairs_lca(G))
         pytest.raises(NNI, nx.lowest_common_ancestor, G, 0, 1)
-        G = nx.MultiDiGraph([(0, 1)])
-        with pytest.raises(NNI):
-            next(tree_all_pairs_lca(G))
-        with pytest.raises(NNI):
-            next(all_pairs_lca(G))
-        pytest.raises(NNI, nx.lowest_common_ancestor, G, 0, 1)
 
     def test_tree_all_pairs_lca_trees_without_LCAs(self):
         G = nx.DiGraph()
@@ -150,6 +144,41 @@ class TestTreeLCA:
         assert ans == [((3, 3), 3)]
 
 
+class TestMultiTreeLCA(TestTreeLCA):
+    @classmethod
+    def setup_class(cls):
+        cls.DG = nx.MultiDiGraph()
+        edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)]
+        cls.DG.add_edges_from(edges)
+        cls.ans = dict(tree_all_pairs_lca(cls.DG, 0))
+        # add multiedges
+        cls.DG.add_edges_from(edges)
+
+        gold = {(n, n): n for n in cls.DG}
+        gold.update({(0, i): 0 for i in range(1, 7)})
+        gold.update(
+            {
+                (1, 2): 0,
+                (1, 3): 1,
+                (1, 4): 1,
+                (1, 5): 0,
+                (1, 6): 0,
+                (2, 3): 0,
+                (2, 4): 0,
+                (2, 5): 2,
+                (2, 6): 2,
+                (3, 4): 1,
+                (3, 5): 0,
+                (3, 6): 0,
+                (4, 5): 0,
+                (4, 6): 0,
+                (5, 6): 2,
+            }
+        )
+
+        cls.gold = gold
+
+
 class TestDAGLCA:
     @classmethod
     def setup_class(cls):
@@ -326,6 +355,62 @@ class TestDAGLCA:
         assert nx.lowest_common_ancestor(G, 1, 3) == 2
 
 
+class TestMultiDiGraph_DAGLCA(TestDAGLCA):
+    @classmethod
+    def setup_class(cls):
+        cls.DG = nx.MultiDiGraph()
+        nx.add_path(cls.DG, (0, 1, 2, 3))
+        # add multiedges
+        nx.add_path(cls.DG, (0, 1, 2, 3))
+        nx.add_path(cls.DG, (0, 4, 3))
+        nx.add_path(cls.DG, (0, 5, 6, 8, 3))
+        nx.add_path(cls.DG, (5, 7, 8))
+        cls.DG.add_edge(6, 2)
+        cls.DG.add_edge(7, 2)
+
+        cls.root_distance = nx.shortest_path_length(cls.DG, source=0)
+
+        cls.gold = {
+            (1, 1): 1,
+            (1, 2): 1,
+            (1, 3): 1,
+            (1, 4): 0,
+            (1, 5): 0,
+            (1, 6): 0,
+            (1, 7): 0,
+            (1, 8): 0,
+            (2, 2): 2,
+            (2, 3): 2,
+            (2, 4): 0,
+            (2, 5): 5,
+            (2, 6): 6,
+            (2, 7): 7,
+            (2, 8): 7,
+            (3, 3): 3,
+            (3, 4): 4,
+            (3, 5): 5,
+            (3, 6): 6,
+            (3, 7): 7,
+            (3, 8): 8,
+            (4, 4): 4,
+            (4, 5): 0,
+            (4, 6): 0,
+            (4, 7): 0,
+            (4, 8): 0,
+            (5, 5): 5,
+            (5, 6): 5,
+            (5, 7): 5,
+            (5, 8): 5,
+            (6, 6): 6,
+            (6, 7): 5,
+            (6, 8): 6,
+            (7, 7): 7,
+            (7, 8): 7,
+            (8, 8): 8,
+        }
+        cls.gold.update(((0, n), 0) for n in cls.DG)
+
+
 def test_all_pairs_lca_self_ancestors():
     """Self-ancestors should always be the node itself, i.e. lca of (0, 0) is 0.
     See gh-4458."""
@@ -334,6 +419,9 @@ def test_all_pairs_lca_self_ancestors():
     G.add_nodes_from(range(5))
     G.add_edges_from([(1, 0), (2, 0), (3, 2), (4, 1), (4, 3)])
 
-    assert all(
-        u == v == a for (u, v), a in nx.all_pairs_lowest_common_ancestor(G) if u == v
-    )
+    ap_lca = nx.all_pairs_lowest_common_ancestor
+    assert all(u == v == a for (u, v), a in ap_lca(G) if u == v)
+    MG = nx.MultiDiGraph(G)
+    assert all(u == v == a for (u, v), a in ap_lca(MG) if u == v)
+    MG.add_edges_from([(1, 0), (2, 0)])
+    assert all(u == v == a for (u, v), a in ap_lca(MG) if u == v)