Знайти всі шляхи між двома вершинами (вузлами)

Я новачок у програмуванні R, і я залучений до представлення графіків за допомогою R. Я хотів би запитати про те, як я реалізую код, який може знайти всі шляхи між двома вершинами або вузлами на основі матриці суміжності. Я бачив багато реалізацій на інших мовах програмування, але більшість з них використовувала черги, як у (BFS), щоб вони працювали. Наприклад, це список країв мого графіка.

          [,1] [,2]
    [1,]    0    1
    [2,]    1    2
    [3,]    1    3
    [4,]    1    4
    [5,]    2    5
    [6,]    2    6
    [7,]    5    7
    [8,]    5    8
    [9,]    6    9
   [10,]    6   10
   [11,]    8   11
   [12,]   10   12
   [13,]   11   13
   [14,]   11   14
   [15,]   11   15
   [16,]   12   16
   [17,]   12   17
   [18,]   12   18
   [19,]   13   19
   [20,]   16   20
   [21,]   19   21
   [22,]   19   22
   [23,]   20   22
   [24,]   20   23    

Якщо я хотів, щоб всі шляхи між вузлом 0 і вузлом 22 були двома шляхами:

   [[1]]
    [1]  0  1  2  6 10 12 16 20 22

   [[2]]
    [1]  0  1  2  5  8 11 13 19 22

Дякую

5
За контуром, ви маєте на увазі шляхи без повторюваних вершин? Інакше у вашому прикладі ви б нескінченно багато, оскільки є петля.
додано Автор Szabolcs, джерело
Я просто хотів знайти всі шляхи між двома заданими вершинами. Прикладом є спрямовані графіки без циклів.
додано Автор malhom, джерело

5 Відповіді

Я використав наступний код, щоб створити матрицю (вершини х вершин) яка містить кількість всіх шляхів між кожними двома вершинами .

library(igraph)
setwd("C:/Workspace")
graph <- read.graph("graph.txt", format="edgelist")
direct <- get.adjacency(graph)
indirect <- direct
max <- vcount(graph)-1
for(i in 0:max)
 for(j in 0:max)
  indirect[i,j] <- length(get.all.shortest.paths(graph, from=i, to=j, mode="out"))

Для цього я пропоную використовувати бібліотеку igraph.

library(igraph)

Я поставив ваш список країв у файл з назвою "graph.txt", який я помістив у "C: workpace". Потім я використовую наступний код для читання цього файлу в R:

setwd("C:/Workspace")
graph <- read.graph("graph.txt", format="edgelist")

Можливо, ви захочете побудувати графік, щоб переконатися, що все в порядку (однак, цей крок можна залишити):

plot(graph, layout=layout.fruchterman.reingold.grid)

Створюю матрицю суміжності, щоб побачити всі прямі зв'язки між вершинами:

direct <- get.adjacency(graph)

Потім я створюю манекенну матрицю під назвою "непрямий", яка є копією матриці adjancency. Мені просто потрібна ця матриця для подальшого заповнення непрямими значеннями:

indirect <- direct

Нарешті, я перебираю весь графік, щоб знайти число всіх непрямих зв'язків між кожними двома вершинами. Я поставив це число в непряму матрицю, яку я тільки що створив раніше (додатково я створив пропозицію, поклавши всі значення на нуль діагоналі). Режим "out" гарантує підрахунок лише вихідних шляхів. Також можна встановити значення "in" або "total":

max <- vcount(graph)-1
for(i in 0:max)
 for(j in 0:max)
   indirect[i,j] <- length(get.all.shortest.paths(graph, from=i, to=j, mode="out"))
4
додано

Припускаючи, що у вас є проста спрямований ациклічний графік (DAG), для підрахунку буде працювати такий підхід:

(A^n)_ij gives you the number of paths of length n between nodes i and j. Therefore you need to compute A + A^2 + ... + A^n + ... to get the total number of paths between any two nodes. It is essential that you work with a DAG, as this guarantees that for large enough n, A^n = 0. Then the result can be written as A . (I - A)^(-1) where I is the identity matrix.


EDIT:

Я не знаю R, так що я можу лише дати вам якийсь псевдокод або пояснення.

По-перше, знайдемо набір вузлів, доступних з вузла i . Давайте визначимо вектор v , щоб містити тільки нулі, за винятком позиції i , де він містить 1. для 1-го вузла

v = (1,0,0, ..., 0)

Тепер нехай v_ (n + 1) = sign (v_n + A. V_n) , де метою функції sign() є замінити ненульові елементи на 1 і зберегти нулі 0. Зробіть цю ітерацію, поки не досягнете фіксованої точки, і ви отримаєте вектор v з ненульовими елементами на позиціях, що відповідають вузлам, доступним з вузла i .

