0

如果我使用随机几何图创建二分图 G，其中节点在半径内连接。然后我想确保所有节点都具有特定的度数（即只有一个或两个边）。我的主要目标是获取其中一个节点集（即节点类型 a），并为每个节点确保它具有我设置的最大度数。因此，例如，如果一个节点 i 的度数为 4，则删除节点 i 的随机边，直到其度数为 1。

在生成边之后，我编写了以下代码在图形生成器中运行。它删除边，但直到所有节点的度数都为 1。

for n in G:
    mu = du['G.degree(n)']
    while mu > 1:
            G.remove_edge(u,v)
    if mu <=1:
            break
return G

完整功能如下：

import networkx as nx
import random

def my_bipartite_geom_graph(a, b, radius, dim):

    G=nx.Graph()
    G.add_nodes_from(range(a+b))
    for n in range(a):
        G.node[n]['pos']=[random.random() for i in range(0,dim)]
        G.node[n]['type'] = 'A'

    for n in range(a, a+b):
        G.node[n]['pos']=[random.random() for i in range(0,dim)]
        G.node[n]['type'] = 'B'

    nodesa = [(node, data) for node, data in G.nodes(data=True) if data['type'] == 'A']
    nodesb = [(node, data) for node, data in G.nodes(data=True) if data['type'] == 'B']

    while nodesa:
        u,du = nodesa.pop()
        pu = du['pos']
        for v,dv in nodesb:
            pv = dv['pos']
            d = sum(((a-b)**2 for a,b in zip(pu,pv)))
            if d <= radius**2:
                G.add_edge(u,v)


    for n in nodesa:
        mu = du['G.degree(n)']
        while mu > 1:
            G.remove_edge(u,v)
        if mu <=1:
           break
    return G

回复 jared 之类的词。我尝试使用您的代码以及我必须进行的一些更改：

def hamiltPath(graph):

    maxDegree = 2
    remaining = graph.nodes()
    newGraph = nx.Graph()
    while len(remaining) > 0:
        node = remaining.pop()
        neighbors = [n for n in graph.neighbors(node) if n in remaining]
        if len(neighbors) > 0:
            neighbor = neighbors[0]
            newGraph.add_edge(node, neighbor)
            if len(newGraph.neighbors(neighbor)) >= maxDegree:
                remaining.remove(neighbor)

    return newGraph

这最终会从我希望它不会的最终图中删除节点。

4

2 回答 2

2

假设我们有一个二分图。如果您希望每个节点的度数为 0、1 或 2，则执行此操作的一种方法如下。如果你想做一个匹配，要么查找算法（我不记得了），要么将 maxDegree 更改为 1，我认为它应该作为匹配来工作。无论如何，如果这不符合您的要求，请告诉我。

def hamiltPath(graph):
    """This partitions a bipartite graph into a set of components with each
    component consisting of a hamiltonian path."""
    # The maximum degree
    maxDegree = 2

    # Get all the nodes.  We will process each of these.
    remaining = graph.vertices()
    # Create a new empty graph to which we will add pairs of nodes.
    newGraph = Graph()
    # Loop while there's a remaining vertex.
    while len(remaining) > 0:
        # Get the next arbitrary vertex.
        node = remaining.pop()
        # Now get its neighbors that are in the remaining set.
        neighbors = [n for n in graph.neighbors(node) if n in remaining]
        # If this list of neighbors is non empty, then add (node, neighbors[0])
        # to the new graph.
        if len(neighbors) > 0:
            # If this is not an optimal algorithm, I suspect the selection
            # a vertex in this indexing step is the crux.  Improve this
            # selection and the algorthim might be optimized, if it isn't
            # already (optimized in result not time or space complexity).
            neighbor = neighbors[0]
            newGraph.addEdge(node, neighbor)
            # "node" has already been removed from the remaining vertices.
            # We need to remove "neighbor" if its degree is too high.
            if len(newGraph.neighbors(neighbor)) >= maxDegree:
                remaining.remove(neighbor)

    return newGraph


class Graph:
    """A graph that is represented by pairs of vertices.  This was created
    For conciseness, not efficiency"""

    def __init__(self):
        self.graph = set()

    def addEdge(self, a, b):
        """Adds the vertex (a, b) to the graph"""
        self.graph = self.graph.union({(a, b)})

    def neighbors(self, node):
        """Returns all of the neighbors of a as a set. This is safe to
        modify."""
        return (set(a[0] for a in self.graph if a[1] == node).
                union(
                set(a[1] for a in self.graph if a[0] == node)
                ))

    def vertices(self):
        """Returns a set of all of the vertices. This is safe to modify."""
        return (set(a[1] for a in self.graph).
                union(
                set(a[0] for a in self.graph)
                ))

    def __repr__(self):
        result = "\n"
        for (a, b) in self.graph:
            result += str(a) + "," + str(b) + "\n"
        # Remove the leading and trailing white space.
        result = result[1:-1]
        return result


graph = Graph()
graph.addEdge("0", "4")
graph.addEdge("1", "8")
graph.addEdge("2", "8")
graph.addEdge("3", "5")
graph.addEdge("3", "6")
graph.addEdge("3", "7")
graph.addEdge("3", "8")
graph.addEdge("3", "9")
graph.addEdge("3", "10")
graph.addEdge("3", "11")


print(graph)
print()
print(hamiltPath(graph))
# Result of this is:
# 10,3
# 1,8
# 2,8
# 11,3
# 0,4
于 2012-04-07T21:17:55.057 回答
0

我不知道这是否是您的问题，但是当我阅读最后两个块时，我的 wtf 检测器快疯了：

while nodesa:
     u,du = nodesa.pop()
     pu = du['pos']
     for v,dv in nodesb:
         pv = dv['pos']
         d = sum(((a-b)**2 for a,b in zip(pu,pv)))
         if d <= radius**2:
             G.add_edge(u,v)

for n in nodesa:
    mu = du['G.degree(n)']
    while mu > 1:
        G.remove_edge(u,v)
    if mu <=1:
       break
  • 你永远不会进入 for 循环，因为 nodea 需要为空才能到达它
  • 即使 nodea 不为空，如果 mu 是 an int，您在最后一个嵌套中也会有一个无限循环，while因为您从未修改它。
  • 即使你设法打破这个while说法，那么你有mu > 1 == False. 所以你立即跳出你的for循环

你确定你在这里做你想做的事吗？你能添加一些评论来解释这部分发生了什么吗？

于 2012-04-08T10:31:11.883 回答