Instructions

User Manual:

Open the PDF directly: View PDF .
Page Count: 12

Download
Open PDF In Browser	View PDF

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 : int ) : bool
+getEdgeWeight ( i n u : int , i n v : int ) : WtType
+add ( i n u : int , i n v : int , i n wt : WyType)
+remove ( i n u : int , i n v : int )

• 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 department’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//csci332/proj1, where  is replaced with the username 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 t o submit programming a s s i g n m e n t s t o g r a d e r s
# Make s u r e you modify t h e $ ( s u b j ) $ ( msg ) above and t h e l i s t o f attachment
# f i l e s i n t h e f o l l o w i n g r u l e − each f i l e n e e d s t o be p r e c e e d e d with an
# −a f l a g a s shown
subj
= ”CSCI332 DDA − P r o j 1 ”
msg
= ” P l e a s e r e v i e w and g r a d e my P r o j e c t −3 S u b m i s s i o n ”
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 ) | $ ( m a i l ) −s $ ( s u b j ) −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 w i t h a d j a c e n c y l i s t i m p l e m e n t a t i o n
∗ V e r t e x i n d i c e s range from 0 t o numVertices −1
∗ M u l t i p l e e d g e s from one v e r t e x t o a n o t h e r v e r t e x a r e not a l l o w e d
∗
∗ @author P h i l l i p J . C u r t i s s
∗ @version 0.95
∗ @date 2016−01−22
∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗/
#i f n d e f WDGRAPH H
#define WDGRAPH H
#include ” G r a p h I n t e r f a c e . h”
/∗ ∗ Weighted DiGraph − m a t r i x i m p l e m e n t a t i o n u s i n g i n t e g e r v e r t e x l a b e l s ∗/
c l a s s WDiGraph : public G r a p h I n t e r f a c e 
{
public :
/∗ ∗ D e f a u l t C o n s t r u c t o r ( 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 l d n v e r t i c e s . ∗/
WDiGraph( int n =10);
/∗ ∗ Copy C o n s t r u c t o r
∗ @param graph − t h e graph t o 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 ) ;
/∗ ∗ D e s t r u c t o r . ∗/
v i r t u a l ˜WDiGraph ( ) ;
/∗ ∗ Determines t h 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 i n t h e graph . ∗/
int getNumVertices ( ) const ;
/∗ ∗ Determines t h e number o f e d g e s i n t h e graph .
∗ @return The number o f e d g e s i n t h e graph . ∗/
int getNumEdges ( ) const ;
bool add ( int s t a r t , int end , int e d g e w e i g h t )
throw ( VertexOutOfRangeException ) ;
bool remove ( int s t a r t , int end )
throw ( VertexOutOfRangeException ) ;
bool e d g e E x i s t s ( int s t a r t , int end ) const
throw ( VertexOutOfRangeException ) ;
int getEdgeWeight ( int s t a r t , int end ) const
throw ( VertexOutOfRangeException ) ;
/∗ ∗ Assignment o p e r a t o r o v e r l o a d f o r deep copy o f r h s graph
∗ @pre The l h s and r h s g r a p h 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 o n t a i n s t h e r h s 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 t a b l o c k ∗/
int ∗ ∗ matrix ; /∗ ∗ 2D m a t r i x t h a t p o i n t s t o rows i n d a t a 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 graph . ∗/
} ; // end WDiGraph
#endif

