Tuesday, September 15, 2015

Pass php variables values to python script

Assume the following php code:

example.php

<?php
$var1 = "1";
$var2 = "2";
$var3 = "3";
$output = exec("example.py ".$var1." ".$var2." ".$var3);
print $output;

?>

$output variable contains python's script output

Then we have to create the example.py script.

example.py 

import sys

print sys.argv[1], sys.argv[2], sys.argv[3] 


Saturday, July 25, 2015

Reduction from SAT to Clique (proving NP-complete)



SAT problem description:

Assume a boolean expression in CNF (conjuctive normal form). The question for this decision problem is, can you set the variables to a combination of TRUE/FALSE so that the boolean expression becomes true.
(Using the laws of Boolean algebra, every boolean expression can be transformed into an equivalent conjuctive normal form, which may, however , be exponentially longer).

In order to show reduction from SAT to Clique, i have to transform the input of the SAT into an input for Clique ( Boolean expression to graph ).
SAT is a NP-complete problem.

BE = (x1 or x2) and (-x2 or x3) and (-x3 or x1 or x2)
This Bollean expression has 3 clauses:
Clause_1 contains x1, x2
Clause_2 contains -x2, x3
Clause_3 contains -x3, x1, x2

The graph is going to have as vertexes as the variables in BE (7 vertices).
Every vertex is going to connect with all the others. Attention, there is no connection among the vertices that belong to the same clause,  and also, there is no connection between the
xi,-xi vertices.

Now it's time to construct the graph

This is the input graph for clique. A max clique for this graph is c1:(x2, x3, x1), another max clique is c2:(x1, x3, x1)

From reduction's definition you know that, solving problem Y (Clique) on transformed input yields some answer as solving X (SAT) on original input.

So if  i set the variables x2, x3, x1 (c1 clique result) to TRUE at the same time,then boolean's expression result should be TRUE. 

We just prove reduction from SAT to Clique. We prove also, that Clique is a NP-complete problem!!!

Below, is presented a function, which take as its input a boolean formula and assignments of the variables and returns TRUE if the formula is satisfied by the assignment and False otherwise. 

def is_satisfied(clauses, assignment):
    
    counter = 0    for clause in clauses:
        for item in clause:
            if item > 0:
                if assignment[item] == 1:
                    counter += 1                    break            else:
                if assignment[abs(item)] == 0:
                    counter += 1                    break
    if counter == len(clauses):
        return True    else:
        return False

def test():
    clauses = [[1,2,-3],[2,-4],[-1,3,4]]
    assignment = [0,1,1,1,1]
    assert is_satisfied(clauses, assignment)

    assignment = [0,1,0,1,1]
    assert not is_satisfied(clauses, assignment)

print test()

Thursday, July 2, 2015

Vertex Cover (python implementation)


