finding all subgraph monomorphisms

[Mark DeBonis]

I have been scouring the internet for an implementation of networkx which finds all the subgraph monomorphisms in a graph just as it can find all subgraph isomorphisms, but I cannot seem to find it. I am using the ISMAGS algorithm.

matcher = isomorphism.ISMAGS(graph, subgraph)

match_list = [m for m in matcher.find_isomorphisms()]

It would be nice if I could do

match_list = [m for m in matcher.find_monomorphisms()]

nextworkx can decide if there is a monomorphism between two graphs using graphmatcher, but can it find the complete list of all monomorphisms?

I apologize if this question is redundant or has an easy answer.

Thanks!

Mark

[Dan Schult]

Yes, there is a method of the GraphMatcher class (using the VF2 interface instead of ISMAGS) called `subgraph_monomorphisms_iter`.

So something like the following should work:

```python

G1 = nx.cycle_graph(5)

G2 = nx.path_graph(4)

GM = nx.isomorphism.GraphMatcher(G1, G2)

for m in GM.subgraph_monomorphisms_iter():

    print(m)

```

with output

```

{0: 0, 1: 1, 2: 2, 3: 3}
{0: 0, 4: 1, 3: 2, 2: 3}
{1: 0, 0: 1, 4: 2, 3: 3}
{1: 0, 2: 1, 3: 2, 4: 3}
{2: 0, 1: 1, 0: 2, 4: 3}
{2: 0, 3: 1, 4: 2, 0: 3}
{3: 0, 2: 1, 1: 2, 0: 3}
{3: 0, 4: 1, 0: 2, 1: 3}
{4: 0, 0: 1, 1: 2, 2: 3}
{4: 0, 3: 1, 2: 2, 1: 3}

```

[Mark DeBonis]

Thanks, Dan, for the information!

I assume the list will include symmetric solutions as well?

The subgraphs I am looking at have lots of symmetries and use up all my RAM when finding solutions, which is why I am using ISMAGS instead of VF2.

It would be nice if ISMAGS had the same method.

Best,

Mark

[Dan Schult]

The "S" in ISMAGS refers to induced subgraphs. So SIMAGS doesn't work with monomorphisms. 

It is possible that a paper has come out with a similar technique aimed at monomorphisms, but I don't know of such an algorithm. NetworkX does not have a monomorphism finding routine that takes symmetries into account.

[Mark DeBonis]

Understood. Thanks again!

Mark