Posts

Vertex Cover (python implementation)

Image
MINIMUM VERTEX-COVER Description Formally, a vertex-cover of an undirected graph  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). A minimum vertex cover is a vertex cover of smallest possible size. The vertex cover number  is the size of a minimum vertex cover. The following figure shows examples of minimum vertex covers in the previous graphs.
Assume that every vertex has an associated cost of . minimize(minimize the total cost)subject tofor all (cover every edge of the graph)for all .(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 = Truefor i in range(len(self.graph)):���…

Transportation Problem (Vogel algorithm python)

Image
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__(…

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…

IP scanning in python

In order to find the IPs using python, we are going to install nmap module. You can installing it, by typing in the terminal the following command : sudo apt-get install python-nmap


ip_scan.py
import nmap nm = nmap.PortScanner() cidr2 ='192.168.1.99/24'a = nm.scan(hosts=cidr2, arguments='-sP') for k,v in a['scan'].iteritems(): if str(v['status']['state']) == 'up': print str(v) try: print str(v['addresses']['ipv4']) + ' => ' + str(v['addresses']['mac']) except: print str(v['addresses']['ipv4']) Output: {'status': {'state': u'up', 'reason': u'conn-refused'}, 'hostname': '', 'addresses': {u'ipv4': u'192.168.1.7'}} 192.168.1.7 {'status': {'state': u'up', 'reason': u'conn-refused'}, 'hostname': '', 'addresses': {u…

Socket programming in python

Image
Socket programming 'means' server-client model
SERVER - CLIENT 

So,we have to two python script. One for the server and one for the client.
For the server: For the client for the client and server python scripts click hereAs you can see, the client is typing and sending a message and the server is receiving and replying. If either the server or the clientwrites 'exit', then the connection stops.The value of the HOST variable is the IP address of the client and the server... ( you can find IP, by pressing ifconfig in your terminal (for linux users) or by pressing ipconfig incommand prompt(for windows users)).So if you want to achieve a communication between 2 computers (they must be connected in the same network) the steps are very simple:1) In computer (A) you have to run the script for the server (don't forget the HOST variable)2) In computer (B) you have to run the script for the client (don't forget the HOST variable)

Find all .txt files

In this post, you are going to see how to find all .txt files in your computer using python's os module.


You can see the code below:




import os def find_all_txtfiles(): for root, dirs, files in os.walk("/"): for file in files: if file.endswith(".txt"): print(os.path.join(file)) find_all_txtfiles()As you can see it's pretty easy to use this code, in order to find whatever kind of file you want. You only have to change .txt extension .Also, you can narrow your search to a specific directory by adding the path of the directory, that you would like to search.( for root, dirs, files in os.walk("/home/user/Desktop/python") ).