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 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:
- The first line of the file will be a number n, indicating
the total number of points in the graph.
- The remaining lines of the file will contain two numbers
between 0 and n-1. Each pair of numbers corresponds to an
edge in the graph; the numbers indicate which vertices form the
endpoints of the edge.
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:
- What are the objects in your program? Edges? Tours? There
are many different ways to decompose the problem.
- How will you know when you've succeeded?
- How will you know if no such tour exists?
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
-
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.
-
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