# Summation of all links that contains nieghbors to certain node in Graph

I'm trying to model a constraint in Python using Pulp and networkX that is getting the sum of the edges that contain this node over all the nodes. The constraint can be like that: $$\sum_{m\in\cal N}z_{(m,n)}\succeq k(1-y_m),\quad\forall m\in\cal N.$$

I have used this code to model the constraint:

for m in g.nodes(): prob += pulp.lpSum(z[(m,n)] for m in g.nodes()) >= k*(1-y[m])

This piece of code rises an error about the key of the dictionary since the variable dictionary $$z$$ doesn't contains all the neighbors values. If I used this instead

for m in g.nodes(): prob += pulp.lpSum(z[(m,n)] for (u,v) in g.edges()) >= k*(1-y[m])

It sums all the links, not the ones associated with link $$m$$.

I would like your help with this!.

Please be noted that $$z_{(m,n)}$$ is a dict of the graph edges

## 2 Answers

Alternatively, just like in your previous question :

for m in g.nodes():
prob += pulp.lpSum(z[(m,n)] for n in g.neighbors(m)) >= k*(1-y[m])

• Thank you @Kuifje. I have tried this actually before asking but it throws an error about the key of the dict. For example, If I have this small set of edges [ [(1,2),(1,4),(1,5),(2,5),(2,3),(3,5),(3,4),(4,5)] ] The optimizer throws an error as KeyError: (2, 1). I think this is because the dict of Z which is the dict of edges doesn't contain the value of z_(2,1) – Amedeo Nov 12 '20 at 12:37
• First, I think there is an extra set of brackets in your set of edges. This may be what triggrs the KeyError. Second, I suggest you post your full code in another question, so that we can see everything and help you with that. – Kuifje Nov 12 '20 at 13:16
• Thank you for your reply. The extra brackets are not in the code, they are here by mistake. However, I will post another question. – Amedeo Nov 12 '20 at 13:21

You can use:

all_neighbors(graph, node): Returns all of the neighbors of a node in the graph.


function in networkX to find all the nodes which are connected to node m and then use the first constraint that you mentioned. I think there is a typo in the constraint as well instead of $$m$$ you should have $$n$$ (it's confusing). The output of that function is iterator you need to save it as a list (I am not sure about the format that PuLP accept).

• Thank you for your reply @Ogzu. – Amedeo Nov 12 '20 at 12:41
• @OguzToragay's comment is relevant : because of the typo, you got your $u$ and $v$ mixed up in the last constraint. – Kuifje Nov 12 '20 at 15:12