CPSC-102: Computing and Algorithms II

Programming Assignment 2

Summer 1998

In this programming assignment, you will demonstrate your knowledge of recursion and problem solving by attempting to find an Euler tour in a given input graph.

Introduction

One of the most famous puzzles in the history of mathematics is the story of the Seven Bridges of Königsberg. In the 18th century, the city of Königsberg had seven bridges which spanned the river which passed through the town:

[The
The puzzle that was proposed was the following. Pick any point on land. Is it possible to walk over the seven bridges exactly once and end up back at the starting point?

This puzzle entertained a number of people of years, notably the great mathematician Leonhard Euler (pronounced ``oiler''), who proved that the problem was impossible. His study of this puzzle (and others) lead to the development of much of modern graph theory.

Introduction to Graph Theory

For purposes of this problem, a graph is a collection of points and a collection of edges. Each edge connects two points of the graph.

A path in a graph is a sequence of points p1, p2, ..., pk such that every pair of adjacent points is connected by an edge of the graphy. A circuit in a graph is a path in which the first and last points in the path are identical. An Euler tour in a graph is a circuit in which every edge of the graph is used exactly once. Thus, the problem of the Seven Bridges of Königsburg was to find an Euler tour of the town, where the land masses were the points in the graph and the bridges were the edges.

Your program will take a graph supplied by the user and attempt to construct an Euler tour in the graph.

File Input

Your program will accept a single argument on the command line, which is a non-empty string giving the name of a file in the current directory. That file will contain a description of a graph organized as follows:

For example, the Seven Bridges of Königsburg could be represented as follows: 
4
0 1
0 1
1 2
1 2
0 3
1 3
2 3
(Notice that one may have multiple edges between a given pair of points.)

Your program will then attempt to construct an Euler tour for that graph. If such a tour exists, your program will print out the tour in an appropriate (i.e. readable) format. If no such tour can be found, your program will print out an appropriate message stating that fact.

Internal Requirements

As always, your program should use good style, as defined by the CPSC-102 Style Requirements handout; it should validate input whenever possible; and it should catch all checked exceptions.

Your program should utilize a recursive-backtracking methodology to find the tour. That is, given a partial tour, your program should try all possible single-step moves to extend that tour, recursively checking each choice to see if it completed the tour. If no choice can possibly help create a tour, your program should ``backtrack'' to a previous level and try again.

Some questions to think about:

Submitting Your Program

Before 11:59:59 p.m., Thursday, 30 July 1998 (4th Thursday), you must email a single file to jhuggins@kettering.edu containing all source code files for your program, including a file named Prog2.java containing a main method.

In addition, you must deliver to the instructor a printout of your program files at the start of class on Friday, 31 July 1998 (4th Friday).

Notes

  1. The class java.util.StringTokenizer will take a String object and break it up into its blank-delimited components. This may be the easiest way to read a line corresponding to an edge and subdivide it into its two components. See the Java API for details.

  2. Remember that an edge is a two-way street; an edge numbered (0,1) can be traveled both from 0 to 1 or from 1 to 0, whichever is most beneficial for the tour.
Jim Huggins / jhuggins@kettering.edu
last updated: 16 July 1998