Project 6: Weighted Graphs Solution

    • Assignment Overview

For this project you will be implementing a weighted graph. A weighted graph, G = (V; E), is de ned as a set of vertices, V = fv0; v1; : : : ; vng, and a set of weighted edges, E = f(u0; v0; w0); (u1; v1; w1); : : : ; (um; vm; wm)g. An edge connects two vertices, u and v, and speci es a weight on that connection, w. Note that edges are undirected and, therefore, symmetric; (u; v; w) means the same thing as (v; u; w).

Your graph will have path nding capabilities; It is able to nd the minimum weight path between two vertices.

Your graph will also be able to report if it is bipartite using a graph coloring algorithm.

    • Assignment Deliverables

You must turn in completed versions of the following    les:

Graph.py

Be sure to use the speci ed le name and to submit your les for grading via Mimir before the project deadline.

    • Assignment Speci cations

Your task will be to complete the methods listed below:

insert edge: Adds an edge of the given weight between the two vertices.

degree: The number of edges that intersect the given vertex.

are connected: Checks whether an edge exists between two vertices.

is path valid: Determines whether an edge exists along each step of the path.

edge weight: Finds the weight of an edge between two vertices.

path weight: Finds the total weight of a path (sum of edge weights).

does path exist: Checks whether a path exists between two vertices.

find min weight path: Finds a path of minimum weight between two vertices.

is bipartite: Determines if the graph is bipartite.






1

You may use any of the collections classes included in the default Python distribution that you need to store your graph. Your graph will have two member variables: order, which is the number of vertices, and size, which is the number of edges. Your insert edge method should update the size member. You may add other member variables in your constructor. The memory requirements for your graph must be O(jV j + jEj). Only the constructor and the insert edge method may modify your graph. You will lose points if any of the other methods modify your graph.


Your insert edge, degree, are connected, and edge weight functions should all run in constant time. is path valid and path weight should run in time linear in the length of the input list. Each of them should also use a xed amount of extra memory. does path exist and is bipartite should use at most O(jV j+jEj) time and (jV j) extra memory. The find min weight path method should use O(jEj+jV j log jV j) time and O(jV j + jEj) extra memory.

The is bipartite method will determine if the graph is a bipartite graph. In a bipartite graph, the vertices can be separated into two sets; all edges in the graph will connect vertices in di erent sets. This can be done using a coloring strategy; each vertex is colored either red or blue, the opposite of the color of one of its neighbors. If two adjacent vertices have the same color then the graph is not bipartite.


Each of your methods should raise an IndexError if one of the vertices is not in the graph. You may assume that the paths input into is path valid and path weight are non-empty (they contain at least one vertex). You may not assume that all of the edges in the path exist. Both edge weight and path weight must return in nity if an edge is missing. Your find min weight path should raise a ValueError if no path exists. No other exceptions should be raised by your program. insert edge inserting an edge that already exists should update the weight on that edge.


You should include comments where appropriate. In particular, you should describe the method used for storing edges (edge list, adjacency matrix, adjacency list, etc.). You must also add documentation for each of the above methods (as well as for any helper functions created) in the same style as for the pre-de ned methods.

    • Assignment Notes

Points will be deducted if your solution has warnings of any type.

You have been supplied with stubs for the required methods. You must complete these methods to complete the project. You may add more functions than what was provided, but you may not modify the signatures of the provided methods.

You do not have to worry about error checking for valid input. You may assume that the supplied reader function correctly reads the input le.

You have been provided with some unit tests that can be used to assess your solution. There are additional test cases that will be kept hidden.

It is your responsibility to check for potential edge cases. The supplied unit tests do not account for all possible valid inputs

Several sample graphs have been provided. Visualizations for two of them are shown in Figures 1b and 1c above.

Note that the graphs may not be connected. For example, the provided g2 graph is not connected but consists of two components. You must be able to determine if a disconnected graph is bipartite.

You may use a wide variety of collections classes. You may want to use list, set, dict, heapq, deque, or defaultdict.





2
























5

015.0

022.0

    • 3  2.0

133.0

412.5

433.5

        (a) g1.txt



(b) Visual representation of g1

(c) Visual representation of g2

Figure 1: Sample Input



















3