Message Boards Message Boards

1
|
5871 Views
|
3 Replies
|
1 Total Likes
View groups...
Share
Share this post:

A sub graph match comparison

Posted 3 years ago

Hi,

I'm trying to do a comparison between a main graph and a sub graph. Simply put, is there a native function to do this job or should I do search and compare in the the following way:

Triangular grid as a main grap:

a = ResourceFunction["WolframModel"][{{x, y}} -> {{x, y},{y, z},{z, x}}, {{1, 2}}, 2, "FinalState"]

Triangle:

b = ResourceFunction["WolframModel"][{{x, y}} -> {{x, y},{y, z},{z, x}}, {{1, 2}}, 1, "FinalState"]

Square:

c = ResourceFunction["WolframModel"][{{x, y}} -> {{x, y},{y, z},{z, u},{u, x}}, {{1, 2}}, 1, "FinalState"]

Looging for triangle:

s = Subgraph[b,b]
Subgraph[a,b] == s -> TRUE

Looginf for square:

Subgraph[a,c] == s -> FALSE

Before I'm going to write a function for the comparison, I'd like to know what is the best way doing this?

POSTED BY: Marko Manninen
3 Replies
Posted 3 years ago

Hi Marko,

Take a look at IsomorphicGraphQ.

POSTED BY: Rohit Namjoshi

Hi Rohit,

I took a look at that, but I'm not sure how to use it:

IsomorphicGraphQ[UndirectedGraph[a],UndirectedGraph[b]]

That won't give the desired result. It looks like the function requires the same amount of points in the graph, but in my case, I want to know if subgraph exists in the main graph. The main graph may be a huge grid of points and the subgraph just a small part. I need to know if a small graph exists inside the big graph as directed (and undirected) list of points.

-Marko

POSTED BY: Marko Manninen

You need a function to say whether one graph is a subgraph of another, a SubGraphQ function.

I recommend the IGraphM package, available at https://github.com/szhorvat/IGraphM. Look for the function IGSubisomorphicQ.

POSTED BY: Jason Biggs
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract