You may use all standard libraries available on ecelinux.
This includes the Standard Template Library (STL), cstring, etc.
However, if you want to compete for the fastest implementations that get
a prize, you should
restrict yourself to using operations like std::swap and other
reasonably straight-forward features. Do not use any of the containers
if you want to compete..
Requirements
In this sub-project, you will implement one class:
- A weighted graph: Weighted_graph.
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
+ distance( in m:Integer, in n:Integer ):Real
+ 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 shortest
distance between two connected vertices. 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 an undirected graph with n vertices (by default, 50).
If n ≤ 0, use n = 1.
Destructor
Clean up any allocated memory.
Accessors
This class has three 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 the same, return 0.
If the vertices are not adjacent, return infinity. Throw an illegal argument
exception if the arguments do not correspond to existing vertices.
Mutators
This class has two mutators:
- void insert( int m, int n, double w )
- If the weight w ≤ 0 if it is infinity, throw an illegal argument exception.
If the weight w > 0, add an edge between vertices m and n.
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.
- double distance( int m, int n )
- Return the shortest distance between vertices m and n. Throw an illegal argument
exception if the arguments do not correspond to existing vertices. The
distance between a vertex and itself is 0.0. The distance between vertices that are not
connected is infinity.