dominating_set.py

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sat May  9 23:53:13 2020

@author: mario
"""
import networkx as nx
import gurobipy as gp
from gurobipy import GRB
    

def add_constraints(G, m, nodes):
    m.addConstrs(((gp.quicksum(nodes[n] for n in G.neighbors(v)) + nodes[v] )>= 1) for v in G.nodes)


def model(G, name):
    m = gp.Model(name)
    
    nodes = m.addVars(G.nodes, vtype = GRB.BINARY, name = "nodes")

    m.setObjective(gp.quicksum(nodes), GRB.MINIMIZE)

    add_constraints(G,m,nodes)
    
    return m, nodes

def solve(G):
    m, nodes = model(G,'DS')
    m.optimize()
    # ds = {v for j,x_j in enumerate(m.getVars()) for i,v in enumerate(G.nodes) if j == i}
    ds = {i for i,x_i in enumerate(m.getVars()) if x_i.x == 1}
    return ds