def simplex_compute_potentials(self, t, root):
        '''
        API:
            simplex_compute_potentials(self, t, root)
        Description:
            Computes node potentials for a minimum cost flow problem and stores
            them as node attribute 'potential'. Based on pseudocode given in
            Network Flows by Ahuja et al.
        Pre:
            (1) Assumes a directed graph in which each arc has a 'cost'
            attribute.
            (2) Uses 'thread' and 'pred' attributes of nodes.
        Input:
            t: Current spanning tree solution, its type is Graph.
            root: root node of the tree.
        Post:
            Keeps the node potentials as 'potential' attribute.
        '''
        self.get_node(root).set_attr('potential', 0)
        j = t.get_node(root).get_attr('thread')
        while j is not root:
            i = t.get_node(j).get_attr('pred')
            potential_i = self.get_node(i).get_attr('potential')
            if (i,j) in self.edge_attr:
                c_ij = self.edge_attr[(i,j)]['cost']
                self.get_node(j).set_attr('potential', potential_i-c_ij)
            if (j,i) in self.edge_attr:
                c_ji = self.edge_attr[(j,i)]['cost']
                self.get_node(j).set_attr('potential', potential_i+c_ji)
            j = t.get_node(j).get_attr('thread')
def simplex_compute_potentials ( self , t , root ) : self . get_node ( root ) . set_attr ( 'potential' , 0 ) j = t . get_node ( root ) . get_attr ( 'thread' ) while j is not root : i = t . get_node ( j ) . get_attr ( 'pred' ) potential_i = self . get_node ( i ) . get_attr ( 'potential' ) if ( i , j ) in self . edge_attr : c_ij = self . edge_attr [ ( i , j ) ] [ 'cost' ] self . get_node ( j ) . set_attr ( 'potential' , potential_i - c_ij ) if ( j , i ) in self . edge_attr : c_ji = self . edge_attr [ ( j , i ) ] [ 'cost' ] self . get_node ( j ) . set_attr ( 'potential' , potential_i + c_ji ) j = t . get_node ( j ) . get_attr ( 'thread' )
API:
            simplex_compute_potentials(self, t, root)
        Description:
            Computes node potentials for a minimum cost flow problem and stores
            them as node attribute 'potential'. Based on pseudocode given in
            Network Flows by Ahuja et al.
        Pre:
            (1) Assumes a directed graph in which each arc has a 'cost'
            attribute.
            (2) Uses 'thread' and 'pred' attributes of nodes.
        Input:
            t: Current spanning tree solution, its type is Graph.
            root: root node of the tree.
        Post:
            Keeps the node potentials as 'potential' attribute.