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.