Якщо замість вектора v ви починаєте з ідентифікаційної матриці (такого ж розміру, як A ), ви отримаєте доступні вузли для кожного іншого вузла за один раз.

Тепер у вас є набір доступних вузлів для будь-якого стартового вузла. Аналогічним чином можна отримати список вузлів, з яких можна досягти будь-якого цільового вузла (просто поверніть зворотне спрямоване ребро, тобто перенесіть A )

Далі перейдемо до графіка та знайдемо всі потрібні вам шляхи .

Ця рекурсивна функція повинна робити це (псевдокод):

traverse( path-so-far, target ):
    let S = the last element of path-so-far
    if S == target:
        output path-so-far
        return
    let N = the set of nodes reachable from S in one step
    remove all nodes from N from which the target is not reachable
    for each K in N:
       traverse( append(path-so-far, K), target )

path-so-far is the list of nodes already visited; target is the target node.

Для даної пари початкових і цільових вузлів просто зробіть траверс ({start}, target) .

Зауважте, що крок, на якому ми видаляємо всі вузли, з яких не може бути досягнута мета, лише там, щоб прискорити обхід, і не вводити "блайнди"

2
додано
Чи можете ви пояснити, що таке сенс цілі не досяжний. Ви маєте на увазі не досяжну в 1 кроці або щось інше, у вас є нерекурсивний метод для того ж.
додано Автор Avinash, джерело
@malhom я оновив свою відповідь. Прийміть, якщо це корисно для вас.
додано Автор Szabolcs, джерело
Я дійсно повинен знайти всі самі шляхи (не рахуючи всіх шляхів). Я знайшов деяку реалізацію на інших мовах, які використовували черги, щоб визначити, які вузли вже відвідували і так далі. Не могли б ви пояснити, як це зробити, простежуючи рекурсивну графу всіма можливими способами. Можливо, мені доведеться використовувати його для великих графіків.
додано Автор malhom, джерело
Я розгляну ваші думки і спробую зробити це. Дякую
додано Автор malhom, джерело

Ви хочете добре прочитати вигляд завдання графічних моделей:

http://ftp.heanet.ie/mirrors /cran.r-project.org/web/views/gR.html

Хоча я не розумію, що ви робите, це графічне моделювання в статистичному сенсі, це перегляд задач окреслює пакети для обробки графіків і алгоритмів.

Я використовував igraph для різних графічних речей.

0
додано
Я бачив і працював над пакетом igraph. Я міг знайти тільки (get.all.shortest.path). Я, можливо, доведеться реалізувати (алгоритм DFS), щоб дати мені всі шляхи між будь-якими даними вершинами.
додано Автор malhom, джерело

Перевірте наступну функцію igraph:

http://igraph.org/r/doc/all_simple_paths.html

У ньому перераховані всі прості шляхи з одного джерела.

Опис Ці списки функцій є простими шляхами від однієї вершини джерела до іншої вершини або вершини. Шлях простий, якщо вершини, які він відвідує, не відвідується більше одного разу.

Використання all_simple_paths (графік, від, до = V (графік), mode = c ("out", "in", "all",   "всього"))

Аргументи

графік
Вхідний графік.

від
Вихідна вершина.

до
Цільова вершина вершин. За замовчуванням для всіх вершин.

режим Константа символів, що дає, чи повинні бути розраховані найкоротші шляхи до або з заданих вершин для спрямованих графів. Якщо згодом будуть розглянуті найкоротші шляхи від вершини, якщо в цьому до неї буде йти. Якщо всі, за замовчуванням, буде використаний відповідний неорієнтований граф, тобто. шукаються ненаправлені шляхи. Цей аргумент ігнорується для неорієнтованих графів.

Деталі

Зауважимо, що потенційно існують експоненціально багато шляхів між двома вершинами графа, і ви можете втратити пам'ять при використанні цієї функції, якщо ваш графік схожий на решітку.

Ця функція в даний час ігнорується декількома краями і петлями.

0
додано

Просто виконайте перший пошук глибини без перевірки відвідуваних вузлів - це може дати вам кількість шляхів між двома точками певної довжини

void dfs(int start, int hops)
{
  if(hops == k && start == t)
    {
      path++;
      return;
    }
  else if(hops >= k)
    return;
  for(int w = 1; w <= n; w++)
    if(routes[start][w])
      dfs(w, hops + 1);
}

І в основному, дзвоніть

dfs(start_node, length);

Як робити, якщо існує кілька шляхів, що з'єднують дві точки, і кожен вважається іншим?

0
додано
працюватиме, лише якщо графік є ациклічним
додано Автор hasanatkazmi, джерело