Tree isomorphism implementation
Isomorphism of graphs in general and also an isomorphism of trees is definitely not a trivial problem. The task was to implement an effective algorithm to find out isomorphism of general trees (both rooted and not-rooted). The main algorithm runs in Θ(nlog(n)) time where n is the number of vertices in each tree.
I based my solution on [1].
Implementation
Implementation was done in C++ using plain text files as input for compared trees. Source code should be fully portable across different platforms. Compilation and testing was done with:
- Compiling: gcc version 4.2.1 (SUSE Linux) (Target: x86_64-suse-linux)
- Memory consistency check: valgrind-3.2.3
Archive
Files in archive: tree-isomorphism.zip (zip, 47,4 KB)
- bin - contains linux build (x64)
- src - contains source files
- test - contains input files of test trees
- build.sh - build script - run build.sh in bash to compile bin/treeIsomorphism binary - uses g++.
- index.html - this manual
Input files
Syntax of input files is very simple, is created by: number of vertices
on the first line and the neighborhood matrix on following lines.
Example of not-rooted tree file:
#3
0 1 0
1 0 1
0 1 0
Exaple of not-rooted tree file - equivalent form:
#3
0 1 0 1 0 1 0 1 0
Both above neighborhood matrices represent simple tree:
(1)--(2)--(3)
Each number of node is given by it's order in neighborhood matrix.
Example of rooted tree file:
#4
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0
This neighborhood matrix represents simple rooted tree:
(1)-->(2)-->(3)-->(4)
Usage
./treeIsomorphism (-h) (-H) (-m) (-r) [ path to 1. tree ] [ path to 2. tree]
-h This help.
-H Human readable output.
-m Display also mapping if trees are isomorphic.
-r Trees provided by neighborhood matrix are already rooted.
Parametrs () are optional, both paths to input files are required.
Examples of usage:
treeIsomorphism -h
treeIsomorphism -m -H test/tree1 test/tree2
treeIsomorphism -r test/rootedTree1 /test/rootedTree2
Test data
There are prepared testing data in
the "test" directory. There are examples for both not-rooted (tree1
tree2) and rooted trees (rootedTree1 rootedTree2).
Not-rooted trees:
The input files contain this two (obviously isomorphic) trees:
bin/treeIsomorphism -H -m test/tree1 test/tree2
Example output:
Trees are isomorphic
Mapping
============================================================
0,0
3,2
8,6
2,1
7,4
6,5
12,9
1,3
5,7
11,10
4,8
9,11
10,12
============================================================
Rooted trees:
The input files contain this two (obviously non-isomorphic) trees:
-->(2)
(1)
-->(3)(1)-->(2)-->(3)
bin/treeIsomorphism -r -H -m test/rootedTree1 test/rootedTree2
Example output:
Trees are NOT isomorphic
References
- Matthew Suderman, Tree Isomorphism,
http://crypto.cs.mcgill.ca/~crepeau/CS250/2004/HW5+.pdf - Website of subject X36TIN,
http://service.felk.cvut.cz/courses/36TI
RSS Feed