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

If I create a bipartite graph G using random geomtric graph where nodes are connected within a radius. I then want to make sure all nodes have a particular degree (i.e. only one or two edges). My main aim is to take one of the node sets (i.e node type a) and for each node make sure it has a maximum degree set by me. So for instance if a take node i that has a degree of 4, delete random edges of node i until its degree is 1.

如果我用随机的地形图来创建一个二部图G，其中节点在一个半径内连接。然后，我要确保所有节点都具有一个特定的程度(即只有一个或两个边)。我的主要目标是获取一个节点集(i。e节点a)对于每个节点，确保它有我设定的最大程度。例如，如果一个节点i的值为4，删除节点i的随机边直到它的度为1。

I wrote the following code to run in the graph generator after generating edges. It deletes edges but not until all nodes have the degree of 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

full function below:

完整的函数如下:

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

Reply to words like jared. I tried using you code plus a couple changes I had to make:

回复像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

This ends up removing nodes from the final graph which I had hoped it would not.

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

2 个解决方案

#1

Suppose we have a Bipartite graph. If you want each node to have degree 0, 1 or 2, one way to do this would be the following. If you want to do a matching, either look up the algorithm (I don't remember it), or change maxDegree to 1 and I think it should work as a matching instead. Regardless, let me know if this doesn't do what you want.

假设我们有一个二部图。如果你想让每个节点都有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

#2

I don't know if it is your problem but my wtf detector is going crazy when I read those two final blocks:

我不知道这是不是你的问题但是我的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

• you never go inside the for loop, since nodesa needs to be empty to reach it
• 你永远不会进入for循环，因为nodesa需要是空的才能到达它。
• even if nodesa is not empty, if mu is an int, you have an infinite loop in in your last nested while since you never modify it.
• 即使nodesa不是空的，如果mu是一个整数，那么在最后一个嵌套的时候，你有一个无限循环，因为你从来没有修改过它。
• even if you manage to break from this while statement, then you have mu > 1 == False. So you immediatly break out of your for loop
• 即使你设法从这个while语句中分离出来，那么你有mu > 1 == False。所以你马上跳出你的for循环。

Are you sure you are doing what you want here? can you add some comments to explain what is going on in this part?

你确定你在做你想做的事吗?你能给我添加一些注释来解释这部分的内容吗?