Привет всем,
Прежде всего, я не пытаюсь создать социальную сеть, facebook достаточно большой! (Комиксы) Я выбрал этот вопрос в качестве примера, потому что он точно соответствует тому, что я пытаюсь сделать.
Представьте, что в MySQL есть таблица users и таблица user_connections с запросами друзей. Если это так, это будет примерно так:
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
Теперь я хочу найти круги между друзьями и создать массив структуры и поместить этот круг в базу данных (ни один из массивов не может включать одних и тех же друзей что другой уже).
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,
)
Я пытаюсь придумать алгоритм, чтобы сделать это, но я думаю, что это займет много времени обработки, потому что он будет случайным образом искать базу данных, пока она не "закрывает" круг.
PS: Минимальная длина структуры окружности - 3 соединения, а предел равен 100 (поэтому демон не выполняет поиск по всей базе данных)
EDIT:
Я думаю о чем-то вроде этого:
function browse_user($userget='random',$users_history=array()){
$user = user::get($userget);
$users_history[] = $user['userid'];
$connections = user::connection::getByUser($user['userid']);
foreach($connections as $connection){
$userid = ($connection['userid_request']!=$user['userid']) ? $connection['userid_request'] : $connection['userid_accepted'];
// Start the circle array
if(in_array($userid,$users_history)) return array($user['userid'] => $userid);
$res = browse_user($userid, $users_history);
if($res!==false){
// Continue the circle array
return $res + array($user['userid'] => $userid);
}
}
return false;
}
while(true){
$res = browse_user();
// Yuppy, friend circle found!
if($res!==false){
user::circle::create($res);
}
// Start from scratch again!
}
Проблема с этой функцией заключается в том, что она может выполнять поиск по всей базе данных без поиска самого большого круга или наилучшего соответствия.
