Graph isomorphism code (explanation follows)

[B.H.]

This code is very drafty; it took longer than I thought and I wanted to go for speed. It took a total of 63 minutes; there might be mistakes, I didn't get a chance to check it and/or fix it. It represents what I can get done in 63 minutes. I'll explain the algorithm in a subsequent post. On the job, I might start by coding something like this and then fix the code...or, I might plan more carefully. Here is the code:

------------


#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

struct graph;
struct node;
struct tree;
struct edge;

void readTwoGraphsFromFile(graph & a, graph & b, string filename);

bool graphsAreIsomorphic(graph a, graph b);

void attachAllNodes(graph a, tree & helper, int index, int counter);

void attachChild(graph a, int label, tree & helper);

bool operator == (tree a, tree b);

int strToInt(string str);



struct node
{
int ID;
};

struct edge
{
node from;
node to;
};

struct graph
{
vector <edge> allEdges;
vector <node> allNodes;
};


struct tree
{
vector <tree> children;
node thisNode;
};




int main()
{
int c;
graph a, b;
readTwoGraphsFromFile(a,b,"input.txt");
cout << graphsAreIsomorphic(a,b);
cin >> c;

return 0;
}


bool graphsAreIsomorphic(graph a, graph b)
{
tree helper;
vector <tree> allAtrees;
vector <tree> allBtrees;
for (int i = 0; i < a.allNodes.size(); i++)
{
// Construct a tree from each node.
helper.thisNode.ID = a.allNodes[i].ID;

// Attach each node as a child to the appropriate parent nodes in the graph/tree.

// Find all the children of the initial node; use a recursive process to connect them all.

attachAllNodes(a,helper,i,a.allNodes.size());

allAtrees.push_back(helper);
}

for (int i = 0; i < b.allNodes.size(); i++)
{
helper.thisNode.ID = b.allNodes[i].ID;

attachAllNodes(b,helper,i,b.allNodes.size());

allAtrees.push_back(helper);
}

bool flag = false;
bool changeFlag = true;
do
{
for (int i = 0; i < allAtrees.size() && !flag; i++)
{
for (int j = 0; j < allBtrees.size() && !flag; j++)
{
if (allAtrees[i] == allBtrees[j])
{
for (int k = i; k < allAtrees.size()-1; k++)
{
allAtrees[k] = allAtrees[k+1];
}
for (int k = j; k < allBtrees.size()-1; k++)
{
allBtrees[k] = allBtrees[k+1];
}
}
}
}
if (flag != true)
{
changeFlag = false;
}
} while (changeFlag == true);

if (allAtrees.size() == 0 && allBtrees.size() == 0) // the trees matched
{
return true;
}
return false;
}



void attachChild(graph a, int label, tree & helper)
{
helper.children.resize(helper.children.size()+1);
helper.children[helper.children.size()-1].thisNode.ID = label;
}


void attachAllNodes(graph a, tree & helper, int index, int counter)
{
if (counter < 0)
{
return; // The recursion is done.
}
int k, val;
for (int j = 0; j < a.allEdges.size(); j++)
{
if (helper.thisNode.ID == a.allEdges[j].from.ID)
{
attachChild(a,a.allEdges[j].to.ID,helper);
}
for (k = 0; k < a.allNodes.size(); k++)
{
if (a.allNodes[k].ID == a.allEdges[k].to.ID)
{
val = k;
}
}
attachAllNodes(a,helper.children[helper.children.size()-1],val, counter-1);
}
}

void readTwoGraphsFromFile(graph & a, graph & b, string filename)
{
ifstream inFile(filename);
if (!inFile.is_open())
{
cout << "ERROR, file not found.";
exit(0);
}
else
{
string str;
int i;
do
{
i = 0;
inFile >> str;
if (str != "#")
{
a.allNodes[i++].ID = strToInt(str);
}
} while (str != "#");
do
{
i = 0;
inFile >> str;
if (str != "#")
{
a.allEdges[i++].from.ID = strToInt(str);
a.allEdges[i++].to.ID = strToInt(str);
}
} while (str != "#");
do
{
i = 0;
inFile >> str;
if (str != "#")
{
b.allNodes[i++].ID = strToInt(str);
}
} while (str != "#");
do
{
i = 0;
inFile >> str;
if (str != "#")
{
b.allEdges[i++].from.ID = strToInt(str);
b.allEdges[i++].to.ID = strToInt(str);
}
} while (str != "#");
}
}

bool operator == (tree a, tree b)
{
return (a.thisNode.ID == b.thisNode.ID && a.children == b.children);
}


int strToInt(string str)
{
int num = 0;
for (int i = 0; i < str.size(); i++)
{
num += str[i] - '0';
num *= 10;
}
return num / 10;
}

[B.H.]

So as I think I said, I barely checked the code. Again, it's to represent what I can currently do with a challenging task in 63 minutes, working as fast as I can.

The idea for the graph isomorphism algorithm was: Turn each node in each graph into the root node of a tree, and try to track/include cycles. Each tree should in the first graph should be identical to one tree in the second graph if and only if the graphs are isomorphic. I just noticed that in this code, I forgot to sort the nodes by label, for one thing. So the code isn't perfect for sure. The idea appears to be good, although I didn't write out a journal-ready proof. There's a second "confirmation step" that can be omitted because it's trivial, too.

-Philip White (philip...@yahoo.com)