CS1210 Computer Science I: Foundations
Homework 3: Character Graphs
Due Friday, November 30 at 11:59PM
Assignment
In this homework, we’re going to extent the solution to HW2 (you may use your own, or use the one I
provide in the template file) to produce character graphs, that is, a graphic representation of the
interactions between characters over the course of a book. As before, we’ll break up the book into evensized
chunks (the xstep parameter of HW2) and produce a graph for each chunk, showing the shifting
interactions of the characters. We base the notion of an interaction on the occurrance of the two
character’s name in "close enough" proximity within the text. So, for example, if our proximity threshold
is 100 words, and Ratty and Badger are mentioned within a 100 words of each other 20 times in a given
chunk of text, then we say their interaction weight is 20.
Our approach is to use the index you built in HW2 with buildIndex() to discover and construct a list of
interactions for each of the xstep chunks of the text. An example should help make this clear; here, we’re
breaking the book into 10 chunks:
p l o t ( fi l e= ’wi nd . t x t ’ , cmi n=4 0, xs t e p s =1 0 )
and we’re using half of the width of the chunk as the interaction threshold (so, if the book is 80000 words
long, each of the 10 chunks are 8000 characters long, and an interaction occurs if the two characters are
mentioned within 4000 words of each other. This should first produce the usual character plot:
followed by 10 character graphs like these:
1 Revised November 14, 2018
2 Revised November 14, 2018
showing the dynamic interactions of the characters over the course of the book.
To plot the character graphs, we’ll be using the NetworkX library:
h t t p s : / / n e t wo r kx . g i t hub . i o / docume n t a t i o n / s t a b l e /
Like with matplotlib, you will probably have to install NetworkX:
cond a i n s t a l l n e t wo r kx
and then import it into your Python session, as in the template.
Plotting the graphs is fairly easy using the spring embedding capacity of NetworkX. Your real work is just
in one function:
d e f ma pCh a r s (N, I , imi n, ima x, dma x ) :
which constructs an edge list of the form:
[ ( ’mo l e ’ , ’ i ’ , { ’we i g h t ’ : 1885 } ) , ( ’mo l e ’ , ’ badg e r ’ , { ’we i g h t ’ : 613 } ) , . . . ( ’ badg e r ’ , ’
Describing all the edges between, e.g., Mole and I in this chunk and the number of proximal occurrances
of the two characters (here, 1885 times). Once you have the list of weighted edges constructed, the rest of
the code won’t be too bad (and we’ll talk about it in class the week after Thanksgiving).
3 Revised November 14, 2018