首页 文章

将图形转换为outdegree 1（除了额外的零权重边缘）

提问于
浏览 次
1

我在python中从http://www.dis.uniroma1.it/challenge9/download.shtml读取http://www.dis.uniroma1.it/challenge9/data/rome/rome99.gr等图形 . 例如，使用此代码 .

#!/usr/bin/python
from igraph import *
fname = "rome99.gr"
g = Graph.Read_DIMACS(fname, directed=True )

（我需要将“p sp 3353 8870”“更改为”p max 3353 8870“以使用igraph来实现此功能 . ）

我想将图形转换为所有节点都具有1度（除了允许添加的额外零权重边缘除外）但仍保留所有最短路径的图形 . 这是原始图中两个节点之间的路径应该是新图中的最短路径，当且仅当它是转换图中的最短路径时 . 我会在一个例子后再详细解释一下 .

一种方法，我想是用v.outdegree（mode = OUT）节点用一个小的线性子图替换每个节点v . 在子图中，节点通过零权重边缘依次连接 . 然后，我们将子图中的节点连接到我们创建的其他小子图中的第一个节点 .

我不介意使用igraph或networkx执行此任务，但我仍然坚持使用如何执行此操作的语法 .

例如，如果我们从图G开始：

enter image description here

我想将其转换为图H：

enter image description here

由于第二个图比第一个图有更多的节点，我们需要通过它具有与第一个图相同的最短路径来定义我们的意思 . 我只考虑用标记为X1的节点的简单字母标记的节点之间的路径 . 换句话说，在此示例中，路径不能在A2或B2中开始或结束 . 我们还在考虑路径时合并节点的所有版本 . 因此，H中的路径A1-> A2-> D被认为与G中的A-> D相同 .

这是我有多远 . 首先，我将零权重边添加到新图中

h = Graph(g.ecount(), directed=True)
#Connect the nodes with zero weight edges
gtoh = [0]*g.vcount()
i=0
for v in g.vs:
    gtoh[v.index] = i 
    if (v.degree(mode=OUT) > 1):
        for j in xrange(v.degree(mode=OUT)-1):
            h.add_edge(i,i+1, weight = 0) 
            i = i+1
    i  = i + 1

然后我添加主边

#Now connect the nodes to the relevant "head" nodes.
for v in g.vs:
    h_v_index = gtoh[v.index]
    i = 0
    for neighbour in g.neighbors(v, mode=OUT):
        h.add_edge(gtoh[v.index]+i,gtoh[neighbour], weight = g.es[g.get_eid(v.index, neighbour)]["weight"])
        i = i +1

这样做有更好/更好的方法吗？我觉得一定有 .

python networkx igraph

1 回答

  • 2

    以下代码应该在 igraph 和Python 2.x中工作;基本上它完成你提出的建议：它为图中的每个单个节点创建一个"linear subgraph"，并将一个外出边连接到与旧节点对应的线性子图中的每个节点 .

    #!/usr/bin/env python

from igraph import Graph
from itertools import izip

def pairs(l):
    """Given a list l, returns an iterable that yields pairs of the form
    (l[i], l[i+1]) for all possible consecutive pairs of items in l"""
    return izip(l, l[1:])

def convert(g):
    # Get the old vertex names from g
    if "name" in g.vertex_attributes():
        old_names = map(str, g.vs["name"])
    else:
        old_names = map(str, xrange(g.vcount))

    # Get the outdegree vector of the old graph
    outdegs = g.outdegree()

    # Create a mapping from old node IDs to the ID of the first node in
    # the linear subgraph corresponding to the old node in the new graph
    new_node_id = 0
    old_to_new = []
    new_names = []
    for old_node_id in xrange(g.vcount()):
        old_to_new.append(new_node_id)
        new_node_id += outdegs[old_node_id]
        old_name = old_names[old_node_id]
        if outdegs[old_node_id] <= 1:
            new_names.append(old_name)
        else:
            for i in xrange(1, outdegs[old_node_id]+1):
                new_names.append(old_name + "." + str(i))

    # Add a sentinel element to old_to_new just to make our job easier
    old_to_new.append(new_node_id)

    # Create the edge list of the new graph and the weights of the new
    # edges
    new_edgelist = []
    new_weights = []

    # 1) Create the linear subgraphs
    for new_node_id, next_new_node_id in pairs(old_to_new):
        for source, target in pairs(range(new_node_id, next_new_node_id)):
            new_edgelist.append((source, target))
            new_weights.append(0)

    # 2) Create the new edges based on the old ones
    for old_node_id in xrange(g.vcount()):
        new_node_id = old_to_new[old_node_id]
        for edge_id in g.incident(old_node_id, mode="out"):
            neighbor = g.es[edge_id].target
            new_edgelist.append((new_node_id, old_to_new[neighbor]))
            new_node_id += 1
            print g.es[edge_id].source, g.es[edge_id].target, g.es[edge_id]["weight"]
            new_weights.append(g.es[edge_id]["weight"])

    # Return the graph
    vertex_attrs = {"name": new_names}
    edge_attrs = {"weight": new_weights}
    return Graph(new_edgelist, directed=True, vertex_attrs=vertex_attrs, \
            edge_attrs=edge_attrs)
    回复于

相关问题