graph

Introduction

This is assignment 7 for a computer science class (CSIS 352) I took recently:

Write a C++ ADT for a graph. Allow for the Graph to be Weighted or Unweighted and either Directed or Undirected, declared in either order. The default is Unweighted and Undirected. These should be an enum (Keyword) type so the following declarations are valid syntax:

  • Graph<City> map(Directed, Weighted);
  • Graph<City> map(Weighted, Directed);
  • Graph<Something> graph(Directed);
  • Graph<Something> graph(Weighted);
  • Graph<AnotherType> graph;
  • etc.

Download

To download the source code it is easiest to use subversion. Simply use subversion to check out the trunk of the repository:

svn co http://svn.alunduil.com/svn/graph/trunk graph

The code is also browse-able online at my subversion repository.

Install

This program was created using Ubuntu Linux with a 2.6.17 kernel revision 11 on an x86 architecture. The compiler used for building and testing is gcc version 4.1.2 pre-release provided by the Ubuntu repositories.

To build this program, simply type 'make' which creates the default executable, prog7.

This program requires the Boost libraries, but all distributions I have seen come with this installed.

Description

This program utilizes the following algorithms and data types:

  1. STL's set
  2. STL's list
  3. Boost's tuple
  4. Boost's lambda
  5. STL's for_each
  6. STL's find_if
  7. Dijkstra's Shortest Path Algorithm

Input and Output

Input

CLI utility to find the shortest path between two nodes.

Output

Outputs the graph as a columnar list with arrows to each vertices' neighbors.

Example:

Dumping graph:
Number of Vertices: 12  Number of Edges: 29
Fargo -> Minneapolis:240
Minneapolis -> Fargo:240 -> Chicago:409 -> Denver:920
etc.

Then prompts for source and destination, and outputs the shortest path.

Program Testing

Checked several paths, and found only one problem with the input parameters.

Bugs

If the source or destination cities are not typed correctly the utility will hang. Looking at how to get an exception into the workings, but can't figure out where to place it right now.

If bugs are found please email Alex Brandt with a bugreport.