Apply transitive reduction on the resulting graph
550332
public Graph<Module> reduced() {
        Graph<Module> graph = build();
        // transitive reduction
        Graph<Module> newGraph = buildGraph(graph.edges()).reduce();

        if (DEBUG) {
            PrintWriter log = new PrintWriter(System.err);
            System.err.println("before transitive reduction: ");
            graph.printGraph(log);
            System.err.println("after transitive reduction: ");
            newGraph.printGraph(log);
        }

        return newGraph;
    }
453904
def get_subgraphs(graph=None):
    
    graph = graph or DEPENDENCIES
    keys = set(graph)
    frontier = set()
    seen = set()
    while keys:
        frontier.add(keys.pop())
        while frontier:
            component = frontier.pop()
            seen.add(component)
            frontier |= set([d for d in get_dependencies(component) if d in graph])
            frontier |= set([d for d in get_dependents(component) if d in graph])
            frontier -= seen
        yield dict((s, get_dependencies(s)) for s in seen)
        keys -= seen
        seen.clear()
555230
def apply(funcs, stack):
  ''''''
  return reduce(lambda x, y: y(x), funcs, stack)
1116209
def scc(graph):
    '''  '''
    order = []
    vis = {vertex: False for vertex in graph}

    graph_transposed = {vertex: [] for vertex in graph}

    for (v, neighbours) in graph.iteritems():
        for u in neighbours:
            add_edge(graph_transposed, u, v)

    for v in graph:
        if not vis[v]:
            dfs_transposed(v, graph_transposed, order, vis)

    vis = {vertex: False for vertex in graph}
    vertex_scc = {}

    current_comp = 0
    for v in reversed(order):
        if not vis[v]:
            # Each dfs will visit exactly one component
            dfs(v, current_comp, vertex_scc, graph, vis)
            current_comp += 1

    return vertex_scc
506877
def node_to_edge(edges, directed=True):
    
    outgoing = defaultdict(set)
    incoming = defaultdict(set) if directed else outgoing
    nodes = set()
    for i, edge in enumerate(edges):
        a, b, = edge[:2]
        outgoing[a].add(i)
        incoming[b].add(i)
        nodes.add(a)
        nodes.add(b)
    nodes = sorted(nodes)
    if directed:
        return outgoing, incoming, nodes
    return outgoing, nodes
1248003
def _subset_graph(graph, include_nodes):
    
    new_graph = nx.algorithms.transitive_closure(graph)

    include_nodes = set(include_nodes)

    for node in graph.nodes():
        if node not in include_nodes:
            new_graph.remove_node(node)

    for node in include_nodes:
        if node not in new_graph:
            raise RuntimeError(
                "Couldn't find model '{}' -- does it exist or is "
                "it disabled?".format(node)
            )
    return new_graph
123126
def _to_edges(self, tokens):
        """"""
        # prepend self.order Nones
        chain = self._end_context + tokens + self._end_context

        has_space = False

        context = []

        for i in xrange(len(chain)):
            context.append(chain[i])

            if len(context) == self.order:
                if chain[i] == self.SPACE_TOKEN_ID:
                    context.pop()
                    has_space = True
                    continue

                yield tuple(context), has_space

                context.pop(0)
                has_space = False
816114
def convert_graph_directed_to_undirected(dg):
    """"""

    udg = UndirectedGraph()

    # Copy the graph
    # --Copy nodes
    # --Copy edges
    udg.nodes = copy.deepcopy(dg.nodes)
    udg.edges = copy.deepcopy(dg.edges)
    udg.next_node_id = dg.next_node_id
    udg.next_edge_id = dg.next_edge_id

    # Convert the directed edges into undirected edges
    for edge_id in udg.get_all_edge_ids():
        edge = udg.get_edge(edge_id)
        target_node_id = edge['vertices'][1]
        target_node = udg.get_node(target_node_id)
        target_node['edges'].append(edge_id)

    return udg
274033
static void reduceTransitive(Collection<GroupTransition> transitive)
    {
        final Collection<GroupTransition> localChecked = new ArrayList<>(transitive.size());
        final Collection<GroupTransition> toRemove = new ArrayList<>();

        final Iterator<GroupTransition> iterator = transitive.iterator();
        GroupTransition first = iterator.next();
        while (iterator.hasNext())
        {
            final GroupTransition current = iterator.next();
            localChecked.add(current);
            if (current.getOut().equals(first.getOut()))
            {
                toRemove.addAll(localChecked);

                localChecked.clear();

                if (iterator.hasNext())
                {
                    first = iterator.next();
                }
            }
        }
        transitive.removeAll(toRemove);
        toRemove.clear();
    }
