13

私はプログラミングの専門家ではないので、助けが必要です。

n 個のノードと E 個のエッジを持つ特定のグラフに対して、平面グラフを描画するにはどうすればよいですか (エッジ交差がないように平面に描画できる場合、グラフは平面であると言われます)。次に、エッジを反転して別の平面グラフを作成します (すべての可能性が得られるまで for ループ)。

よろしくお願いいたします。

西暦

>>>#visualize with pygraphviz
    A=pgv.AGraph()
    File "<stdin>", line 6
    A=pgv.AGraph()
    ^
    SyntaxError: invalid syntax
>>> A.add_edges_from(G.edges())
    Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    NameError: name 'A' is not defined
>>> A.layout(prog='dot')
    Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    NameError: name 'A' is not defined
>>> A.draw('planar.png')
    Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    NameError: name 'A' is not defined
4

1 に答える 1

23

あなたの質問には、いくつかの難しい計算問題が含まれています。

まず、いくつかの理論。グラフ G が平面の場合、G のすべてのサブグラフは平面です。G (エッジを持つ) からエッジを反転すると、指数関数的 (つまり、巨大で「悪い」) な平面サブグラフ (接続性を気にしない場合e) が得られます。2^e-1おそらく、「最大」の平面サブグラフを見つけたいと思うでしょう。

平面のように見える平面グラフを描画したい場合は、計算上困難です。つまり、エッジが交差しないグラフィカルな表現が存在することを知ることと、そのような表現を見つけることは別のことです。

実装へ。networkx には、グラフが平面かどうかをチェックする機能がないようです。グラフを操作する他のパッケージには、(たとえば、sageにはグラフ オブジェクトであるg.is_planar()関数があります) があります。以下に、クラトフスキーの定理gに基づいて、networkx を使用した「単純な」(より効率的な方法があるに違いない) 平面性チェックを書きました。

import pygraphviz as pgv
import networkx as nx
import itertools as it
from networkx.algorithms import bipartite

def is_planar(G):
    """
    function checks if graph G has K(5) or K(3,3) as minors,
    returns True /False on planarity and nodes of "bad_minor"
    """
    result=True
    bad_minor=[]
    n=len(G.nodes())
    if n>5:
        for subnodes in it.combinations(G.nodes(),6):
            subG=G.subgraph(subnodes)
            if bipartite.is_bipartite(G):# check if the graph G has a subgraph K(3,3)
                X, Y = bipartite.sets(G)
                if len(X)==3:
                    result=False
                    bad_minor=subnodes
    if n>4 and result:
        for subnodes in it.combinations(G.nodes(),5):
            subG=G.subgraph(subnodes)
            if len(subG.edges())==10:# check if the graph G has a subgraph K(5)
                result=False
                bad_minor=subnodes
    return result,bad_minor

#create random planar graph with n nodes and p probability of growing
n=8
p=0.6
while True:
    G=nx.gnp_random_graph(n,p)
    if is_planar(G)[0]:
        break
#visualize with pygraphviz
A=pgv.AGraph()
A.add_edges_from(G.edges())
A.layout(prog='dot')
A.draw('planar.png')

編集2。pygraphviz で問題が発生した場合は、networkx で描画してみてください。おそらく結果は問題ないでしょう。したがって、「pygraphviz で視覚化する」ブロックの代わりに、次のことを試してください。

import matplotlib.pyplot as plt
nx.draw(G)
# comment the line above and uncomment one of the 3 lines below (try each of them):
#nx.draw_random(G)
#nx.draw_circular(G)
#nx.draw_spectral(G)
plt.show()

edit2 の終了。

結果はこんな感じ。ランダム平面グラフ

画像上に 1 つの交差があることがわかります (しかし、グラフは平面です)。これは実際には良い結果です (問題が計算上難しいことを忘れないでください)。pygraphviz は、ヒューリスティック アルゴリズムを使用するGraphvizのラッパーです。この行A.layout(prog='dot')で、「ドット」を「twopi」、「neato」、「circo」などに置き換えて、視覚化が向上するかどうかを確認してください。

編集します。平面サブグラフに関する質問についても考えてみましょう。非平面グラフを生成しましょう:

while True:
    J=nx.gnp_random_graph(n,p)
    if is_planar(J)[0]==False:
        break

平面サブグラフを見つける最も効率的な方法は、「悪いマイナー」(つまり、K(5) または K(3,3)) からノードを削除することだと思います。これが私の実装です：

def find_planar_subgraph(G):
    if len(G)<3:
        return G
    else:
        is_planar_boolean,bad_minor=is_planar(G)
        if is_planar_boolean:
            return G
        else:
            G.remove_node(bad_minor[0])
            return find_planar_subgraph(G)

アクション：

L=find_planar_subgraph(J)
is_planar(L)[0]
>> True

これで、非平面グラフ G の平面サブグラフ L (networkx グラフ オブジェクト) ができました。

于 2012-02-07T13:39:11.820 に答える