Алгоритм поиска цепочки друзей для пользователей соцсети

Моя цель - предложение широкого ассортимента товаров и услуг на постоянно высоком качестве обслуживания по самым выгодным ценам.

Предыстория

Будучи студентом, я решил в качестве курсовой разработать бота для поиска цепочки друзей для соцсети. Мне это показалось достаточно интересным, начал поиск информации на эту тему. В итоге я наткнулся на статью о теория шести рукопожатий, там была описана идея двунаправленного поиска, что показалось мне самым лучшим решением для такой задачи. Вот только никакого алгоритма и его реализации я не обнаружил, поэтому решил разработать свой вариант алгоритма. Теперь же хочу поделиться алгоритмом, который мне удалось разработать.

Обозначения

S(source) — id первого пользователя
SF(source friends) — список id друзей первого пользователя
T(target) — id второго пользователя
TF(target friends) — список id друзей второго пользователя
M(mutual friend) — самый дальний общий знакомый, т.е. расстояние от Sдо Mи расстояние от Tдо Mравны либо отличаются на 1

Алгоритм

0. Находим списки друзей дляSиTи рассматриваем следующие варианты:
1*. ЕслиS\in TFилиT\in SF, то выводим цепочку[S,F]
2*. ЕслиSF\cap TF\neq\varnothing, то выводим цепочку[S,m,F], гдеm— любое id изSF\cap TF
3*. Если не выполнено 1* и 2*, то переходим к шагу 1

1.
Исследуем новый уровень друзей дляT, т.е. смотримSF\cap T_iF, гдеT_i\in TF. Если находится такойT_i, чтоSF\cap T_iF\neq\varnothing, тогдаM=T_i и переходим к шагу 3, иначе
TF=\{T_iF|i=\overline{1,|TF|}\}и переходим к шагу 2

2.
Исследуем новый уровень друзей дляS, т.е. смотримTF\cap S_iF, гдеS_i\in SF. Если находится такойS_i, чтоTF\cap S_iF\neq\varnothing, тогдаM=S_i и переходим к шагу 3, иначе
SF=\{S_iF|i=\overline{1,|SF|}\}и переходим к шагу 1

3.
НайденM, тогда цепочка будет иметь вид[S,…, M,…, T]. Рассмотрим подцепочки [S, …, M]и[M, …, T]Проделаем шаг 1 для парSиM,MиT. Тогда получимM_1для парыSиM,M_2для парыMиT.

4. НайденыM_1иM_2, тогда цепочка будет иметь вид[S,...,M_1,...,M,...,M_2,...,T]. Тогда проделаем шаг 1 для пар SиM_1,M_1иM,MиM_2,M_2иT. Тогда получим M_3для парыSиM_1,M_4для парыM_1иM,M_5для парыMиM_2,M_6для парыM_2иT.

5. Найдены M_3,M_4,M_5,M_6, тогда цепочка будет иметь вид [S,...,M_3,...,M_1,...,M_4,...,M,...,M_5,...,M_2,...,M_6,...,T].
Проделаем шаг 1 для парSиM_3,...,M_6иT.

И т.д. пока все новыеM_i, найденные на k-ом шаге, не станут равны \varnothing.

Графическая интерпретация алгоритма

Шаг 0 (Находим списки друзей дляSиT)

Шаг 0.1* (ЕслиS\in TFили T\in SF)

Шаг 0.2* (Если SF\cap TF\neq\varnothing)

Шаг 0.3* (Не выполнены шаги 1* и 2*, значит переходим к шагу 1)

Шаг 1

Случай перехода к шагу 2
Случай перехода к шагу 2

Случай перехода к шагу 3
Случай перехода к шагу 3

Шаг 2

Случай перехода к шагу 1
Случай перехода к шагу 1

Случай перехода к шагу 3
Случай перехода к шагу 3

Шаг 2 \rightarrowШаг 1 (Для наглядности посмотрим, что происходит при переходе с шага 2 на шаг 1)

Случай перехода к шагу 2
Случай перехода к шагу 2

Случай перехода к шагу 3
Случай перехода к шагу 3

Шаг 3 ([S,...,M,...,T]. Проделаем шаг 1 для парSиM, MиT)

ПараSиM

Случай перехода к шагу 2
Случай перехода к шагу 2

Случай перехода к шагу 4
Случай перехода к шагу 4

ПараMиT

Случай перехода к шагу 2
Случай перехода к шагу 2

Случай перехода к шагу 4
Случай перехода к шагу 4

Последующие шаги понятны, поэтому в графической интерпретации не нуждаются.

Замечание

Если посмотреть на шаги, на которых находимM, то можно заметить момент, который оптимизирует алгоритм. Когда проходим поi-ому другу изTF(SF)и находим для его спискаT_iF(S_iF)пересечение cSF(TF), то можно возвращать не толькоM, но и этого
i-ого друга. Таким образом, за каждую итерацию находим 2 последовательных элемента цепочки, т.е. вместо[S, …, M, …, T]получаем[S,…, M, m, …, T]либо[S,…, m, M, …, T].

Реализация

Функция для поискаM

