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

On Saturday, July 30, 2022 at 4:20:41 PM UTC-4, B.H. wrote:
> 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;
> }

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 (philipjwhite@yahoo.com)