# Thread: Rather coplex algorithmic problem

1. ## 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.

* 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?

2. 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. 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. 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. 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. ## just wanted to give my 2 cents.. since i wasn't active @ the time.

PHP Code:
``` select ''+ u.name + '->' + getusername(f1.friends_id) from users AS uINNER JOIN friends AS f1 on (f1.users_id = u.id OR f1.friends_id = u.id)where u.id = startnode AND f1.friends_id=endnodeUNIONselect ''+ u.name + '->' + getusername(f1.friends_id)  + '->' + getusername(f2.friends_id) from users AS uINNER 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=endnodeUNIONselect ''+ u.name + '->' + getusername(f1.friends_id)  + '->' + getusername(f2.friends_id)+ '->' + getusername(f3.friends_id) from users AS uINNER 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. Originally Posted by DarkAngelBGE
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.

#### Posting Permissions

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