naive graph coloring

  Coloring nodes of a graph, simple and naive approach:

	#!/usr/bin/env python
	import random
	import sys
	class node( object ):
	""" a vertex
	"""
	def __init__( self, key ):
	""" c'tor """
	self.key = key
	self.c = None
	self.outEdges = []
	self.inEdges = []
	def connect( self, other ):
	""" connect this verted to the other one """
	if self not in other.inEdges and other not in self.outEdges:
	other.inEdges.append( self )
	self.outEdges.append( other )
	class graph( object ):
	""" simple graph """
	nodes = []
	def __init__( self ):
	""" c'tor """
	self.nodes = []
	self.chroma = 1
	self.palette = []
	def __contains__( self, node ):
	""" in operator """
	return node in self.nodes
	def add( self, n ):
	""" add vertex """
	if n not in self.nodes:
	self.nodes.append( n )
	def colors( self ):
	""" create random palette """
	while len(self.palette) < self.chroma:
	newcol = "#%s" % hex( random.randint(0, 256*256*256 ) )[2:].zfill(6)
	if newcol not in self.palette:
	self.palette.append( newcol )
	def dot( self, fname ):
	""" create dot file """
	self.colors()
	if not fname.endswith(".dot"):
	fname = "%s.dot" % fname
	fname = open( fname, "w+" )
	fname.write( "digraph G {\n")
	for node in self.nodes:
	fname.write( "%s [color=\"%s\",bgcolor=\"%s\",label=\"%s\",shape=\"circle\",style=\"filled\"];\n" % ( node.key,
	self.palette[node.c-1],
	self.palette[node.c-1],
	node.key ) )
	for node in self.nodes:
	for c in node.outEdges:
	fname.write( "%s -> %s;\n" % ( node.key, c.key ) )
	fname.write( "}\n" )
	fname.close()
	def color( gr ):
	""" colorize graph """
	for n in gr.nodes:
	n.c = None
	def colorize( n, col ):
	""" can use color c for vertex n? """
	for item in n.inEdges + n.outEdges:
	if item.c == col:
	return False
	return col
	# # sort by number of in and out edges
	nodes = sorted( [ (len(n.outEdges + n.inEdges), n) for n in gr.nodes ], reverse = True )
	colors = [ 1 ]
	for i, n in nodes:
	if not n.c:
	while not n.c:
	for c in colors:
	can = colorize( n, c )
	if can:
	n.c = can
	break
	if not n.c:
	colors.append( colors[-1] +1 )
	n.c = colors[-1]
	## set chromatic number
	gr.chroma = len(colors)
	return colors
	## execution
	if __name__ == "__main__":
	if len(sys.argv) != 4:
	print "usage: color.py nbNodes nbEdges dotFile"
	sys.exit(0)
	nodes, edges, fname = int(sys.argv[1]), int(sys.argv[2]), sys.argv[3]
	gr = graph()
	nodes = [ node(i) for i in range(nodes) ]
	for i in range(edges):
	inode = random.choice( nodes )
	jnode = random.choice( nodes )
	inode.connect( jnode )
	for node in nodes:
	gr.add(node)
	c = color(gr)
	gr.dot( fname )

view raw color.py hosted with ❤ by GitHub

Usage is very simple:

python color.py  nbNodes nbEdges dotFileName

and then use dot, neato or twopi for rendering.

Example gallery is here.

don't pay taxes for CO2 emission, just plant more red black trees

Just for fun and making plots like that [small rbtrees gallery].

