[Python] Use Gurobi to create networkx.Graph that has highest edge connectivity

I have the following graph G



G is created using the following code

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()


G consists of 50 nodes. I only want to include 25 nodes. In addition, I only want to include the nodes (and edges) that maximizes the connectivity between node A (=5) and node B (=20).

I wrote the following code:

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()


This results in an error because nx.from_numpy_array() cannot deal the datatype of E. How do I create a temporary np.ndarray of the .X-values ({0, 1}) of E and use this to determine the solution(s)?

Continue reading...