MINIMUM VERTEX-COVER
Description
Formally, a vertex-cover of an undirected graph G=(V, E) is a subset V′ of V such that if edge (u, v) is an edge of G, then u is in V′, or v is in V′, or both. The set V′ is said to "cover" the edges of G. The following figure shows examples of vertex covers in two graphs (and the set V' is marked with red).
Vertex-cover.svg
A minimum vertex cover is a vertex cover of smallest possible size. The vertex cover number \tau is the size of a minimum vertex cover. The following figure shows examples of minimum vertex covers in the previous graphs.
Minimum-vertex-cover.svg

Assume that every vertex has an associated cost of c(v)\geq 0.
minimize\sum_{v \in V} c(v) x_v  (minimize the total cost)
subject tox_u+x_v\geq 1for all \{u,v\} \in E(cover every edge of the graph)
x_v\in\{0,1\}for all v\in V.(every vertex is either in the vertex cover or not)

Python implementation(running-time: exponential)

import itertools

class Vertex_Cover:

    def __init__(self, graph):
        self.graph = graph

    def validity_check(self, cover):
        is_valid = True        for i in range(len(self.graph)):
            for j in range(i+1, len(self.graph[i])):
                if self.graph[i][j] == 1 and cover[i] != '1' and cover[j] != '1':
                    return False
        return is_valid

    def vertex_cover_naive(self):
        n = len(self.graph)
        minimum_vertex_cover = n
        a = list(itertools.product(*["01"] * n))
        for i in a:
            if Vertex_Cover.validity_check(ins, i):
                counter = 0                for value in i:
                    if value == '1':
                        counter += 1                minimum_vertex_cover = min(counter, minimum_vertex_cover)

        return minimum_vertex_cover

if __name__ == '__main__':
    graph =[[0, 1, 1, 1, 1],[1, 0, 0, 0, 1],[1, 0, 0, 1, 1], [1, 0, 1, 0, 1], [1, 1, 1, 1, 0]]
    ins = Vertex_Cover(graph)

    print 'the minimum vertex-cover is:', Vertex_Cover.vertex_cover_naive(ins)


Sunday, May 24, 2015

Transportation Problem (Vogel algorithm python)

Transportation Problem

A typical transportation problem is shown in Fig. 9. It deals with sources where a supply of some commodity is available and destinations where the commodity is demanded. The classic statement of the transportation problem uses a matrix with the rows representing sources and columns representing destinations. The algorithms for solving the problem are based on this matrix representation. The costs of shipping from sources to destinations are indicated by the entries in the matrix. If shipment is impossible between a given source and destination, a large cost of M is entered. This discourages the solution from using such cells. Supplies and demands are shown along the margins of the matrix. As in the example, the classic transportation problem has total supply equal to total demand.
Figure 9. Matrix model of a transportation problem.
(http://www.me.utexas.edu/~jensen/models/network/net8.html)

Vogel Algorithm as a solution (python)

class Vogel():

    def __init__(self, warehouses, stores, supply, demand, cost):
        self.warehouses = warehouses
        self.stores = stores
        self.supply = supply
        self.demand = demand
        self.cost = cost

    def rows_dict(self):
        rows_d = {}
        for i in range(len(self.supply)):
            if self.supply[i] > 0:
                row = []
                for j in range(self.stores):
                    row.append(self.cost[i][j])
                rows_d[i] = row
        return rows_d

    def cols_dict(self):
        cols_d = {}
        for l in range(len(self.demand)):
            if self.demand[l] > 0:
                col = []
                for k in range(self.warehouses):
                    col.append(self.cost[k][l])
                cols_d[l] = col
        return cols_d

    @staticmethod    def two_mins(array):
        temp = []
        if array == ['']:
            minimum = -1            return minimum
        else:
            for i in range(len(array)):
                if array[i] == ['']:
                    i += 1                else:
                    temp.append(array[i])

            temp = sorted(temp)
            if len(temp) > 1:
                minimum = abs(temp[0] - temp[1])
            else:
                minimum = temp[0]
            return minimum

    @staticmethod    def diff_r(rows_d, supply, cols_d):

        diff_rows = {}

        for i in rows_d:
            if supply[i] > 0:
                minimum = Vogel.two_mins(rows_d[i])
                diff_rows[i] = minimum
            elif supply[i] == 0 and rows_d[i] != ['']:
                rows_d[i] = ['']
                for k in cols_d:
                    if cols_d[k] != ['']:
                        cols_d[k][i] = ['']

        return diff_rows

    @staticmethod    def diff_c(cols_d, demand, rows_d):

        diff_cols = {}

        for i in cols_d:
            if demand[i] > 0:
                minimum = Vogel.two_mins(cols_d[i])
                diff_cols[i] = minimum
            elif demand[i] == 0 and cols_d[i] != ['']:
                cols_d[i] = ['']
                for k in rows_d:
                    if rows_d[k] != ['']:
                        rows_d[k][i] = ['']

        return diff_cols

    @staticmethod    def find_max(diff_rows, diff_cols):
        maximum_row = -1        for i in diff_rows:
            flag = diff_rows[i]
            if flag > maximum_row:
                maximum_row = flag

        maximum_col = -1        for i in diff_cols:
            temp = diff_cols[i]
            if temp > maximum_col:
                maximum_col = temp

        if maximum_col > maximum_row:
            return maximum_col
        else:
            return maximum_row

    @staticmethod    def max_location_row(diff_rows, maximum):

        location_row = []
        for i in diff_rows:
            if maximum == diff_rows[i]:
                location_row.append(i)

        return location_row

    @staticmethod    def max_location_cols(diff_cols, maximum):

        location_col = []
        for i in diff_cols:
            if maximum == diff_cols[i]:
                location_col.append(i)

        return location_col

    @staticmethod    def find_pivot(location_row, location_col, rows_d, cols_d):
        minimum = 99999        if len(location_row) > 0:
            for id in location_row:
                if min(rows_d[id]) <= minimum:
                    minimum = min(rows_d[id])
                    supply_pos = id
                    demand_pos = rows_d[id].index(minimum)

        if len(location_col) > 0:
            for id in location_col:
                if min(cols_d[id]) <= minimum:
                    minimum = min(cols_d[id])
                    supply_pos = cols_d[id].index(minimum)
                    demand_pos = id

        return supply_pos, demand_pos

    def implementation(self):

        rows_d = Vogel.rows_dict(ins)
        cols_d = Vogel.cols_dict(ins)
        # print rows_d        # print cols_d        score = 0        while 1:
            counter = 0            for i in range(len(self.demand)):
                if self.demand[i] == 0:
                    counter += 1            # total demand = 0            if counter == len(self.demand):
                break            else:

                diff_rows = Vogel.diff_r(rows_d, self.supply, cols_d)
                diff_cols = Vogel.diff_c(cols_d, self.demand, rows_d)
                # print 'diff for rows:', diff_rows                # print 'diff for cols:', diff_cols
                maximum = Vogel.find_max(diff_rows, diff_cols)
                # print 'maximum:', maximum
                location_row = Vogel.max_location_row(diff_rows, maximum)
                location_col = Vogel.max_location_cols(diff_cols, maximum)
                # print 'pivot location', Vogel.find_pivot(location_row, location_col, rows_d, cols_d)
                supply_pos = Vogel.find_pivot(location_row, location_col, rows_d, cols_d)[0]
                demand_pos = Vogel.find_pivot(location_row, location_col, rows_d, cols_d)[1]

                # cost Calculation                if self.supply[supply_pos] == self.demand[demand_pos]:
                    score = score + self.demand[demand_pos] * self.cost[supply_pos][demand_pos]
                    self.supply[supply_pos] -= self.demand[demand_pos]
                    self.demand[demand_pos] = 0                elif self.demand[demand_pos] > self.supply[supply_pos]:
                    score = score + self.supply[supply_pos] * self.cost[supply_pos][demand_pos]
                    self.demand[demand_pos] -= self.supply[supply_pos]
                    self.supply[supply_pos] = 0                else:
                    score = score + self.demand[demand_pos] * self.cost[supply_pos][demand_pos]
                    self.supply[supply_pos] -= self.demand[demand_pos]
                    self.demand[demand_pos] = 0                # print 'supply:', self.supply                # print 'demand:', self.demand                # print ''
        print "The Vogel's cost is", score

if __name__ == '__main__':
    # number of warehouses    w = warehouses_construction()
    # number of stores    st = stores_construction()
    # supply array for example:([3, 4, 5])    sup = supply_construction()
    # demand array for example:([2, 5, 2, 3])    dem = demand_construction()
    # cost array for example: ([[5, 3, 1 ,8],    #                          [1, 7, 2 ,3],    #                          [6, 2, 11 ,9]])    cst = cost_construction()

    ins = Vogel(w, st, sup, dem, cst)
    Vogel.implementation(ins)

Tuesday, May 19, 2015

cProfile python (benchmark)

Python includes a profiler called cProfile. It not only gives the total running time, but also times each function separately, and tells you how many times each function was called, making it easy to determine where you should make optimizations.

For example, you can invoke the cProfile when running a script with the following:

python -m cProfile myscript.py  

the output of this script look like this below:

4550013 function calls in 4.187 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.002    0.002    4.187    4.187 my_trans.py:1(<module>)
      297    0.002    0.000    0.002    0.000 my_trans.py:107(max_location_row)
      297    0.003    0.000    0.003    0.000 my_trans.py:117(max_location_cols)
      594    0.002    0.000    0.022    0.000 my_trans.py:127(find_pivot)
        1    0.006    0.006    0.008    0.008 my_trans.py:14(rows_dict)
        1    0.010    0.010    4.165    4.165 my_trans.py:146(main)
        1    0.006    0.006    0.008    0.008 my_trans.py:24(cols_dict)
    45078    2.611    0.000    4.013    0.000 my_trans.py:34(two_mins)
        1    0.000    0.000    0.000    0.000 my_trans.py:5(Vogel)
      297    0.037    0.000    2.118    0.007 my_trans.py:54(diff_r)
        1    0.000    0.000    0.000    0.000 my_trans.py:7(__init__)
      297    0.055    0.000    1.987    0.007 my_trans.py:71(diff_c)
      297    0.006    0.000    0.006    0.000 my_trans.py:88(find_max)
        1    0.000    0.000    0.000    0.000 timeit.py:105(Timer)
        1    0.000    0.000    0.000    0.000 timeit.py:53(<module>)
        1    0.000    0.000    0.000    0.000 txtdata.py:1(<module>)
        1    0.000    0.000    0.000    0.000 txtdata.py:1(warehouses_construction)
        1    0.000    0.000    0.000    0.000 txtdata.py:16(stores_construction)
        1    0.000    0.000    0.000    0.000 txtdata.py:31(supply_construction)
        1    0.000    0.000    0.000    0.000 txtdata.py:46(demand_construction)
        1    0.015    0.015    0.018    0.018 txtdata.py:60(cost_construction)
    45072    0.006    0.000    0.006    0.000 {abs}
    92044    0.012    0.000    0.012    0.000 {len}
        4    0.000    0.000    0.000    0.000 {map}
  4272686    0.349    0.000    0.349    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
      646    0.004    0.000    0.004    0.000 {method 'index' of 'list' objects}
      104    0.001    0.000    0.001    0.000 {method 'split' of 'str' objects}
     1420    0.016    0.000    0.016    0.000 {min}
        5    0.000    0.000    0.000    0.000 {open}
    45780    0.057    0.000    0.057    0.000 {range}
    45078    0.986    0.000    0.986    0.000 {sorted}
        2    0.000    0.000    0.000    0.000 {time.time}