SitePoint Sponsor

User Tag List

Results 1 to 7 of 7
  1. #1
    SitePoint Wizard
    Join Date
    May 2003
    Location
    Berlin, Germany
    Posts
    1,829
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    Rather coplex algorithmic problem

    Hi everybody,
    just out of interest, I would like to know an algorithmic solution to the common "networking" function of social applications.

    Here is the task:
    * people each have profiles on a website
    * everybody has a friend's section
    * everybody can invite everybody as a friend


    Well that could mean that we have a members table and a friends table whereas the latter is a lookup-table for the former with id, member_id,friend_id.

    Now I want to achieve this "networking" thing, which means that in the friends section of a members profile, you can see if you have a "relation" to that member via friends.

    Like you have a friend "A", who has a friend "B", who has a friend "C", who has that target member as friend.

    How can this be done without breaking the whole system with stack overflows in a recursive setup?

    Thanks in advance!

  2. #2
    SitePoint Addict
    Join Date
    Nov 2005
    Location
    Germany
    Posts
    235
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Well basically the relationships can be seen as a Graph. There are different ways to represent a graph, see adjacency-matrix/list.
    When walking this graph of relationships I guess you will have to restrict the depth (maybe try a breadth-first-traversal) and mark already visited elements to avoid infinite loops and cycles.

  3. #3
    SitePoint Wizard
    Join Date
    May 2003
    Location
    Berlin, Germany
    Posts
    1,829
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Yes, I knew that.

    However, my question is more like, how would I go for sql querying? Would I query all relationships in the database and pick out the ones I need? Or is there a clever way to store the data rows like in adjacent tree traversal?

  4. #4
    SitePoint Addict
    Join Date
    Nov 2005
    Location
    Germany
    Posts
    235
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Ah, sorry.

    Depending on the number of users pulling the whole DB into a adjacency matrix (n^2 entries) might be no option. On the other hand I imagine walking the graph with several queries (A has relation to B, C --> query B, query C ...) is only possible in an environment where elements have little or no relationships.

    Ok, let's have another stab into the dark:
    Since querying is so expensive I think one could implement some independent update mechanism which stores the relations in a large database regularly.

  5. #5
    SitePoint Wizard Ren's Avatar
    Join Date
    Aug 2003
    Location
    UK
    Posts
    1,060
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Store the transistive closure of the graph would leave finding relations as a simple select, though require more storage.

    Perhaps some triggers on the friends table to maintain it.

  6. #6
    SitePoint Evangelist
    Join Date
    Aug 2004
    Posts
    428
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    just wanted to give my 2 cents.. since i wasn't active @ the time.

    PHP Code:
    select ''u.name '->' getusername(f1.friends_idfrom users AS u
    INNER JOIN friends 
    AS f1
     on 
    (f1.users_id u.id OR f1.friends_id u.id)
    where u.id startnode AND f1.friends_id=endnode

    UNION

    select 
    ''u.name '->' getusername(f1.friends_id)  + '->' getusername(f2.friends_idfrom users AS u
    INNER JOIN friends 
    AS f1
     on 
    (f1.users_id u.id OR f1.friends_id u.id)
    INNER JOIN friends AS f2
     on 
    (f2.users_id IN (f1.friends,f1.users_id) OR f2.friends_id IN (f1.friends,f1.users_id))
    where u.id startnode AND f2.friends_id=endnode


    UNION

    select 
    ''u.name '->' getusername(f1.friends_id)  + '->' getusername(f2.friends_id)+ '->' getusername(f3.friends_idfrom users AS u
    INNER JOIN friends 
    AS f1
     on 
    (f1.users_id u.id OR f1.friends_id u.id)
    INNER JOIN friends AS f2
     on 
    (f2.users_id IN (f1.friends,f1.users_id) OR f2.friends_id IN (f1.friends,f1.users_id))
    INNER JOIN friends AS f2
     on 
    (f3.users_id IN (f2.friends,f2.users_id) OR f3.friends_id IN (f2.friends,f2.users_id))
    where u.id startnode AND f3.friends_id=endnode

    ....... continue up to 7 levels ...... 



    notes:
    I think you can use a nested inner join with friends to users to create a tmp table with the name column appended to friends
    so that calling the function isn't required. i used a function to make my solution readable somewhat more readable.



    friends table:
    users_id, friends_id

    primary key on both columns will allow
    1,2
    2,1
    with the solution i provided you need to create a trigger to stop
    2,1 from being inserted.

    this is why someone needs to accept that you are their friend.


    disclaimer:
    this is untested.. came up with the solution off the top of my head. as i thought this was an interesting post.


    this is placing the responsibility on the db which gives you less power for visual format...
    so i would use a format as follows: id:name, id2:name2, ....
    and use preg_match then trim then explode
    this will allow you to grab images of the user by id

    or you can move to an all php solution using recursion ... look for an old thread of mine where i answer someone's problem with building a composite menu

  7. #7
    SitePoint Addict Jasper Bekkers's Avatar
    Join Date
    May 2007
    Location
    The Netherlands
    Posts
    282
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)
    Quote Originally Posted by DarkAngelBGE View Post
    However, my question is more like, how would I go for sql querying?
    You don't, a relational database is not optimal for these kinds of data structures.

    What I would do is store the adjacency matrix of the graph in a custom binary format which can be be pretty optimized if you realize the matrix only consists of 0's and 1's (assuming every 'relationship' is mutual), making it able to store 8 relationships in a byte. And because it's only a few calculations this might be faster than querying a SQL database.

    Hmm, this sounds like an interesting thing to implement, I might do that tonight .

    Edit: never mind, the adjacency matrix would require O(kn) time to find all friends for k levels deep and n total users. Although an adjacency list doesn't have the neat storage optimizations, should take less time for a larger n. If I'm not talking out of my *** that would be O(k) when implemented with a hash map because they have constant lookup time.
    Last edited by Jasper Bekkers; Jun 7, 2007 at 11:54.
    Design patterns: trying to do Smalltalk in Java.
    I blog too, you know.


Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •