mainly a fonction pruning an un-directed multigraph

pruning.py

def at_least_one_vertex_of_degree_above_one(graph):
    ''' check if there's at least one vertex of degree above 1 in the graph.
    '''
    graph = gt.GraphView(graph, vfilt= lambda v : v.out_degree() > 1)
    try:
        first = next(graph.vertices())
    except StopIteration:
        return False
    return True


def is_VeV(graph):
    ''' True if the graph contain only two vertices of degree 1 and possibly vertex of deg=0
    '''
    return (number_of_degree1_vertices(graph) == 2) and \
            (not(at_least_one_vertex_of_degree_above_one(graph)))

def prune_VeV(graph):
    '''prune a graph with two vertices of degree 1 (V1) and one weighted edge
        return the the weight of the edge and 0, the number of V1 (0).
    '''
    index_degree1_vertices = vertices_of_degree(graph, 1)[0]
    v1_index = index_degree1_vertices[0]
    vertex = graph.vertex(v1_index)
    bound_edge = vertex.out_edges()
    BE = [be for be in bound_edge][0]
    weight = graph.ep.weight[BE]
    graph.remove_edge(BE)
    assert(number_of_degree1_vertices(graph) == 0)
    return weight, number_of_degree1_vertices(graph)

def prune_once_faster(graph):
    
    #filter the vertices of degree 1
    subg = gt.GraphView(graph, vfilt= lambda v : v.out_degree() == 1)
    weight_vertex_edge = defaultdict(list)
    
    test_degree = is_VeV(graph)
    if test_degree == False:
        for v in subg.vertices():
            #print type(v)
            #print graph.vertex(v)
            #GET THE ONLY EDGE BOUND TO THE VERTEX (SINCE DEGREE=1)
            edge = next(graph.vertex(v).out_edges())
            weight = graph.ep.weight[edge]
            #print'edge', edge
            #print edge, ' weight ',weight
            weight_vertex_edge[weight].append((v, edge))

        shortest_edge = min(weight_vertex_edge.keys())
        #print 'shortest', shortest_edge
        #print 'decrease weight'
        #loop = 1
        for v in subg.vertices():
            vertex = graph.vertex(v)
            bound_edge = vertex.out_edges()
            BE = next(bound_edge)
            #BE = [be for be in bound_edge][0]
            #print vertex, BE, graph.ep.weight[BE]
            graph.ep.weight[BE] = graph.ep.weight[BE]-shortest_edge
            #print 'after', graph.ep.weight[BE]
            if graph.ep.weight[BE] == 0.0:
                graph.remove_edge(BE)
        return shortest_edge,number_of_degree1_vertices(graph)  
    elif test_degree == True:
            # Get the two bound vertices of degree 1 Vertex_edge_Vertex
            #V_e_V = gt.GraphView(graph, vfilt= lambda v : v.out_degree() == 1)
            #edge_of_VEV = next(V_e_V.edges()) # ONLY ONE EDGE
            #weight = graph.ep.weight[edge_of_VEV]
            #graph.remove_edge(edge_of_VEV)
            return prune_VeV(graph)