And here goes the humble code...

	class Node( object ):
	"""
	.. class:: Node
	rbTree Node
	"""
	def __init__( self, key ):
	""" c'tor """
	self.left = None
	self.right = None
	self.red = False
	self.key = key
	self._parent = None
	@property
	def parent(self):
	return self._parent
	@parent.setter
	def parent( self, parent ):
	self._parent = parent
	def grandpa( self ):
	""" grandparent """
	if self.parent:
	return self.parent.parent
	def uncle( self ):
	""" uncle """
	grandpa = self.grandpa()
	if not grandpa:
	return None
	if self.parent == grandpa.left:
	return grandpa.right
	return grandpa.left
	class rbTree( object ):
	"""
	.. class:: rbTree
	as seen in T. Cormen, C. Leiseron, R. Rivest, C. Stein
	"""
	def __init__( self ):
	""" c'tor """
	# # dummy node
	self._null = Node(None)
	self._null.left = self._null
	self._null.right = self._null
	self._null.parent = self._null
	# # initial tree root
	self.root = self._null
	def insert( self, key ):
	""" insert key :key: into the tree """
	y = self._null
	x = self.root
	while x != self._null:
	y = x
	if key <= x.key:
	x = x.left
	else:
	x = x.right
	node = Node( key )
	node.parent, node.left, node.right, node.red = y, self._null, self._null, True
	if y == self._null:
	self.root = node
	elif node.key <= y.key:
	y.left = node
	else:
	y.right = node
	self._fixIns( node )
	def min( self, node = None ):
	""" find min from a given node """
	node = node if node else self.root
	while node.left.key:
	node = node.left
	return node.key
	def max( self, node = None ):
	""" find max from a given node """
	node = node if node else self.root
	while node.right.key:
	node = node.right
	return node.key
	def _fixIns( self, node ):
	""" fixtures after insertion """
	while node.parent.red:
	if node.parent == node.parent.parent.left:
	if node.parent.parent.right.red:
	node.parent.red = False
	node.parent.parent.right.red = False
	node.parent.parent.red = True
	node = node.parent.parent
	else:
	if node == node.parent.right:
	node = node.parent
	self.rol(node)
	node.parent.red = False
	node.parent.parent.red = True
	self.ror( node.parent.parent )
	else:
	if node.parent.parent.left.red:
	node.parent.red = False
	node.parent.parent.left.red = False
	node.parent.parent.red = True
	node = node.parent.parent
	else:
	if node == node.parent.left:
	node = node.parent
	self.ror(node)
	node.parent.red = False
	node.parent.parent.red = True
	self.rol( node.parent.parent )
	self.root.red = False
	def rol( self, x ):
	""" rotate left """
	if not x.key: return
	y = x.right
	x.right = y.left
	if y.left != self._null:
	y.left.parent = x
	y.parent = x.parent
	if x.parent == self._null:
	self.root = y
	elif x == x.parent.left:
	x.parent.left = y
	else:
	x.parent.right = y
	y.left = x
	x.parent = y
	def ror( self, y ):
	""" rotate right """
	if not y.key: return
	x = y.left
	y.left = x.right
	if x.right != self._null:
	x.right.parent = y
	x.parent = y.parent
	if y.parent == self._null:
	self.root = x
	elif y == y.parent.right:
	y.parent.right = x
	else:
	y.parent.left = x
	x.right = y
	y.parent = x
	def transplant( self, u, v ):
	""" transplant subtrees
	plant v in place of u
	"""
	if u.parent == self._null:
	self.root = v
	elif u == u.parent.left:
	u.parent.left = v
	else:
	u.parent.right = v
	v.parent = u.parent
	def find( self, k ):
	""" find for a key k """
	node = self.root
	while node != self._null and node.key != k:
	if k < node.key:
	node = node.left
	else:
	node = node.right
	return node
	def delete( self, z ):
	""" delete Node z """
	y = z
	zcol = y.red
	if z.left == self._null:
	x = z.right
	self.transplant( z, z.right )
	elif z.right == self._null:
	x = z.left
	self.transplant( z, z.left )
	elif y == self.min( z.right ):
	zcol = y.red
	x = y.right
	if y.parent == z:
	x.parent = y
	else:
	self.transplant( y, y.right )
	y.right = z.right
	y.right.parent = y
	self.transplant( z, y )
	y.left = z.left
	y.left.parent = y
	y.red = z.red
	if not zcol:
	self._fixDel( x )
	def _fixDel( self, x ):
	""" fixtures after deletion """
	while x != self.root and x.red:
	if x == x.parent.left:
	w = x.parent.right
	if w.red:
	w.red = False
	x.parent.red = True
	self.rol( x.parent )
	w = x.parent.right
	if not w.left.red and not w.right.red:
	w.red = True
	x = x.parent
	else:
	if not w.right.red:
	w.left.red = False
	w.red = True
	self.ror(w)
	w = x.parent.right
	w.red = x.parent.red
	x.parent.red = False
	w.right.red = False
	self.rol( x.parent )
	x = self.root
	else:
	w = x.parent.left
	if w.red:
	w.red = False
	x.parent.red = True
	self.ror( x.parent )
	w = x.parent.left
	if not w.left.red and not w.right.red:
	w.red = True
	x = x.parent
	else:
	if not w.left.red:
	w.right.red = False
	w.red = True
	self.rol(w)
	w = x.parent.left
	w.red = x.parent.red
	x.parent.red = False
	w.left.red = False
	self.ror( x.parent )
	x = self.root
	def dfs( self, node = None ):
	""" dummy inorder dfs to check """
	node = node if node else self.root
	if node.left.key:
	self.dfs( node.left )
	print node.key,
	if node.right.key:
	self.dfs( node.right )
	def dot( self, fname ):
	""" dummy dot file creation
	to generate pic run:
	neato -T png fname > fname.png
	or
	dot -T png fname > fname.png
	"""
	f = open( fname, "w+" )
	f.write( "digraph rb {\n")
	def nodeId( node ):
	return "node%s" % id(node)
	def nodeCol( node ):
	return "red" if node.red else "black"
	def visit( node, f ):
	f.write( '%s [label="%s",color="%s",shape="circle"];\n' % ( nodeId(node), node.key, nodeCol(node) ) )
	if node.left.key:
	visit( node.left, f )
	f.write( "%s -> %s;\n" % ( nodeId(node), nodeId(node.left) ) )
	if node.right.key:
	visit( node.right, f )
	f.write( "%s -> %s;\n" % ( nodeId(node), nodeId(node.right) ) )
	visit( self.root, f )
	f.write( "}\n" )
	f.close()
	# # just for fun make some dot
	if __name__ == "__main__":
	t = rbTree()
	x = range(500)
	import random
	random.shuffle( x )
	for i in x:
	t.insert( i )
	t.dot( "rb500.dot")

