पायथन, नेटवर्क x

Question

मुझे मदद चाहिए क्योंकि मैं प्रोग्रामिंग में विशेषज्ञ नहीं हूं।

मैं एक प्लानर ग्राफ़ कैसे खींच सकता हूं (एन ग्राफ और ए किनारों के साथ दिए गए ग्राफ के लिए एक ग्राफ़ को प्लानर कहा जा सकता है यदि इसे विमान में खींचा जा सकता है जैसे कि कोई एज-क्रॉसिंग नहीं है)। और फिर किनारों को एक और प्लानर ग्राफ रखने के लिए फ़्लिप करें। (लूप के लिए जब तक हम सभी संभावनाएं प्राप्त नहीं करते)।

अग्रिम धन्यवाद, और मैं आपकी मदद की सराहना करता हूं।

PY

---

>>>#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 

Answer 1

कई हार्ड कम्प्यूटेशनल अपने प्रश्न में शामिल समस्याएं हैं।

पहला, कुछ सिद्धांत। यदि ग्राफ़ जी प्लानर है, तो जी का प्रत्येक सबग्राफ प्लानर है। जी से किनारों को फ़्लिप करना (जिसमें e किनारों हैं), 2^e-1 प्लानर सबग्राफ (अगर हमें कनेक्टिविटी की परवाह नहीं है), जो घातीय है (यानी विशाल और "खराब")। शायद, आप "अधिकतम" प्लानर सबग्राफ ढूंढना चाहते हैं।

यदि आप प्लानर ग्राफ को आकर्षित करना चाहते हैं जो कि प्लानर की तरह दिखता है computationally hard है, यानी यह जानना एक बात है कि एक ग्राफिकल प्रतिनिधित्व मौजूद है जहां किनारों को पार नहीं किया जाता है और दूसरा ऐसा प्रतिनिधित्व ढूंढने के लिए होता है।

लागू करने के लिए। ऐसा लगता है जैसे नेटवर्कक्स में ऐसा फ़ंक्शन नहीं है जो जांचता है कि कोई ग्राफ प्लानर है या नहीं। ग्राफ के साथ काम करने वाले कुछ अन्य पैकेज हैं (उदाहरण के लिए, sage में g.is_planar() फ़ंक्शन है जहां g ग्राफ़ ऑब्जेक्ट है)। नीचे, मैंने Kuratowski theorem पर आधारित "बेवकूफ" लिखा है (वहां अधिक कुशल विधियां होनी चाहिए) नेटवर्कर के साथ प्लानरिटी जांच करें।

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') 

EDIT2। यदि आपको pygraphviz के साथ परेशानी का सामना करना पड़ता है, तो नेटवर्कक्स के साथ आकर्षित करने का प्रयास करें, शायद आपको परिणाम ठीक लगे। तो, के बजाय "pygraphviz साथ कल्पना" ब्लॉक निम्नलिखित कोशिश: EDIT2 की

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() 

अंत।

परिणाम इस तरह दिखता है।

आप तस्वीर पर एक पार है यह देखने के (लेकिन ग्राफ प्लानर है), यह वास्तव में एक अच्छा परिणाम (मत भूलना समस्या computationally कठिन है), pygraphviz Graphviz जो अनुमानी एल्गोरिदम का उपयोग करने के लिए एक आवरण है। A.layout(prog='dot') लाइन में आप 'डॉट' को 'twopi', 'neato', 'circo' आदि से प्रतिस्थापित करने का प्रयास कर सकते हैं ताकि आप यह देख सकें कि क्या आप बेहतर विज़ुअलाइजेशन प्राप्त करते हैं या नहीं।

संपादित करें। आइए प्लानर सबग्राफ पर भी अपना प्रश्न मानें। के एक गैर प्लानर ग्राफ उत्पन्न करते हैं:

मुझे लगता है कि एक समतल subgraph खोजने में सबसे कारगर तरीका "बुरा नाबालिग" से नोड्स को खत्म करने की है (यानी कश्मीर (5) या कश्मीर (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 

अब आप गैर प्लानर ग्राफ StackOverflow करने के लिए जी