Проблема, как реализовать алгоритм для шести градусов разделения?

Графические алгоритмы могут помочь вам здесь. Изучение о них тоже весело!

• Графическое подключение Для подключения.
• Dijkstra (A *) для путей между пользователями
• Простые DFS для поиска всех пользователей n узлов от вашего пользователя

Dijkstra или аналогичные должны использоваться, если вы хотите найти кратчайший путь между двумя пользователями. Между ними может быть несколько путей, а Dijkstra позаботится о том, чтобы отметить, когда он нашел замыкающий путь, чем другой, который был найден раньше.

Чтобы найти кратчайшие пути между всеми пользователями, которые вам придется использовать что-то вроде Floyd-Warshall . Это хороший пример динамического программирования и довольно прост в реализации. Псевдокод из Википедии:

 1 /* Assume a function edgeCost(i,j) which returns the cost of the edge from i to j
 2    (infinity if there is none).
 3    Also assume that n is the number of vertices and edgeCost(i,i) = 0
 4 */
 5
 6 int path[][];
 7 /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
 8    from i to j using intermediate vertices (1..k−1).  Each path[i][j] is initialized to
 9    edgeCost(i,j) or infinity if there is no edge between i and j.
10 */
11
12 procedure FloydWarshall ()
13    for k := 1 to n
14       for i := 1 to n
15          for j := 1 to n
16             path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

У меня было посмотрено на это некоторое время назад и не смог придумать эффективное решение для веб-приложения.

Я оказался 5 уровнями, а не в шесте

см. Здесь для моего Google Group Post Существует решение SQL и C #.

Примечание: , что вы должны Google для «алгоритма Dijkstra», как известно, является хорошим алгоритмом, чтобы найти кратчайший путь.

Редактировать: Попробуйте это Ссылка

BTW Метод CLR выполнил самый быстрый.

Первый вопрос может быть решен с использованием алгоритма ДижКСТРА. Второе на использование алгоритма DFS. Это уже говорилось с другими парнями, просто хотел указать, что наиболее эффективное решение для обеих проблем не доступно в одном алгоритме.

псевдокод можно найти по адресу:

[Wikipedia] [1]

для Dijkstra и один в Python для DFS по адресу:

http://en.wikipedia.org/wiki/depth-first_search

Google и вы найдете много.

Сомневаюсь, что вы сможете найти псевдокод (по крайней мере, я еще не нашел). Вот некоторые из интересных читателей:

"Шесть степеней разделения", объясненная в Новом Компьютерном Алгоритме
CU computer scientist помогает объяснить, как работает "шесть степеней разделения"
SO - Как я могу программно доказать концепцию "шести степеней разделения"?

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

При переходе вас просят перейти из определенного пункта . TSVN спрашивает вас, что бы вы хотели, чтобы этот пункт была, и у вас есть один из трех выбор:

• , где вы работаете прямо сейчас (ваша рабочая версия копии)
• , где репозиторий находится сейчас ( версия HEAD репозитория)
• некоторые другие произвольные версии (конкретная версия)

Обновить: ОП добавила несколько дополнительных вопросов, которые не были частью оригинала, поэтому я изменил свой ответ.

Почему мы не можем перейти от самого GUI репозитария (может быть головной редакцией)?

Графический интерфейс TortoiveSVN не представляет полный набор операций, которые возможны с Subversion. Subversion - это просто набор инструментов командной строки, а TSVN - обертка вокруг них. Если вы хотите полностью создать новую ветвь на сервере, просто используйте:

svn copy svn://example.com/repo/trunk/ svn://example.com/repo/branches/1.4

Можете ли вы перечислить шаги, необходимые для ветвления из каталога?

Руководство TortouseSVN достаточно четко в том, как это сделать. См. здесь .

Я стараюсь не полагаться на Singleton, однако я предпочитаю развязку, чтобы не использовать Singleton. Таким образом, я часто использую Singleton в сочетании с образцом Prototype, которые позволяют регистрировать Прототипы при загрузке библиотеки (построение глобальных объектов).

