# How do you find a sub-graph and replace it with another subgraph?

I saw a video where SW shows how he has a large graph and some rules for finding a given subgraph in a graph and replacing it with another subgraph.

How would one go about doing this in Mathematica?

Edit video here: 15:23

• What was the video? – b3m2a1 Nov 7 '18 at 6:59
• I voted to close as unclear until the problem is explained in precise terms. I would interpret the question as a subgraph isomorphism problem (given a small graph, see whether and where it occurs in a larger one). But Mathematica has no built-in functionality for this (IGraph/M does though), so it can't possibly be what you saw. – Szabolcs Nov 7 '18 at 8:49
• I second Szabolcs statement: Although I am very interested in the problem, the question in its current form is just impossible to answer. Please, at the very least, provide a link to the video. Even better, try to provide as much code as possible (in a minimal working example sense), so that we don't have to poke in the dark. – Henrik Schumacher Nov 7 '18 at 9:32
• @Szabolcs It was what I saw. I'm sure Mr S. Wolfram built his own functionality to do this not yet in Mathematica. I think it was in his TED talk. – zooby Nov 8 '18 at 1:44

If I think more carefully, the interpretation I provided below is also not good.

Consider this graph:

With this subgraph replacement:

There are two matches in the big graph. But replacing one would create the edge 1 -> 4 (without 1 <- 4) while the other would create 4 -> 1 (without 4 <- 1).

So what is the correct result? The problem is not clearly defined, even after my attempt below. I will not delete this answer yet, as I think it is a good illustration of how complicated it can be to just provide a good problem description.

I saw a video where SW shows how he has a large graph and some rules for finding a given subgraph in a graph and replacing it with another subgraph.

I am going to write an answer with one possible interpretation of the (rather vague) question. I must note that I doubt that this is what the OP saw in a video, as it is not that easy to do with the built-in functionality of Mathematica. I am going to use IGraph/M for the task.

Question interpretation:

Given a larger graph g, and a smaller graph patt (for "pattern"), find all occurrences of patt as an induced subgraph in g. Then replace all these occurrences with another graph of the same size, repl, having the same automorphism group as patt.

Why require the same automorphism group for patt and repl? Because otherwise the problem is not well defined. Suppose we search for the directed pattern A <-> B and want to replace it with A -> B. The vertices of the pattern are interchangeable, so it is always going to match in two ways, A <-> B and B <-> A. Which of these two matches should be replaced by the non-symmetric A -> B? The two possible choices yield two distinct results.

Let's get started. First we load IGraph/M.

<<IGraphM


Here's our big graph:

SeedRandom[42];
g = RandomGraph[{10, 30}, DirectedEdges -> True]


I am going to choose a 3-vertex pattern with no automorphisms (symmetries) at all.

patt = IGData[{"AllDirectedGraphs", 3}][[6]]


IGBlissAutomorphismGroup[patt]
(* {} *)


Find all occurrences:

subgraphs = IGLADFindSubisomorphisms[patt, g, "Induced" -> True]
(* {<|1 -> 5, 2 -> 4, 3 -> 10|>, <|1 -> 5, 2 -> 8,
3 -> 10|>, <|1 -> 6, 2 -> 8, 3 -> 2|>, <|1 -> 6, 2 -> 10,
3 -> 4|>, <|1 -> 7, 2 -> 8, 3 -> 1|>, <|1 -> 9, 2 -> 2,
3 -> 8|>, <|1 -> 9, 2 -> 4, 3 -> 10|>, <|1 -> 9, 2 -> 5, 3 -> 1|>} *)


These associations are mappings from the vertices of the pattern to the vertices of the large graph. I am going to assume that the vertex names in both of these graphs are the same as their indices, i.e. VertexList[...] === {1, 2, 3, ...}. If this is not the case for your graph, use IndexGraph on it before you start. With this property, we can use the vertex names (which are also indices) to index into the adjacency matrix.

"Induced" -> True means that we are looking for induced subgraphs, i.e. both present and absent edges must match.

You can verify the result by extracting the appropriate sub-matrices of the adjacency matrix: AdjacencyGraph[AdjacencyMatrix[g][[#, #]]] & /@ Values[subgraphs]. Of course, the verification would be easier with Subgraph, but this time we work with matrices and indices, so we can easily carry out the subgraph-replacement later.

Now let us find a candidate to replace this subgraph with. Which other 3-vertex directed graphs have no automorphisms?

Select[IGData[{"AllDirectedGraphs", 3}],
IGBlissAutomorphismGroup[#] === {} &]


I will arbitrarily choose the 4th one from above.

repl = %[[4]]


Let us do the replacement through the adjacency matrix:

am = AdjacencyMatrix[g];

Scan[
Values[subgraphs]
]


The result looks like this:

AdjacencyGraph[am, DirectedEdges -> True]


Once again, you can verify the result using

AdjacencyGraph[am[[#, #]]] & /@ Values[subgraphs]

• This is what I mean. It just has to find one instance of the sub-graph. BTW, I just meant an undirected graph. But it is interesting what you did here. – zooby Nov 8 '18 at 1:47
• @zooby To find a single subgraph and stop, you can use IGLADGetSubisomorphism`. This will be much faster than anything one could implement in Mathematica code. It uses Christine Solnon's LAD library under the hood. – Szabolcs Nov 8 '18 at 7:45