34240
def _to_graph(self, contexts):
        """"""
        prev = None

        for context in contexts:
            if prev is None:
                prev = context
                continue

            yield prev[0], context[1], context[0]
            prev = context
823928
def from_edge_pairs(pairs, num_vertices=None, symmetric=False, weights=None):
  '''
  '''
  if not symmetric:
    if weights is None:
      return EdgePairGraph(pairs, num_vertices=num_vertices)
    row, col = np.asarray(pairs).T
    row, weights = np.broadcast_arrays(row, weights)
    shape = None if num_vertices is None else (num_vertices, num_vertices)
    adj = ss.coo_matrix((weights, (row, col)), shape=shape)
    return SparseAdjacencyMatrixGraph(adj)
  # symmetric case
  G = SymmEdgePairGraph(pairs, num_vertices=num_vertices)
  if weights is None:
    return G
  # Convert to sparse adj graph with provided edge weights
  s = G.matrix('coo').astype(float)
  # shenanigans to assign edge weights in the right order
  flat_idx = np.ravel_multi_index(s.nonzero(), s.shape)
  r, c = np.transpose(pairs)
  rc_idx = np.ravel_multi_index((r,c), s.shape)
  cr_idx = np.ravel_multi_index((c,r), s.shape)
  order = np.argsort(flat_idx)
  flat_idx = flat_idx[order]
  s.data[order[np.searchsorted(flat_idx, rc_idx)]] = weights
  s.data[order[np.searchsorted(flat_idx, cr_idx)]] = weights
  return SparseAdjacencyMatrixGraph(s)
17136
def graph_from_adjacency_matrix(matrix, node_prefix='', directed=False):
    

    node_orig = 1

    if directed:
        graph = Dot(graph_type='digraph')
    else:
        graph = Dot(graph_type='graph')

    for row in matrix:
        if not directed:
            skip = matrix.index(row)
            r = row[skip:]
        else:
            skip = 0
            r = row
        node_dest = skip + 1

        for e in r:
            if e:
                graph.add_edge(
                    Edge(
                        node_prefix + node_orig,
                        node_prefix + node_dest))
            node_dest += 1
        node_orig += 1

    return graph
636719
def graph_from_edges(edges: Iterable[Edge], **kwargs) -> BELGraph:
    """"""
    graph = BELGraph(**kwargs)

    for edge in edges:
        edge.insert_into_graph(graph)

    return graph
89385
def _dinic_step(graph, capacity, lev, flow, u, target, limit):
    
    if limit <= 0:
        return 0
    if u == target:
        return limit
    val = 0
    for v in graph[u]:
        residual = capacity[u][v] - flow[u][v]
        if lev[v] == lev[u] + 1 and residual > 0:
            z = min(limit, residual)
            aug = _dinic_step(graph, capacity, lev, flow, v, target, z)
            flow[u][v] += aug
            flow[v][u] -= aug
            val += aug
            limit -= aug
    if val == 0:
        lev[u] = None         # remove unreachable node
    return val
899060
def decompose_graph(g, heuristic='tour', max_odds=20, verbose=0):
    ''''''
    # Get the connected subgraphs
    subgraphs = [nx.subgraph(g, x).copy() for x in nx.connected_components(g)]

    chains = []
    num_subgraphs = len(subgraphs)
    step = 0
    while num_subgraphs > 0:
        if verbose:
            print('Step #{0} ({1} subgraphs)'.format(step, num_subgraphs))

        for i in range(num_subgraphs-1, -1, -1):
            subg = subgraphs[i]

            # Get all odd-degree nodes
            odds = [x for x,y in dict(nx.degree(subg)).items() if y % 2 == 1]

            if verbose > 1:
                if len(odds) == 0:
                    print('\t\tNo odds')
                elif len(odds) == 2:
                    print('\t\tExactly 2 odds')
                else:
                    print('\t\t{0} odds'.format(len(odds)))
            
            # If there are no odd-degree edges, we can find an euler circuit
            if len(odds) == 0:
                trails = [list(nx.eulerian_circuit(subg))]
            elif len(odds) == 2:
                # If there are only two odd-degree edges, we can find an euler tour
                trails = [calc_euler_tour(subg, odds[0], odds[1])]
            elif heuristic in ['min', 'max', 'median', 'any']:
                trails = select_odd_degree_trail(subg, odds, max_odds, heuristic, verbose)
            elif heuristic == 'random':
                trails = select_random_trail(subg, verbose)
            elif heuristic == 'mindegree':
                trails = select_min_degree_trail(subg, max_odds, verbose)
            elif heuristic == 'ones':
                trails = select_single_edge_trails(subg, verbose)
            elif heuristic == 'tour':
                trails = pseudo_tour_trails(subg, odds, verbose)
            elif heuristic == 'greedy':
                trails = greedy_trails(subg, odds, verbose)

            if verbose > 2:
                print('\t\tTrails: {0}'.format(len(trails)))

            # Remove the trail
            for trail in trails:
                subg.remove_edges_from(trail)

            # Add it to the list of chains
            chains.extend(trails)
            
            # If the subgraph is empty, remove it from the list
            if subg.number_of_edges() == 0:
                del subgraphs[i]
            else:
                comps = list(nx.connected_components(subg))

                # If the last edge split the graph, add the new subgraphs to the list of subgraphs
                if len(comps) > 1:
                    for x in comps:
                        compg = nx.subgraph(subg, x)
                        if compg.number_of_edges() > 0:
                            subgraphs.append(compg)
                    del subgraphs[i]

        # Update the count of connected subgraphs
        num_subgraphs = len(subgraphs)
        step += 1

    return chains
