# Nick Peters
# COMP 452
# EXONCHAINING.py
DEBUG = False

# Input: Set of weighted intervals
# Output: Length of longest path
def MakeGraph(s):
	# Reverse the set for the pop operation
	s.reverse()
	G = {}
	# There will be 2n vertices where n is the number of weighted intervals
	# in the given set.
	n = 2*len(s)
	for i in range(1,n+1):
		# Add the right adjacent vertex with a weight of 0
		if i < n:
			G[i] = {i+1:0}
		# Don't add the adjacent vertex to the last vertex since it doesn't exist
		else:
			G[i] = {}
		# If we have a weighed edge in the given set, add it to the graph
		if len(s) != 0 and s[-1][0] == i:
			# Remove the last element of the set when we add it to the graph
			temp = s.pop()
			G[i][temp[1]] = temp[2]
	return G
	
def ExonChain(G):
	# n - number of vertices
	n = len(G)
	# s - the length of the longest path for a given vertex
	# s[2n] gives us the solution to the exon chaining problem
	s = [0 for i in range(0,n)]
	for i in range(1,n+1):
		# Examine each edge in the adjacency list
		for adj in G[i].keys():
			if G[i][adj] + s[i-1] > s[adj-1]:
				s[adj-1] = G[i][adj] + s[i-1]
	return s
	


if __name__ == '__main__':
	if DEBUG:
		# Set of weighted intervals.
		# According to the book we may assume the set is sorted in increasing order.
		WeightedIntervals = [(1,8,7), (2,4,3), (3,5,5), (6,9,3), (7,11,4), (10,12,5)]
		G = MakeGraph(WeightedIntervals)
		print G == {1: {8: 7, 2: 0}, 2: {3: 0, 4: 3}, 
		3: {4: 0, 5: 5}, 4: {5: 0}, 5: {6: 0}, 6: {9: 3, 7: 0}, 7: {8: 0, 11: 4}, 
		8: {9: 0}, 9: {10: 0}, 10: {11: 0, 12: 5}, 11: {12: 0}, 12: {}}
		print ExonChain(G) == [0,0,0,3,5,5,5,7,8,8,8,9,13]
	else:
		WeightedIntervals = [(1,5,5),(2,3,3),(4,8,6),(6,12,10),(7,17,12),(9,10,1),(11,15,7),(13,14,0),(16,18,4)]
		G = MakeGraph(WeightedIntervals)
		s = ExonChain(G)
		print "Graph:", G
		print "Longest Path for each vertex:", s
		print "Longest Path: ", s[-1]