#!/usr/bin/ruby

# A simple graph generator (for graphviz)
# author: Yoan Blanc <yoan at dosimple dot ch>

# usage: ./graph.rb <quantity> <luck>
# example: ./graph.rb 100 .98 | dot -Tpng -o graph.png

def genGraph( size, luck )
	# Generate a graph of the given size
	# two nodes have the luck (in %) chance to NOT have connection
	graph = Array.new
	size.times do |i|
		# a new array for the current cell
		graph[i] = Array.new
		# mirror
		(0..(i-1)).step do |j|
			graph[i] << graph[j][i]
		end
		# no link to self
		graph[i] << false
		
		# new values
		((i+1)..(size-1)).step do |j|
			# lowing the chances
			graph[i] << (rand > luck)
		end
	end
	graph
end

def genLetter( size )
	# Generate a serie of human readable numbers (with letters)
	# like a, b, c ... aa, ab, ac
	
	offset = ?a
	if size <= 26
		("a"..(offset + size - 1).chr)
	elsif size <= 26**2
		div, rest = size.divmod(26).map {|x| x+offset}
		("aa"..(div.chr + rest.chr))
	elsif size <= 26**3
		div2, rest = size.divmod(26**2)
		div, rest = rest.divmod(26).map {|x| x+offset}
		div2 += offset
		("aaa"..(div2.chr + div.chr + rest.chr))
	else
		# be a samourai (http://c2.com/cgi/wiki?SamuraiPrinciple)
		raise "Size of the graph is too big for the letter mapping"
	end
end

def buildDot( graph, dive )
	# Build the dot semantic for GraphViz
	
	size = graph[0].length
	letters = genLetter( size )
	
	dot = "graph noname {\n"
	dot += " center = false\n"
	dot += " ratio = fill\n"
	dot += " node [style=filled,fontsize=10,width=0.000,height=0.000]\n"
	
	# Nice colors and label (with level in it)
	# Not required without colors neither label
	nodes = letters.to_a
	depth = dive.length
	
	size.times do |i|
		dot += " #{nodes[i]}"
		depth.times do |n|
			unless dive[n].index(i).nil?
				color = 1.0 - n/depth.to_f
				dot += ' [label="'+nodes[i]+' ('+n.to_s+')",color="'+format("%.3f", color)+' 1.000 1.000"]'
				break
			end
		end
		dot += "\n"
	end
	
	# The connections between nodes
	size.times do |i|
		dot += " #{nodes[i]}--{"
		((i+1)..size).step do |j|
			if graph[i][j]
				dot += " #{nodes[j]}"
			end
		end
		dot += " }\n"
	end
	dot + "}"
end

def diveGraph( graph, node, level)
	# Dive into the graph and find every nodes that are accessible for the given
	# node. It'll stop at the level (if targeted) that is the max depth.
	
	size = graph.length
	dive = Array.new
	
	level.times do |i|
		dive << Array.new
		if i == 0
			# first level is self
			dive[i] << node
		else
			# find all nodes that are accessible at this level
			dive[i-1].each do |node|
				size.times do |j|
					dive[i] << j if graph[node][j]
				end
			end
			# Remove already known nodes
			dive[i].uniq!
			dive[i] = dive[i] - dive[0..i-1].flatten
			
			# no more, leave
			break if dive[i].length == 0
		end
	end
	dive
end

# not very nice... (sorry)
graph = genGraph(ARGV[0].to_i, ARGV[1].to_f)
dive = diveGraph( graph, 0, 50)
puts buildDot(graph, dive)