phpalgorithmgraphmatching

Edmonds maximum matching algorithm in PHP


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.


Solution

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