view raw rbTree.py hosted with ❤ by GitHub

:)

python popcnt

popcnt - count bits set ("1") in a integer, of course using python

I've implemented only four ways to do this:

• using look up table 0..255 (no iterations, oen sum and a few shifting by 8 bits)
• naive (number of iterations ==  number of bits)
• Brian Kernighan way (number of iterations == number of bits set)
• pythonic by ugly (count "1"s after calling bin()...)

	#!/bin/env python
	""" :mod: popcnt
	============
	.. module: popcnt
	:synopsis: couting bits set ("1") in int or long
	.. moduleauthor:: Krzysztof.Ciba@NOSPAMgmail.com
	"""
	## bit count look up table in range 0..255
	__bcLUT = [ 0 ] * 256
	for i in range(256):
	__bcLUT[i] = ( i & 1 ) + __bcLUT[i/2]
	def popcntLUT( arg ):
	""" popcnt using look up table """
	assert type(arg) in ( int, long )
	e = lambda x, y: x + int( bool( y ) ) << 3
	return sum( [ __bcLUT[ ( arg >> i ) & 255 ]
	for i in range( 0, e( *divmod( arg.bit_length(), 8) ), 8 ) ] )
	def popcntBK( arg ):
	""" Brian Kernighan way - loop only for bits set """
	assert type(arg) in ( int, long )
	pop = 0
	while arg:
	arg &= arg - 1
	pop += 1
	return pop
	def popcntNaive( arg ):
	""" naive - loop for every bit in arg """
	assert type(arg) in ( int, long )
	pop = 0
	while arg:
	pop += arg & 1
	arg >>= 1
	return pop
	def popcntUgly( arg ):
	""" ugly but pythonic way? """
	assert type(arg) in ( int, long )
	return bin(arg).count("1")
	# # eep!
	if __name__ == "__main__":
	# dummy testing
	for i in range(1024):
	ugly = popcntUgly(i)
	lut = popcntLUT(i)
	bk = popcntBK(i)
	naive = popcntNaive(i)
	assert ugly == lut
	assert ugly == bk
	assert ugly == naive

