我们从Python开源项目中，提取了以下9个代码示例，用于说明如何使用networkx.max_weight_matching()。
def Zcorrections(self): '''Qubits on which to apply Z operator to fix the X stabilizer.''' L = self.L graph = self.Xwgraph() matches = {tuple(sorted(_)) for _ in nx.max_weight_matching(graph, maxcardinality=True).items()} qubits = set() for (y1, x1), (y2, x2) in matches: ym, yM = 2*min(y1, y2), 2*max(y1, y2) if yM-ym > L: ym, yM = yM, ym+2*L horizontal = yM if (x2-x1)*(y2-y1)<0 else ym else: horizontal = ym if (x2-x1)*(y2-y1)<0 else yM xm, xM = min(x1, x2), max(x1, x2) if xM-xm > L/2: xm, xM = xM, xm+L vertical = xM else: vertical = xm qubits.update((horizontal%(2*L), _%L) for _ in range(xm, xM)) qubits.update(((_+1)%(2*L), vertical%L) for _ in range(ym, yM, 2)) return matches, qubits
def Xcorrections(self): '''Qubits on which to apply X operator to fix the Z stabilizer.''' L = self.L graph = self.Zwgraph() matches = {tuple(sorted(_)) for _ in nx.max_weight_matching(graph, maxcardinality=True).items()} qubits = set() for (y1, x1), (y2, x2) in matches: ym, yM = 2*min(y1, y2), 2*max(y1, y2) if yM-ym > L: ym, yM = yM, ym+2*L horizontal = yM if (x2-x1)*(y2-y1)<0 else ym else: horizontal = ym if (x2-x1)*(y2-y1)<0 else yM xm, xM = min(x1, x2), max(x1, x2) if xM-xm > L/2: xm, xM = xM, xm+L vertical = xM else: vertical = xm qubits.update(((horizontal+1)%(2*L), (_+1)%L) for _ in range(xm, xM)) qubits.update(((_+2)%(2*L), vertical%L) for _ in range(ym, yM, 2)) return matches, qubits
def get_max_wt_matching(row_label,column_label, weight_matrix): """ From clustering_on_transcript_compatibility_counts, see github for MIT license """ # Create a bipartite graph where each group has |unique labels| nodes G = nx.complete_bipartite_graph(len(row_label), len(column_label)) # Weight each edge by the weight in weight matrix.. for u,v in G.edges(): G[u][v]["weight"]=weight_matrix[u,v-len(row_label)] # Perform weight matching using Kuhn Munkres H=nx.max_weight_matching(G) max_wt=0 for u,v in H.items(): max_wt+=G[u][v]["weight"]/float(2) return max_wt
def match_objects_uniquely(candidates, targets, threshold=0.5): g = nx.Graph() for t in targets: g.add_node(t) for c in candidates: g.add_node(c) for t in targets: tbb = BBox(*t.bbox) for c in candidates: cbb = BBox(*c.bbox) intersection = tbb.intersection(cbb).area union = tbb.area + cbb.area - intersection try: current_iou = intersection / float(union) except ZeroDivisionError: current_iou = float('inf') pass if current_iou >= threshold: g.add_edge(t, c, weight=current_iou) target_set = set(targets) matching = nx.max_weight_matching(g, maxcardinality=True) # <- a dict with v->c and c->v both hits = [(t, c) for (t, c) in matching.items() if t in target_set] return hits
def construct_graph(user_ids, disallowed_meetings): """ We can use a maximum matching algorithm for this: https://en.wikipedia.org/wiki/Blossom_algorithm Yay graphs! Networkx will do all the work for us. """ # special weights that be put on the matching potential of each meeting, # depending on heuristics for what makes a good/bad potential meeting. meeting_to_weight = {} # This creates the graph and the maximal matching set is returned. # It does not return anyone who didn't get matched. meetings = [] possible_meetings = { meeting for meeting in itertools.combinations(user_ids, 2) } allowed_meetings = possible_meetings - disallowed_meetings for meeting in allowed_meetings: weight = meeting_to_weight.get(meeting, 1.0) meetings.append(meeting + ({'weight': weight},)) graph = nx.Graph() graph.add_nodes_from(user_ids) graph.add_edges_from(meetings) return nx.max_weight_matching(graph)
def DSP_Matching(Syndrome, External, dim, alt_ext): # Fully connect check operators for check1 in Syndrome.nodes(): for check2 in Syndrome.nodes(): if check1 != check2: weight = - common.euclidean_dist(check1, check2) +.1 Syndrome.add_edge(*(check1, check2), weight=weight) # Generate Boundary Graph External_Graph = nx.Graph() for m in Syndrome.nodes(): ext = DSP_AssociatedExternal(m, External) External_Graph.add_node(ext) weight = - common.euclidean_dist(m, ext) Syndrome.add_edge(*(m, ext), weight=weight) # Ensure even number of elements in Syndrome # so min weight matching can proceed successfully if len(Syndrome.nodes()) % 2 != 0: Syndrome.add_node(alt_ext) External_Graph.add_node(alt_ext) # Connect External Nodes edges = itertools.combinations(External_Graph,2) Syndrome.add_edges_from(edges, weight = 0) TempMatching = nx.max_weight_matching(Syndrome, maxcardinality=True) Matching = {} # each edge appears twice in TempMatching # Should only appear once in Matching for node, neighbor in TempMatching.items(): if neighbor not in Matching and node not in Matching: if node not in External or neighbor not in External: if node != alt_ext and neighbor != alt_ext: Matching[node] = neighbor return Matching
def max_weight_matching(Mrkt, Agents, verbose=False, maxcardinality=True): """ Computes max-weight matching of graph of inputted agents based on the “blossom” method for finding augmenting paths and the “primal-dual” method for finding a matching of maximum weight, both methods invented by Jack Edmonds Implemented by NetworkX Runtime: O(n^3) for n nodes Arguments --------- Mrkt: mm.Market object The market in which the matches are made Agents: list list of agents initiating matches maxcardinality: bool if True, compute the maximum-cardinality matching with maximum weight among all maximum-cardinality matchings. verbose: bool Whether algorithm prints information on action Returns ------- dict { agent.name : agent.name } of matches Reference: “Efficient Algorithms for Finding Maximum Matching in Graphs”, Zvi Galil, ACM Computing Surveys, 1986. """ if verbose: print("\nMax Weight Match Algorithm\n") print("Agents to match ", [a.name for a in Agents], "\n") # If Agents not whole market, get subgraph if len(Mrkt.Graph.nodes()) != len(Agents): to_match = deepcopy(Mrkt.Graph.subgraph(Agents)) else: to_match = Mrkt.Graph # Workaround of assertionerror in Nx verifyOptimum() function # Breaks around integer weights for u, v, d in to_match.edges(data=True): d['weight'] = float(d['weight']) mate = nx.max_weight_matching(to_match, maxcardinality=maxcardinality) result = {a.name: mate[a].name for a in mate} return result
def max_matching(total_distance): graph = nx.Graph() graph.add_weighted_edges_from(list_of_mergeable_trips) matching_dictionary = nx.max_weight_matching(graph, maxcardinality=True) trip_set = set() distance_saved = 0 for key in matching_dictionary: if (key in trip_set) and (matching_dictionary[key] in trip_set): continue else: trip_set.add(key) trip_set.add(matching_dictionary[key]) keyvalue = str(key) + "-" + str(matching_dictionary[key]) keyvalue1 = str(matching_dictionary[key]) + "-" + str(key) if keyvalue in trips_merged_metadata.keys(): trips = trips_merged_metadata[keyvalue] # print(str(trips[0].trip_id) + "," + str(trips[0].passenger_count) + "," + str(trips[0].trip_duration_from_source) + "," + str(trips[0].trip_distance_from_source) + "," + str(trips[0].dropoff_lattitude) + "," + str(trips[0].dropoff_longitude) + "," + str(trips[0].willing_to_walk)) # print(str(trips[1].trip_id) + "," + str(trips[1].passenger_count) + "," + str(trips[1].trip_duration_from_source) + "," + str(trips[1].trip_distance_from_source) + "," + str(trips[1].dropoff_lattitude) + "," + str(trips[1].dropoff_longitude) + "," + str(trips[1].willing_to_walk)) print(str(trips[0].trip_id) + "," + str(trips[0].passenger_count) + "," + str(trips[0].dropoff_lattitude) + "," + str(trips[0].dropoff_longitude)) print(str(trips[1].trip_id) + "," + str(trips[1].passenger_count) + "," + str(trips[1].dropoff_lattitude) + "," + str(trips[1].dropoff_longitude)) print("---------------------------------------------------------------------------------------------") distance_saved += distance_dictionary[keyvalue] elif keyvalue1 in trips_merged_metadata.keys(): trips = trips_merged_metadata[keyvalue1] # print(str(trips[0].trip_id) + "," + str(trips[0].passenger_count) + "," + str(trips[0].trip_duration_from_source) + "," + str(trips[0].trip_distance_from_source) + "," + str(trips[0].dropoff_lattitude) + "," + str(trips[0].dropoff_longitude) + "," + str(trips[0].willing_to_walk)) # print(str(trips[1].trip_id) + "," + str(trips[1].passenger_count) + "," + str(trips[1].trip_duration_from_source) + "," + str(trips[1].trip_distance_from_source) + "," + str(trips[1].dropoff_lattitude) + "," + str(trips[1].dropoff_longitude) + "," + str(trips[1].willing_to_walk)) print(str(trips[0].trip_id) + "," + str(trips[0].passenger_count) + "," + str(trips[0].dropoff_lattitude) + "," + str(trips[0].dropoff_longitude)) print(str(trips[1].trip_id) + "," + str(trips[1].passenger_count) + "," + str(trips[1].dropoff_lattitude) + "," + str(trips[1].dropoff_longitude)) print("---------------------------------------------------------------------------------------------") distance_saved += distance_dictionary[keyvalue1] else : print("no there") print("---------------------------------------------------------------------------------------------") print("-----------------------------------------------------------------------------------") print("input_trips_for_algorithm ", str(len(input_trips_for_algorithm))) print("input_trips_for_max_matching ", str(len(input_trips_for_max_matching))) print("lone_trip ", input_trips_for_max_matching.difference(matching_dictionary.keys())) no_trips_saved = len(input_trips_for_algorithm) - len(matching_dictionary.keys()) / 2 - len(input_trips_for_max_matching.difference(matching_dictionary.keys())) print("no of trips saved " + str(no_trips_saved)) print("total_distance " + str(total_distance)) print("distance saved " + str(total_distance - distance_saved)) print("Total_trips_without_ridesharing " + str(len(input_trips_for_algorithm))) unmergeable_trips = len(input_trips_for_algorithm) - len(input_trips_for_max_matching) print("unmergeable trips " + str(unmergeable_trips)) total_trips_due_to_ridesharing = len(matching_dictionary.keys()) / 2 + len(input_trips_for_max_matching.difference(matching_dictionary.keys())) + unmergeable_trips print("Total_trips_due_to_ridesharing " + str(total_trips_due_to_ridesharing)) print("Merged_trips_only_after_ridesharing(without unmergeable trips and lone trips) " + str(len(matching_dictionary.keys()) / 2)) print("-----------------------------------------------------------------------------------")
def MinWeightMatching(code, Syndrome, type, charge_type): dim = code.dimension # Fully connect check operators for check1 in Syndrome.nodes(): for check2 in Syndrome.nodes(): if check1 != check2: # weight = - code.distance(type, check1, check2) weight = - common.euclidean_dist(check1, check2) Syndrome.add_edge(*(check1, check2), weight=weight) # Generate Boundary Graph External_Graph = nx.Graph() for node in Syndrome.nodes(): charge = Syndrome.node[node]['charge'] external_node = AssociatedExternal(node, code.Dual[type], code.External[type]) External_Graph.add_node(external_node, charge=(-charge) % dim) # weight = -code.distance(type, node, external_node) weight = - common.euclidean_dist(node, external_node) Syndrome.add_edge(*(node, external_node), weight=weight) # Ensure even number of elements in Syndrome # so min weight matching can proceed successfully if len(Syndrome.nodes()) % 2 != 0: removed_external = External_Graph.nodes()[0] edge = Syndrome.edges(removed_external)[0] min_weight = Syndrome.get_edge_data(*edge)['weight'] for external_node in External_Graph.nodes(): edge = Syndrome.edges(external_node)[0] weight = Syndrome.get_edge_data(*edge)['weight'] if weight < min_weight: removed_external = external_node min_weight = weight External_Graph.remove_node(removed_external) Syndrome.remove_node(removed_external) # Connect External Nodes for ext1 in External_Graph: for ext2 in External_Graph: if ext1 != ext2: Syndrome.add_edge(*(ext1, ext2), weight=0) TempMatching = nx.max_weight_matching(Syndrome, maxcardinality=True) Matching = {} # each edge appears twice in TempMatching # Should only appear once in Matching for node, neighbor in TempMatching.items(): if neighbor not in Matching: if node in code.Dual[type].nodes() or neighbor in code.Dual[type].nodes(): Matching[node] = neighbor return Matching # Recovery Operations # Generate recovery chains to correct for errors during code cycle.
