python - 有向图中的最大公共(public)子图

我试图将一组句子表示为一个有向图，其中一个单词由一个节点表示。如果重复单词，则不重复该节点，则使用先前存在的节点。我们将此图称为MainG。

接下来，我采用了一个新句子，创建了该句子的有向图(将此图称为SubG)，然后在SubG中寻找MainG的Maximum Common Subgraph。

我在Python 3.5中使用NetworkX api。我了解这是正常图的NP完全问题，但对于有向图则是线性问题。我提到的链接之一:

How can I find Maximum Common Subgraph of two graphs?

我尝试执行以下代码:

import networkx as nx
import pandas as pd
import nltk

class GraphTraversal:
    def createGraph(self, sentences):
        DG=nx.DiGraph()
        tokens = nltk.word_tokenize(sentences)
        token_count = len(tokens)
        for i in range(token_count):
            if i == 0:
                continue
            DG.add_edges_from([(tokens[i-1], tokens[i])], weight=1)
        return DG


    def getMCS(self, G_source, G_new):
        """
        Creator: Bonson
        Return the MCS of the G_new graph that is present
        in the G_source graph
        """
        order =  nx.topological_sort(G_new)
        print("##### topological sort #####")
        print(order)

        objSubGraph = nx.DiGraph()

        for i in range(len(order)-1):

            if G_source.nodes().__contains__(order[i]) and G_source.nodes().__contains__(order[i+1]):
                print("Contains Nodes {0} -> {1} ".format(order[i], order[i+1]))
                objSubGraph.add_node(order[i])
                objSubGraph.add_node(order[i+1])
                objSubGraph.add_edge(order[i], order[i+1])
            else:
                print("Does Not Contains Nodes {0} -> {1} ".format(order[i], order[i+1]))
                continue


obj_graph_traversal = GraphTraversal()
SourceSentences = "A series of escapades demonstrating the adage that what is good for the goose is also good for the gander , some of which occasionally amuses but none of which amounts to much of a story ."
SourceGraph = obj_graph_traversal.createGraph(SourceSentences)

TestSentence_1 = "not much of a story"    #ThisWorks
TestSentence_1 = "not much of a story of what is good"    #This DOES NOT Work
TestGraph = obj_graph_traversal.createGraph(TestSentence_1)

obj_graph_traversal.getMCS(SourceGraph, TestGraph)

当我尝试进行拓扑排序时，第二个不起作用。

有兴趣了解可能的解决方法。

最佳答案

以下代码从有向图获取最大公共(public)子图:

def getMCS(self, G_source, G_new):
    matching_graph=nx.Graph()

    for n1,n2,attr in G_new.edges(data=True):
        if G_source.has_edge(n1,n2) :
            matching_graph.add_edge(n1,n2,weight=1)

    graphs = list(nx.connected_component_subgraphs(matching_graph))

    mcs_length = 0
    mcs_graph = nx.Graph()
    for i, graph in enumerate(graphs):

        if len(graph.nodes()) > mcs_length:
            mcs_length = len(graph.nodes())
            mcs_graph = graph

    return mcs_graph

关于python - 有向图中的最大公共(public)子图，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43108481/