#!/usr/bin/python

import DNASim
	
def filter( patterns, numVertices, N ):
	# get those of write length
	print "Filtering by length"
	N1 = []
	N2 = []
	DNASim.seperate( N, DNASim.lengthEquals, numVertices*20, N1, N2 )
	N = N1
	print "%d candidates" % len(N)
	
	# get those that start at right place
	print "Filtering by start position"
	N1 = []
	N2 = []
	DNASim.seperate( N, DNASim.startsWith, patterns[ 0 ], N1, N2 )
	N = N1
	print "%d candidates" % len(N)
	
	# get those that end at right place
	print "Filtering by end position"
	N1 = []
	N2 = []
	DNASim.seperate( N, DNASim.endsWith, patterns[ -1 ], N1, N2 )
	N = N1
	print "%d candidates" % len(N)
	
	# get those that contain all of the vertices
	print "Filtering for all vertices"	
	for pattern in patterns:
		N1 = []
		N2 = []
		DNASim.seperate( N, DNASim.contains, pattern, N1, N2 )
		N = N1
		print "%d candidates" % len(N)
	return N
	
def runAlgo( numVertices , graph ):
	
	patterns = [];
	
	# make the sequences that represent the vertices
	for n in range( 0, numVertices ):
		patterns.append( DNASim.randomStrand( 20 ) )
	
	
	# make all paths
	print "Generating all paths"	
	N = DNASim.generateAllVertexEdgePatterns( patterns, range( 0, numVertices ), graph )
	
	print "%d candidates" % len(N)
	
	N = filter( patterns, numVertices, N )	
	
	# N should now contain all of the correct solutions (if any)
	if len( N ) > 0:
		print "%d path(s)" % len( N )
		for strand in N:
			path = DNASim.sequence( strand, patterns )
			print path
	else:
		print "No Path Found"

# default to
# adelmans graph
def run( numVertices = 7, graph = { 0: [ 1, 3, 6 ], 1: [ 2, 3 ], 2: [ 1, 3 ], 3: [ 2, 4 ], 4: [ 1, 5 ], 5: [ 1, 2, 6 ] } ):
	print "Searching Graph:"
	print graph
	runAlgo( numVertices, graph )