Я пишу сервер, состоящий из нескольких библиотек. Существует ряд «общих» библиотек, затем по одной библиотеке на службу. Перед «главной» библиотекой ставится задача посмотреть на полученное сообщение и вызвать нужный сервис в зависимости от ключа... Используется простой std:: map .

Использование синглтона для карты позволяет мне иметь полностью развязанный код. Ни одна библиотека не зависит от моей библиотеки служб, ни одна строка кода вне моей библиотеки служб не предназначена для регистрации ее службы. На самом деле, это такое, что я могу решить, какие сервисы встраиваются просто, изменив мою команду «ссылку» во время компиляции: если я не связываюсь с библиотекой, ее сервис не встраивается.

Я действительно считаю это полезным... для конфигурации и такой я предпочитаю использовать Монообразец: т.е. нормальный класс поиска со всеми экземплярами, совместно использующими одни и те же данные (таким образом, оборачивая реальный синглтон). Облегчает миграцию на случай необходимости, так как клиенты не знают, что используют Singleton под прикрытием.

Для задачи 2, вы не будете делать лучше, чем поиск по ширине, за исключением, возможно, кэширования.

Для задачи 1 примените решение для задачи 2. Найти всех пользователей не более 3 прыжков от пользователя X. Конечно, если пользователь Y в этом наборе, вы закончили. В противном случае выполните ширину-сначала поиск, начиная с пользователя Y, и остановка, как только вы достигнете любого пользователя, который, как вы уже знаете, доступен из X.

(Если вы кэшируете небольшую информацию о том, как вы достигли каждого пользователя во время задачи 2, то будет легко восстановить точный путь, когда вы найдете ссылку в задаче 1.)

На Sybase SQL записаны следующие скрипты. Возможно, вам придется пройти небольшие модификации в соответствии с вашим сервером БД.

Проблема 1.

create table #connections (
    my_user  varchar(10)  not null  ,
    knows varchar(10)  not null  ,
        CONSTRAINT connection_pk PRIMARY KEY CLUSTERED ( my_user, knows)   
) 

create table #traversed (id varchar(10) primary key)

insert into #connections VALUES ('UserA','UserB')
insert into #connections VALUES ('UserB','UserA')
insert into #connections VALUES ('UserB','UserC')
insert into #connections VALUES ('UserC','UserB')
insert into #connections VALUES ('UserC','UserD')
insert into #connections VALUES ('UserD','UserC')
insert into #connections VALUES ('UserD','UserF')
insert into #connections VALUES ('UserF','UserD')

DECLARE @str_sql   varchar(200)               
DECLARE @str_order varchar(60)

declare @start varchar(10)
set @start = ('UserD')
declare @end varchar(10)
set @end = ('UserA')

if (@start >= @end)
    set @str_order = " order by id desc"
else
    set @str_order = " order by id asc"


INSERT INTO #traversed VALUES (@start)