view raw popcnt.py hosted with ❤ by GitHub

All function were run on 1000 samples made by 100 random numbers:

	# --- testBK.py
	import sys
	import random
	from popcnt import popcntBK
	up = 2**256
	for i in range(1, 1001):
	if not i % 10:
	print ".",
	sys.stdout.flush()
	if not i % 100:
	print
	sys.stdout.flush()
	for j in range(1000):
	popcntBK( random.randint( 0, up ) )
	# --- testLUT.py
	import sys
	import random
	from popcnt import popcntLUT
	up = 2**256
	for i in range(1, 1001):
	if not i % 10:
	print ".",
	sys.stdout.flush()
	if not i % 100:
	print
	sys.stdout.flush()
	for j in range(1000):
	popcntLUT( random.randint( 0, up ) )
	# --- testNaive.py
	import sys
	import random
	from popcnt import popcntNaive
	up = 2**256
	for i in range(1, 1001):
	if not i % 10:
	print ".",
	sys.stdout.flush()
	if not i % 100:
	print
	sys.stdout.flush()
	for j in range(1000):
	popcntNaive( random.randint( 0, up ) )
	# --- testUgly.py
	import sys
	import random
	from popcnt import popcntUgly
	up = 2**256
	for i in range(1, 1001):
	if not i % 10:
	print ".",
	sys.stdout.flush()
	if not i % 100:
	print
	sys.stdout.flush()
	for j in range(1000):
	popcntUgly( random.randint( 0, up ) )

view raw gistfile1.py hosted with ❤ by GitHub

And now testing results:

• naive (Zzzzz...)

[Wed, 05 Jun 22:07 E0][cibak@localhost:~/popcnt]> time python testNaive.py
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
175.885u 0.055s 2:56.35 99.7%    0+0k 0+0io 0pf+0w

• BK way (much better!)

[Wed, 05 Jun 22:04 E0][cibak@localhost:~/popcnt]> time python testBK.py
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
75.853u 0.028s 1:16.03 99.7%    0+0k 0+0io 0pf+0w 

• look up table (niiiice!)

[Wed, 05 Jun 22:06 E0][cibak@localhost:~/popcnt]> time python testLUT.py
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
42.828u 0.030s 0:42.93 99.8%    0+0k 0+0io 0pf+0w 

• ugly but pythonic (wut?)

[Wed, 05 Jun 22:04 E1][cibak@localhost:~/popcnt]> time python testUgly.py
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
. . . . . . . . . .
40.880u 0.040s 0:41.06 99.6%    0+0k 0+0io 0pf+0w


And guess what? Ugly (but pythonic) won! Coincidence? I don't think so... ;)

EDIT:
And of course I can completely remove lines with lambda and all this stuff within popcntLUT  and it could be coded just like that:

	## bit count look up table in range 0..255
	__bcLUT = [ 0 ] * 256
	for i in range(256):
	__bcLUT[i] = ( i & 1 ) + __bcLUT[i/2]
	def popcntLUT( arg ):
	""" popcnt using look up table """
	assert type(arg) in ( int, long )
	return sum( [ __bcLUT[ ( arg >> i ) & 255 ]
	for i in range( 0, arg.bit_length(), 8 ) ] )

view raw popcntLUT.py hosted with ❤ by GitHub

