मेरे पास एक डेटा संरचना है जो अलग-अलग अप्रत्यक्ष "सबग्राफ" के ग्राफ की तरह दिखती है और उन सबग्राफ को प्राप्त करना चाहती है जिनमें एन किनारों से कम है, इस मामले में केवल एक या दो किनारों वाले। मैं यहाँ थोड़ा खो गया हूँ और मुझे यकीन नहीं है कि इसके साथ कैसे जाना है। वास्तव में, जिस तरह से मैंने डेटा संग्रहीत किया है वह इस समस्या के लिए सबसे अच्छा तरीका भी नहीं हो सकता है।

एक उदाहरण के रूप में, नीचे graph के लिए मैं नोड्स A-B, H-J और K-M को पुनः प्राप्त करना चाहता हूं, लेकिन C-G नहीं क्योंकि इसमें 2 से अधिक किनारे हैं .

graph = {  # using sets
    # single (A-B)
    'A': {'B'},
    'B': {'A'},
    # complex (C-G)
    'C': {'D'},
    'D': {'C', 'E'},
    'E': {'D', 'F'},
    'F': {'G', 'E'},
    'G': {'F'},
    # digraph1 (H-J)
    'H': {'J', 'I'},
    'I': {'H'},
    'J': {'H'},
    # digraph2 (K-M)
    'K': {'L'},
    'L': {'K', 'M'},
    'M': {'L'},
}

पाइथन में इस समस्या से निपटने के तरीके पर कोई विचार या सुझाव?

1
PedroA 28 मार्च 2018, 00:32

3 जवाब

सबसे बढ़िया उत्तर

आप प्रत्येक नोड पर एक साधारण चौड़ाई-प्रथम खोज कर सकते हैं जो आपके उप-घटकों की पहचान करेगा। जब आप ऐसा करते हैं तो आप किनारों को भी गिन सकते हैं और उप-घटकों के साथ वापस कर सकते हैं। उदाहरण के लिए आपकी ग्राफ संरचना को देखते हुए आप कुछ ऐसा कर सकते हैं:

from collections import deque

def bfs(graph, start_node):
    searched = set([start_node])
    edge_count = 0
    queue = deque(start_node)
    while(len(queue)):
        current = queue.popleft()
        for node in graph[current]:
            edge_count += 1                
            if node not in searched:
                searched.add(node)
                queue.append(node)
    return (searched, edge_count/2)

def findSubGraphs(graph):
    subgraphs = []
    found = set()
    for node in graph:
        if node not in found:
            (subgraph, edge_count) = bfs(graph, node)
            found.update(subgraph)
            subgraphs.append((subgraph, edge_count))
    return subgraphs

findSubGraphs(graph)

यह आपके सबग्राफ के नोड्स और किनारे की गणना के साथ डेटा संरचना वापस करनी चाहिए। उदाहरण के लिए:

[({'A', 'B'}, 1.0),
 ({'C', 'D', 'E', 'F', 'G'}, 4.0),
 ({'H', 'I', 'J'}, 2.0),
 ({'K', 'L', 'M'}, 2.0)]
1
Mark M 27 मार्च 2018, 22:40

आप ग्राफ़ नोड को बंद करने के लिए मानक एल्गोरिथम का पालन करते हैं:

अपनी सुविधा का एक नया ढांचा तैयार करें।

Pick a starting node however you like; you'll eventually get to all of them.  Put it on the "not visited" list.

While the "not visited" list is not empty:
    Remove the top node from the list.
    Add it to the structure.
    Iterate through its edges.
        If the node on the other end isn't already in the structure,
            add the node and edge to the structure.

अब, बस जांचें कि आपकी संरचना में कितने किनारे हैं। यदि यह 3 से कम है, तो आपके पास वांछित ग्राफ है।

उन नोड्स को अपने शब्दकोश से हटा दें। नए शुरुआती बिंदुओं के साथ जारी रखें जब तक कि आपका शब्दकोश खाली न हो जाए। अब आपने सभी छोटे रेखांकन की पहचान कर ली है।

1
Prune 27 मार्च 2018, 21:43