WHILE (select count(*) from #traversed where id = @end) = 0    
BEGIN     
  INSERT INTO #traversed (id)    
  SELECT DISTINCT knows  
  FROM #connections e JOIN #traversed p ON p.id = e.my_user  
  WHERE e.knows NOT IN (SELECT id FROM #traversed)     
  AND e.knows between (select case when @start < @end then @start else @end end)  
      and (select case when @start < @end then @end  else @start end) 
END

set @str_sql = "SELECT #traversed.id FROM #traversed" + @str_order 
exec (@str_sql)

Проблема 2.

create table #connections (
    my_user  varchar(10)  not null  ,
    knows varchar(10)  not null  ,
        CONSTRAINT connection_pk PRIMARY KEY CLUSTERED ( my_user, knows)   
) 

create table #traversed (id varchar(10) primary key)

insert into #connections VALUES ('UserA','UserB')
insert into #connections VALUES ('UserB','UserA')
insert into #connections VALUES ('UserB','UserC')
insert into #connections VALUES ('UserC','UserB')
insert into #connections VALUES ('UserC','UserD')
insert into #connections VALUES ('UserD','UserC')
insert into #connections VALUES ('UserD','UserF')
insert into #connections VALUES ('UserF','UserD')

declare @start varchar(10)
set @start = ('UserB')

declare @higher_counter int
declare @lower_counter int

set @higher_counter = 0
set @lower_counter = 0

INSERT INTO #traversed VALUES (@start)

WHILE (@higher_counter < 3)
BEGIN     
  INSERT INTO #traversed (id)    
  SELECT DISTINCT knows  
  FROM #connections e JOIN #traversed p ON p.id = e.my_user  
  WHERE e.knows NOT IN (SELECT id FROM #traversed)     
  AND e.knows > @start 

  set @higher_counter = @higher_counter +1
END  

WHILE (@lower_counter < 3)
BEGIN     
  INSERT INTO #traversed (id)    
  SELECT DISTINCT knows  
  FROM #connections e JOIN #traversed p ON p.id = e.my_user  
  WHERE e.knows NOT IN (SELECT id FROM #traversed)     
  AND e.knows < @start 

  set @lower_counter = @lower_counter +1
END   

SELECT #traversed.id FROM #traversed

Предполагая, что исходные данные находятся в таблице: соединения: (Personeid, KnowspersonId)

1) Это придется использовать широкий подход. Ваш потенциал для хорошей производительности ограничен из-за экспоненциального характера проблемы (хотя этот экспоненциальный характер - это почему теоретически вам нужно только 6 градусов: D). Убедитесь, что вы ограничиваете глубину своего поиска . Какой бы вкус SQL вы выбираете, вы, вероятно, будете лучше, используя его итеративные расширения, в отличие от чистого установленного решения на основе.

Следующее будет основным подходом с использованием Microsoft T-SQL:

CREATE PROCEDURE FindPath (@UserX int, @UserY int)

CREATE TABLE #SixDegrees(
  ConnectedUser int,
  Depth int,
  Path varchar(100),
  CONSTRAINT PK_SixDegrees PRIMARY KEY CLUSTERED (
    ConnectedUser
  )
)

DECLARE @Depth int,
        @PathFound varchar(100)
SET @Depth = 0

INSERT INTO #SixDegrees (@UserX, 0, CAST(@UserX as varchar))
/*Next line just in case X & Y are the same*/
SET @PathFound = (SELECT Path 
                  FROM #SixDegrees 
                  WHERE ConnectedUser = @UserY)

WHILE @Depth < 6 AND @PathFound IS NULL
BEGIN
  SET @Depth = @Depth + 1
  INSERT INTO #SixDegrees
  SELECT  k.KnowsPersonID, @Depth, (SELECT Path 
                                    FROM #SixDegrees 
                                    WHERE ConnectedUser = k.Link) + ',' + CAST(k.KnowsPersonID AS varchar)
  FROM (
      SELECT  MIN(ConnectedUser) Link, KnowsPersonID
      FROM    #SixDegrees
              JOIN Connections ON
                PersonID = ConnectedUser
      WHERE   Depth = @Depth
              /*EDIT: Added the following*/
              AND KnowsPersonID NOT IN (
                  SELECT  ConnectedUser
                  FROM    #SixDegrees
                  )
      GROUP BY KnowsPersonID
      ) k

  SET @PathFound = (SELECT Path 
                    FROM #SixDegrees 
                    WHERE ConnectedUser = @UserY)
END

IF @Path IS NULL
  PRINT 'No path found'
ELSE
  PRINT @Path
GO

Редактирование : в вышеупомянутом решении я изначально забыл исключить пользователей уже в таблице Temp #sixdegres.

2) Маленький твик на вышеупомянутом, чтобы всегда петли на глубину 3, оставит вас с #sixdegres, содержащие все, что вы заинтересованные.

