SPC

The following function implements SPC.

spc <- function(g) {
  linegraph <- make_line_graph(g)
  source_edges <- V(linegraph)[degree(linegraph, mode = "in") == 0]
  sink_edges <- V(linegraph)[degree(linegraph, mode = "out") == 0]
  tabulate(
    unlist(
      lapply(
        source_edges,
        all_simple_paths,
        graph = linegraph,
        to = sink_edges,
        mode = "out")))
}

Main path search

The following function finds a main path. Do note that there may be other main paths, if there are several main paths with the same total SPC value. This function returns the first main path it finds.

main_search <- function(g) {
  linegraph <- make_line_graph(g)
  V(linegraph)$spc <- spc(g)
  source_edges <- V(linegraph)[degree(linegraph, mode = "in") == 0]
  sink_edges <- V(linegraph)[degree(linegraph, mode = "out") == 0]
  paths <- unlist(
    lapply(
      source_edges,
      all_simple_paths,
      graph = linegraph,
      to = sink_edges,
      mode = "out"),
    recursive = FALSE)
  path_lengths <- unlist(lapply(paths, function (x) sum(x$spc)))
  vertex_attr(linegraph, "main_path") <- 0
  vertex_attr(
    linegraph,
    "main_path",
    paths[[which(path_lengths == max(path_lengths))[[1]]]]) <- 1
  V(linegraph)$main_path
}

Testing

The Wikipedia article for main path analysis has a figure of a graph with SPC values attached to all edges. You can see a copy of this figure above. I transcribed this graph into R, including the expected SPC values and (global) main path.

library(tibble)

wikipedia_g <- graph_from_data_frame(
  tibble::tribble(
    ~from, ~to, ~expected_spc, ~expected_main_path
    "A", "C", 2, 0,
    "B", "C", 2, 0,
    "B", "D", 5, 1,
    "B", "J", 1, 0,
    "C", "E", 2, 0,
    "C", "H", 2, 0,
    "D", "F", 3, 1,
    "D", "I", 2, 0,
    "J", "M", 1, 0,
    "E", "G", 2, 0,
    "F", "H", 1, 0,
    "F", "I", 2, 1,
    "G", "H", 2, 0,
    "I", "L", 2, 0,
    "I", "M", 2, 1,
    "H", "K", 5, 0,
    "M", "N", 3, 1),
  directed = TRUE)

The expectation is that all values output by the spc function equal the expected_spc values, which is the case. Similarly, the values for expected_main_path should match those output by main_search, which is the case as well.

all(E(wikipedia_g)$expected_spc == spc(wikipedia_g))
# TRUE
all(E(wikipedia_g)$expected_main_path == main_search(wikipedia_g))
# TRUE

Update

If you want to find out which path gives the highest sum weight, you can try the code below

g <- graph_from_data_frame(edgelst)
asp <- unlist(
  sapply(
    names(dna_sources),
    function(s) {
      all_simple_paths(g, s, names(dna_sinks))
    }
  ),
  recursive = FALSE
)

path_weight <- sapply(
  asp,
  function(p) {
    v <- names(p)
    sum(merge(
      edgelst,
      data.frame(from = head(v, -1), to = tail(v, -1))
    )$weight)
  }
)

max_cum <- max(path_weight)
path_max <- asp[path_weight == max_cum]

and you will see

> max_cum
[1] 30

> path_max
$`61`
+ 7/33 vertices, named, from a74a1fe:
[1] 6  9  12 29 32 36 39

$`111`
+ 6/33 vertices, named, from a74a1fe:
[1] 11 20 31 32 36 39

Here is a brute-force method using all_shortest_paths (if you don't need all paths being the shortest, you can use all_simple_paths instead)

dna_g <- graph_from_data_frame(dna_edges, directed = T)

dna_sources <- V(dna_g)[degree(dna_g, mode = "in") == 0]
dna_sinks <- V(dna_g)[degree(dna_g, mode = "out") == 0]

edgelst <- aggregate(weight ~ ., cbind(
  do.call(
    rbind,
    unlist(sapply(
      dna_sources,
      function(s) {
        # asp <- all_simple_paths(dna_g, s, dna_sinks) ## if we apply `all_simple_paths`
        asp <- all_shortest_paths(dna_g, s, dna_sinks)$res
        lapply(asp, function(p) {
          v <- names(p)
          data.frame(from = head(v, -1), to = tail(v, -1))
        })
      }
    ), recursive = FALSE)
  ),
  weight = 1
), sum)

dna_df <- merge(dna_edges, edgelst, all = TRUE)

g <- graph_from_data_frame(dna_df, directed = TRUE)

plot(g, edge.label = dna_df$weight)

where

> dna_df
   from to weight
1     1  8      1
2     2 18      1
3     3  4      1
4     3  5     NA
5     3 21      3
6     5 12     NA
7     6  9      3
8     9 12      3
9    10 17      1
10   11 13     NA
11   11 20      4
12   12 15     NA
13   12 29      3
14   13 20     NA
15   14 16      1
16   14 20     NA
17   14 31      3
18   15 22     NA
19   15 29     NA
20   16 17      1
21   16 20     NA
22   17 34      2
23   19 20      2
24   19 21      2
25   19 24      2
26   19 25      2
27   19 25      2
28   20 22     NA
29   20 22     NA
30   20 30      2
31   20 31      4
32   21 22     NA
33   21 32      5
34   22 27     NA
35   23 27      3
36   24 28      1
37   24 37      1
38   26 27      3
39   27 32      6
40   29 32      3
41   30 40      2
42   31 32      4
43   31 40      3
44   32 33     NA
45   32 36     11
46   32 38      7
47   33 32     NA
48   33 35     NA
49   35 38     NA
50   35 39     NA
51   36 38     NA
52   36 39      7
53   36 40      4

and you will get a plot like below