GraphTools Namespace Reference

This is a namespace that provides various functions for operations on the Graph class. More...

Functions
int	findMinWeight (Graph &graph)
	Finds the minimum edge weight in the Graph graph. More...
int	findShortestPath (Graph &graph, Vertex start, Vertex end)
	Returns the shortest distance (in edges) between the Vertices start and end. More...
void	findMST (Graph &graph)
	Finds a minimal spanning tree on a graph. More...

Detailed Description

This is a namespace that provides various functions for operations on the Graph class.

Your assignment this lab will be to implement these three functions.

Function Documentation

findMinWeight()

int GraphTools::findMinWeight

(

Graph &

graph

)

Finds the minimum edge weight in the Graph graph.

THIS FUNCTION IS GRADED.

Parameters

graph

- the graph to search

Returns

the minimum weighted edge

Todo:

Label the minimum edge as "MIN". It will appear blue when graph.savePNG() is called in minweight_test.

Note

You must do a traversal.

You may use the STL stack and queue.

You may assume the graph is connected.

Initially label vertices and edges as unvisited.

findShortestPath()

int GraphTools::findShortestPath	(	Graph &	graph,
		Vertex	start,
		Vertex	end
	)

Returns the shortest distance (in edges) between the Vertices start and end.

THIS FUNCTION IS GRADED.

Parameters

graph	- the graph to search
start	- the vertex to start the search from
end	- the vertex to find a path to

Returns

the minimum number of edges between start and end

Todo:

Label each edge "MINPATH" if it is part of the minimum path

Note

Remember this is the shortest path in terms of edges, not edge weights.

Again, you may use the STL stack and queue.

You may also use the STL's unordered_map, but it is possible to solve this problem without it.

In order to draw (and correctly count) the edges between two vertices, you'll have to remember each vertex's parent somehow.

findMST()

void GraphTools::findMST

(

Graph &

graph

)

Finds a minimal spanning tree on a graph.

THIS FUNCTION IS GRADED.

Parameters

graph

- the graph to find the MST of

Todo:

Label the edges of a minimal spanning tree as "MST" in the graph. They will appear blue when graph.savePNG() is called.

Note

Use your disjoint sets class from MP 7.1 to help you with Kruskal's algorithm. Copy the files into the libdsets folder.

You may call std::sort instead of creating a priority queue.