18056
def _rm_gos_edges(rm_goids, edges_all):
        """"""
        edges_reduced = []
        for goid_child, goid_parent in sorted(edges_all, key=lambda t: t[1]):
            if goid_child not in rm_goids and goid_parent not in rm_goids:
                edges_reduced.append((goid_child, goid_parent))
        return edges_reduced
1071560
def tsp_gurobi(edges):
    
    from gurobipy import Model, GRB, quicksum

    edges = populate_edge_weights(edges)
    incoming, outgoing, nodes = node_to_edge(edges)
    idx = dict((n, i) for i, n in enumerate(nodes))
    nedges = len(edges)
    n = len(nodes)

    m = Model()

    def step(x): return "u_{0}".format(x)
    # Create variables
    vars = {}
    for i, (a, b, w) in enumerate(edges):
        vars[i] = m.addVar(obj=w, vtype=GRB.BINARY, name=str(i))
    for u in nodes[1:]:
        u = step(u)
        vars[u] = m.addVar(obj=0, vtype=GRB.INTEGER, name=u)
    m.update()

    # Bounds for step variables
    for u in nodes[1:]:
        u = step(u)
        vars[u].lb = 1
        vars[u].ub = n - 1

    # Add degree constraint
    for v in nodes:
        incoming_edges = incoming[v]
        outgoing_edges = outgoing[v]
        m.addConstr(quicksum(vars[x] for x in incoming_edges) == 1)
        m.addConstr(quicksum(vars[x] for x in outgoing_edges) == 1)

    # Subtour elimination
    edge_store = dict(((idx[a], idx[b]), i)
                      for i, (a, b, w) in enumerate(edges))

    # Given a list of edges, finds the shortest subtour
    def subtour(s_edges):
        visited = [False] * n
        cycles = []
        lengths = []
        selected = [[] for i in range(n)]
        for x, y in s_edges:
            selected[x].append(y)
        while True:
            current = visited.index(False)
            thiscycle = [current]
            while True:
                visited[current] = True
                neighbors = [x for x in selected[current] if not visited[x]]
                if len(neighbors) == 0:
                    break
                current = neighbors[0]
                thiscycle.append(current)
            cycles.append(thiscycle)
            lengths.append(len(thiscycle))
            if sum(lengths) == n:
                break
        return cycles[lengths.index(min(lengths))]

    def subtourelim(model, where):
        if where != GRB.callback.MIPSOL:
            return
        selected = []
        # make a list of edges selected in the solution
        sol = model.cbGetSolution([model._vars[i] for i in range(nedges)])
        selected = [edges[i] for i, x in enumerate(sol) if x > .5]
        selected = [(idx[a], idx[b]) for a, b, w in selected]
        # find the shortest cycle in the selected edge list
        tour = subtour(selected)
        if len(tour) == n:
            return
        # add a subtour elimination constraint
        c = tour
        incident = [edge_store[a, b] for a, b in pairwise(c + [c[0]])]
        model.cbLazy(quicksum(model._vars[x]
                              for x in incident) <= len(tour) - 1)

    m.update()

    m._vars = vars
    m.params.LazyConstraints = 1
    m.optimize(subtourelim)

    selected = [v.varName for v in m.getVars() if v.x > .5]
    selected = [int(x) for x in selected if x[:2] != "u_"]
    results = sorted(x for i, x in enumerate(edges) if i in selected) \
        if selected else None
    return results