CSCI 311

Spring 2006

Program 3: Graph with minimal spanning tree

Due: 19 May 2006 by Midnight.

The sample program is in written in C++. Consequently it only runs on jaguar.

If you find anything inconsistant with either this document or the tests send me email.

Overview:

You are to implement an undirected graph. See my sample program.
You will use the STL map data structure to implement your adjacency matrix.
If you haven't used C++ STL classes before then you must make it a point to attend lab.
STL classes are templetized and generate some interesting compiler output when you have a syntax error.

I haven't decided how the points will be dished out on this one.
As usual there is NO PARTIAL CREDIT. You get points for each test you pass.
The algorithm to generate a spanning tree (itself another instance of your graph class) is on page 592 Kruse.

Name your executable 'graph'.

Since this is an undirected graph when you insert and edge connecting two vertices you must actually add two edges.
One is from the source to the destination.
The other is from the destination to the source

Output:

You will note that the sample program prints out stuff to stderr too.

Send it to /dev/null to see only the testable outpu: 


$./example_graph < tests/t01 2>/dev/null
Your output will have the following format for the graph described below: 
//////////////////////////////////////////
// You don't ouput this fancy ascii Graph
//
//                [3]
//               /   \
//              /     \
//             / /[0]\ \
//            / / / \ \ \
//           / /[1]-[5]\ \
//          / / /     \ \ \
//         / //         \\ \
//        [2]-------------[4]
//////////////////////////////////////////
added vertex: 0
added vertex: 1
added vertex: 2
added vertex: 3
added vertex: 4
added vertex: 5
added edge: 3 to 4, cost=4
added edge: 4 to 2, cost=2
added edge: 2 to 3, cost=4
added edge: 0 to 3, cost=3
added edge: 2 to 0, cost=3
added edge: 1 to 0, cost=3
added edge: 5 to 0, cost=3
added edge: 0 to 4, cost=3
added edge: 2 to 1, cost=2
added edge: 1 to 5, cost=2
added edge: 5 to 4, cost=1
///////////////////////////////////////////////////////////////
// here the graph gets printed
///////////////////////////////////////////////////////////////
Graph:
Vertex: 0
    1, cost=3
    2, cost=3
    3, cost=3
    4, cost=3
    5, cost=3
Vertex: 1
    0, cost=3
    2, cost=2
    5, cost=2
Vertex: 2
    0, cost=3
    1, cost=2
    3, cost=4
    4, cost=2
Vertex: 3
    0, cost=3
    2, cost=4
    4, cost=4
Vertex: 4
    0, cost=3
    2, cost=2
    3, cost=4
    5, cost=1
Vertex: 5
    0, cost=3
    1, cost=2
    4, cost=1
///////////////////////////////////////////////////////////////
// here the spanning tree generated from the graph gets printed
///////////////////////////////////////////////////////////////
Graph:
Vertex: 0
    1, cost=3
    3, cost=3
Vertex: 1
    0, cost=3
    2, cost=2
Vertex: 2
    1, cost=2
    4, cost=2
Vertex: 3
    0, cost=3
Vertex: 4
    2, cost=2
    5, cost=1
Vertex: 5
    4, cost=1

As you can see the output is verbose like always.

Input:

Your main.cpp will read in the commands from standard input again.

Input summary:


NOTE:numbers you do not need to worry about negative numbers
NOTE:assume all input will be formatted correctly

'/....'		comments.  Yes put comments in your test inputs
'V' string                  add Vertex
'P'                         print Vertexes only
'E' string string number    add Edge
'F' string                  print edges for the listed vertex
'S' string                  print the spanning tree starting from listed vertx
'M'                         print adjacency Matrix

You main.cpp will output to stdout. This way you can redirect your output to a file of your choosing.

You may output whatever you like to cerr. cerr is just like cout except that when you write to it with << it can be redirectly separately. You can still see it print out normally because cerr by default goes to the same place as cout. 


$graph < tests/t01 > tests/t01.out 2> tests/t01.cerr
Would redirect cerr to a file called t01.cerr in the tests subdirectory.
$cat tests/t01.cerr

Here is an in depth break down of the commands:

Lines that begin with '/' are comments until the end of the line


V sacramento

You need to echo that a vertex was added to the graph:

added vertex: sacramento

You need to output this message if the vertex being added is already in the graph:

duplicate vertex: sacramento



E sacramento reno 1099

If you can successfully add this edge echo that an edge between the two vertices was added:

added edge: sacramento to reno, cost=1099

When either of the vertices used with the add edge command are not in the graph output:

"string" is not a vertex

When there already is an edge between the two vertices output:

duplicate edge: vertex1 to vertex2, cost=1


S sacramento

This is the spanning tree command.  Print out the new graph created.

When the vertex specified after the 'S' Command is not in the graph output:

sacramento is not a vertex


P

This command prints only the vertices of the graph in the order maintained by the map object:

Vertex:(0)-->sacramento

Format: (number) is just to help you see the count

The string after the "-->" is the vertex name.


F sacramento

Print out ALL the edges of the specified vertex

