Repository: networkx/networkx
Pull request: Enforce correct graph types for graph matchers
Fixes #7964.

Check that both graphs have the correct directedness in `(Multi-)(Di-)GraphMatcher` initialization.

@dschult, you mentioned switching to a function-oriented interface in the linked issue. Is this something that has been discussed previously/is there some kind of consensus on what that should look like? I feel the graph matching subsection of the codebase could use a revamp (there are still untouched lines of code from 2007 in there! :) ). I'd give it a shot, but it would entail some significant, opinionated API changes, and I'm curious what people think about that.

Problem statement:
Directed edges in MultiDiGraph not handled correctly by subgraph monomorphism
### Current Behavior

A directed graph without edges should not have a subgraph monomorphic to a digraph with one edge.
However, current implementation says it is monomorphic.

### Expected Behavior

It should not be considered monomorphic.

### Steps to Reproduce

import networkx as nx

G = nx.MultiGraph()
G.add_node("A", label="A")
G.add_node("B", label="B")
H = nx.MultiGraph([["A", "B"]]) # one edge
matcher = nx.isomorphism.GraphMatcher(G, H)
print(matcher.subgraph_is_monomorphic()) ## False, as expected

G = nx.MultiDiGraph()
G.add_node("A", label="A")
G.add_node("B", label="B")
H = nx.MultiDiGraph([["A", "B"]]) # one edge
matcher = nx.isomorphism.GraphMatcher(G, H)
print(matcher.subgraph_is_monomorphic()) ## True, should be false

### Environment

Ubuntu 22.04 inside Windows 10 WSL

Python version: Python 3.12.3
NetworkX version: 3.4.2

### Additional context

My suspicion as to what is going on: 

Say the edge is A -> B. I suspect A is mapped first and added into core_1. A has no mapped neighbor yet that needs to check the edge existence, so it's fine. And when B is mapped and added, it has no (outgoing) neighbors, so the edge is also not checked. The program never notices that the "monomorphism" is missing the directed edge.

Hints from issue discussion:
Be careful to use the right class for your matcher:
GraphMatcher is for undirected non-multiedge graphs

