Notice:
Project 5 is due either at 12:00 midnight of the last day of class.
There are no resubmissions
or late submissions for Project 4; however, projects which achieve a grade less than 80
will be examined to determine if they deserve a grade great than what was actually
received (to a maximum of 80).
You may use all standard libraries available on ecelinux.
This includes the Standard Template Library (STL), cstring, etc.
In this sub-project, you will implement one class:
- A weighted graph: Weighted_graph.
This class will implement a weighted undirected graph with Prim's algorithm.
Class Specification
UML Class Diagram
| Weighted_graph |
|---|
+ create( in n:Integer = 50 ):Weighted_graph
+ degree( in n:Integer ):Integer
+ edge_count():Integer
+ adjacent( in m:Integer, in n:Integer ):Real
+ minimum_spanning_tree( in m:Integer ):Real
+ is_connected():Boolean
+ insert( in m:Integer, in n:Integer, in w:Real )
+ destroy()
|
Description
This class allows the user to create and destroy an
undirected weighted graph.You will be able to find the minimum span tree of a graph, using Prim's algorithm.
The vertices are numbered 0 through n − 1 where
n is the argument to the constructor.
Member Variables
You may define whatever member variables you wish.
Member Functions
Constructors
Weighted_graph( int n = 50 )
Construct a weighted undirected graph with n vertices (by default, 50).
Destructor
Clean up any allocated memory.
Accessors
This class has four accessors:
- int degree( int n ) const
- Returns the degree of the vertex n. Throw an illegal argument
exception if the argument does not correspond to an existing vertex. (O(1))
- int edge_count() const
- Returns the number of edges in the graph.
(O(1))
- double adjacent( int m, int n ) const
- Returns the weight of the edge connecting vertices m and n.
If the vertices are equal, return 0.
If the vertices are not adjacent, return infinity.
Throw an illegal argument exception if the arguments do not correspond to existing vertices.
- bool is_connected() const
- Determine if the graph is connected.
- double minimum_spanning_tree( int m ) const
- Return the size of the minimum spanning tree of those nodes which are connected to vertex m.
Throw an illegal argument exception if the arguments do not correspond to existing vertices.
Mutators
This class has one mutator:
- void insert( int m, int n, double w )
- If the weight w < 0 or w = ∞, throw an illegal argument exception.
If the weight w is 0, remove any edge between m and n (if any).
Otherwise, add an edge between vertices m and n with weight w.
If an edge already exists, replace the weight of the edge with the new weight.
If the vertices do not exist or are equal, throw an illegal argument exception.