#NEWLINE# def min_feedback_arc_set( edges , remove = False , maxcycles = 20000 ) : #NEWLINE# #INDENT# '\n    A directed graph may contain directed cycles, when such cycles are\n    undesirable, we wish to eliminate them and obtain a directed acyclic graph\n    (DAG). A feedback arc set has the property that it has at least one edge\n    of every cycle in the graph. A minimum feedback arc set is the set that\n    minimizes the total weight of the removed edges; or alternatively maximize\n    the remaining edges. See: <http://en.wikipedia.org/wiki/Feedback_arc_set>.\n\n    The MIP formulation proceeds as follows: use 0/1 indicator variable to\n    select whether an edge is in the set, subject to constraint that each cycle\n    must pick at least one such edge.\n\n    >>> g = [(1, 2, 2), (2, 3, 2), (3, 4, 2)] + [(1, 3, 1), (3, 2, 1), (2, 4, 1)]\n    >>> min_feedback_arc_set(g)\n    ([(3, 2, 1)], 1)\n    >>> min_feedback_arc_set(g, remove=True)  # Return DAG\n    ([(1, 2, 2), (2, 3, 2), (3, 4, 2), (1, 3, 1), (2, 4, 1)], 1)\n    ' #NEWLINE# G = nx . DiGraph ( ) #NEWLINE# edge_to_index = { #NEWLINE# #INDENT# #NEWLINE# #UNINDENT# } #NEWLINE# for ( i , ( a , b , w ) ) in enumerate ( edges ) : #NEWLINE# #INDENT# G . add_edge ( a , b ) #NEWLINE# edge_to_index [ ( a , b ) ] = i #NEWLINE# #UNINDENT# nedges = len ( edges ) #NEWLINE# L = LPInstance ( ) #NEWLINE# L . add_objective ( edges , objective = MINIMIZE ) #NEWLINE# constraints = [ ] #NEWLINE# ncycles = 0 #NEWLINE# for c in nx . simple_cycles ( G ) : #NEWLINE# #INDENT# cycle_edges = [ ] #NEWLINE# rc = ( c + [ c [ 0 ] ] ) #NEWLINE# for ( a , b ) in pairwise ( rc ) : #NEWLINE# #INDENT# cycle_edges . append ( edge_to_index [ ( a , b ) ] ) #NEWLINE# #UNINDENT# cc = summation ( cycle_edges ) #NEWLINE# constraints . append ( '{0} >= 1' . format ( cc ) ) #NEWLINE# ncycles += 1 #NEWLINE# if ( ncycles == maxcycles ) : #NEWLINE# #INDENT# break #NEWLINE# #UNINDENT# #UNINDENT# logging . debug ( 'A total of {0} cycles found.' . format ( ncycles ) ) #NEWLINE# L . constraints = constraints #NEWLINE# L . add_vars ( nedges ) #NEWLINE# ( selected , obj_val ) = L . lpsolve ( clean = False ) #NEWLINE# if remove : #NEWLINE# #INDENT# results = ( [ x for ( i , x ) in enumerate ( edges ) if ( i not in selected ) ] if selected else None ) #NEWLINE# #UNINDENT# else : #NEWLINE# #INDENT# results = ( [ x for ( i , x ) in enumerate ( edges ) if ( i in selected ) ] if selected else None ) #NEWLINE# #UNINDENT# return ( results , obj_val )