删除节点的随机边，直到度=1 networkx

Question

如果我使用随机几何图创建一个二部图G，其中节点在半径内连接。然后，我想确保所有节点都有特定的阶数（即只有一条或两条边）。我的主要目标是获取一个节点集（即节点类型a），并确保每个节点都有我设置的最大度。例如，如果一个阶数为4的take节点i，则删除节点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

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

Answer 1

我不知道这是不是你的问题，但是当我读到最后两个块时，我的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循环，因为nodesa需要为空才能到达它

你确定你在这里做你想做的事吗？你能添加一些评论来解释这部分的内容吗？

Answer 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