का विभाजन मैं महत्वपूर्ण शीर्षकों के सेट के आधार पर एक या अधिक भागों में नेटवर्क को विभाजित करने का प्रयास कर रहा हूं। मुझे कोड मिला है जो मुझे विश्वास है कि मेरी समस्या हल होती है (कम से कम, इसमें उन मामलों के लिए है जिनके लिए मुझे रूचि है), लेकिन सामान्य रूप से शुद्धता सुनिश्चित करने के लिए, मैं जो कर रहा हूं उसका नाम ढूंढ रहा हूं ग्राफ सिद्धांत से, या समकक्ष एल्गोरिदम या प्रक्रिया पर भी एक संदर्भ।एक निर्देशित ग्राफ
इनपुट नेटवर्क एक एकल स्रोत और सिंक वर्टेक्स के साथ एक निर्देशित ग्राफ है। परिणामी विभाजनों में मूल (निर्देशित ग्राफ, एकल स्रोत वर्टेक्स, सिंगल सिंक वर्टेक्स) के समान गुण होना चाहिए, अतिरिक्त आवश्यकता के साथ कि प्रत्येक विभाजन में केवल दो कोष्ठक होना चाहिए जो महत्वपूर्ण सेट में हैं, और वे प्रारंभिक और टर्मिनल शिखर।
संपादित
स्रोत और सिंक एक ही शिखर कर रहे हैं, उसके एवज में उप ग्राफ एक चक्र होते हैं। मौजूदा चक्र ऐसे चक्रों का पता लगाने और निकालने के लिए उपलब्ध है। ।
समाप्ति संपादित
इस मामले एक चित्र 1000 शब्दों के बराबर है में, मैं एक साधारण ग्राफ तैयार किया है, रंग कोने महत्वपूर्ण कोने का प्रतिनिधित्व करते हैं, और बिंदु वाली रेखा ग्राफ का विभाजन कर रहे हैं।
alt text http://i50.tinypic.com/1254bkg.jpg
इस मामले में, इरादा के बीच किसी भी संभावित विभाजन को मिल रहा है 1-1, 1-3, 1-7, 3-1, 3-3, 3-7, 7-1, 7-3 या 7-7। केवल विभाजन 1-3, 3-3 और 3-7 वास्तव में मौजूद हैं (नीचे छवि देखें)। इसके अतिरिक्त, क्योंकि 3-3 विभाजन अमान्य है, ग्राफ को असंगतता को हटाने के लिए लेबल किया गया है।
alt text http://i49.tinypic.com/2qdsf42.png
यदि यह मदद करता है, आगे और पीछे ग्राफ traversals की एक श्रृंखला प्रदर्शन से मेरी अजगर-eque psuedocode काम करता है संभव विभाजन के सभी की पहचान।
def graphTraversal(graph,srcid,endids):
'''
Given a graph, start a traversal from srcid, stopping search
along a branch any time a vertex is in endids.
Return the visited subgraph
'''
closed = set()
open = set([srcid])
while len(open) != 0:
i = open.pop()
for j in graph.succ(i):
if (i,j) not in closed:
if j not in endids:
open.add(j)
closed.add((i,j))
return = graphFromList(closed)
def findAllValidPartitions(graph,srcids):
res = []
for n in srcids:
g2 = graphTraversal(graph,n,t)
g2rev = reverseEdgesInGraph(g2)
for s in srcids:
g3 = graphTraversal(g2rev ,s,t)
g3rev = reverseEdgesInGraph(g3)
g3rev = removeCycles(g3rev,s)
if len(g3rev .E) > 0:
res.append(g3rev)
return res
"महत्वपूर्ण" vertex क्या है? – Dmitry