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

Question

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

Answer 1

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.

---

Original answer:

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[
 Set[am[[#, #]], AdjacencyMatrix[repl]] &,
 Values[subgraphs]
]

The result looks like this:

AdjacencyGraph[am, DirectedEdges -> True]

Once again, you can verify the result using

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