Scheduling group presentations using Graph Theory and Sage.

Yesterday (2014-03-26) I spoke at the Embedded Enterprise Exchange about my new first year module. I used a Hangout on air during the talk and you can see it here:

That's not what I'm going to talk about here though. The course I talked baout ends with all the 'companies' (groups of 4 students) giving a $\approx 25$ minute talk.

I need to schedule 40ish talks and this needs to fit around the student availability as well as my own. In this post I'll describe how I did this using a combination of Doodle, +Sage Mathematical Software System and Graph Theory.

The beginning of this post will be some of the boring details but towards the end I start talking about the mathematics (so feel free to skip to there...).

First of all I needed to know my students availability.

For this I simply used Doodle: https://doodle.com. I kind of use Doodle for every meeting I have to schedule (they also offer a cool tool that lets you show your availability so students/colleagues have an indication of when I might be able to meet with them).

Here's a screenshot of the responses:

You can't really see anything there as I had to zoom out a lot to grab the whole picture. Doodle allows you to download the information for any given poll in .xls format so I could relatively easily obtain the biadjacency matrix $M$ for my problem. Where $M_{ij}$ is 1 if group $i$ is available for schedule slot $j$ and 0 otherwise.

The mathematics and code needed.

Once I've got a .csv file (by tweaking the .xls file) of the biadjacency matrix I import that in to +Sage Mathematical Software System  and convert it to an instance of the `Matrix` class using the following:

import csv 
f=open(DATA+'availabilitymatrix','r') 
data = [[int(j) for j in row] for row in csv.reader(f)] 
f.close() 
M = Matrix(data)

I then need to remove any particular scheduled slots that are not picked by any company:

M = matrix([row for row in M.transpose() if max(row) != 0]).transpose()

Once I've done this I can define the bi-partite graph (bi-partite simply means that the vertices can be separated in to 2 non adjacent collections):

g = BipartiteGraph(M)

We can then get a get a picture of this, I do this using a 'partition' (a graph colouring) that will colour the groups (red) and the schedule slots (blue):

g = BipartiteGraph(M)
p = g.coloring()
g.show(layout='circular',dist=1,vertex_size=250, graph_border=True, figsize=[15,15],partition=p)

The various options I pass to the `show` command are simply to get the circular arrangement (and other minor things):

The above looks quite messy and what I essentially want is get as many pairwise matchings between the blue vertices (slots) and red vertices (companies) so that each schedule slot is attributed at most 1 company and every company has at least 1 schedule slot.

On any given graph $G=(V,E)$ this problem is known as looking for a maximal matching and can be written down mathematically:

Max:  $\sum_{e \in E(G)} m_e$

Such that:  $\forall v$ $\sum_{e \in E(G) \atop v \sim e} m_e \leq 1$

We are in essence finding a subset of edges of our original graph in such a way as to maximise the number of edges such that no vertex has more than 1 edge.

This is all explained extremely well at the +Sage Mathematical Software System documentation pages here.

Furthermore at the documentation the code needed to solve the problem is also given:

p = MixedIntegerLinearProgram()  
matching = p.new_variable(binary=True)
p.set_objective(sum(matching[e] for e in g.edges(labels=False)))
for v in g:
      p.add_constraint(sum(matching[e]
          for e in g.edges_incident(v, labels=False)) <= 1)
p.solve()

When I run the above, `p` is now a solved Mixed Integer Linear Program (corresponding to the matching problem described). To obtain the solution:

matching = p.get_values(matching)
schedule = [e for e,b in matching.iteritems() if b == 1]

Calling `schedule` gives a set of edges (denoted by the corresponding vertex numbers):

[(5, 57), (0, 45), (23, 50), (4, 42), (38, 60), (26, 56), (34, 62), (16,

68), (1, 43), (7, 40), (9, 44), (36, 58), (12, 49), (35, 71), (28, 66),
(25, 47), (24, 53), (6, 46), (3, 64), (39, 67), (17, 69), (22, 55), (13,
48), (33, 41), (10, 63), (21, 61), (30, 52), (29, 65), (37, 70), (15,
54), (19, 51), (11, 59)]

It is then really easy to draw another graph:

B=Graph(schedule)
p = B.coloring()
B.show(layout='circular',dist=1,vertex_size=250, graph_border=True, figsize=[15,15],partition=p)

Which gives:

You can see that the obtained graph has all the required properties and most importantly is a lot less congested.

Some details.

I'm leaving out some details, for example I kept track of the names of the companies and also the slots so that the final output of all this looked like this:

4InARow: Fri1100

Abacus: Tue0930

Alpha1: Thu1130

Alpha2: Mon0930

AusfallLtd: Fri1230

AxiomEnterprise: Thu1000

Batduck: Thu1430

CharliesAngles: Thu1500

CwmniRhifau: Mon1330

EasyasPi: Fri1130

Evolve: Thu1300

HSPLLtd.: Mon1030

JECT: Tue1200

JJSL: Thu1030

JNTL: Mon1400

JennyCash: Tue1630

