//CHECK THE DOCUMENTATION by expanding the comment block /*______________________ |Vertex |_____________________ |-name: String |-edges: List |------------------------ |<>+Vertex(_name:String, edgeNum:int, _edges:Vertex[]) |+getName(): string |+getEdge(index:int): Vertex |+setEdge(edgeNumber:int, vert:Vertex) |+removeEdge(index:int) |+getEdges(): Vertex[] |+printVertex() |+isSameEdgesAs(testEdges:Vertex[]): bool |+shiftEdges() |______________________________________ ______________________ |VertGraph |_____________________ |-name: string |-vertices: :Vertex[] |------------------------ |<>+VertGraph(_name:string, _vertices:List) |+getVertex(index:int): Vertex |+getVertices(): List |+printVertices() |+findPendants(): List |+addVertex(newVertex:Vertex, newVertexEdgeIndex:int, onVertex:Vetex, onVertexEdgeIndex:int) |+splitGraph()(selected:Vertex, selectedEdge:int) |______________________________________ */ //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;} */ using System; using System.Collections.Generic; using System.Linq; class Vertex { private int tileID; private string name; private Vertex[] edges; private bool[] relativeEdges = new bool[5]{false,false,false,false,false}; public Vertex(string _name, int edgeNum, Vertex[] _edges, int _tileID){ this.tileID = _tileID; this.name = _name; this.edges = _edges; } public int getTileID(){return this.tileID;} public string getName(){ return this.name;} public Vertex getEdge(int edgeNumber){return this.edges[edgeNumber];} public void setEdge(int edgeNumber, Vertex vert){ this.edges[edgeNumber] = vert; this.relativeEdges[edgeNumber] = true; } public void removeEdge(int index){ this.edges[index] = null; this.relativeEdges[index] = false; } public Vertex[] getEdges(){return this.edges;} public bool[] getRelativeEdges(){return this.relativeEdges;} public void printVertex(){ Console.Write(this.name); Console.Write(tileID+" - ["); //iterate through the edges, avoid getting content of nulls and if its the last element of edges, dont print an ending comma for (int i = 0; i < edges.Length;i++){ if (edges[i] != null){ if (i == edges.Length-1) Console.Write(edges[i].getName()); else Console.Write(edges[i].getName()+", "); } else { if (i == edges.Length-1) Console.Write(" "); else Console.Write(", "); } } Console.WriteLine("]"); } public bool isSameEdgesAs(Vertex[] testEdges){ //I plan on using this to later validate a VertGraph with another vertGraph return Enumerable.SequenceEqual(this.edges, testEdges); } public void shiftRelativeEdges(){ bool tempEdge; tempEdge = this.relativeEdges[0]; for (int i = 0; i < this.relativeEdges.Length-1;i++) this.relativeEdges[i] = this.relativeEdges[i+1]; this.relativeEdges[this.relativeEdges.Length-1] = tempEdge; } public void printRelativeEdges(){ Console.Write(this.getName()); for(int i = 0;i < relativeEdges.Length; i++){ Console.Write(" "+ relativeEdges[i]); } Console.WriteLine(); } } class VertGraph{ private string name; private List vertices = new List(); private List relAdjMatrix = new List(); public VertGraph(string _name, List _vertices){ this.name = _name; this.vertices = _vertices; } public Vertex getVertex(int index){ return this.vertices[index]; } public List getVertices(){ List copiedVertices = this.vertices; return copiedVertices; } public void printVertices(){ Console.WriteLine(this.name); foreach(Vertex vert in vertices) vert.printVertex(); } public List findPendants(){ //initial studies show that identifying "leafs" may help in later validating a match between one vertGraph and another int edgeCount; List pendants = new List(); //Count each edge of each vertex, determine if it has only one edge and return a list of the verts that do foreach (Vertex vert in vertices){ edgeCount = 0; foreach(Vertex edge in vert.getEdges()) if (edge != null) edgeCount++; if (edgeCount == 1) pendants.Add(vert); } return pendants; } public void addVertex(Vertex newVertex, int newVertexEdgeIndex, Vertex onVertex, int onVertexEdgeIndex){ //get the vertex if this vertGraph that matches the parameter vert mentioned and gets the index of that vert int onVerticesIndex = -1; foreach (Vertex vert in this.vertices) if (onVertex.getName() == vert.getName()) onVerticesIndex = this.vertices.IndexOf(vert); //Adds the vert to the list of vertices this.vertices.Add(newVertex); //the attached vert and attahing vert need their edges set to eachother using setEdge of the Vertex class this.vertices[vertices.Count-1].setEdge(newVertexEdgeIndex,this.vertices[onVerticesIndex]); this.vertices[onVerticesIndex].setEdge(onVertexEdgeIndex,this.vertices[vertices.Count-1]); } //splitGraph needs recursion to split any vertGraph with more than 2 tiles away from the selected edge. public VertGraph splitGraph(Vertex selected, int selectedEdge){ //The strategy is to make two empty VertGraphs List vertsCopyA = new List(); List vertsCopyB = new List(); //Then get the index the tiles adjacent to the edge to split and add them to the two different VertGraphs int vertIndex = this.vertices.IndexOf(selected); vertsCopyA.Add(this.getVertex(vertIndex)); vertIndex = this.vertices.IndexOf(selected.getEdge(selectedEdge)); vertsCopyB.Add(this.getVertex(vertIndex)); //Remove the edge to be split of each tile in its new VertGraph vertsCopyA[vertsCopyA.Count-1].removeEdge(selectedEdge); vertsCopyB[vertsCopyA.Count-1].removeEdge(selectedEdge); //and add the remaining tiles from referencing each edge of the vertex while avoiding nulls foreach(Vertex edge in vertsCopyA[vertsCopyA.Count-1].getEdges()) { if (edge != null) { vertIndex = this.vertices.IndexOf(edge); vertsCopyA.Add(this.vertices[vertIndex]); } } foreach(Vertex edge in vertsCopyB[vertsCopyB.Count-1].getEdges()) { if (edge != null) { vertIndex = this.vertices.IndexOf(edge); vertsCopyB.Add(this.vertices[vertIndex]); } } //one of the new VertsGraph replaces the original this.vertices = vertsCopyA; //the other is returned as a new VertGraph return new VertGraph("newGraph",vertsCopyB); //If on same side as vertices[0], copy this side of the bond //else copy the other side of the bond } public void shiftVertexList(){ Vertex tempVertex; tempVertex = this.vertices[0]; for (int i = 0; i < this.vertices.Count-1;i++) this.vertices[i] = this.vertices[i+1]; this.vertices[this.vertices.Count-1] = tempVertex; } /* public void makeRelativeMatrix(){ bool[] relEdges = findPendants()[0].getRelativeEdges(); int edgeIndex = 0; while (relEdges[edgeIndex] == false){edgeIndex++;} for(int j = 0; j < edgeIndex; j++) shiftRelativeEdges(); }*/ public bool isSimilarTo(VertGraph otherGraph){ //makeRelativeAdjMatrix for this graph //make adjMtrx object for this graph //find first pendant //make adjMatrix 1,0,0,0,0 where 1 connects to the only edge //connected edge position is true for index 0 in adjmatrix // all other connected edges are true for their relative positions using modulus to wrap around the array //use recursion to get all tiles //loop through each pendant of otherGraph to makeRelativeAdjMatrix // and compare to adjMatrix for this instance of graph // return true of it comes across a match // return false if loop ends without a match return false;} } class Program { static void Main(string[] args) { List tiles = makeTiles(); Console.WriteLine("Unshuffled Tiles"); //List thet tiles in columns of 8 using a modulus operator for(int i = 0; i < tiles.Count; i++){ Console.Write(tiles[i].getName()+ ", "); if (i%8 == 7) Console.WriteLine(""); } Console.WriteLine("----------------------------------------------------------------"+tiles.Count); //Removed Shuffle for Testing /*shuffleTiles(tiles); shuffleTiles(tiles); Console.WriteLine("Shuffled Tiles"); for(int i = 0; i < tiles.Count; i++) { Console.Write(tiles[i].getName()+ ", "); if (i%8 == 7) Console.WriteLine(""); } Console.WriteLine("----------------------------------------------------------------"+tiles.Count); */ //Use the addVertex of the VertGraph function to assemble a group of tiles called firstGraph VertGraph firstGraph = constructFirstGraph(tiles); //List thet tiles left to make the sprot Objective for(int i = 0; i < tiles.Count; i++){ Console.Write(tiles[i].getName()+ ", "); if (i%8 == 7) Console.WriteLine(""); } VertGraph sproutObjective = constructSproutObjective(tiles); //Split the graph into two, modifying the original and returning the second using the splitGraph method /* VertGraph newGraph = firstGraph.splitGraph(firstGraph.getVertex(0),0); */ Console.WriteLine(); firstGraph.printVertices(); sproutObjective.printVertices(); //newGraph.printVertices(); Console.WriteLine("----------------------------------------------------------------"+tiles.Count); } static List makeTiles(){ //Make 64 tiles by creating 4 tiles each for the given string names string[] tileStrings = { "IEQAB", "IPCOG", "IRDAT", "IZNXL", "KECOT", "KPQHL", "KRNXB", "KZDHG", "MEDHL", "MPQAG", "MRCOL", "MZNOB", "YECXG", "YPNXT", "YRDHB", "YZQAT" }; List tiles = new List(); int tileID = 0; foreach(string name in tileStrings){ for (int i = 0; i < 4; i++){ //create instances of each of the tiles using the Vertex class tileID ++; tiles.Add(new Vertex(name,5, new Vertex[]{null , null , null , null , null },tileID)); } } return tiles; } static void shuffleTiles(List tiles){ //Randomly pull from 64 and place it at the end, then randomly pull from 1 less and stick it on the bottom Random rnd = new Random(); Vertex tileShifter; int thisRand; for(int i = tiles.Count-1; i > 0; i--) { thisRand = rnd.Next(0,i); tileShifter = tiles[thisRand]; tiles.RemoveAt(thisRand); tiles.Add(tileShifter); } } static void countTiles(List tiles, string[] tileStrings){ //for each of the names in tileString look through each Vertex name in tiles and count and display the number of occurances int nameCount; int enterCounter = 0; foreach(string name in tileStrings) { nameCount = 0; Console.Write(name); foreach(Vertex vert in tiles) { if(vert.getName() == name) { nameCount +=1; } } Console.Write(": "+ nameCount+" "); enterCounter++; if (enterCounter%4 ==0) Console.Write("\n"); } } static Vertex pullTile(List tiles, int index = 0){ //copy a tile into a temp Vertex variable, remove that tile from the tiles List and return the temp Vertex Vertex pulledTile; pulledTile = tiles[index]; tiles.RemoveAt(index); return pulledTile; } static VertGraph constructFirstGraph(List tiles){ //Create the initial List to place in the vertGraph List paramenter then use VertGraph AddVertices method to create the graph //Count the tiles list to make sure that each tile laid is removing one from the tile List //return the complete VertGraph to the program. List startVertex = new List(); startVertex.Add(pullTile(tiles)); VertGraph firstGraph = new VertGraph("firstGraph",startVertex); firstGraph.addVertex(pullTile(tiles,3),0,firstGraph.getVertex(0),0); firstGraph.addVertex(pullTile(tiles,14),3,firstGraph.getVertex(1),3); firstGraph.addVertex(pullTile(tiles,25),4,firstGraph.getVertex(1),4); //removing to test sprout detection /* firstGraph.addVertex(pullTile(tiles,59),2,firstGraph.getVertex(0),2); firstGraph.printVertices(); Console.WriteLine("----------------------------------------------------------------"+tiles.Count); */ return firstGraph; } static VertGraph constructSproutObjective(List tiles){ List startVertex = new List(); startVertex.Add(pullTile(tiles,26)); VertGraph sproutGraph = new VertGraph("sproutObjective",startVertex); sproutGraph.addVertex(pullTile(tiles,6),2,sproutGraph.getVertex(0),2); sproutGraph.addVertex(pullTile(tiles,32),3,sproutGraph.getVertex(1),3); sproutGraph.addVertex(pullTile(tiles,56),4,sproutGraph.getVertex(1),4); return sproutGraph; } }

undirectedGraph