Isomorphic Graphs?

[fg109]

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):

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;
}

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)?

[keskiverto]

Which part of Wikipedia did you read? This?
http://en.m.wikipedia.org/wiki/Graph_isomorphism_problem

[fg109]

I read this:

http://en.wikipedia.org/wiki/Graph_isomorphism

The analogy with beads and strings is just something I came up with. Is my understanding of it wrong?

EDIT: Thanks for the link. I'll be looking through the linked algorithms "McKay (1981), Schmidt & Druffel (1976), Ullman (1976)".