Click here to Skip to main content
15,848,393 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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;
    std::vector<Vertex*> adjacents;
    void addAdjacent(Vertex *v);
    unsigned int numAdjacent() const { return this->adjacents.size(); }
};

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)
    {
        return (a->numAdjacent() < b->numAdjacent());
    }
public:
    //mutators
    void addVertex(Vertex *v);
    void addVertex(char c);
    void addEdge(std::pair<Vertex*, Vertex*> p);
    void addEdge(Vertex* a, Vertex* b);
    void addEdge(char a, char b);
    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)
    {
        if (a.getVertex(i)->numAdjacent() != b.getVertex(i)->numAdjacent())
            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

1 solution

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.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900