Detecting Isomorphism of graphs with fixed edge...?positions? | Sololearn: Learn to code for FREE!
New course! Every coder should learn Generative AI!
Try a free lesson
+ 4

Detecting Isomorphism of graphs with fixed edge...?positions?

I updated my Question in the comments below. The problem is described below and in the code playground. https://code.sololearn.com/cJvn8noA4Viy By using pentagon shaped tiles, shapes can be created, and I am looking on how to recognize specific shapes or match to preexisting shapes. I am looking for anyone who can direct me to towards how to come up with an existing class I am unaware of or tutorial on how to determine isomorphism with Location Specific Edges. I feel it would be an advanced use of an adjacency list or matrix. //Current Problem 6/23/18 /* ^ / \ \_/ 0 / | \ _ _ / _ \ _ 4 / \1 / \ / \ / \ \ / \ / \ / \ / 3 V 2 V V V The left example is a vertex with specific edge locations[0-4] The right example is not a tree, but an undirected graph. The vertex is to represesnt a pentagon, and the graph is to represent a collection of vertices. By placing several tiles toether you can create shapes, the image to the right is to represent a graph I have called 'Sprout'. If I have a graph, independent of the vertex data but dependent on specific edges connected, I would like to compare it to another graph in the form of an isomorphism detection algorithm caring only about the edge location data. I have several shapes I am looking for, and can construct them with the code below, but I do not know how to compare one graph to another. I am looking for a method in the graph class that looks like this... public bool isSimilarTo(VertGraph otherGraph){ [[Code Stuff]]; return true/false;} */

23rd Jun 2018, 6:07 PM
sharpProgrammer
sharpProgrammer - avatar
1 Answer
+ 1
More details about my question. Context: A game of aligning 4-6 pentagon tiles edge to edge to make specific shapes. Match a pattern of 4-6 tiles with a specific pattern of 4-6 tiles. https://i.stack.imgur.com/WcWB0.png Goal: Be able to match two undirected graphs of vertices with edges of relative fixed positions. Fixed positions refers to each node having a "cardinality"(North, East, South, West) but with five paths out of the node instead of four. Relative fixed positions refers to treating vertex1 with edge2 and edge3 leaving the vertex being the same as vertex1 with edge3 and edge4 leaving the vertex. Its like two people have drawn a map each with 5 way intersections and I want to see if the paths of each map are the same. And one of the would be cartographers drew the map sideways on their paper so while their paths are relatively correct, they don't match up perfectly. Abilities: I am confident in representing the tile as a vertex class and the patterns as a graph class. I know how to create an adjacency matrix and adjacency list. I think I could determine isomorphism of the two graphs if needed, although I do not think that will work in my case.My study in graphs so far using C#. https://code.sololearn.com/cJvn8noA4Viy#cs Limitations: I think this case differs from isomorphism because each node has a specific number of edge locations whether the edge is there or not. My understanding of how an adjacency matrix might solve the issue is not complete, if it will at all. I have designed recursive algorithms(with help) to solve a maze, and feel that recursion would be necessary in solving this issue. Limited experience in traversing trees or graphs. Call to Action: Is there a specific phrasing that I am lacking in searching for a graph with specific possible edges? Is there a strategy that you mind sharing for determining matches of two graphs in this case? Is there an algorithm that you can point me towards that would match paths, but independent of direction and with forks?
26th Jun 2018, 9:34 PM
sharpProgrammer
sharpProgrammer - avatar