This project determines whether two graphs are isomorphic, and, if so, outputs the permutation required to change one graph to the other. We first find the strongly connected components. Then SCCs of each graph are mapped to each other by in degree and out degree, and the number of vertices and edges in each SCC. Then the vertices of each stronly connected component are mapped to the vertices of the SCC of the other graph that maps to this SCC by in degree, out degree, and the characteristics of their neighbors. If applying this last heuristic find a better mapping for a certain vertex then it is applied again, until this heuristic does not find a better mapping for any vertex. If there are still any vertices left which have not been mapped to just one vertex, first we check for circular component of the graph. Those vertices that are in circular components can be immediately mapped from the first to the second graph. For the remaining vertices, we generate permutations using the given permutation generating code, and then check to see if the permutation successfully maps graph 1 to graph 2.
The code for this project contains about 1500 lines of code in C++. The story of its creation is one of my favorite "Tales From the Life of an EECS Major." Basically, the project was written over 3 days and 2 nights of nonstop coding. Neither of us working on the project knew any C++ when we started, and both of us were simultaneously working on projects for other classes due around the same time.
Report available in text.
Also available the code (compiles with gcc 2.x) and graphs used in the project. zip
Given two files, this project determines the minimum set of changes that need to be made to file 1 to change it into file 2. The core of the diff finder is the computation of the longest common subsequence; our algorithm uses a divide-and-conquer approach to reduce the space complexity from O(n2) to O(n log n)
Report available in text.
Also available the code and graphs used in the project. zip