Python networkx 模块，minimum_spanning_tree() 实例源码

def from_graph(self, G):
        self.G = G.copy()
        cliques = nx.clique.find_cliques(G)
        cliquegraph = nx.clique.make_max_clique_graph(G)
        clique_dict = {}
        for v, clq in zip(cliquegraph.nodes(), cliques):
            clique_dict[v] = clq

        for u, v, data in cliquegraph.edges(data=True):
            cliquegraph.remove_edge(u, v)
            sep = set(clique_dict[u]).intersection(set(clique_dict[v]))
            w = len(sep)
            cliquegraph.add_edge(u, v, nodes=sep, weight=-w)
        self.cliquetree = nx.minimum_spanning_tree(cliquegraph)

        for v in self.G:
            self.node_in_cliques[v] = set()
        for v in clique_dict:
            self.nodes_in_clique[v] = set()
            for node in clique_dict[v]:
                self.nodes_in_clique[v].add(node)
                self.node_in_cliques[node].add(v)
        self.uid = len(G) + 1
        self.insertable = set()
        for v in self.G:
            self.update_insertable(v)

def work(fil):

    G = dataToGraph(fil)
    ori = sum([G.get_edge_data(i,j)['weight'] for i,j in G.edges_iter()])
    MST = nx.minimum_spanning_tree(G)
    new = sum([G.get_edge_data(i,j)['weight'] for i,j in MST.edges_iter()])
    saved = ori - new

    return saved

def find_tree(sub_network, weight='x_pu'):
    """Get the spanning tree of the graph, choose the node with the
    highest degree as a central "tree slack" and then see for each
    branch which paths from the slack to each node go through the
    branch.

    """

    branches_bus0 = sub_network.branches()["bus0"]
    branches_i = branches_bus0.index
    buses_i = sub_network.buses_i()

    graph = sub_network.graph(weight=weight)
    sub_network.tree = nx.minimum_spanning_tree(graph)

    #find bus with highest degree to use as slack
    tree_slack_bus, slack_degree = max(degree(sub_network.tree), key=itemgetter(1))
    logger.info("Tree slack bus is %s with degree %d.", tree_slack_bus, slack_degree)

    #determine which buses are supplied in tree through branch from slack

    #matrix to store tree structure
    sub_network.T = dok_matrix((len(branches_i),len(buses_i)))

    for j,bus in enumerate(buses_i):
        path = nx.shortest_path(sub_network.tree,bus,tree_slack_bus)
        for i in range(len(path)-1):
            branch = next(iterkeys(graph[path[i]][path[i+1]]))
            branch_i = branches_i.get_loc(branch)
            sign = +1 if branches_bus0.iat[branch_i] == path[i] else -1
            sub_network.T[branch_i,j] = sign

def extractMinSubgraphContainingNodes(self, minSet):
        """
        Find the minimum subgraph of the dependency graph that contains the provided set of nodes. Useful for finding dependency-path like structures

        :param minSet: List of token indices
        :type minSet: List of ints
        :return: All the nodes and edges in the minimal subgraph
        :rtype: Tuple of nodes,edges where nodes is a list of token indices, and edges are the associated dependency edges between those tokens
        """

        assert isinstance(minSet, list)
        for i in minSet:
            assert isinstance(i, int)
            assert i >= 0
            assert i < len(self.tokens)
        G1 = nx.Graph()
        for a,b,depType in self.dependencies:
            G1.add_edge(a,b,dependencyType=depType)

        G2 = nx.Graph()
        paths = {}

        minSet = sorted(list(set(minSet)))
        setCount1 = len(minSet)
        minSet = [ a for a in minSet if G1.has_node(a) ]
        setCount2 = len(minSet)
        if setCount1 != setCount2:
            sys.stderr.write("WARNING. %d node(s) not found in dependency graph!\n" % (setCount1-setCount2))
        for a,b in itertools.combinations(minSet,2):
            try:
                path = nx.shortest_path(G1,a,b)
                paths[(a,b)] = path
                G2.add_edge(a,b,weight=len(path))
            except nx.exception.NetworkXNoPath:
                sys.stderr.write("WARNING. No path found between nodes %d and %d!\n" % (a,b))

        # TODO: This may through an error if G2 ends up having multiple components. Catch it gracefully.
        minTree = nx.minimum_spanning_tree(G2)
        nodes = set()
        allEdges = set()
        for a,b in minTree.edges():
            path = paths[(min(a,b),max(a,b))]
            for i in range(len(path)-1):
                a,b = path[i],path[i+1]
                dependencyType = G1.get_edge_data(a,b)['dependencyType']
                edge = (min(a,b),max(a,b),dependencyType)
                allEdges.add(edge)
            nodes.update(path)

        return nodes,allEdges

def extractMinSubgraphContainingNodes(self, minSet):
        import networkx as nx

        assert isinstance(minSet, list)
        for i in minSet:
            assert isinstance(i, int)
            assert i >= 0
            assert i < len(self.tokens)
        G1 = nx.Graph()
        for a,b,_ in self.dependencies:
            G1.add_edge(a,b)

        G2 = nx.Graph()
        paths = {}

        #print "-"*30
        #print [ (i,t) for i,t in enumerate(self.tokens) ]
        #print
        #print self.dependencies
        #print
        #print self.predictedEntityLocs
        #print self.knownEntityLocs
        #print
        #print minSet
        #self.printDependencyGraph()
        #print "-"*30

        minSet = sorted(list(set(minSet)))
        setCount1 = len(minSet)
        minSet = [ a for a in minSet if G1.has_node(a) ]
        setCount2 = len(minSet)
        if setCount1 != setCount2:
            print "WARNING. %d node(s) not found in dependency graph!" % (setCount1-setCount2)
        for a,b in itertools.combinations(minSet,2):
            try:
                path = nx.shortest_path(G1,a,b)
                paths[(a,b)] = path
                G2.add_edge(a,b,weight=len(path))
            except nx.exception.NetworkXNoPath:
                print "WARNING. No path found between nodes %d and %d!" % (a,b)

        # TODO: This may through an error if G2 ends up having multiple components. Catch it gracefully.
        minTree = nx.minimum_spanning_tree(G2)
        nodes = set()
        allEdges = set()
        for a,b in minTree.edges():
            path = paths[(min(a,b),max(a,b))]
            for i in range(len(path)-1):
                a,b = path[i],path[i+1]
                edge = (min(a,b),max(a,b))
                allEdges.add(edge)
            nodes.update(path)

        return nodes,allEdges