Lab 9: Connected Graphs

Finding connected components Finding connected components and graph coloring

are important problems in computer science. Connected components in an undirected

graph give information about sets of vertices such that each pair of vertices has a path

between them.

This is an optional extra credit lab assignment. You can earn up to 50 points as extra

credit toward the lab category.

A coloring is an assignment of a color to each vertex in the graph so that no two

adjacent vertices have the same color. Colorings are important in modeling problems

where a set of objects must satisfy certain constraints. More information on bicoloring

and bipartite graphs can be found here: https://en.wikipedia.org/wiki/Bipartite_graph. A

graph is bipartite or bicolorable if the vertices of the graph can be assigned labels, say

red and black, such that no two adjacent vertices have the same label. (An equivalent

definition is that the vertex set can be divided into two disjoint subsets where all the

edges go from a vertex in one subset to a vertex in another subset.) You may assume

that the graph is undirected and does not contain self-loops (edges from a vertex to

itself). A good place to start is the graph class given in the lecture. Your goal is to have

a correct algorithm that is as simple and clear as possible.

Implement algorithms based on Depth First Search to:

1. Determine the connected components of an undirected graph

2. Determine if it is a bipartite graph (or in different words, 2 colorable.)

Implement an algorithm based on Breadth First Search as well. YOU MAY NOT USE

BUILTIN LIST POP FUNCTION NOR DICTIONARY. USE ONE OF YOUR QUEUES

FROM LAB4 AS THE QUEUE.

An input file consists of one graph for testing:

• Each graph will represent an undirected graph.

• The first line contains a positive integer n, that is the number of vertices in the graph to be

tested, where 1<n<200. Each vertex is represented by a number from 1 to n

• The second line is the number of edges, call this number e.

• This is followed by e lines each containing a pair of integers each integer between 1 and n

1

CPE202 Spring 2020

separated by a space that represents an edge between the vertices represented by the numbers.

Create a file my_graph.py, and implement the following functions in the file:

● def __init__ (self, filename):

○ reads in the specification of a graph and creates a graph using an

adjacency list representation. You may assume the graph is not empty

and is a correct specification. E.g. each edge is represented by a pair of

vertices between 1 and n. Note that the graph is not directed so each

edge specified in the input file should appear on the adjacency list of each

vertex of the two vertices associated with the edge.

● def get_conn_components (self, is_dfs=True):

○ returns a list of lists. For example, if there are three connected

components then you will return a list of three lists. The order of the

sub-lists is not important. However each sub-list will contain the vertices

(in ascending order) in the connected component represented by that list.

Each vertex is represented by an integer from 1 to n. If a vertex has no

edges it will be in a connected component containing only itself. This

function shall call either dfs or bfs method depending on the value of the

argument is_dfs: i.e. do DFS if is_dfs=True, otherwise do BFS.

● def init_vertices(self):

○ a helper function for resetting values of the attributes of vertices.

● def dfs(self, vertex, component):

○ does dfs, finds connected components, and determines if the graph is

bicolorable or not. If it is bicolorable, it is going to set the is_bicolor

member variable to True, otherwise False. Takes two arguments, vertex

(Vertex) and component (list). Returns a connected component as a list of

vertex keys.

● def bfs(self, vertex, component):

○ does bfs, finds connected components, and determines if the graph is

bicolorable or not. If it is bicolorable, it is going to set the is_bicolor

member variable to True, otherwise False. Takes two arguments, vertex

(Vertex) and component (list). Returns a connected component as a list of

vertex keys.

● def bicolor (self):

○ returns True if the graph is bicolorable and false otherwise. i.e. It returns

the value of is_bicolor.

SUBMISSION Upload a zip file containing my_graph.py, which contains a class

2

CPE202 Spring 2020

MyGraph, and your tests to the grader, Gradzilla, then to Canvas. MyGraph should

contain your new graph class including functions that determine the connected

components, get_conn_components (self), which returns a list of lists of vertex

keys, and if the graph is bipartite, bicolor (self), which simply returns a boolean

value.

Examples:

Test input files are available on Canvas.

Input:

9

8

1 2

1 3

1 4

1 5

6 7

7 9

9 8

8 6

9 is the number of vertices and 8 is the number of edges.

If the graph created is g1, then g1.get_conn_components() returns: [[1, 2, 3, 4, 5],

[6, 7, 8, 9]], and g1.bicolor() returns: True.

Input:

8

6

1 2

2 3

3 1

4 6

4 7

4 8

8 is the number of vertices and 6 is the number of edges.

In this graph based on 8 vertices 5 is not connected to any other vertices and has

no edges, therefore it is a component containing only itself.

If the graph created is g2, then

g2.get_conn_components() returns: [[1, 2, 3], [4, 6, 7, 8], [5]], and g2.bicolor()

returns: False.

3

Sale!