But it doesn't help to much.

Also one can check say 16 bits look up table, say:

	__bc16b = [ 0 ] * (256*256)
	for i in range(256*256):
	__bc16b[i] = ( i & 1 ) + __bc16b[i/2]
	def popcnt16b( arg ):
	""" popcnt using 16bits loom up table """
	return sum( [ __bc16b[( arg >> i ) & 65535 ] for i in range( 0, arg.bit_length(), 16 ) ] )

view raw popcnt16b.py hosted with ❤ by GitHub

 This should run at least 2 times faster that original popcntLUT.

 

one does not simply pickle a tree

Ahrrr... It took me 5 hours to figure it out.

Python multiprocessing.Queue is using internally shelve module, which again internally is using cPickle for speed up.  But if something cannot be pickled, when calling Queue.put, you will see some cryptic error message:


File "/opt/dirac/pro/Linux_x86_64_glibc-2.5/lib/python2.6/multiprocessing/queues.py", line 242, in _feed
-    send(obj)
TypeError: expected string or Unicode object, NoneType found

Ugh! Not helping at all, but what to do except start debugging? Taking the advantage of the opportunity I had fixed also some problems here and there (un-shelvable locks or instance methods in several classes), but at the very, very end  I've got this:

pickle.PicklingError: Can't pickle : it's not found as __main__.copyelement

 Huh? What the heck? Where is this one? Find and grep fellows stayed completely  muted, so I've started to dump symbols from *.so under PYTHONPATH, and guess what? I HAVE FOUND IT!

[volhcb13] /opt/dirac/pro > nm Linux_x86_64_glibc-2.5/lib/python2.6/lib-dynload/_elementtree.so | grep copyelement
0000000000209dd8 b elementtree_copyelement_obj



This little bastard was hiding in cElementTree! I've swapped this one with its  python twin (ElementTree). Taa-daam!  Queue.put is working again, not a big deal for me,  XML fragments I'm dealing with are rather small.

5 hours! Five! FIVE HOURS lost...

So, dear children, please remember: when going multiprocessing forget about cElementTree (and perhaps several other modules rewritten in C for speed up) and use pure python implementations.

nth permutation in a lexicographical order

Problem:

Somebody is generating permutations of a given list of elements in a lexicographical order. What is the value of say nth permutation?

Brute force solution is to generate them all, but in that case you'll spend quite a lot of time generating useless permutations - O(n!). So here is the easy way:

	#!/bin/env python
	"""
	Solves a problem of getting permutation of a given index,
	while you know that permutations are created in a lexicographical order.
	As input you are specifying a list of elements and index of permutation you want to get.
	"""
	## imports
	from math import factorial
	## this one just for checking
	from itertools import permutations
	def getNthPermutation( pIndex, inList, outList=[] ):
	""" get :pIndex: permutation of :inList:
	:warn: permutations are sorted in lexicographical order starting from 0, i.e.:
	0 -> [1, 2, 3], 1 -> [1, 3, 2] and so on
	:param int pIndex: given permutation index
	:param list inList: initial list of elements
	:param list outList: result list
	"""
	## permutation index too big
	if pIndex >= factorial( len(inList) ): return []
	## no more elements to use
	if not inList: return outList
	## make sure eList is sorted
	inList.sort()
	## get factorial
	f = factorial( len(inList)-1 )
	index = pIndex / f
	reminder = pIndex % f
	## add new element to outList
	outList.append( inList[index] )
	## ...and remove it from inList
	del inList[index]
	## bail out or call recursively depending of the reminder
	if not reminder:
	return outList + inList
	else:
	return getNthPermutation( reminder, inList, outList )
	### test execution
	if __name__ == "__main__":
	ps = permutations( [1,2,3,4,5,6] )
	for i in range(factorial(6)):
	resList = []
	res = getNthPermutation( i, [1,2,3,4,5,6], resList )
	check = list( ps.next() )
	assert( res == check )

