Implement a backtracking tree search to find all copies of GM
in GD. In other words, find all mappings with zero
error. The pseudo-code for this algorithm was given in the Friday May 17th lecture.
Write a program that can be executed from the command line with
java Match gmfile gdfile
The gmfile and gdfile arguments should be the
names of two files that contain graphs (see the format specified below).
Details
Reading the Graphs
You will need to read the graphs from two files, one for each graph. The
graphs are undirected, and the nodes are labeled between 1 and the
number of nodes, which is specified in the file. The file format is as
follows:
GRAPH NAME (a string)
N (the number of nodes, an integer)
M (the number of edges, an integer)
U1 V1 (two node labels specifying an edge, both integers)
U2 V2
U3 V3
.
.
.
UM VM
For example, a graph file might look like:
triangle
3
3
1 2
1 3
2 3
|
|
|
or
|
kite
4
4
1 2
2 3
2 4
3 4
|
|
|
Output
Suppose the above two graphs are stored in files triangle.graph
and kite.graph. Then, the command
java Match triangle.graph kite.graph
should output
ISOMORPHISM: {(1,2),(2,3),(3,4)}
ISOMORPHISM: {(1,2),(2,4),(3,3)}
ISOMORPHISM: {(1,3),(2,2),(3,4)}
ISOMORPHISM: {(1,3),(2,4),(3,2)}
ISOMORPHISM: {(1,4),(2,2),(3,3)}
ISOMORPHISM: {(1,4),(2,3),(3,2)}
If there are no isomorphisms, output nothing.
What To Turn In
You should turn in the following:
- a readme file describing what you did
- all of your code
- the output you get for each of the following invocations of your
program:
- java Match small_house.graph big_house.graph (2 expected.)
- java Match c4.graph small_house.graph (16 expected).
- java Match k4.graph big_house.graph (0 expected).
For your own amusement, you can try
- java Match k5.graph usa.graph
All of the above files are included in the graphs.zip archive. You can use the triangle and
kite graphs to help debug your program.
And Remember.....
- Your java class which contains the main method must be named Match
- Your program must take in two input filenames in the same
order as stated earlier in this document. You can refer to your
earlier projects or the sample file given to you with this project
to figure out: how command line arguments are passed.
- Please make sure you follow the output format as closely as possible.
Some sample outputs for your comparison
Comparing k5.graph to usa.graph gives this
Comparing triangle.graph to k4.graph gives this
Comparing small_house.graph to usa.graph gives this