15,848,393 members
See more:
My instructor told my class that we have to write a program that checks whether or not two graphs are isomorphic. I'm not asking for code, just wanted some ideas on algorithms. Just how exactly do I check if two graphs are isomorphic?

From reading on wikipedia two graphs are isomorphic if they are permutations of each other. Think of a graph as a bunch of beads connected by strings. If I could move the beads around without changing the number of beads or strings, or how they are connected, then the new "graph" would be isomorphic to the old one.

This is what I have so far (I left out the code in most of the functions):
C#
```struct Vertex
{
char ID;
};

class Graph
{
private:
std::vector<Vertex*> vertices;
std::vector< std::pair<Vertex*, Vertex*> > edges;
//going to use this to sort the list of vertices
static bool compareVertices(const Vertex *a, const Vertex *b)
{
}
public:
//mutators
void sortVertices()    { std::sort(vertices.begin(), vertices.end(), compareVertices); }
//accessors
unsigned int numVertices() const { return this->vertices.size(); }
unsigned int numEdges() const { return this->edges.size(); }
Vertex* getVertex(unsigned int i) { return vertices[i]; }
};

bool areIsomorphic(Graph &a, Graph &b)
{
if (a.numVertices() != b.numVertices())
return false;
if (a.numEdges() != b.numEdges())
return false;
a.sortVertices();
b.sortVertices();
for (unsigned int i = 0; i < a.numVertices(); ++i)
{
return false;
}
return true;
}```

What I have tried:

So I checked that they have the same amount of vertices and edges, and that there are similar amount of vertices that are connected to certain amounts of other vertices.

What's next? I can only think of going through the vertices one by one and checking all their connections. But I'm not quite sure how to do that.

What if I create a third graph in the function, then assign it all the edges from graph B, but using the IDs of the vertices in graph A (depending on numAdjacent() of the vertex from graph A and vertex from graph B)?
Posted
Updated 2-Oct-16 8:17am
v4

## Solution 1

You can build some vectors between some (special) points and check these vectors, whether they are parallel or have a common center.

Some interesting stuff you can read in the wikipedia and I found this The Graph Isomorphism Algorithm article from Ashay Dharwadker and John-Tagore Tevet which really looks impressive mathematics.