view raw perm.py hosted with ❤ by GitHub

clogged pipe

What if? Say you want to execute something in a python sub-process and you want to read and resend all output data, no matter how big they are?

The simplest solution to use pipe is BAD idea - pipe has it's own buffer and what's worse size of this buffer is constant and cannot be changed by using some smart fnctl call any more. Let's run a simple test:



On my laptop I'm not able to send more than 64kB at a time, moreover its completely hanging:

	[Tue, 19 Feb 19:25 E1][cibak@localhost:~]> python pipeBuf.py
	send 0 B
	read 0 B
	send 1024 B
	read 1024 B
	send 2048 B
	read 2048 B
	[...cut...]
	read 59392 B
	send 60416 B
	read 60416 B
	send 61440 B
	read 61440 B
	send 62464 B
	read 62464 B
	send 63488 B
	read 63488 B
	send 64512 B
	read 64512 B
	^CTraceback (most recent call last):
	File "pipeBad.py", line 8, in <module>
	pin.send("."*i*1024)
	KeyboardInterrupt

view raw gistfile1.txt hosted with ❤ by GitHub

Hmmm... So how can you send more than that? Let's say this way:

	from multiprocessing import Process, Manager
	def sender( S ):
	print "sending 256 MB"
	S["foo"] = "."*256*1024*1024
	if __name__ == '__main__':
	m = Manager()
	S = m.dict()
	p1 = Process( target=sender, args=( S, ) )
	p1.start()
	p1.join()
	print "'read' it all", len(S["foo"])

view raw bigChunk.py hosted with ❤ by GitHub

Use a simple manager, man! More info here.

There is also possibility  to use shared memory objects (read this), but those are rather for storing not so huge amount of data.

Disclaimer: Before use, read the contents of the package insert or consult your physician or pharmacist because each drug used improperly threatens your life or health.

Revert words in a sentence.

Revert words in a sentence, so " The quick brown fox jumped over the lazy dog." becomes "dog. lazy the over jumped fox brown quick The" .

In C:

	#include <stdio.h>
	void revertWord( char *start, char *end ) {
	char temp;
	while( start < end ) {
	temp = *start;
	*start = *end;
	*end = temp;
	++start;
	--end;
	}
	}
	void revertString(char *sentence) {
	char *start = sentence;
	char *end = sentence;
	while ( *(++end) ); // to the null
	// but don't touch not null
	--end;
	// all sentence first
	revertWord( start, end );
	// and now word by word
	while ( *start ) { // not null?
	// find space if any, move start to it
	for (; *start && *start == ' '; ++start );
	// find end fo the word, move end to it
	for ( end = start; *end && *end != ' '; ++end );
	// space or null, back one
	--end;
	// reverse from start to end
	revertWord( start, end );
	// next word or null
	start = ++end;
	}
	}
	int main() {
	char test[] = "The quick brown fox jumped over the lazy dog.";
	printf( "before: %s\n", test );
	revertString(test);
	printf( "after: %s\n", test );
	return 0;
	}

view raw revert.C hosted with ❤ by GitHub

In C++:

	#include <iostream>
	#include <sstream>
	#include <stack>
	using namespace std;
	// using stack
	string revertStack( string sentence ) {
	stringstream inout(sentence);
	string word, news;
	stack<string> st;
	while ( inout >> word ) {
	st.push( word );
	}
	while ( st.size() ) {
	news += " " + st.top();
	st.pop();
	}
	return news;
	}
	int main() {
	string sentence = "The quick brown fox jumped over the lazy dog.";
	sentence = revertStack( sentence );
	cout << sentence << endl;
	}

view raw revert.cpp hosted with ❤ by GitHub

In py:

	sentence = "The quick brown fox jumped over the lazy dog."
	print "before: ", sentence
	sentence = " ".join( sentence.split()[::-1] )
	print "after: ", sentence

view raw revertSentence.py hosted with ❤ by GitHub

52 > 27 > 4!