R语言一种边权最大化的断开图方法

x33g5p2x 于 2022-12-25 发布在其他

关注(0)|答案(2)|浏览(145)

给定一个连通图和一个N个指定顶点的列表，我想找到一种有效的方法来创建N个子图，每个子图包含一个指定顶点。为了实现这一点，我们可以修剪边。但是，我们应该修剪尽可能少的边权重。
例如，让我们从下面的图开始，我们想要得到三个包含三个红色顶点

之一的子图
结果应如下所示：

现在，我使用的是启发式算法，但它在某些边的情况下效果不好，并且在顶点数量上有n^2的复杂度。其思想是计算两个顶点之间的最短路径，并删除最亮的边，重复直到顶点断开连接。以下是我的代码：

import pandas as pd
import igraph as ig
from collections import Counter

ucg_df = pd.DataFrame(
    [
        [0, 1, 100],
        [0, 2, 110],
        [2, 3, 70],
        [3, 4, 100],
        [3, 1, 90],
        [0, 3, 85],
        [5, 7, 90],
        [0, 8, 100],
        [3, 6, 10],
        [2, 5, 60],
    ],
    columns=["nodeA", "nodeB", "weight"],
)

ucg_graph = ig.Graph.DataFrame(ucg_df, directed=False)

ig.plot(
    ucg_graph,
    target='stack1.pdf',
    edge_label=ucg_graph.es["weight"],
    vertex_color=['red']*3 +  ['green']*(len(ucg_df)-3),
    vertex_label = ucg_graph.vs.indices
)


def generate_subgraphs_from_vertexes(g, vertex_list):
    for i, vertex in enumerate(vertex_list):
        for j in range(i + 1, len(vertex_list)):
            while True:
                path = g.get_shortest_paths(vertex_list[i], vertex_list[j], mode='ALL', output='epath',
                                     weights='weight')[0]
                if len(path) == 0:
                    break
                edge_2_drop = min(g.es[path], key=lambda x: x['weight'])
                edge_2_drop.delete()

    return g
graph = generate_subgraphs_from_vertexes(ucg_graph, ucg_graph.vs[0,1,2])

ig.plot(
    graph,
    target='stack2.pdf',
    edge_label=graph.es["weight"],
    vertex_color=['red']*3 +  ['green']*(len(ucg_df)-3),
    vertex_label = graph.vs.indices
)

我可以用什么样的算法来更好地解决这个问题？

来源：https://stackoverflow.com/questions/74854464/efficient-way-to-disconnect-graphs-while-maximising-edges-weight

2条答案

按热度按时间

im9ewurl1#

我对Python中的igraph不太熟悉，但下面是我对R的尝试，希望你能从中得到一些提示。
我认为您的问题可以重新表述为assignment problem，因为关键部分是将"红色"分配给关联的"绿色"顶点以使成本最大化

library(igraph)
library(lpSolve)

# red vertices
vred <- V(g)[V(g)$color == "red"]

# subgraph that contains vred
sg <- induced.subgraph(
  g,
  unique(unlist(ego(g, 1, vred)))
)

# green vertices in sg
vgreen <- V(sg)[V(sg)$color == "green"]

# cost matrix
cost.mat <- get.adjacency(sg, attr = "label", sparse = FALSE)[vred, ][, vgreen]
p <- lp.assign(cost.mat, "max")
idx <- which(p$solution > 0, arr.ind = TRUE)
# edge list for max assignment
el1 <- cbind(names(vred[idx[, 1]]), names(vgreen[idx[, 2]]))

# all edges associated with vred
el <- get.edgelist(g)
el2 <- el[rowSums(matrix(el %in% names(vred), ncol = 2)) > 0, ]

# remove edges that are not obtained for the max assignment
rmEls <- do.call(
  paste,
  c(
    data.frame(
      el2[!apply(el2, 1, function(x) toString(sort(x))) %in% apply(el1, 1, function(x) toString(sort(x))), ]
    ),
    sep = "|"
  )
)
out <- g %>%
  delete.edges(rmEls)

运行plot(out, layout = layout_nicely(g))时，您将看到

数据

df <- data.frame(
  from = c(0, 0, 2, 3, 3, 0, 5, 0, 3, 2),
  to = c(1, 2, 3, 4, 1, 3, 7, 8, 6, 5),
  weight = c(100, 110, 70, 100, 90, 85, 90, 100, 10, 60)
)

# original graph object
g <- df %>%
  graph_from_data_frame(directed = FALSE) %>%
  set_edge_attr(name = "label", value = df$weight) %>%
  set_vertex_attr(name = "color", value = ifelse(names(V(.)) %in% c("0", "1", "2"), "red", "green"))

赞(0）回复(0）举报 2022-12-25

kzipqqlq2#

受Find rows of matrix which contain rows of another matrix的启发，假设图是无向的，我发现：

mtch  <- matrix(match(el2, el1), ncol = 2)
    idx   <- which(abs(mtch[,1] - mtch[,2]) == nrow(el1))
    rmEls <- get.edge.ids(g, t(el2[-idx,]))
    rmEls
    ## [1] 1 2 3 6

赞(0）回复(0）举报 2022-12-25

我来回答

R语言一种边权最大化的断开图方法

2条答案

数据

相关问题

热门标签

最新问答

R语言 一种边权最大化的断开图方法

2条答案

数据

相关问题

热门标签

最新问答

R语言一种边权最大化的断开图方法