Vertex: sacramento
    reno, cost=1099
    stockton, cost=90

When a non-existant vertex is specified output:

<vertex> is not a vertex

When the vertex after the 'F' command has no edges:

<vertex> has no edges


M

This command prints the entire graph, that is all vertices and all edges.

Print out a header: Graph:
Then print out each vertex left justified and then indent over for each of that vertex's edges:

Graph:
Vertex: sacramento
    reno, cost=1099
Vertex: reno
    sacramento, cost=1099


When the graph is empty:

Graph:
graph is empty

How to test your program:

**TIPS** First set up your ecst account with a SSH key. Second prefer to logon to jaguar.ecst.csuchico.edu Third add a rule to your Makefile that looks like this: 


tests:
    rm -i tests/*
    scp username@jaguar.ecst.csuchico.edu:/user/s4/admiral/p3_tests.tar .
    tar xvf p3_tests.tar
Now you can get the latest test just by typing:
$make tests

To obtain the tests manually when logged into your ecst account. 

$cp /user/s4/admiral/p2_tests.tar .
$tar xvf p1_tests.tar
Please familiarize yourself with how the program is to behave by giving my sample program a test drive:

$./example_graph
Manual Example of verifying your output matches mine: 
$./example_graph< tests/t01 > tests/t01.myout
$diff tests/t01.myout test/t01.out
$
The diff command will output nothing if your output matches mine. However if there are differences diff will tell you which lines are your file but not mine and vice versa. 
<......    means this is only in the first file NOT the second
>......    means this is only in the second file NOT the first

Diff will be the basis of how I will test your program's outputs against my absolutely 100% correct output.

Again you will find a perl script to run all the tests. 

$./run_p3_tests
I advise running the script after every change you make to your program. You can edit the script with your text editor to change the directory where it looks for files and the program it uses to generate your outputs.

How to submit the program:

You will find a turn-in directory under:
/user/projects/csci311/p3/your-user-name
All your .cpp and .h files and your Makefile should be turned in.
I will compile your programs when I grade them so DO NOT turn in an executable or any .o files.
This time I want you to provide a clean: rule in your make file. Looks like this: 


clean:
    rm -f *.o graph

I would advise you to make a rule for copying your program into the turn directory. Use it whenever you hit a major milestone in your program. 


turn_in:
    cp *.cpp *.h Makefile /user/projects/csci311/p1/user_name
To automatically copy your program into the turn directory type: 

$make turn_in

Debugging

Compiler:

First you will want to turn on compiler warnings:

Makefile:
graph: main.o graph.o
	g++ -g -Wall -o main.o graph.o

main.o: main.cpp graph.o
    g++ -g -Wall -c main.cpp
.
.
.

Debugger:

When you encounter segmentation faults don't panic. You will get many of these. They are just minor annoyances.

What to do when you get one: 


$graph < tests/t01
Segmentation fault
$
Start the debugger, gdb on your file like so: 

$gdb graph
Now you are inside the dugger. The prompt is (gdb) 

(gdb)
use the run command of the debugger. Pass in the usual arguements such as which test to use as input: 

(gdb) run < tests/t01
.
normal output....
.
Program received signal SIGSEGV, Segmentation fault.
0x0804b4e4 in Node::print (this=0x0) at node.cpp:9
Now sometimes the line number and file are useful and sometimes not. In this case the source file where the segmentation fault occured is node.cpp, the line number is 9.

Notice that the this pointer is NULL (0x0 is Hexidecimal for 0). To find out more about how Node::print() was called on a NULL pointer use the where command to observe the runtime stack: 

(gdb) where
#0  0x0804b4e4 in Node::print (this=0x0) at node.cpp:9
#1  0x0804bc95 in Node::push_in (this=0x8050008, new_value=1, new_pointer=0x0, position=0)
    at node.cpp:153
#2  0x080494e0 in B_tree::push_down (this=0xbffa7d0c, node=0x8050008, new_value=1,
    insert_value=@0xbffa7cc8, insert_branch=@0xbffa7ccc) at btree.cpp:193
#3  0x08049bb2 in B_tree::insert (this=0xbffa7d0c, new_value=1) at btree.cpp:22
#4  0x08048cec in main (argv=0x1, argc=-1074102860) at main.cpp:41

runtime stack:
==================
Node::print()
Node::push_in()
B_tree::push_down()
B_tree::insert()
main()
Now we are talking! Files, line numbers. So Node::push_in() called print() on a null pointer from line 153. This is usually enough to figure out what happened.

If you need more info use the frame command to dive into a function on the stack to query the values of variables: 

(gdb) frame 1

(gdb) print variable
$1 = (Node*) 0x0

Late assignments:

I will not be accepting late assignments.

What I want from you is to turn in what you have.

Please add a README to your turn in directory explaining what isn't working. This is not required if you have everything working.

If you don't include a README I will not give you partial credit. I probably won't give you partial credit anyway. However if can tell me how to fix what is broken with your program I would give you the points for that test.

"Turn off" any portions of your code that are broken so that what I get from you will compile.