#NEWLINE# def path( edges , source , sink , flavor = 'longest' ) : #NEWLINE# #INDENT# '\n    Calculates shortest/longest path from list of edges in a graph\n\n    >>> g = [(1,2,1),(2,3,9),(2,4,3),(2,5,2),(3,6,8),(4,6,10),(4,7,4)]\n    >>> g += [(6,8,7),(7,9,5),(8,9,6),(9,10,11)]\n    >>> path(g, 1, 8, flavor="shortest")\n    ([1, 2, 4, 6, 8], 21)\n    >>> path(g, 1, 8, flavor="longest")\n    ([1, 2, 3, 6, 8], 25)\n    ' #NEWLINE# ( outgoing , incoming , nodes ) = node_to_edge ( edges ) #NEWLINE# nedges = len ( edges ) #NEWLINE# L = LPInstance ( ) #NEWLINE# assert ( flavor in ( 'longest' , 'shortest' ) ) #NEWLINE# objective = ( MAXIMIZE if ( flavor == 'longest' ) else MINIMIZE ) #NEWLINE# L . add_objective ( edges , objective = objective ) #NEWLINE# constraints = [ ] #NEWLINE# for v in nodes : #NEWLINE# #INDENT# incoming_edges = incoming [ v ] #NEWLINE# outgoing_edges = outgoing [ v ] #NEWLINE# icc = summation ( incoming_edges ) #NEWLINE# occ = summation ( outgoing_edges ) #NEWLINE# if ( v == source ) : #NEWLINE# #INDENT# if ( not outgoing_edges ) : #NEWLINE# #INDENT# return None #NEWLINE# #UNINDENT# constraints . append ( '{0} = 1' . format ( occ ) ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# if ( v == sink ) : #NEWLINE# #INDENT# if ( not incoming_edges ) : #NEWLINE# #INDENT# return None #NEWLINE# #UNINDENT# constraints . append ( '{0} = 1' . format ( icc ) ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# constraints . append ( '{0}{1} = 0' . format ( icc , occ . replace ( '+' , '-' ) ) ) #NEWLINE# if incoming_edges : #NEWLINE# #INDENT# constraints . append ( '{0} <= 1' . format ( icc ) ) #NEWLINE# #UNINDENT# if outgoing_edges : #NEWLINE# #INDENT# constraints . append ( '{0} <= 1' . format ( occ ) ) #NEWLINE# #UNINDENT# #UNINDENT# #UNINDENT# #UNINDENT# L . constraints = constraints #NEWLINE# L . add_vars ( nedges ) #NEWLINE# ( selected , obj_val ) = L . lpsolve ( ) #NEWLINE# results = ( sorted ( ( x for ( i , x ) in enumerate ( edges ) if ( i in selected ) ) ) if selected else None ) #NEWLINE# results = edges_to_path ( results ) #NEWLINE# return ( results , obj_val )