WDiGraph Implementation
/∗ ∗ @ f i l e WDiGraph . cpp
∗ @author P h i l l i p J . C u r t i s s
∗ @version 0.95
∗ @date 2016−01−22
∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ ∗/
#include ”WDiGraph . h”
WDiGraph : : WDiGraph( int n ) : numOfVertices ( n ) , numOfEdges ( 0 )
{
// A l l o c a t e 2D m a t r i x t o c o n t a i n w e i g h t e d graph

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 a l w a y s s u c c e e d s ∗/
data = new int [ numOfVertices ∗ numOfVertices ] ;
matrix = new int ∗ [ numOfVertices ] ;
f o r ( int i = 0 ; i < numOfVertices ; ++i )
{
matrix [ i ] = &data [ i ∗ numOfVertices ] ;
f o r ( int j = 0 ; j = numOfVertices | | end >= numOfVertices ) {
throw VertexOutOfRangeException ( ” I n v a l i d Vertex number” ) ;
}
// S t u d e n t ne e ds t o implement
return found ;
}
int WDiGraph : : getNumVertices ( ) const
{
return numOfVertices ;
} // end getNumVertices
int WDiGraph : : getNumEdges ( ) const
{
return numOfEdges ;
} // end getNumEdges
int WDiGraph : : getEdgeWeight ( int s t a r t , int end ) const
throw ( VertexOutOfRangeException )
{
int w e i g h t = 0 ;
// S t u d e n t ne e ds 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 w e i g h t ;
} // end g e t W e i g h t

bool WDiGraph : : add ( int s t a r t , int end , int w)
throw ( VertexOutOfRangeException )
{
// S t u d e n t ne e ds t o implement
return f a l s e ;
}
bool WDiGraph : : remove ( int s t a r t , int end )
throw ( VertexOutOfRangeException )
{
// S t u d e n t ne e ds t o implement
return f a l s e ;
}
WDiGraph& WDiGraph : : operator=(const WDiGraph& r h s )
{
// S t u d e n t ne e ds t o implement
return ∗ t h i s ;
}
Graph Header
//
//

Created by Frank M. Carrano and Tim Henry .
Pearson Education . All r i g h t s reserved .
C o p y r i g h t ( c ) 2013

/∗ ∗ @ f i l e Graph . h ∗/
#i f n d e f GRAPH
#define GRAPH
#include ” G r a p h I n t e r f a c e . h”
#include ” Vertex . h”
//
//
//
//
//
//

NOTE <<<<<<<
R e p l a 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 h e ADT t h a t s t o r e s t h e v e r t i c e s .
R e p l a c e SomeADTIterator w i t h t h e name o f t h e i t e r a t o r c l a s s
for these vertices .
These c h o i c e s can be d i f f e r e n t from t h o s e used i n t h e c l a s s V e r t e x .

#include ”SomeADT . h”
// ADT f o r V e r t e x L i s t
#include ” SomeADTIterator . h” // I t e r a t o r f o r V e r t e x L i s t
template
c l a s s Graph : public G r a p h I n t e r f a c e 
{
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∗ > v e r t i c e s ;
SomeADTIterator∗ > c u r r e n t V e r t e x ;
// These a r e 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 d e p t h F i r s t T r a v e r s a l H e l p e r ( Vertex∗ s t a r t V e r t e x ,
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 H e l p e r ( Vertex∗ s t a r t V e r t e x ,
void v i s i t ( LabelType & ) ) ;
Vertex∗ f i n d O r C r e a t e V e r t e x ( const LabelType& v e r t e x L a b e l ) ;
public :
Graph ( ) ;
int getNumVertices ( ) const ;
int getNumEdges ( ) const ;
bool add ( LabelType s t a r t , LabelType end , int edgeWeight = 0 ) ;
// For remove t o r e t u r 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 be 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 h o s e a r e 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 o n g e r
// has n e i g h b o r s , t h e v e r t e x i s removed from t h e graph
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 b e 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 a r 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 o r t h e ADT u n d i r e c t e d , c o n n e c t e d graph .
Carrano and Henry Code L i s t i n g 20 −1.
@ f i l e G r a p h I n t e r f a c e . h ∗/
#i f n d e f
#define
#include
#include

GRAPH INTERFACE
GRAPH INTERFACE
” VertexOutOfRangeException . h”
” NotFoundException . h”

const int NOEDGE = 0 ;
template
class GraphInterface
{
public :
/∗ ∗ Gets t h e 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 . ∗/
v i r t u a l int getNumVertices ( ) const = 0 ;
/∗ ∗ Gets t h e number o f e d g e s i n t h i s graph .
@pre
None .
@return The number o f e d g e s i n t h e graph . ∗/
v i r t u a l int getNumEdges ( ) const = 0 ;
/∗ ∗ C r e a t e s an u n d i r e c t e d e d g e i n t h i s graph b e t w e e n two v e r t i c e s
t h a t have t h e g i v e 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 t h e graph b e f o r e c r e a t i n g t h e e d g e .
@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 second v e r t e x .
@param edgeWeight The i n t e g e r w e i g h t o f t h e e d g e .
@throw VertexOutOfRangeException i f e i t h e r v e r t e x i s not i n range .
@return True i f t h e e d g e i s c r e a t e d , or f a l s e o t h e r w i s e . ∗/
v i r t u a l bool add ( LabelType s t a r t , LabelType end , int edgeWeight ) = 0 ;
/∗ ∗ Removes an e d g e from t h i s graph . I f a v e r t e x has no o t h e r e d g e s ,
i t i s removed from t h e graph s i n c e t h i s i s a c o n n e c t e d graph .
@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 second v e r t e x .
@throw VertexOutOfRangeException i f e i t h e r v e r t e x i s not i n range .
@return True i f t h e e d g e i s removed , or f a l s e o t h e r w i s e . ∗/
v i r t u a l bool remove ( LabelType s t a r t , LabelType end ) = 0 ;
/∗ ∗ Determine i f e d g e i s i n graph
@param s t a r t − e d g e s t a r t v e r t e x
@param end − e d g e 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 not i n range .
@return t r u e i f e d g e ( s t a r t , end ) i s i n t h e graph ∗/
v i r t u a l bool e d g e E x i s t s ( LabelType s t a r t , LabelType end ) const = 0 ;
/∗ ∗ Gets t h e w e i g h t o f an e d g e 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 not i n range .
@return The w e i g h t o f t h e s p e c i f i e d e d g e .
I f no such e d g 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 . ∗/
v i r t u a l int getEdgeWeight ( LabelType s t a r t , LabelType end ) const = 0 ;
/∗ ∗ Performs a depth − f i r s t s e a r c h o f t h i s graph 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 v e n f u n c t 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 e r f o r m s an o p e r a t i o n on
or w i t h each v i s i t e d v e r t e x . ∗/
//
v i r t u a l v o i d 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 , v o i d v i s i t ( LabelType &)) = 0 ;
/∗ ∗ Performs a b r e a d t h − f i r s t s e a r c h o f t h i s graph 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 v e n f u n c t 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 e r f o r m s an o p e r a t i o n on
or w i t h each v i s i t e d v e r t e x . ∗/
//
v i r t u a l v o 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 , v o 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 G r a p h I n t e r f a c e
#endif
Custom Exception Classes
/∗ ∗ @ f i l e NotFoundException . h ∗/
#i f n d e f NOT FOUND EXCEPTION
#define NOT FOUND EXCEPTION
#include 
#include 
using namespace s t d ;
c l a s s NotFoundException : public l o g i c e r r o r
{
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 E x c e p t i o n : ” + message )
{
} // end c o n s t r u c t o r
// End o f i m p l e m e n t a t i o n f i l e .
/∗ ∗ @ f i l e VertexOutOfRangeException . h
∗/
#i f n d e f VERTEX EXCEPTS H
#define VERTEX EXCEPTS H
#include 
#include 
using namespace s t d ;
/∗ ∗ V e r t e x Out o f Range E x c e p t i o n c l a s s
∗ E x c e p t i o n c l a s s f o r v e r t i c e s t h a t a r e not i n t h e graph .
∗/
c l a s s VertexOutOfRangeException : public s t d : : o u t o f r a n g e
{
public :
/∗ ∗
∗ C r e a t e s e x c e p t 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 t d : : 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 t d : : 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
∗
∗ Contains C++ f u n c t i o n s f o r p r i n t i n g menus , r e a d i n g i n p u t v a l u e s , e t c .
∗ @author Braun
∗ @date 9/16/13
∗/
#i f n d e f IO FUNCTIONS H
#define IO FUNCTIONS H
#include 
#include 
using namespace s t 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 t o e n t e r an i n t e g e r
∗ @post none
∗ @return i n t e g e r v a l u e
∗/
int g e t I n t ( ) ;
/∗ ∗
∗ Prompts f o r a l i s t item 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 A c c e p t s s t r i n g s w i t h s p a c e s
∗/
s t r i n g getItem ( ) ;
#endif

/∗ ∗ @ f i l e i o f u n c t i o n s . cpp
∗
∗ Contains C++ f u n c t i o n s f o r p r i n t i n g menus , r e a d i n g i n p u t v a l u e 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 s t d ;
/∗ ∗ P r i n t s main program menu
∗ @pre none
∗ @post none
∗/
void printMenu ( ) {
c o u t << ” 1 ) P r i n t t h e s i z e o f graph ” << e n d l ;
c o u t << ” 2 ) Check i f an edge i s i n t h e graph ” << e n d l ;
c o u t << ” 3 ) I n s e r t an edge i n t o t h e graph ” << e n d l ;
c o u t << ” 4 ) D e l e t e an edge from t h e graph ” << e n d l ;
c o u t << ” 5 ) R e t r i e v e an edge w e i g h t ” << e n d l ;
c o u t << ” 6 ) D i s p l a y t h e graph ” << e n d l ;
c o u t << ” 7 ) Quit t h e program ” << e n d l ;
}
/∗ ∗ Reads , v a l i d a t e s , and r e t u r n s a p o s i t i v e i n t e g e r
∗ @pre User has been prompted t o e n t e r an i n t e g e r
∗ @post none
∗ @return n o n n e g a t i v e i n t e g e r v a l u e
∗/
int g e t I n t ( ) {
int i n t V a l u e = 0 ;
string inputStr ;
do{
g e t l i n e ( cin , inputStr ) ;
s t r i n g s t r e a m ( i n p u t S t r ) >> i n t V a l u e ;
i f ( i n t V a l u e < 0 ) c o u t << ”ERROR − p l e a s e e n t e r a n o n n e g a t i v e i n t e g e r > ” ;
} while ( i n t V a l u e < 0 ) ;
return i n t V a l u e ;
}

