Get paths from a specified node in a directed graph

Share:

Description

Obtain a list of all possible paths from a given node within a directed graph

Usage

1
2
get_paths(graph, from = NULL, to = NULL, shortest_path = FALSE,
  longest_path = FALSE, distance = NULL)

Arguments

graph

a graph object of class dgr_graph.

from

the node from which all paths will be determined.

to

the node to which all paths will be determined.

shortest_path

an option to return paths that are the shortest in the set of all determined paths.

longest_path

an option to return paths that are the longest in the set of all determined paths.

distance

a vector of integer values that specify which of the valid paths to return when filtering by distance.

Value

a list of paths, sorted by ascending traversal length, comprising vectors of node IDs in sequence of traversal through the graph.

Examples

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
library(magrittr)

# Create a simple graph
graph <-
  create_graph() %>%
  add_node_df(create_nodes(1:8)) %>%
  add_edge(1, 2) %>%
  add_edge(1, 3) %>%
  add_edge(3, 4) %>%
  add_edge(3, 5) %>%
  add_edge(4, 6) %>%
  add_edge(2, 7) %>%
  add_edge(7, 5) %>%
  add_edge(4, 8)

# Get a list of all paths outward from node `1`
get_paths(graph, from = "1")
#> [[1]]
#> [1] "1" "3" "5"
#>
#> [[2]]
#> [1] "1" "2" "7" "5"
#>
#> [[3]]
#> [1] "1" "3" "4" "6"
#>
#> [[4]]
#> [1] "1" "3" "4" "8"

# Get a list of all paths leading to node `6`
get_paths(graph, to = "6")
#> [[1]]
#> [1] "4" "6"
#>
#> [[2]]
#> [1] "3" "4" "6"
#>
#> [[3]]
#> [1] "1" "3" "4" "6"

# Get a list of all paths from `1` to `5`
get_paths(graph, from = "1", to = "5")
#> [[1]]
#> [1] "1" "3" "5"
#>
#> [[2]]
#> [1] "1" "2" "7" "5"

# Get a list of all paths from `1` up to a distance
# of 2 node traversals
get_paths(graph, from = "1", distance = 2)
#> [[1]]
#> [1] "1" "3" "5"
#>
#> [[2]]
#> [1] "1" "2" "7"
#>
#> [[3]]
#> [1] "1" "3" "4"

# Get a list of the shortest paths from `1` to `5`
get_paths(
  graph,
  from = "1",
  to = "5",
  shortest_path = TRUE)
#> [[1]]
#> [1] "1" "3" "5"

# Get a list of the longest paths from `1` to `5`
get_paths(
  graph,
  from = "1",
  to = "5",
  longest_path = TRUE)
#> [[1]]
#> [1] "1" "2" "7" "5"

Want to suggest features or report bugs for rdrr.io? Use the GitHub issue tracker.