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
Mathematica Stack Exchange is a question and answer site for users of Wolfram Mathematica. It only takes a minute to sign up.
Sign up to join this communityI 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
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 graphpatt
(for "pattern"), find all occurrences ofpatt
as an induced subgraph ing
. Then replace all these occurrences with another graph of the same size,repl
, having the same automorphism group aspatt
.
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]
IGLADGetSubisomorphism
. This will be much faster than anything one could implement in Mathematica code. It uses Christine Solnon's LAD library under the hood.
$\endgroup$
– Szabolcs
Nov 8 '18 at 7:45
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. $\endgroup$ – Henrik Schumacher Nov 7 '18 at 9:32