Makefile
#
#
#
#
#
#
#
#
#
#
#

M a k e f i l e f o r G e n e r a t i n g 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 l g o r i t h m s
P h i l l i p J . Curtiss , Associate Professor
Computer S c i e n c e Department , Montana Tech
Museum B u i l d i n g s , Room 105
P r o j e c t −1: Weighted D i r e c t e d Graph
Date A s s i g n e d : 2016−01−22
Date Due : 2016−02−05 by Midnight

# D e f i n e Macros r e l a t e d t o p r i n t i n g and s u b m i t t i n g p r o j e c t
a2ps
= a2ps −T 2
mail
= mail
addr
= p c u r t i s s @ m t e c h . edu #rmoon@mtech . edu
tar
= t a r −c v z f
# D e f i n e Macros r e l a t e d t o o b j e c t code and program g e n e r a t i o n

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 = d i a 2 c o d e
C++ = g++ −s t d=c++11
CFLAGS = −g −Wall −Werror
LD = g++
LDFLAGS =
LIBS =
SRCS = D r i v e r . cpp WDiGraph . cpp WDiGraph . h \
VertexOutOfRangeException . h NotFoundException . cpp NotFoundException . h \
Graph . h G r a p h I n t e r f 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 i v e r . o WDiGraph . o i o f u n c t i o n s . o
EXEC = D r i v e r
# P r o v i d e Make with a d d i t i o n a l l y known s u f f i x e s
. SUFFIXES :
. dia
# D e f a u l t r u l e t o make i f now t a r g e t s p e c i f i e d on command l i n e
all :
$ (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
Driver . o :
D r i v e r . cpp WDiGraph . h
#Rules t o c r e a t e t a r g e t f i l e D r i v e r
# I f any f i l e s on l i n e with c o l o n a r e m o d i f i e d , then r e c o m p i l e t h e o b j e c t f i l e
# Target Rules f o r Make
$ (EXEC) :
$ (OBJS)
$ (LD) $ (LDFLAGS) −o $ (EXEC) $ (OBJS) $ ( LIBS )
clean :
rm −f $ (OBJS) $ (EXEC)
s u b j = ”CSCI332 DAA − P r o j 1 ”
msg =
” P l e a s e r e v i e w and g r a d e my P r o j e c t −1 S u b m i s s i o n ”
submit : $ (SRCS)
$ ( t a r ) $ (USER)− p r o j 1 . t g z $ ?
echo $ ( msg ) | $ ( m a i l ) −s $ ( s u b j ) −a $ (USER)− p r o j 1 . t g z $ ( addr )
print :

$ (SRCS)
$ ( a2ps ) $ ?

# I m p l c i t Rules based on f i l e e x t e n s i o n d e p e n d e n c i e s
. cpp . o :
$ (C++) $ (CFLAGS) −c $<
. dia . h :
$ (DIA) −t cpp $<
. d i a . cpp :
$ (DIA) −t cpp $<

Philip J. Curtiss, Assistant Professor
Computer Science Department, Montana Tech

Page 12 of 12



File Type                       : PDF
File Type Extension             : pdf
MIME Type                       : application/pdf
PDF Version                     : 1.5
Linearized                      : No
Page Count                      : 12
Producer                        : pdfTeX-1.40.16
Creator                         : TeX
Create Date                     : 2016:01:22 08:36:44-07:00
Modify Date                     : 2016:01:22 08:36:44-07:00
Trapped                         : False
PTEX Fullbanner                 : This is pdfTeX, Version 3.14159265-2.6-1.40.16 (TeX Live 2015/W32TeX) kpathsea version 6.2.1