Verwenden Sie Gurobi, um networkx.Graph mit der höchsten Edge-Konnektivität zu erstellen
Posted: 14 Jan 2025, 11:07
Ich habe das folgende Diagramm G
wird mit dem folgenden Code erstellt
besteht aus 50 Knoten. Ich möchte nur 25 Knoten einbeziehen. Darüber hinaus möchte ich nur die Knoten (und Kanten) einbeziehen, die die Konnektivität zwischen Knoten A (=5) und Knoten B (=20) maximieren.
Ich habe den folgenden Code geschrieben:
Dies führt zu einem Fehler, da nx.from_numpy_array() den Datentyp von E nicht verarbeiten kann. Wie erstelle ich ein temporäres np.ndarray der .X-Werte ({0, 1}) von E und verwende dieses, um die Lösung(en) zu bestimmen?
Code: Select all
GCode: Select all
import networkx as nx
import matplotlib.pyplot as plt
G = nx.hoffman_singleton_graph()
pos = nx.spring_layout(G)
nx.draw(G, pos=pos)
nx.draw_networkx_labels(G=G, pos=pos)
plt.show()
Code: Select all
GIch habe den folgenden Code geschrieben:
Code: Select all
import numpy as np
import gurobipy as grb
from networkx.algorithms.connectivity import local_edge_connectivity
A = 5
B = 20
nodes = list(G.nodes)
n_nodes = len(nodes)
edges = nx.to_numpy_array(G, nodelist=nodes)
thresh_nodes = 25
model = grb.Model()
F = model.addMVar(n_nodes, vtype=grb.GRB.BINARY)
model.addConstr(F.sum() == thresh_nodes)
model.addConstr(F[nodes.index(A)] == 1)
model.addConstr(F[nodes.index(B)] == 1)
E = F * edges
model.setObjective(local_edge_connectivity(nx.from_numpy_array(A=E), A, B), grb.GRB.MAXIMIZE)
model.optimize()