Edmonds maximum matching algorithm in PHP

Question

I have searched all over the internet trying to find example code in PHP but I am unable to do so. What I am trying to do is match courses to rooms where courses have a set of rooms that they are compatible with.

example: course A can be taught in rooms X, Y and Z, Course B rooms P and Q ect.

Each course can be matched to exactly one room in a given timeslot. I have to create a function that will accept these two sets of rooms and courses and output a maximum matching. Can anyone provide source code in PHP that could get me started? I've never built an algorithm for matching before and don't really know where to begin.

How are you storing/retrieving your data(courses, rooms)? Or have you gotten to that point yet? — Ben Ashton
– Ben Ashton, Commented Mar 9, 2012 at 4:17
Pseudo code is in wikipedia en.wikipedia.org/wiki/Edmonds's_matching_algorithm, you can probably start from there? — Andreas Wong
– Andreas Wong, Commented Mar 9, 2012 at 4:18
The setup you're describing is a bipartite graph, and there are algorithms for finding maximum matchings in bipartite graphs that are much faster than Edmonds' algorithm. You will almost certainly have better luck finding and implementing one of these algorithms. — templatetypedef
– templatetypedef, Commented Mar 9, 2012 at 4:51
The data is stored in and retrieved from a mysql database. @templatetypedef I agree there are much faster algorithms. I believe the Hopcroft-Karp bipartite matching algorithm is faster such as this one. But I dont know how to go about writing the actual code to accept as input an associative array of course name and room. — kenth619
– kenth619, Commented Mar 9, 2012 at 5:36

Sabbir Yousuf Sanny · Accepted Answer · 2012-03-09 07:18:22Z

2

You can try Igor Naverniouk's library code for Bipartite Matching. It's written in C++, but you can easily convert it to PHP.

answered Mar 9, 2012 at 7:18

Sabbir Yousuf Sanny

5944 silver badges9 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

kenth619 Over a year ago

Thank you very much this is definitely a start in the right direction for me. However I am still not sure about the format of the input matrix. Upon further reading I found out that PHP uses matrices as 2D arrays. For this code to work the input must be an m x n matrix which will have a value 1 if there is a matching and 0 for no matching. Should I have a matrix such that $matrix['course_name']['room_name'] = 1 for match and 0 for no match or is it that I have to assign a unique number for each course name and room name and use these as the indexes of the array?

Sabbir Yousuf Sanny Over a year ago

I think you should assign unique number (incremental, from 1 to m) for each course and room (from 1 to n). Of course, it is possible to modify the code to use names as indices, but I think this would be a bit slow.

Collectives™ on Stack Overflow

Edmonds maximum matching algorithm in PHP

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related