If you use `MultiDiGraphMatcher` (or even `DiGraphMatcher` since you don't have any multiedges) for the directed case, it returns False as expected.

I guess this shows that we could/should check if the input graphs are the right directed/multiedge form in the `__init__` method for each class. I think this would become mute once we switch completely to a function oriented interface: `nx.is_monomorphic` but that doesn't exist yet.

Commit message: Enforce correct graph types for graph matchers

Check that both graphs have the correct directedness in
(Multi-)(Di-)GraphMatcher initialization

Patch to review:
diff --git a/networkx/algorithms/isomorphism/isomorphvf2.py b/networkx/algorithms/isomorphism/isomorphvf2.py
index cb0c84fa82c..e914df5d131 100644
--- a/networkx/algorithms/isomorphism/isomorphvf2.py
+++ b/networkx/algorithms/isomorphism/isomorphvf2.py
@@ -146,6 +146,8 @@
 
 import sys
 
+import networkx as nx
+
 __all__ = ["GraphMatcher", "DiGraphMatcher"]
 
 
@@ -172,6 +174,17 @@ def __init__(self, G1, G2):
         >>> G2 = nx.path_graph(4)
         >>> GM = isomorphism.GraphMatcher(G1, G2)
         """
+        if G1.is_directed() and G2.is_directed():
+            raise nx.NetworkXError(
+                "(Multi-)GraphMatcher() not defined for directed graphs. "
+                "Use (Multi-)DiGraphMatcher() instead."
+            )
+        self._init(G1, G2)
+
+    def _init(self, G1, G2):
+        if G1.is_directed() != G2.is_directed():
+            raise nx.NetworkXError("G1 and G2 must have the same directedness")
+
         self.G1 = G1
         self.G2 = G2
         self.G1_nodes = set(G1.nodes())
@@ -618,7 +631,12 @@ def __init__(self, G1, G2):
         >>> G2 = nx.DiGraph(nx.path_graph(4, create_using=nx.DiGraph()))
         >>> DiGM = isomorphism.DiGraphMatcher(G1, G2)
         """
-        super().__init__(G1, G2)
+        if not G1.is_directed() and not G2.is_directed():
+            raise nx.NetworkXError(
+                "(Multi-)DiGraphMatcher() not defined for undirected graphs. "
+                "Use (Multi-)GraphMatcher() instead."
+            )
+        super()._init(G1, G2)
 
     def candidate_pairs_iter(self):
         """Iterator over candidate pairs of nodes in G1 and G2."""
diff --git a/networkx/algorithms/isomorphism/tests/test_isomorphvf2.py b/networkx/algorithms/isomorphism/tests/test_isomorphvf2.py
index d6697a6d14b..9a351edef92 100644
--- a/networkx/algorithms/isomorphism/tests/test_isomorphvf2.py
+++ b/networkx/algorithms/isomorphism/tests/test_isomorphvf2.py
@@ -6,6 +6,8 @@
 import random
 import struct
 
+import pytest
+
 import networkx as nx
 from networkx.algorithms import isomorphism as iso
 
@@ -215,6 +217,34 @@ def test_multiedge():
             assert gm.subgraph_is_monomorphic()
 
 
+@pytest.mark.parametrize("G1", [nx.Graph(), nx.MultiGraph()])
+@pytest.mark.parametrize("G2", [nx.Graph(), nx.MultiGraph()])
+def test_matcher_raises(G1, G2):
+    undirected_matchers = [iso.GraphMatcher, iso.MultiGraphMatcher]
+    directed_matchers = [iso.DiGraphMatcher, iso.MultiDiGraphMatcher]
+
+    for matcher in undirected_matchers:
+        matcher(G1, G2)
+
+        msg = r"\(Multi-\)GraphMatcher\(\) not defined for directed graphs"
+        with pytest.raises(nx.NetworkXError, match=msg):
+            matcher(G1.to_directed(), G2.to_directed())
+
+    for matcher in directed_matchers:
+        matcher(G1.to_directed(), G2.to_directed())
+
+        msg = r"\(Multi-\)DiGraphMatcher\(\) not defined for undirected graphs"
+        with pytest.raises(nx.NetworkXError, match=msg):
+            matcher(G1, G2)
+
+    for matcher in undirected_matchers + directed_matchers:
+        msg = r"G1 and G2 must have the same directedness"
+        with pytest.raises(nx.NetworkXError, match=msg):
+            matcher(G1, G2.to_directed())
+        with pytest.raises(nx.NetworkXError, match=msg):
+            matcher(G1.to_directed(), G2)
+
+
 def test_selfloop():
     # Simple test for graphs with selfloops
     edges = [


Code review comments:
diff_hunk: @@ -618,7 +631,12 @@ def __init__(self, G1, G2):
         >>> G2 = nx.DiGraph(nx.path_graph(4, create_using=nx.DiGraph()))
         >>> DiGM = isomorphism.DiGraphMatcher(G1, G2)
         """
-        super().__init__(G1, G2)
+        if not G1.is_directed() and not G2.is_directed():
+            raise nx.NetworkXError(
+                "(Multi-)DiGraphMatcher() not defined for undirected graphs. "
+                "Use (Multi-)GraphMatcher() instead."
+            )
+        super()._init(G1, G2)
path: networkx/algorithms/isomorphism/isomorphvf2.py
text: @user1:
This way of calling a different initialized sounds a bit odd to me. What about defining a class variable like directed_allowed` and you override that on the subclass?

Another option is to have a method to check graph types and you override that.

Maybe you can leverage not_implemented_for decorator for this 

@author:
I agree with you that it's not the prettiest work-around... I'd be curious if anyone knows of any places in the codebase where a similar problem is handled, so I can match that pattern!

@user2:
How about aligning this structure with the base graph class approach: make a method of the matcher classes:
```
    def is_directed_matcher(self):
        return False
```
And base the logic in the `__init__` off of that value.  Part of me thinks it should just be a class attribute, but the method approach has worked well for the base classes -- it helps ensure that the attribute doesn't get changed.



@author:
Both of you essentially suggested a similar update, so I went ahead and made the change. I agree it's much neater this way! :)