Programming Assignment 3: Graph Matching

Due: Wednesday, June 4 at 5:00 PM

ReadGraph.java
some Java code to help you read a graph from a file, also check out Sample.java
ReadGraph.c
some C++ code to help you read a graph from a file, also check out Sample.cpp
graphs.zip
several graph data files for testing your program
pictures.zip
pictures of the above graphs, useful for debugging

Overview

This project is related to the problem of recognizing objects in images. Given a known object and a new image, we want to determine whether or not that object is present in the image. Both the image and the object are represented as graphs, where a node corresponds to a region of pixels and the edges correspond to adjacencies between regions.

Suppose we have a model graph GM (the object) and an image graph GD (the image). With this representation, the problem reduces to:

Suppose GM has vertices {1,2,3,...,n1} and GD has vertices {1,2,3,...,n2}, where n1 <= n2. Then, a mapping f(v) can be expressed as a set of pairs {(1,i1),(2,i2),(3,i3),(n1,in1)} such that every vertex in GM is mapped to exactly one vertex in GD. The error in a mapping is simply the number of edges (u,v) in GM for which (f(u),f(v)) is not an edge in GD.

What You Need To Do

Part 1

Use a backtracking tree search to find all copies of GM in GD. In other words, find all mappings with zero error. If there are none, output a message reporting this.

Part 2

Use the branch-and-bound technique to find the best mapping from GM to GD (the one with the least error). The pseudocode for this can be found here.

Write a program that can be executed from the command line with 

	Match gmfile gdfile p|b

for C++, or 

	java Match gmfile gdfile p|b

for Java. The gmfile and gdfile arguments should be the names of two files that contain graphs (see the format specified below). The third argument should be p to list all perfect matchings, or b to find the best matching.

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 

	Match triangle.graph kite.graph p

should output something like 

	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 NO ISOMORPHISMS. The command 

	Match triangle.graph kite.graph b

should output something like 

MATCHING: (1,2),(2,3),(3,4)
ERROR: 0

since in this case we have a perfect match. In fact, we have several perfect matches. You should output the first one you find. More generally, if multiple matchings have the minimum error, you should only output the first one you find.

What To Turn In

You should turn in the following:

All of the above files are included in the graphs.zip archive.

Please print out the readme file and your output, and bring it to class on the due date.

Bonus

Use your program to discover the longest tour one can make around the United States (by land) without visiting any state more than once. You also have to end up in the state you started in. List all the states on this tour, in order.

In order to answer this question, you may need to construct some new graph files. You could also modify your program, but you don't have to.