10-06 Graph

Graph class

Default Dictionary

Sometimes you want to have a “default value” in a dictionary. The default value is returned whenever you ask for the value of a key that is not in the dictionary. A typical use would be counting words, where the count starts at 0 the first time you see a word.

Basic Usage

Import the default dictionary from the collections package.

from collections import defaultdict

a = dict()
a[5] ## error

b = defaultdict(int)
b[5] ## gives 0

Advanced Usage

You can write your own default function, or use built in constructors like list or set.

def ten(): return 9
c = defaultdict(ten)
c[5] ## gives 9

d = defaultdict(list)
d[5].append(9)
d[5].append(11)
d[5] ## the list [9,11]

g = defaultdict(set)
g[5].add(100)
g[5].add(200)
g[5] ## the set {100,200}

Practice

Generate a list of 25 random integers like this: choose an integer x in the interval [0,10], square it, add that to the list. Produce a histogram chart of the frequency of each number 0..100. Print out each nonzero count number: count.

Example:

a = [4,81,81,25,81,25,4,4,4,4,4] # should be random squares
b = histogram(a)
print(b)
## { 4: 6, 25: 2, 81 : 3}
print(fancy(b))
##  4 xxxxxx   <-- good spacing on 4 optional
## 25 xx
## 81 xxx

Stress testing: change your list to be 250,000 random integers in the range [0,100000]. Find every number that appears more than nine times. Output your information in ascending order so it looks organized.

Graph

Make a Graph class that the following methods:

  • adjacency list is stored in the dictionary self.edges

  • (OMIT) adjacency list is sorted in ascending numerical order

  • vertices are numbered 0 up to but not including self.nvertices

  • (OMIT) total count of edges is self.nedges

  • self.degree(v) gives the degree of vertex v = number of edges going out of v.

  • Create a graph from a number of vertices along with a list of lists of integers, “edges”. See the Reader Tests section for examples of the format. The line [1,5,6] in edges indicate that vertex 1 connects to vertices 5 and 6. That could also be specified on two lines with edges being [[1,5],[1,6]].

     Graph.read_graph1(nvertices: int, edges: [[int]]) -> 'Graph'

  • Graph.read_string1(theString): load a graph from a single string. See below for the format.

  • Graph.read_graph(fileH) loads the graph from an open filehandle.

  • self.__str__() prints out the human-readable representation just like maze.

Reader Tests

Graph: BFS

(Assignment change: Do shortest distance first!)

Write a function to produce a list of vertices in the graph, starting with 0, in breadth first order.

gdata = """
NVERT 11
0 8
1 2
2 8
3 5 8
4 5
5 10
6 9
7 10
8
9 10
10
"""

Test output:

g = Graph.read_graph(gdata.strip().split("\n"))
order = g.bfs0()
print(order)
## [0,8,2,3,1,5,4,10,7,9,6]