CSE 373: Data Structures and Algorithms

Autumn 1994

Programming Assignment 3

  
Due at the start of class on Monday December 5.
  
  Write a program that takes undirected graphs as input, and for
  each graph, prints an Eulerian path or circuit if one exists (and
  some message of one doesn't), using an O(V+E) algorithm.
  
  As you know, the basic algorithm has the following components:
  
  - Read the input and create an adjacency list representation.
  
  - Use the necessary and sufficient conditions to determine
    whether the graph has an Eulerian circuit, an Eulerian path
    (and its starting point), or neither.
  
  - Assuming that an Eulerian circuit or path exists, conduct a
    sequence of depth-first searches, splicing together the
    resulting circuits/paths, until all edges have been traversed.
  
  - Print the result.
  
  As you also know, there are a set of slightly tricky issues that
  arise:
  
  - Making sure that edges don't get traversed twice (either from
    the same vertex or from opposite vertices).
  
  - Deciding where to begin each depth-first search.
  
  - Figuring out how to splice the circuits/paths.
  
  These issues are not too hard to deal with if you're not too
  concerned with efficiency (that is, if you're content to produce
  an O(V**2) algorithm), but they're considerably more challenging if
  you're seeking an efficient (O(V+E)) algorithm.
  
  My earnest suggestion is that you get this working as an O(V**2)
  algorithm and then improve it to an O(V+E) algorithm.  There are
  plenty of headaches you'll have to deal with even in implementing
  the porky algorithm.  You'll have to read the input and construct
  the adjacency list representation.  You'll have to program depth-
  first search.  You'll have to maintain and splice the
  circuits/paths.   You'll have to clean up after yourself so that
  you're ready to process the next graph.  Etc.
  
  I'll provide some test data in the following format:
  
       [count of vertices]
       [vertex ID] [count of adjacent vertices] [ID of adjacent vertex] ...
       ...
  
  The input consists entirely of integers.  If the count of
  vertices is 0, that denotes the end of the input.  Vertex IDs
  appear in order, both "down" (the "root vertex" of the adjacency
  list) and "across" (the adjacent vertices).  Since it's an
  undirected graph, each edge appears only once in the input, in
  the adjacency list of the lower-numbered vertex to which it's
  incident.
  
  The test data will be found in ~c373/graph/test.  It's not there
  yet, but don't let its absence keep you from getting to work!
  
  You should submit:
  
  - A listing of your program.
  - A listing of the output.
  - A writeup analyzing the running time of your algorithm, in
    detail.
  
  This assignment should provide a good exercise of your data
  structure skills.