WeightedGraph
implement a weighted graph in C++ . Both undirected and directed graphs must be supported. The public part of the class definition is given to you in WeightedGraph.h. Make whatever changes you need there, and implement functions in WeightedGraph.cpp.
This is not an abstract class. You are not expected to create separate Sparse and Dense implementations — just pick one (sparse!) and implement it directly in this class. New functions that are not in the other Graph class:
edgeWeight: Looks for an edge between v1 and v2 and returns the weight. If there’s no edge, then INT_MAX must be returned.
isPath: Returns a pair instead of just a bool. The first value in the pair is true or false, and the second value is the total weight of the path. If it’s not a path, the weight value is undefined (which means you can return anything).
hasCycle: For an undirected graph, this always returns true. For a directed graph, returns true if there is a cycle and false if not.
shortestPath: Returns the shortest path between two vertices. The return value is a vector of integers. If there is no path, the vector must be empty.
Please implement the CPP class for the following one.
WeightedGraph.h
#ifndef WeightedGraph_h
#define WeightedGraph_h
// this is not an abstract class — must implement all member functions
// recommend using adjacency list representation, but not required
class WeightedGraph {
public:
WeightedGraph(size_t numNodes, bool isDirected = false);
~WeightedGraph();
int size() const; // return number of nodes
bool isDirected() const;
void addEdge(int v1, int v2, int weight);
bool isEdge(int v1, int v2) const;
int edgeWeight(int v1, int v2) const; // returns INT_MAX if no edge
std::list<int> getAdjacencyList(int v) const; // returns list of nodes adjacent to v
bool hasCycle() const; // returns true if there is a cycle, false if no cycles
// isPath returns pair: first value is true if path, false if not
// second value is weight (of entire path), undefined if not a path
std::pair<bool,int> isPath(const std::vector<int>& ) const;
// shortestPath returns empty path if there is no path,
// or if there is any negative weight (assumes Dijkstra algorithm)
std::vector<int> shortestPath(int from, int to) const;
private:
//TBD
};
#endif