KADE: Fri1330

MIAS: Fri1300

MIPE: Thu1100

MLC: Tue1600

Nineties: Mon0900

Promis: Fri1400

R.A.C.H: Tue1530

RYLR: Tue1230

SBTP: Fri1030

Serendipity: Mon1230

UniMath: Tue1300

VectorEnterprises: Tue1330

Venus: Thu1400

codeX: Mon1300

dydx: Wed1630

eduMath: Thu0930

(BatDuck is my favourite company name by far...)

Why did I do this this way?

There are 3 reasons:

1. I shared the schedule with my students through a published Sage sheet on our server. That way they can see a direct applied piece of mathematics and can also understand some of the code if they wanted to.

2. "Point and click doesn't scale" - I'm sure I could have solved this one instance of my problem with pen and paper and some common sense faster than it took me to write the code to solve the problem. The thing is next year when I need to schedule these talks again it will at most take me 3 minutes as the code is all here and ready to go. (Most readers of this blog won't need that explained but if any of my students find their way here: that's an important message for you).

3. It was fun.

My students write about their first Python conference

Last week I wrote about my impressions from my first Open Source Software conference (OSS): https://djangoweekend.org/

It was an awesome conference but the highlight for me was seeing 3 of my students take full advantage of the event. I asked Matt, Alex and James to write a bit of a guest post for this blog about their experiences:

--------------------------------

Here's what Matt had to say:

"Having never been to a conference like this before, and with only a few months of coding experience under my belt, I had no idea what to expect from Django Weekend Cardiff. Despite this I had an incredible weekend. Everyone that I met and talked to was friendly and more than willing to answer my questions. 

While some of the talks went a little over my head, the clinics were very helpful in getting me started with Django. I even felt confident enough to give a lightning talk, that gave me the chance to voice my opinion on computing with regards to education, and how it had helped me over the few months I was leaning it as part of my undergraduate course for maths.


Overall I had a great time, and will definitely be keeping an eye out for Django Weekend Cardiff 2015."

Matt's lightning talk was recorded so as soon as it's online I will be post about it. He did an awesome job.

--------------------------------

Here's what +Alex Carney had to say:

"I first became aware of the open source scene when I was in Year 7 and my dad installed Ubuntu 7.10 on my ancient laptop in a bid to keep it usable. I slowly became more and more fascinated on what software I was able to download for free and have a play with, from creating animations with Blender to messing around in GIMP and to hear him say that it was made by normal people such as ourselves I was blown away thinking how on Earth could people like my dad and myself create such wonders?

Well needless to say it reignited my desire to learn programming, I had dabbled with Pascal and BASIC beforehand but I couldn't get much further than a series of print statements and lost interest. But then to discover Python, a language with syntax that was actually readable to someone just starting secondary school was amazing, slowly I was able to teach myself parts of it in short bursts over the years, before dropping it when I was in Year 11, to learn C++ mostly forgetting about Python.

Fast forward to September 2013, when I started my Maths degree at Cardiff Uni, and I finding out that I would be taught Python as part of the course was like being reunited with an old friend. But this time there was a major difference I was actually using Python. Back when I was teaching myself I never had any concrete goals or deadlines, I would follow one example before swiftly moving on to the next without stopping to apply what I had learnt. So naturally it was hard to maintain focus and I never produced anything worthwhile. 

However being set tasks to complete was great as I was finally applying my knowledge I had gained over the years and was able to appreciate how useful being able to program is, once you start thinking like a programmer the only limit is your imagination - Oh! and of course how powerful your computer is...

I can't thank Vince and the School of Mathematics at Cardiff enough for sponsoring me to go to the conference because it made me realise a lot of things. Firstly is that there really is a thriving welcoming community on the open source scene. I was always vaguely aware that it existed as I trawled through forums and mailing lists looking for solutions to problems I was having, but something always stopped me from joining in. I was thinking that even though it was open there was some mystical entry barrier that you had to pass before you would be accepted.

However by going to the conference I was shown the complete opposite. Nobody so much batted an eyelid when they saw me, some student only just able to scratch the surface of Python's power and knowing absolutely nothing about Django. Moreover they wanted to speak to me, they wanted to hear about it from a beginner's perspective, they wanted to know what it was like learning Django for the first time, what could they do to make it easier for me to learn? While having a chat with one of the core Django developers I pointed out that I didn't find certain steps in a tutorial that clear and afterwards he went away and amended the tutorial clearing up the confusion that I had!

It was incredibly interesting to hear how other people have used Python in their work and I was blown away at the power of not only the programming language itself but the community as well. An example from a particular talk was the Astronomy community, how Python was able to help the community create a common standard for sharing data and how all the tools developed by individuals went on to benefit the community as a whole. Leaving researchers able to concentrate more on the science than the technical difficulties and headaches of having to deal with fragmented standards and datasets.

