# Compute the box covering on a graph using CPython

Edit:

My initial idea was to use numpy to solve efficiently this problem but after trying without results, someone comment on stackoverflow:

"Numpy can speed things up a lot IF your problem is essential parallel in nature"

I realize that numpy is not the best tool in this case and tried using cython.

I have defined the type of most of the variables. And followed this guide but the results are only 1/3 faster. I know there is still a big room fro improvements but given that I just meet cython today I want to ask you how can I improve it:

---------- New Cython code--------------:

import random as rnd
import numpy as np

cimport cython
cimport numpy as np

DTYPE = np.int
ctypedef np.int_t DTYPE_t

def choose_color(not_valid_colors, valid_colors):
possible_values = list(valid_colors - not_valid_colors)

if possible_values:
return rnd.choice(possible_values)
else:
return max(valid_colors.union(not_valid_colors)) + 1

@cython.boundscheck(False)
def greedy_coloring(np.ndarray[DTYPE_t, ndim=2] distances, int num_nodes, int diameter):
cdef int  i, lb, j
cdef np.ndarray[DTYPE_t, ndim=2] c = np.empty((num_nodes+1, diameter+2), dtype=DTYPE)

c.fill(-1)
# Matrix C will not use the 0 column and 0 row to
# let the algorithm look very similar to the paper
# pseudo-code

nodes = list(range(1, num_nodes+1))
rnd.shuffle(nodes)

c[nodes[0], :] = 0

# Algorithm
for i in nodes[1:]:
for lb in range(2, diameter+1):
not_valid_colors = set()
valid_colors = set()

for j in nodes[:i]:

if distances[i-1, j-1] >= lb:
not_valid_colors.add(c[j, lb])
else:
valid_colors.add(c[j, lb])

c[i, lb] = choose_color(not_valid_colors, valid_colors)

return c

def test():
distances = np.matrix('0 3 2 4 1 1; \
3 0 1 1 3 2; \
2 1 0 2 2 1; \
4 1 2 0 4 3; \
1 3 2 4 0 1; \
1 2 1 3 1 0')

c = greedy_coloring(distances, 6, 4)


Initial post:

I have read this blog which shows how an algorithm had a 250x speed-up by using numpy. I have tried to improve the following code by using numpy but I couldn't make it work:

    for i in nodes[1:]:
for lb in range(2, diameter+1):
not_valid_colors = set()
valid_colors = set()

for j in nodes:
if j == i:
break

if distances[i-1, j-1] >= lb:
not_valid_colors.add(c[j, lb])
else:
valid_colors.add(c[j, lb])

c[i, lb] = choose_color(not_valid_colors, valid_colors)

return c


Explanation

The code above is part of an algorithm used to calculate the self similar dimension of a graph. It works basically by constructing dual graphs G' where a node is connected to each other node if the distance between them is greater or equals to a given value (Lb) and then compute the graph coloring on those dual networks.

The algorithm description is the following:

1. Assign a unique id from 1 to N to all network nodes, without assigning any colors yet.
2. For all Lb values, assign a color value 0 to the node with id=1, i.e. C_1l = 0.
3. Set the id value i = 2. Repeat the following until i = N.
• a) Calculate the distance l_ij from i to all the nodes in the network with id j less than i.
• b) Set Lb = 1
• c) Select one of the unused colors C[ j][l_ij] from all nodes j < i for which l_ij ≥ Lb . This is the color C[i][Lb] of node i for the given Lb value.
• d) Increase Lb by one and repeat (c) until Lb = Lb_max.
• e) Increase i by 1.

I wrote it in python (see below) but it takes more than a minute when try to use it with small networks which have 100 nodes and p=0.9.

As I'm still new to python and numpy I did not find the way to improve its efficiency.

Is it possible to remove the loops by using the numpy.where to find where the paths are longer than the given Lb? I tried to implement it but didn't work...

This is the full code:

import random as rnd
import numpy as np

def choose_color(not_valid_colors, valid_colors):
possible_values = list(valid_colors - not_valid_colors)

if possible_values:
return rnd.choice(possible_values)
else:
return max(valid_colors.union(not_valid_colors)) + 1

def greedy_coloring(distances, num_nodes, diameter):

c = np.empty((num_nodes+1, diameter+2), dtype=int)
c.fill(-1)
# Matrix C will not use the 0 column and 0 row to
# let the algorithm look very similar to the paper
# pseudo-code

nodes = list(range(1, num_nodes+1))
rnd.shuffle(nodes)

for j in range(diameter+1):
c[nodes[0]][j] = 0

# Algorithm
for i in nodes[1:]:
for lb in range(1, diameter+2):
not_valid_colors = set()
valid_colors = set()

for j in nodes[:i]:

if distances[i-1, j-1] >= lb:
not_valid_colors.add(c[j][lb])
else:
valid_colors.add(c[j][lb])

c[i][lb] = choose_color(not_valid_colors, valid_colors)

return c

if __name__ == "__main__":
distances = np.matrix('0 3 2 4 1 1; \
3 0 1 1 3 2; \
2 1 0 2 2 1; \
4 1 2 0 4 3; \
1 3 2 4 0 1; \
1 2 1 3 1 0')

c = greedy_coloring(distances, 6, 4)
print(c)

• Which paper are you talking about? – 200_success Oct 15 '15 at 18:00
• This one dspace.mit.edu/openaccess-disseminate/1721.1/74063, that paper explains the concept and present the algorithm – Hernandcb Oct 15 '15 at 18:07
• I read the paper, but do not see how to relate the algorithm in the paper to the code in your question. In particular, your algorithm assigns a colour to each pair (node, box size). But in the paper, the box size is given (does not vary), and none of the steps in the paper involve assigning colours to nodes. – Gareth Rees Oct 17 '15 at 22:09