Instructions
User Manual:
Open the PDF directly: View PDF 
.
Page Count: 12
Project-1: Weighted Directed Graph
S15 CSCI 332 - Design and Analysis of Algorithms
Phillip J. Curtiss, Assistant Professor
Computer Science Department, Montana Tech
Museum Building, Room 105
January 22, 2016
Project-1: Due 2016-02-5 by midnight
Purpose: This assignment consists of two parts - implement the weighted digraph class and the graph test
driver program.
The WDiGraph class header file is supplied and contains basic graph ADT operations like create graph,
destroy graph, copy graph, add edge, remove edge, check if an edge exists, get an edge weight, etc. Most
of these operations are left to you to complete. Specifically, graph methods you need to finish are the copy
constructor, destructor, check if edge exists, add edge, get edge weight, and remove edge. Specifications for
each are provided in the interface header file. Make sure you review the documentation that specifies the
input, outputs, and exceptions. A UML diagram is also provided.
A driver program to test the graph class has been started, which you need to be complete. You will add
code so all menu options work properly and correctly handle all errors. A Makefile is supplied so you can
easily compile your program. You will be expected to create makefiles for all your programs, so make sure
you understand it.
Javadoc style documentation is used throughout and should be used to document any code you add.
When done, update the version to 1.0 and add your name to the author tag (or add a second @author tag
with your name).
The WDiGraph will be used in future programming assignments. You should be familiar with key
programming techniques you are expected to use good programming techniques learned in CSCI 232 for file
I/O, error handling, exceptions, JavaDoc style documentation, makefiles, etc.
You may create your own driver program, but please use the following numbers for the menu:
1. Print the size of the graph
2. Check if an edge is in the graph
3. Insert an edge into the graph
4. Delete an edge from the graph
5. Retrieve an edge weight
6. Display a copy of the graph
7. Quit the program
Objectives:
•Using UML Diagrams to Specify ADT
•Using existing C++ class methods
Project-1
S15 CSCI 332 - DAA Weighted Directed Graph
Assigned: 2016-01-22
Due: 2016-02-05 by midnight
Table 1: UML Specification for the Weighted DiGraph ADT
+getNumVertices (): int const
+getNumEdges ( ) : int
+getNumberOfNodes ( ) : i n t e g e r
+e d g e E x i s t s ( u : int , v : in t ) : bool
+getEdgeWeight( in u: int , in v : i nt ) : WtType
+add ( in u : int , in v : int , i n wt : WyType)
+remove ( in u : int , in v : in t )
•Using Class Inheritence
•Understanidng Class Inheritence Relationships
•Create methods that implement the WDiGraph ADTs
•Manipulate Lists of Complex Data Types
•Manipulate Linked List Structures
•Work with Pointers in C++
•Pass objects by reference
•Use C++ source file standards and doxygen to generate documentation
•Modify and add features to the provided main program
Obtaining the Project Files: You will complete the project using your own user account on the de-
partment’s linux system katie.mtech.edu. You should ssh into your account, and execute the command
mkdir -p csci332/proj1. This will make the directory proj1 inside the directory csci332, and also create
the directory csci332 if it does not yet exist - which it may from any previous project sessions. You should
then change the current working directory to proj1 by executing the command cd csci332/proj1. You can
test that you are in the correct current working directory by executing the command pwd which should print
something like /home/students/<username>/csci332/proj1, where <username> is replaced with the user-
name associated with your account. Lastly, execute the command tar -xzvf ~curtiss/csci332/proj1.tgz
and this will expand the project files from the archive into your current working directory. You may consult
man tar to learn about the archive utility and its command line options.
Building the Project: The project includes a basic Makefile you may use to generate the object files
from source code files. If you wisht to provide a test driver for your project, make sure to edit the Makefile
as needed. Consult the Makefile and understand the rules included and the dependencies and the rule sets
that are used to generate the executable program. Use caution when updating the Makefile to ensure rule
sets make sense.
Helpful Reminders: Study and pay close attention to the provided class(es) and methods. Understand
their return types and use them in the code you author to provide robust code that can handle exceptions to
inputs and boundary conditions. Look at all the code provided. Read the codes’s comments and implement
what is required where indicated. Make sure you are reusing code inside methods from inherited classes.
Be cognizant of the best practices we discussed in lecture and abide by good coding style - all of which will
be factored into the assessment and grade for this project. Be sure to review the UML diagram and the
Makefile and understand how files are being generated and their dependencies.
Philip J. Curtiss, Assistant Professor
Computer Science Department, Montana Tech
Page 2 of 12
Project-1
S15 CSCI 332 - DAA Weighted Directed Graph
Assigned: 2016-01-22
Due: 2016-02-05 by midnight
Submission of Project: You have been provided a Makefile for this project that will help you not only
build your project, but also submit the project in the correct format for assessment and grading. Toward
the bottom of the provided Makefile you should see lines that look like:
#Rule to sub mit programming a s si g nm en t s t o g r a d e r s
#Make sur e you modify the $ ( su bj ) $ ( msg ) above and the l i s t o f attachment
#f i l e s in the f o l l o w i n g r u l e −each f i l e needs to be p rece e ded with an
#−a f l a g as shown
subj = ”CSCI332 DDA −Proj1 ”
msg = ” Pl e a se rev i e w and grad e my P r o j e c t −3 Submission”
submit : l i s t i n g −A1 . cpp l i s t i n g −A2 . cpp
$ ( t a r ) $ (USER)−p r o j 1 . t g z $ ?
echo $ ( msg ) |$ ( mail ) −s $ ( su bj ) −a $ (USER)−p r o j 1 . t a r . gz $ ( addr )
Make sure you update the dependencies on the submit: line to ensure all the required files (source files)
are included in the archive that gets created and then attached to your email for submission. You do not
need to print out any of your program files - submitting them via email will date and time stamp them and
we shall know they come from your account. If you submit multiple versions, we will use the latest version
up to when the project is due.
Questions: If you have any questions, please do not hesitate to get in contact with either Phil Curtiss
(pjcurtiss@mtech.edu) or Ross Moon (rmoon@mtech.edu) at your convenicne, or stop by during office
hours, and/or avail yourself of the time in the MUS lab when Ross is available.
Project File Manifest:
WDiGraph Header
/∗∗ @ f i l e WDiGraph . h
∗Weighted Digraph C l a s s with ad j acenc y l i s t imp l eme ntat i on
∗Verte x i n d i c e s range from 0 t o numVertices −1
∗M u l t i pl e e dg es from one v e r t e x t o a no the r v e r t e x are no t a l lo w e d
∗
∗@author P h i l l i p J . Cu r ti ss
∗@versi on 0 . 95
∗@date 2016−01−22
∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗/
#i f n de f WDGRAPH H
#define WDGRAPHH
#include ” Gra p h I n t e r f a c e . h”
/∗∗ Weighted DiGraph −m atr ix i mp le me nta tion u si n g i n t e g e r v e r t e x l a b e l s ∗/
class WDiGraph : public GraphInterface<int>
{
public :
/∗∗ D ef au lt Constru ctor ( d e f a u l t s i z e i s 10 v e r t i c e s )
∗@pre The graph i s empty .
∗@post The graph i s i n i t i a l i z e d t o h o ld n v e r t i c e s . ∗/
WDiGraph( in t n=10);
/∗∗ Copy Co n s t r u c t o r
∗@param graph −t h e graph to copy . ∗/
Philip J. Curtiss, Assistant Professor
Computer Science Department, Montana Tech
Page 3 of 12
Project-1
S15 CSCI 332 - DAA Weighted Directed Graph
Assigned: 2016-01-22
Due: 2016-02-05 by midnight
WDiGraph( const WDiGraph& graph ) ;
/∗∗ Destructor . ∗/
vi rt ua l ˜WDiGraph ( ) ;
/∗∗ Determines th e number o f v e r t i c e s i n t h e graph .
∗@return The number o f v e r t i c e s in t h e graph . ∗/
int getNumVertices () const ;
/∗∗ D et er mi nes t h e number o f e d g es i n t h e gra ph .
∗@r eturn The number o f e d g e s i n t h e g ra ph . ∗/
int getNumEdges () const ;
bool add ( int s t a r t , i nt end , in t edgeweight )
throw (VertexOutOfRangeException );
bool remove ( in t s t a r t , int end )
throw (VertexOutOfRangeException );
bool e d g e E x i s t s ( in t s t a r t , in t end ) const
throw (VertexOutOfRangeException );
int getEdgeWeight ( int s t a r t , i nt end ) const
throw (VertexOutOfRangeException );
/∗∗ A ssi gnm ent o p e ra t o r o v e r l o a d f o r deep c opy o f r hs gr ap h
∗@pre The l h s and rhs graph s e x i s t
∗@post The l h s graph i s d e a l l o c a t e d and now c on ta in s t he r hs graph ∗/
WDiGraph& operator=(const WDiGraph& r h s ) ;
private :
int ∗data ; /∗∗ Dynamicly a l l o c a t e d c o n t i g u o u s d a ta b l o c k ∗/
int ∗ ∗ matrix ; /∗∗ 2D m atr ix t h a t p o i n t s t o rows i n da ta b l o c k ∗/
int numOfVertices ; /∗∗ Number o f v e r t i c e s i n t h e graph . ∗/
int numOfEdges ; /∗∗ Number o f e d g e s i n t h e gr ap h . ∗/
};// end WDiGraph
#endif
WDiGraph Implementation
/∗∗ @ f i l e WDiGraph . cpp
∗@author P h i l l i p J . Cu r ti ss
∗@version 0 .95
∗@date 2016−01−22
∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗/
#include ”WDiGraph . h”
WDiGraph : : WDiGraph( i n t n ) : n umOf Vertices ( n ) , numOfEdges ( 0 )
{
// A l l o c a t e 2D m at rix t o co nt a in w ei g ht e d grap h
Philip J. Curtiss, Assistant Professor
Computer Science Department, Montana Tech
Page 4 of 12
Project-1
S15 CSCI 332 - DAA Weighted Directed Graph
Assigned: 2016-01-22
Due: 2016-02-05 by midnight
/∗assume new alway s su c c e ed s ∗/
data = new int [ numOfVertices∗numOfVertices ] ;
matrix = new int ∗[ numOfVertices ] ;
for (int i = 0 ; i <numOfVertices ; ++i )
{
matrix [ i ] = &data [ i ∗numOfVertices ] ;
for(i n t j = 0 ; j<numOfVertices ; ++j )
{
matrix [ i ] [ j ] = NOEDGE;
}
}
}//end constuctor
WDiGraph : : WDiGraph( const WDiGraph& graph )
{
// S tu de nt n eed s t o implement f o r deep copy
}
WDiGraph : : ˜ WDiGraph ( )
{
// St u dent needs t o implement
}
bool WDiGraph : : e d g e E x i s t s ( int s t a r t , int end ) const
throw (VertexOutOfRangeException)
{
bool found = f a l s e ;
//Check i f s t a r t and end are i n range
i f (start <0| | end <0| | start >= numOfVertices | | end >= numOfVertices){
throw VertexOutOfRangeException ( ” I n v a l i d Vertex number” ) ;
}
// St u dent needs t o implement
return found ;
}
int WDiGraph : : ge tNumVertices ( ) const
{
return numOfVertices ;
}// end getNumVertices
int WDiGraph : : getNumEdges ( ) const
{
return numOfEdges ;
}// end getNumEdges
int WDiGraph : : getEdgeWeight ( i nt s t a r t , int end ) const
throw (VertexOutOfRangeException)
{
int w ei gh t = 0 ;
// St u dent needs t o implement
Philip J. Curtiss, Assistant Professor
Computer Science Department, Montana Tech
Page 5 of 12
Project-1
S15 CSCI 332 - DAA Weighted Directed Graph
Assigned: 2016-01-22
Due: 2016-02-05 by midnight
return wei ght ;
}// end get Wei ght
bool WDiGraph : : add ( int s t a r t , int end , in t w)
throw (VertexOutOfRangeException)
{
// St u dent needs t o implement
return f a l s e ;
}
bool WDiGraph : : remove ( i nt s t a r t , int end )
throw (VertexOutOfRangeException)
{
// St u dent needs t o implement
return f a l s e ;
}
WDiGraph& WDiGraph : : operator=(const WDiGraph& rhs )
{
// St u dent needs t o implement
return ∗th i s ;
}
Graph Header
// Created by Frank M. Carrano and Tim Henry .
// C op y ri gh t ( c ) 2013 P ea r so n E d u ca t i on . A l l r i g h t s r e s e r v e d .
/∗∗ @ f i l e Graph . h ∗/
#i f n de f GRAPH
#define GRAPH
#include ” Gra p h I n t e r f a c e . h”
#include ” Vertex . h”
// NOTE <<<<<<<
// R ep la c e SomeADT i n t h e f o l l o w i n g s t a t e m e n t s w i t h t h e name
// o f t he ADT t h at s t o r e s th e v e r t i c e s .
// Replac e SomeADTIterator with t h e name o f th e i t e r a t o r c l a s s
// f o r t h e s e v e r t i c e s .
// These c ho i ce s can be d i f f e r e n t from th os e used in th e c l a s s Vertex .
#include ”SomeADT. h” // ADT f o r Ver te x L i s t
#include ”SomeADTIterator . h” // I t e r a t o r f o r Vertex L i s t
template<class LabelType>
class Graph : public GraphInterface<LabelType>
{
private :
int numberOfVertices ;
Philip J. Curtiss, Assistant Professor
Computer Science Department, Montana Tech
Page 6 of 12
Project-1
S15 CSCI 332 - DAA Weighted Directed Graph
Assigned: 2016-01-22
Due: 2016-02-05 by midnight
int numberOfEdges ;
SomeADT<LabelType , Vertex<LabelType>∗>vertices ;
SomeADTIterator<LabelType , Vertex<LabelType>∗>currentVertex ;
// These a re o p t i o n a l h e l p e r methods t h a t may be u s e f u l
void depthFirstTraversalHelper(Vertex<LabelType>∗startVertex ,
void v i s i t ( LabelType &));
void breadthFirstTraversalHelper(Vertex<LabelType>∗startVertex ,
void v i s i t ( LabelType &));
Vertex<LabelType>∗findOrCreateVertex(const LabelType& ve r t e xL ab el ) ;
public :
Graph ( ) ;
int getNumVertices () const ;
int getNumEdges () const ;
bool add ( LabelType s t a r t , LabelType end , i nt edgeWeight = 0 ) ;
// For remove t o r e t ur n t r u e a l l t h r e e o f t h e f o l l o w i n g must b e t r u e :
// 1) s t a r t and end v e r t i c e s e x i s t
// 2) Edge s t a r t −>end i s s u c c e s s f u l l y d i s c o n n e c t e d
// 3) Edge end−>s t a r t s u c c e s s f u l l y d i s c o n n e c t e d
// Then , i f t ho se are s u c c e s s f u l and e i t h e r s t a r t or end no l on g e r
// has ne ig hb or s , t he v e r t e x i s removed from t he grap h
bool remove ( LabelType s t a r t , LabelType end ) ;
int getEdgeWeight ( LabelType s t a r t , LabelType end ) const ;
void d e p t h F i r s t T r a v e r s a l ( LabelType s t a r t L a be l , void v i s i t ( LabelType & ) ) ;
void b r e a d t h F i r s t T r a v e r s a l ( LabelType s t ar t L a b e l , void v i s i t ( LabelType & ) ) ;
};// end Graph
#include ”Graph . cpp”
#endif
Graph Interface
/∗∗ An i n t e r f a c e f or t h e ADT u nd i r ec t e d , con nec ted graph .
Carrano and Henry Code L i s t i n g 20−1.
@file GraphInterface .h ∗/
#i f n de f GRAPH INTERFACE
#define GRAPH INTERFACE
#include ”VertexOutOfRangeException .h”
#include ”NotFoundException . h”
const i nt NOEDGE = 0 ;
template<class LabelType>
class GraphInterface
{
public :
/∗∗ Gets t he number o f v e r t i c e s i n t h i s graph .
Philip J. Curtiss, Assistant Professor
Computer Science Department, Montana Tech
Page 7 of 12
Project-1
S15 CSCI 332 - DAA Weighted Directed Graph
Assigned: 2016-01-22
Due: 2016-02-05 by midnight
@pre None .
@return The number o f v e r t i c e s i n t h e graph . ∗/
vi rt ua l i nt getNumVertices () const = 0 ;
/∗∗ Gets t he number o f ed g e s in t h i s graph .
@pre None .
@r eturn The number o f e d g e s i n t h e g ra ph . ∗/
vi rt ua l i n t getNumEdges () const = 0 ;
/∗∗ C r ea te s an u n d i r e c t e d e dg e i n t h i s g ra ph b et we en two v e r t i c e s
t h a t have t h e gi ve n l a b e l s . I f such v e r t i c e s do not e x i s t , c r e a t e s
them and adds them t o th e graph b e f o r e c r e a t i n g t h e ed ge .
@param s t a r t A l a b e l f o r t h e f i r s t v e r t e x .
@param end A l a b e l f o r t h e sec ond v e r t e x .
@param edgeWeight The i n t e g e r we igh t of t he ed ge .
@throw VertexOutOfRangeException i f e i t h e r v e r t e x i s n ot in ra nge .
@r etu rn True i f t h e edg e i s cr e at ed , or f a l s e o t h e r w i s e . ∗/
vi rt ua l bool add ( LabelType s t a r t , LabelType end , i n t edgeWeight ) = 0 ;
/∗∗ Removes an ed ge from t h i s g raph . I f a v e r t e x has no o th e r ed ges ,
i t i s removed from t h e gr ap h s i n c e t h i s i s a c on ne ct ed gr ap h .
@pre None .
@param s t a r t A l a b e l f o r t h e f i r s t v e r t e x .
@param end A l a b e l f o r t h e sec ond v e r t e x .
@throw VertexOutOfRangeException i f e i t h e r v e r t e x i s n ot in ra nge .
@r etu rn True i f t h e edg e i s removed , or f a l s e o t h e r w i s e . ∗/
vi rt ua l bool remove ( LabelType s t a r t , LabelType end ) = 0 ;
/∗∗ Determine i f edge i s i n graph
@param s t a r t −ed ge s t a r t v e r t e x
@param end −edge end v e r t e x
@throw VertexOutOfRangeException i f e i t h e r v e r t e x i s n ot in ra nge .
@return t ru e i f edge ( s t a r t , end ) i s in t he grap h ∗/
vi rt ua l bool e d g e E x i s t s ( LabelType s t a r t , LabelType end ) const = 0 ;
/∗∗ Gets t he w ei g h t of an e dge i n t h i s graph .
@throw VertexOutOfRangeException i f e i t h e r v e r t e x i s n ot in ra nge .
@return The w e i gh t o f t h e s p e c i f i e d edge .
I f no suc h e dg e e x i s t s , r e t u r n s a n e g a t i v e i n t e g e r . ∗/
vi rt ua l i n t getEdgeWeight ( LabelType s t a r t , LabelType end ) const = 0 ;
/∗∗ Performs a depth−f i r s t s e a rc h o f t h i s gr ap h b e g i n n i n g a t t h e g i v e n
v e r t e x and c a l l s a g i ve n f u n ct i o n once f o r each v e r t e x v i s i t e d .
@param s t a r t A l a b e l f o r t h e f i r s t v e r t e x .
@param v i s i t A c l i e n t −d e f i n e d f u n c t i o n t h a t p erf or ms an o p e ra t i o n on
or wi t h each v i s i t e d v e r t e x . ∗/
// v i r t u a l vo i d d e p t h F i r s t T r a v e r s a l ( La belType s t a r t , v o id v i s i t ( LabelTy pe &)) = 0 ;
/∗∗ P erf orms a b re a dt h −f i r s t s e a rc h o f t h i s g ra ph b e g i n n i n g a t t h e g i v e n
v e r t e x and c a l l s a g i ve n f u n ct i o n once f o r each v e r t e x v i s i t e d .
@param s t a r t A l a b e l f o r t h e f i r s t v e r t e x .
@param v i s i t A c l i e n t −d e f i n e d f u n c t i o n t h a t p erf or ms an o p e ra t i o n on
or wi t h each v i s i t e d v e r t e x . ∗/
// v i r t u a l vo i d b r e a d t h F i r s t T r a v e r s a l ( LabelType s t a r t , vo i d v i s i t ( LabelType &)) = 0 ;
Philip J. Curtiss, Assistant Professor
Computer Science Department, Montana Tech
Page 8 of 12
Project-1
S15 CSCI 332 - DAA Weighted Directed Graph
Assigned: 2016-01-22
Due: 2016-02-05 by midnight
};// end GraphInterface
#endif
Custom Exception Classes
/∗∗ @ f i l e NotFoundException . h ∗/
#i f n de f NOT FOUND EXCEPTION
#define NOT FOUND EXCEPTION
#include <stdexcept>
#include <s t r i n g >
using namespace st d ;
class NotFoundException : public logic error
{
public :
NotFoundException(const s t r i n g& message = ”” ) ;
};// end NotFoundException
#endif
/∗∗ @ f i l e NotFoundException . cpp ∗/
#include ”NotFoundException . h”
NotFoundException : : NotFoundException (const s t r i n g& message )
: l o g i c e r r o r ( ”Not Found Exception : ” + message )
{
}// end constructor
// End o f imp leme ntat ion f i l e .
/∗∗ @ f i l e VertexOutOfRangeException . h
∗/
#i f n de f VERTEX EXCEPTS H
#define VERTEX EXCEPTS H
#include <stdexcept>
#include <s t r i n g >
using namespace st d ;
/∗∗ V ertex Out o f Range Exc e ptio n c l a s s
∗Ex c epti o n c l a s s f o r v e r t i c e s t h a t are not in t h e graph .
∗/
class VertexOutOfRangeException : public s td : : o u t o f r a n g e
{
public :
/∗∗
∗Cr e ates e x c e pt i o n i n i t i a l i z e d w i t h a message .
∗@param message e x c e p t i o n message s t r i n g
∗/
VertexOutOfRangeException(const s td : : s t r i n g & message = ”” )
Philip J. Curtiss, Assistant Professor
Computer Science Department, Montana Tech
Page 9 of 12
Project-1
S15 CSCI 332 - DAA Weighted Directed Graph
Assigned: 2016-01-22
Due: 2016-02-05 by midnight
: s td : : o u t o f r a n g e ( message . c s t r ( ) )
{ }
};// end VertexOutOfRangeException
#endif
IO Functions
/∗∗ @ f i l e i o f u n c t i o n s . h
∗
∗Con tai ns C++ f u n c t i o n s f o r p r i n t i n g menus , r ea d in g i np u t v al ue s , e t c .
∗@author Braun
∗@date 9/16/13
∗/
#i f n de f IO FUNCTIONS H
#define IO FUNCTIONS H
#include <iostream>
#include <sstream>
using namespace st d ;
/∗∗ P r i n t s main program menu
∗@pre none
∗@post none
∗/
void printMenu () ;
/∗∗ Reads and r e t u r n s an i n t e g e r
∗@pre User has been prompted to e nt er an i n t e g e r
∗@post none
∗@return i n t e g e r v a lu e
∗/
int g e t I n t ( ) ;
/∗∗
∗Prompts f o r a l i s t ite m and r e t u r n s i t t o c a l l e r
∗@return l i s t item
∗@remarks Accepts s t r i n g s wi th sp a c e s
∗/
s t r i n g g et Item ( ) ;
#endif
/∗∗ @ f i l e i o f u n c t i o n s . cpp
∗
∗Con tai ns C++ f u n c t i o n s f o r p r i n t i n g menus , r ea d in g i np u t v al ue s , e t c .
∗@author Braun
∗@date 1/12/14
∗/
#include ” i o f u n c t i o n s . h”
Philip J. Curtiss, Assistant Professor
Computer Science Department, Montana Tech
Page 10 of 12
Project-1
S15 CSCI 332 - DAA Weighted Directed Graph
Assigned: 2016-01-22
Due: 2016-02-05 by midnight
using namespace st d ;
/∗∗ P r i n t s main program menu
∗@pre none
∗@post none
∗/
void printMenu (){
cou t << ” 1) Pr i n t the s i z e o f graph ” << en d l ;
cou t << ” 2) Check i f an ed ge i s i n t he graph ” << endl ;
cou t << ” 3) I n s e r t an edge i nt o the graph ” << end l ;
cou t << ” 4) D el e t e an e dge from th e graph ” << en d l ;
cou t << ” 5 ) R e t r i e v e an e dge w ei ght ” << e ndl ;
cou t << ” 6) Di s pl a y th e graph ” << endl ;
cou t << ” 7) Quit the program ” << e ndl ;
}
/∗∗ Reads , v a l i d a t e s , and r e tu rn s a p o s i t i v e i n t e g e r
∗@pre User has been prompted to e nt er an i n t e g e r
∗@post none
∗@return n on ne gat ive i n t e g e r v a lu e
∗/
int g e t I n t ( ) {
int i nt Va lu e = 0 ;
s t r i n g i np ut S tr ;
do{
g e t l i n e ( c i n , i n p u t S t r ) ;
s t r i n g s t r e a m ( i n pu t S t r ) >> intValue ;
i f (intValue <0) cout << ”ERROR −p l e a s e e n t e r a n o nn eg at iv e i n t e g e r >” ;
}while(intValue <0 ) ;
return intValue ;
}
Makefile
#
#Makefile for Ge ner ati ng C++ e x e c u t a b l e s
#
#S16 CSCI 332 −Design and A n a l y s i s o f A lg or i th ms
#P h i l l i p J . C u rt is s , A s so c i a te P r o f e s s o r
#Computer S c i e n c e Department , Montana Tech
#Museum B u i l d i n gs , Room 105
#
#Project −1: Weighted D i r e ct e d Graph
#Date Assigned : 2016−01−22
#Date Due : 2016−02−05 by Midnight
#Def in e Macros r e l a t e d to p r i n t i n g and su bm it ting p r o j e c t
a2ps = a2ps −T 2
mail = mail
addr = pcurtiss@mtech . edu #rmoon@mtech . edu
t a r = t a r −c v z f
#Def in e Macros r e l a t e d to o b j ec t code and program generation
Philip J. Curtiss, Assistant Professor
Computer Science Department, Montana Tech
Page 11 of 12
Project-1
S15 CSCI 332 - DAA Weighted Directed Graph
Assigned: 2016-01-22
Due: 2016-02-05 by midnight
DIA = dia2 c o d e
C++ = g++ −std=c++11
CFLAGS = −g−Wall −Werror
LD = g++
LDFLAGS =
LIBS =
SRCS = Driv er . cpp WDiGraph . cpp WDiGraph . h \
VertexOutOfRangeException . h NotFoundException . cpp NotFoundException . h \
Graph . h G ra p h I n t e rf a c e . h \
i o f u n c t i o n s . cpp i o f u n c t i o n s . h
OBJS = D r iver . o WDiGraph . o i o f u n c t i o n s . o
EXEC = Driver
#Provi de Make with a d d i t i o n a l l y known s u f f i x e s
. SUFFIXES : . di a
#De fa ul t r u l e to make i f now t a r ge t s p e c i f i e d on command line
a l l : $ (EXEC)
#Dependency Rules
i o f u n c t i o n s . o : i o f u n c t i o n s . h i o f u n c t i o n s . cpp
WDiGraph . o : VertexOutOfRangeException . h WDiGraph . h WDiGraph . cpp
Dri v e r . o : Dri v e r . cpp WDiGraph . h
#Ru les to c r e a t e t a r g e t f i l e D ri ve r
#I f any f i l e s on line with c ol o n a re mo dif ied , then r ec o mp i l e th e o b j e c t f i l e
#Target Rules for Make
$ (EXEC) : $ (OBJS)
$ (LD) $ (LDFLAGS) −o $ (EXEC) $ (OBJS) $ ( LIBS )
c l e a n :
rm −f $ (OBJS) $ (EXEC)
subj = ”CSCI332 DAA −Proj1 ”
msg = ” Pl e a s e review and grade my Pr o j e c t −1 Submission”
submit : $ (SRCS)
$ ( t a r ) $ (USER)−p r o j 1 . t g z $ ?
echo $ ( msg ) |$ ( mail ) −s $ ( su bj ) −a $ (USER)−p r o j 1 . t g z $ ( addr )
p r i n t : $ (SRCS)
$ ( a2ps ) $?
#I m p l c i t Ru le s based on f i l e e x t e n s i o n d e pe n de n ci e s
. cpp . o :
$ (C++) $ (CFLAGS) −c $<
. di a . h :
$ (DIA) −t cpp $<
. di a . cpp :
$ (DIA) −t cpp $<
Philip J. Curtiss, Assistant Professor
Computer Science Department, Montana Tech
Page 12 of 12
