降低算法的复杂度，从满足给定约束的无向图构造有向图（DAG）

Question

我有一个包含 4,000 多个节点的网络，并且我有一个边列表（节点对之间的连接）。所有节点都应该汇聚到一个中心点，但我无法对节点进行排序，因为它们没有以可以重新排序的方式进行编号或标记。

我需要什么？：根据附带的小例子，我需要所有节点都指向节点F（F可以从所有节点到达），这样无向图成为有向图 (DAG) 并且作为限制，每个节点对之间只有一条边。当且仅当要删除循环（例如 A -> B，B <- A）时，我才可以删除边。我也不能添加边，因为这是一个真实的网络，我不能在它们不存在的地方创建连接。

我有的是这个：

 library(igraph)
 library(tidygraph)
 library(ggraph)
 library(tidyverse)

 # edge list
 edgelist <- tribble(
  ~from, ~to,
  "A", "B",
  "A", "C",
  "B", "D",
  "C", "D",
  "C", "E",
  "D", "E",
  "D", "F")
 
 # create the graph
 g <- as_tbl_graph(edgelist)
 
 # undirected graph 
 g %>% 
  ggraph(layout = "graphopt") +
  geom_edge_link() +
  geom_node_point(shape = 21, size = 18, fill = 'white') +
  geom_node_text(aes(label = name), size = 3) +
  theme_graph()

这是我想出的排序过程，这样边缘列表就会变成 DAG：

 s <- names(V(g))
 
 # define node objective
 target <- "F"
 
 # exclude target from vertex list
 vertex_list <- s[s != target]
 
 # calculate the simple path of each node to the destination node (target)
 route_list <- map(vertex_list, ~ all_simple_paths(graph = g, 
                                                   from = .x,
                                                   to = target)) %>% 
  set_names(vertex_list) %>% 
  map(~ map(., ~ names(.x))) %>%
  flatten() %>% 
  map(~ str_c(.x, collapse = ","))
 
 
 # generate the list of ordered edges
 ordered_edges <- do.call(rbind, route_list) %>% 
  as.data.frame(row.names = F) %>%  
  set_names("chain") %>% 
  group_by(chain) %>% 
  summarise(destination = str_split(chain, ","), .groups = "drop") %>% 
  mutate(
   
   from = map(destination, ~ lag(.x)) %>% 
    map(~ .x[!is.na(.x)]),
   
   to = map(destination, ~ lead(.x)) %>% 
    map(~ .x[!is.na(.x)]),
  ) %>% 
  
  select(from, to) %>% 
  unnest(cols = everything()) %>% 
  group_by(across(everything())) %>% 
  summarise(enlaces = n(), .groups = "drop") %>% 
  select(-enlaces)

警告：当节点数达到一定大小（假设为 90）时，此算法会生成使图成为非循环图的循环，因此我需要一个额外的过程要做的是在 Python 中应用一个名为 feedback_arc_set 的函数来删除使图形成为 DAG 的边。

为简单起见，我没有包括删除这些循环的必要代码，因为在这个特定示例中没有生成循环。

 # draw the graph again
 as_tbl_graph(ordered_edges) %>% 
  ggraph(layout = "graphopt") +
  geom_edge_link(arrow = arrow(length = unit(3, 'mm'),
                               type = "closed", 
                               angle = 30),
                 end_cap = circle(7, 'mm')) +
  geom_node_point(shape = 21, size = 18, fill = 'white') +
  geom_node_text(aes(label = name), size = 3) +
  theme_graph()

^{由 reprex package (v2.0.0)}

于 2021-07-07 创建

那么有什么问题吗?:当节点数大于2000[=19=时算法复杂度 ]

如果我尝试对 2000 个节点执行此操作，算法将永远不会结束。我把它运行放了 24 小时，它没有完成。事实上，我没有找到一种方法来知道它是否有效。在这个place我发现{igraph}all_simple_paths的函数在幕后使用了DFS，但是复杂度是O(|V|!) where |V|是顶点数，|V|!是顶点数的阶乘。

有没有更简单的方法来做到这一点？

Answer 1

无法避免进行 DFS。然而，问题不是由于 DFS 算法的复杂性。我可以在不到一秒的时间内对 403,394 个节点和 3,387,388 links 的图进行 DFS https://github.com/JamesBremner/PathFinder2/wiki/Performance

可能的问题是您的算法需要执行大量 DFS。

我建议使用以下算法，该算法应该运行在一秒钟左右的时间内生成一个中等大小的图，例如 4,000 个节点。

您需要做的第一件事是检查每个节点是否都可以从 F 到达。从 F 开始的单个 DFS 会告诉您这一点。如果每个节点都不可达，那么不加边就无法解决问题。

现在，遍历路径以确定每个 link 应该有的方向。请注意，任何未遍历的边都是不必要的，可以删除 - 从而防止“意外”引入循环

请注意，如果您有一个不错的 DFS 实现，允许您指定访问者，您可以一步完成，在 DFS 进行时标记边的方向。剩下的就是删除未访问过的不必要的边。然后整个事情将运行在 4,000 节点图上闪现。

===

对快速解决此问题的应用程序感兴趣吗？运行在 MSWindows 机器上，用 C++17 编写，基于 PathFinder class，保证性能 > 1,000 nodes/second?

Answer 2

快速回答

其实可以将顶点按照distances到"F"进行分组，然后检查两个相邻组的节点之间的邻域添加边。

背后的想法

关于到 "F" 的距离，这个想法来自以下事实：

如果一个节点的距离为 d，则其父节点的距离必须为 d+1。
如果X的距离为d+1，那么距离为d的节点必须是X的子节点当且仅当它们是[=的邻居时17=].

我的尝试

D <- distances(g)
d <- distances(g, "F")
lst <- split(colnames(d), d)
lst <- lst[order(as.integer(names(lst)))]
res <- c()
for (k in head(seq_along(lst), -1)) {
    pre <- lst[[k]]
    nxt <- lst[[k + 1]]
    for (p in pre) {
        dp <- D[p, nxt, drop = FALSE]
        if (any(dp == 1)) {
            res[[length(res) + 1]] <- data.frame(
                from = colnames(dp)[dp == 1],
                to = p
            )
        }
    }
}
dag <- graph_from_data_frame(do.call(rbind, res))

然后

plot(dag)

给予

降低算法的复杂度，从满足给定约束的无向图构造有向图（DAG）

Reduce the complexity of the algorithm to construct a directed graph (DAG) from an undirected graph that satisfies the given constraints

r

graph-theory

time-complexity

igraph

tidygraph

快速回答

背后的想法

我的尝试