How to find connections between users so I can create a closed friend circle?

Question

Hi all, First of all, I'm not trying to create a social network, facebook is big enough! (comic) I've chosen this question as example because it fits exactly on what I'm trying to do. Imagine that I have in MySQL a `users` table and a `user_connections` table with 'friend requests'. If so, it would be something like this: ``` Users Table: userid username 1 John 2 Amalia 3 Stewie 4 Stuart 5 Ron 6 Harry 7 Joseph 8 Tiago 9 Anselmo 10 Maria User Connections Table: userid_request userid_accepted 2 3 7 2 3 4 7 8 5 6 4 5 8 9 4 7 9 10 6 1 10 7 1 2 ``` Now I want to find circles between friends and create a structure array and put that circle on the database (none of the arrays can include the same friends that another has already). ``` Return Example: // First Circle of Friends Circleid => 1 CircleStructure => Array( 1 => 2, 2 => 3, 3 => 4, 4 => 5, 5 => 6, 6 => 1, ) // Second Circle of Friends Circleid => 2 CircleStructure => Array( 7 => 8, 8 => 9, 9 => 10, 10 => 7, ) ``` I'm trying to think…

Accepted Answer

Alfred Godoy's answer is very useful, in that processing should be done incrementally. I'll try to flesh out some specific detail.

Rather than "people" being "friends" I'll talk about "nodes" connected by "edges". It's not true that cycles grow from 3 to 4 (or n to n+1) nodes. Several edges, not forming a cycle, could be closed by a new edge and form a new cycle.

So instead (or as well) as a list of cycles, we should maintain a list of edge chains. e.g. assuming this Connection table:

```
userid_request  userid_accepted
2               7
3               7
3               8
```

Then the Chain table should contain this:

```
chainid  start  end  length
1        2      3    2
1        2      8    3
2        7      8    2
```

This structure lets you record and retrieve chains of any length, and given two ends of a chain, follow it through using id and length. It takes space... But that's the memory cost of searching for cycles in a graph for you. It can be simplified, depending on exactly what you want to do; give details.

By the way, I assume that the graph is undirected - in other words, an edge from a node to the other goes both ways. In the connection, the node with the lowest id will always be the "request" and the highest id at the "accepted" end.

When a new node is added, you want to maintain the chain table and look whether the new node closes the chain cycles. It involves a couple of queries. I give you one.

Suppose a new entry is added in the Connection table:

```
userid_request  userid_accepted
@new_request    @new_accepted
```

You can use a query to select any such cycle. You already know about the new link and its two nodes so you're only looking for a chain that closes it:

```
select chainid, length
from chain
where (start = @new_request and end = @new_accepted)
or (end = @new_request and start = @new_accepted)
```

(note that because the graph is not directed, you have to look for two cycle configurations).

To maintain the chain table, each time an edge is added:

- look for existing chains prolonged by the node

- look for new chains of length 2.

And then when nodes are removed, you should take out corresponding chains and cycles - the chain table will be big enough as it is.

How to find connections between users so I can create a closed friend circle?

Solution

Problem

Related problems