# source и target - id пользователей S и T
# limit - флаг ограничения по количеству проверяемых пользователей в списках друзей 
def find_mutual_friend(source, target, limit=False):
	# Ограничение по количеству проверяемых пользователей в списках друзей
    FRIENDS_COUNT = 100

	if source == target:
		return None, None, None

	if None in [source, target]:
		return None, None, None

    # Получаем списки друзей для S и T
	source_friends = get_friends(source)
	target_friends = get_friends(target)

	if source in target_friends or target in source_friends:
		return None, None, None
	
	mutual_friends = intersection(source_friends, target_friends)
	if mutual_friends:
		return None, None, mutual_friends[0]

	source_friends = get_friends(source) if not limit else get_friends(source, count=FRIENDS_COUNT)
	target_friends = get_friends(target) if not limit else get_friends(target, count=FRIENDS_COUNT)

	# 0 - достраиваем уровень друзей для T
	# 1 - достраиваем уровень друзей для S
	i = 0
	last_source_level = source_friends
	last_target_level = target_friends
	while True:
        # Обновление SF как более глубокий уровень друзей для S
		if i:
			next_source_level = []

			for friend in last_source_level:
				friends = get_friends(friend, count=FRIENDS_COUNT)
				if not friends:
					continue
				mutual_friends = intersection(last_target_level, friends)					
				
				if mutual_friends:
					return i, friend, mutual_friends[0]

				next_source_level = union(next_source_level, friends)
				
			last_source_level = next_source_level
			i = 0
			continue

        # Обновление TF как более глубокий уровень друзей для T
		next_target_level = []

		for friend in last_target_level:
			friends = get_friends(friend, count=FRIENDS_COUNT)
			if not friends:
				continue
			mutual_friends = intersection(last_source_level, friends)

			if mutual_friends:
				return i, friend, mutual_friends[0]
					
			next_target_level = union(next_target_level, friends)
				
		last_target_level = next_target_level
		i = 1

Функция для формирования цепочки друзей дляSиT

# source и target - id пользователей S и T
def create_chain(source, target):
    # Шаг 0
    # Получаем списки друзей для S и T
	source_friends = get_friends(source)
	target_friends = get_friends(target)

    # Если |TF| > |SF|, то лучше поменять пользователей S и T местами
    # Это связано с тем, что в алгоритме поиск начинается с пользователя T
	if len(target_friends) > len(source_friends):
		temp = source
		source = target
		target = temp

    # Находим M и m (про это описано в замечании)
    # i - указатель стороны, с которой находится пользователь m
    # friend - m
    # mutual_friend - M
	i, friend, mutual_friend = find_mutual_friend(source, target)

    # Шаг 0.1
    # Пользователи S и T являются друзьями 
	if mutual_friend is None:
		return [source, target]

	chain = [source, mutual_friend, target]

    # Шаг 0.2
    # Нет пользователя m, значит возаращаем цепочку [S, M, T]
	if not friend:
		return chain

    # Шаг 0.3
    # Определяем начальную цепочку, которую будет достраивать
	chain = [source, friend, mutual_friend, target] if i else [source, mutual_friend, friend, target]
	while True:
		new_chain = []
		new_mutual_friends = []

        # Находим M и m для пар пользователей из уже составленной цепочки
		for i in range(len(chain) - 1):
			j, friend, mutual_friend = find_mutual_friend(chain[i], chain[i + 1], limit=True)

			new_mutual_friends.append(mutual_friend)

            # Составление подцепочки в формате [S, M, T], либо [S, M, m, T], либо [S, m, M, T] 
			new_chain.append(chain[i])
			if friend not in chain:
				if j:
					new_chain += [friend, mutual_friend]
				else:
					new_chain += [mutual_friend, friend]
			else:
				if mutual_friend:
					new_chain.append(mutual_friend)

        # Дополняем цепочку новыми промежуточными пользователями
		chain = new_chain + [chain[-1]]

        # Проверка на то, что все новые M являются None
		if new_mutual_friends.count(None) == len(new_mutual_friends):
			break

    # Избавляемся от значений None в итоговой цепочке
    # None появляется как M для некоторой пары пользователей, которые являются друзьями
	return remove_None(chain)

Заключение

Алгоритм получился достаточно интересным, но его ещё можно улучшить. Он не является оптимальным, т.к. находит хотя бы какую-то цепочку друзей. Также пользователи могут встречаться не один раз, что приводит к выполнению лишних проверок.

Надеюсь, что данная статья будет кому-нибудь полезна, и жду предложений по оптимизации в комментариях.

Источник: https://habr.com/ru/post/701380/

Интересные статьи

Интересные статьи

poiskvps.ru — сайт для поиска виртуальных серверов. Многие ошибочно называют его “рейтингом”, но это в корне не верно, отмечает создатель сервиса. Сайт отличается от других тем, что там нет сортировки...
Всем привет, меня зовут Иван, я Android-разработчик. Сегодня хочу поделится своим опытом работы с RxJava2 и рассказать, как происходит инициализация цепочки. Почему я вообще решил поднять...
При работе с алгоритмами есть две реальности: как это написано в учебнике и как это получается у тебя. Второе ближе к телу, и хочется, чтобы оно получалось. Главное, понимать, что ты ра...
Изображение: Unsplash Вопрос поиска удаленной работы в хороших компаниях из США и Европы актуален всегда – не все хотят переезжать в другую страну, а участвовать в интересных п...
Привет, я Никита Брижак, серверный разработчик из Pixonic. Сегодня я хотел бы поговорить о компенсации лагов в мобильном мультиплеере. Про серверную лагкомпенсацию написано мно...