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)
python类minimum_spanning_tree()的实例源码
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
