Circular matching. PHP / MySql

Question

Hi I need some help with the following scenario in php. I have a db with users every user has an ID, have_card and want_card. I know how to make a direct match (one user trades with another user). But if there is no direct match but there is a circular swap like:

User #1 has card A wants card B

User #2 has card B wants card C

User #3 has card C wants card A

In this scenario there is no direct match between two users. But if:

User #1 gives his card to User #3

User #3 gives his card to User #2

User #2 gives his card to User #1

Every ones happy.

All the info I have to start with is User #1 how do I find User #2 and User #3?

Thanks to everyone for your answers.

Answer 1

This is how I would do it: Create a recursive algorithm like this:

1 take one user, see what he wants

2 find another user who has what user one wants

- if user two wants, what user one has, everything is fine an we're done
- if not, continue

3 find another user who has what user two wants

- if user three wants, what user one has, everything is fine and we're done
- if not, continue ...

... and so on, but you should a have limit for recursive levels to prevent endless searching.

Answer 2

Maybe this:

Finding possible first matches (users who have the card user#1 wants)

select name from user where has in (select wants from user where name = '1');

Iterate through those matches and try finding the missing link:

select name from user where name in (select name from user where has in (select wants from user where name = <match>));

Answer 3

This is a challenging scenario. I had to build this for a book swapping application a while back and using a white board I was able to more easily visual and solve the problem.

What I did was use the same table inside the query multiple times, just using a different name.

In my scenario, the books that were needed were in a separate table from the books the users had. Hopefully you'll be able to see the logic in this query:

$query = "SELECT 
        A.Owner_ID as Owner_1, C.Owner_ID as Owner_2, E.Owner_ID as Owner_3 
    FROM
        E_User_Books_Have as A, E_User_Books_Have as C, E_User_Books_Have as E,
        E_User_Books_Needed as B, E_User_Books_Needed as D,E_User_Books_Needed as F

    WHERE 
     A.Book_ID=D.Book_ID AND
     C.Book_ID=F.Book_ID AND
     E.Book_ID=B.Book_ID AND 
     A.Owner_ID='$ME' AND B.Owner_ID='$ME' AND A.ID='$ID'AND 
     C.Owner_ID=D.Owner_ID AND  
     E.Owner_ID=F.Owner_ID AND
     C.Owner_ID!='$ME' AND
     E.Owner_ID!='$ME'";

Answer 4

Interestingly, I came across a similar thing to this with the BoardGameGeek Maths Trade. Basically, everyone specifies that they either want a game or have a game and the algorithm maximises trades including circular dependencies.

This is exactly what you want.

Here is an explanation of how TradeMaximizer works. It uses Dijkstra's algorithm and skew heaps to find minimal matching solutions (ie a smaller circle is preferable to a larger circle).

Granted this is created in Java but algorithms are universal and you can recreate it as required, particularly once you understand what it's doing and why.

Answer 5

Thanks to everyone for your help.