python - 次数 = 1 networkx までノードのランダムなエッジを削除します

Question

ノードが半径内で接続されているランダム幾何グラフを使用して、二部グラフ G を作成するとします。次に、すべてのノードが特定の次数 (つまり、1 つまたは 2 つのエッジのみ) を持っていることを確認します。私の主な目的は、ノードセット (つまり、ノードタイプ a) の 1 つを取得し、各ノードに対して、私が設定した最大次数があることを確認することです。たとえば、次数が 4 のノード i を取得する場合、次数が 1 になるまでノード i のランダムなエッジを削除します。

エッジを生成した後にグラフジェネレーターで実行する次のコードを記述しました。エッジは削除されますが、すべてのノードの次数が 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

これにより、最終的なグラフからノードが削除されることになりますが、そうならないことを望んでいました。

score 2 · Accepted Answer

二部グラフがあるとします。各ノードの次数を 0、1、または 2 にしたい場合、これを行う 1 つの方法は次のとおりです。マッチングを行いたい場合は、アルゴリズムを調べるか (覚えていません)、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

score 0 · Accepted Answer

それがあなたの問題かどうかはわかりませんが、これらの 2 つの最後のブロックを読み取ると、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

nodesa に到達するには空である必要があるため、 for ループ内には決して入りません。
nodesa が空でなくても、 mu がの場合int、最後のネストされたものを変更しないため、無限ループが発生しますwhile。
このwhileステートメントから抜け出すことができたとしても、 mu > 1 == False. forだからあなたはすぐにあなたのループから抜け出します

ここでやりたいことをやっていると確信していますか？この部分で何が起こっているかを説明するコメントを追加できますか?

python - 次数 = 1 networkx までノードのランダムなエッジを削除します

2 に答える 2

Related

Reference