, однако, следующее чистое решение на основе набора должно быть более эффективным :

SELECT  DISTINCT KnowsPersonID
FROM    Connections
WHERE   PersonID IN (
    SELECT  DISTINCT KnowsPersonID
    FROM    Connections
    WHERE   PersonID IN (
        SELECT  KnowsPersonID
        FROM    Connections
        WHERE   PersonID = @UserX
        ) l1
    ) l2

Что-то вроде этого?

http://net.tutsplus.com/freebies/themes/netbeans-twilight-theme/

http: //nettuts.s3.cdn. plus.org/338_netBeansfreebie/twilight.png http://nettuts.s3.cdn.plus.org/338_netbeansfreebie/twilight.png

(Этот ответ эквивалентен Djikstra. Это в основном деталь реализации.)

Чтобы ответить № 2, вы можете использовать мультипликацию Boolean Matrix для определения подключения до степени P .

Предполагая, что у вас есть булева Matrix M , где:

M(A, B)= A is directly connected to B

затем

(M(A, B))^P= A is connected to B within P links.

Матричное умножение должно использовать и для умножения и или для добавления:

Вы можете много оптимизировать это, только делая умножение для записей, которые были ранее ложными, а также осознавая, что матрица симметричная. Это оставлено как упражнение для читателя.

У меня есть предложение, которое сильно отличается от тех, у вас уже есть. Если вы должны придерживаться базы данных SQL, и вы не знаете, какая-либо Java, это предложение не будет многое использовать.

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

Проект NEO4J содержит базу данных диаграммы на основе диска, совместно будет много алгоритмов графов для работы. Цитата:

Neo4j - это графическая база данных. Это встроен, на основе диска, полностью Трансуляционный двигатель Java настойчивости что хранит данные, структурированные на графах а не в таблицах. График (Математическое Линго для сети) Гибкая структура данных, которая позволяет более гибкий и быстрый стиль разработка.

Соответствующий пример использования Neo4j на их Wiki демонстрирует веб-приложение середина разделения с использованием данных IMDB. Пример иллюстрирует кратчайшие расчеты на пути между любым актером и Кевином беконом.

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

1. Направленные против некрития
2. Типы / отношения кромки
4. Атрибуты, такие как тяжелые весики

Как уже было упомянуто на других сообщениях, есть ряд алгоритмов для Расчет самых коротких путей, таких как Dijkstra, Floyd Warshall или BFS. Все они были реализованы в Neo4J, а некоторые примеры предусмотрены здесь .

Я отвечаю только на решение SQL. Это дает все пути 3 шага, хотя он не может быть «эффективным» для больших наборов данных. Таблицы «знают», «NOW_1» и т. Д. Все идентичны и имеют два поля P1 и P2. Он имеет запись только тогда, если 1) P1 знает P2 или 2) P2 знает P1. Данные в P1 и P2 могут быть произвольными строками, соответствующими каждому человеку.

Этот запрос SQL Acccess должен приносить все пути, в которых знание B знает, знает D без циклов (например, знание B знает, знает). Вам все еще нужно устранить дубликаты (ABCD = DCBA), но их можно легко сделать легко на втором шаге. Циклы устранены путем предотвращения повторов предыдущих людей в заявлениях, где.

Выберите Know.p1, all.p2, come_1.p2, all_2.p2

От (знайте внутреннее присоединение знают как all_1 onny.p2 = all_1.p1)

Внутреннее соединение знают как знание_2 по знанию_1. P2 = come_2.p1

где (((CONLE_1.P2) <> [Знаешь]. [P1]) и ((CONLE_2.P2) <> [Знаете]. [P1] и (all_2.p2) <> [Знаешь]. [P2]))

order kne.p1, all.p2, come_1.p2, all_2.p2;

Не так элегантно, как предыдущие решения, но, похоже, работает нормально. У нас был какой-то опыт работы с программированием с ограниченными возможностями и обнаружил, что процесс SQL быстрее для определенных проблем.