I want to finish by saying how truly inspired attending the conference made me and I not only want to thank Vince and the School of Mathematics for giving me the opportunity, but to thank Daniele Procida for making the conference a reality in the first place. I will definitely want to attend next year's and I'm even thinking of going to  PyConUK in September. I am yet to contribute to an open source project but I'm hoping that's an issue I can fix sooner rather than later."

Alex was one of the students in the class with the most starting knowledge; in fact he helped me win a bet with +Jason Young (that I would be able to get a student to use Vim before the end of the year: Alex used Vim from the start...). It's really nice to read that he found the whole conference interesting and more importantly inspiring.

--------------------------------

The final post is from +James Campbell but he has his own blog that I'd really recommend you taking a look at (James is also a rugby referee so he blogs about that as well). Here's the post he wrote about the conference: http://www.jamescampbell.org.uk/?p=417

If it's too much effort to click over to there here's a bit I stole:

"Today they were working on fixing bugs and reviewing code for the upcoming Django 1.7 release. However, despite how busy they were, whenever I needed a hand someone was happy to help. At one point I had Django core developers discussing the best way to solve one of my problems. These guys are some of the best in the world at what they do, yet they still found time to help a complete newcomer, and I’m really grateful to all those who did so."

My students and my first PyCon

A couple of months ago an email somehow found it's way in to my inbox mentioning a new user group that was setting up in Cardiff. This was from some guy called Daniele Procida. As a Python coder really enthusiastic to be part of the Open Source Software (OSS) community I thought this would be awesome so I've been along to the monthly meetings where all things Python and Django are discussed.

However many months later I got to attend my first PyCon (in fact a DjangoCon): https://djangoweekend.org/

Here's the programme that I carried around in my back pocket:

Professor Tim Phillips, the head of the School of Mathematics kindly agreed to sponsor 3 tickets for students on my Computing for Mathematics course. I gave 3 tickets to students as a reward for their individual coursework (James wrote about Markov chains and Snakes and Ladders, Alex about Fractals and Matt about prime numbers).

+Jason Young who has been my research undergraduate student for a couple of years now (and is a very able coder) attended and +Izabela Komenda (a post-doc) also presented some of her PhD work.

Here's a picture of my Cardiff students, Daniele and I:

It was great that so many sponsors contributed to the conference (full list here) and also that +Cardiff University supported the event wholeheartedly, Roger Whitaker (the dean of research for the physical sciences) even opened the scientific talks on Friday.

Frankly:

It was the best conference I've ever been to.


The atmosphere cultivated by the OSS community is really amazing. Everyone is really encouraging, understanding and just plain ol' nice.

From the scientific talks on the Friday where usages for Python in Science were discussed to witnessing what a 'code sprint' was on the Sunday: everyone was just exceptionally nice.

I learnt Django over christmas and the help people were willing to give (not once making my mistakes more than they were) was really cool.

For example this morning I sat down with Baptiste, one of the core Django developers and he really kindly answered all the (noobish) questions I had (before leaving today he actually gave me his card and told me to get in touch if I had any further problems with a particular thing).

That is just one example of the awesome atmosphere that was cultivated during the conference. The event brilliantly mixed advanced programming for one of the most popular web frameworks with accessible topics for every attendee. I think that this is something that is kind of inherent to the OSS community, you are encouraged to put yourself out there and potentially make mistakes.

For this reason alone I'm extremely glad that the 3 undergraduates got to attend the event. 

Fear of failure and mistakes is something that sometimes really holds students back. As educators it's very important for us to make sure students learn to embrace mistakes.

During one of the talks on Saturday a particular particularity of Django was being discussed and I thought to myself:

I wonder if my students will be put off by "how much they don't understand" and perhaps this will end up being a negative experience for them...

I could not have been more wrong, their attitudes were perfect. They realised that they were very much at the beginning of the road (some of them had not coded before October) and just took advantage of everything around them.

James gave a talk on the Friday which was great and Matt gave a lightning talk (less than 5mins):

They all spoke to the experts around them constantly and by Sunday were themselves writing Django apps. It was great to have +Robert Dragan of learnium help some of them debug their code on the Sunday.

In fact towards the end of Sunday James even had Daniele (a core Django developer) and Charlie (a super-duper really helpful and nice Django developer/person) helping him work on a site:

I won't write much more about the whole event but I'll just repeat something that Matt said during his lightning talk.

He started by saying that he was a bit dismayed when at the beginning of his degree he was told that he was going to have to learn how to code (my course is brand new), he then talked about how he thought +Sage Mathematical Software System helped him gain a better understanding of the prime number theorem but it was what he said last that was really awesome (a lot of other attendees commented on it):

"Why did I have to wait until coming to University to learn to code?"

(All the talks on Saturday were recorded so I really look forward to sharing his talk, it was very well delivered.)

This whole event was a really great experience for me but more importantly my students.

The conference will be running again next here which is awesome for my future students. Next time Daniele, (who is one of the most impressive human beings I've ever met) will have (at least) me to help organise the it.

I've already signed up for my next PyCon (http://pyconuk.org/) and more importantly I've asked myself:

"Why did I have to wait till now to attend an OSS conference?"