gpp -- model for the graph partitioning problem
    Parameters:
        - V: set/list of nodes in the graph
        - E: set/list of edges in the graph
    Returns a model, ready to be solved.
764672
def gpp(V,E):
    
    model = Model("gpp")

    x = {}
    y = {}
    for i in V:
        x[i] = model.addVar(vtype="B", name="x(%s)"%i)
    for (i,j) in E:
        y[i,j] = model.addVar(vtype="B", name="y(%s,%s)"%(i,j))

    model.addCons(quicksum(x[i] for i in V) == len(V)/2, "Partition")

    for (i,j) in E:
        model.addCons(x[i] - x[j] <= y[i,j], "Edge(%s,%s)"%(i,j))
        model.addCons(x[j] - x[i] <= y[i,j], "Edge(%s,%s)"%(j,i))

    model.setObjective(quicksum(y[i,j] for (i,j) in E), "minimize")

    model.data = x
    return model
1131363
public static <K, VV, EV> Graph<K, VV, EV> fromCollection(Collection<Vertex<K, VV>> vertices,
			Collection<Edge<K, EV>> edges, ExecutionEnvironment context) {

		return fromDataSet(context.fromCollection(vertices),
				context.fromCollection(edges), context);
	}
531245
def build_groups_depgraph
        dp = ::GRATR::Digraph.new

        # Add each group to the graph
        @groups.each_value do |group|
          dp.add_vertex! group

          # Select group names from the users
          subgroups = group.users.select {|u| u =~ /^#{Group::PREPEND_CHAR}.*$/}.map{|g| get_group g.gsub(Group::PREPEND_CHAR, '') }

          subgroups.each do |subgroup|
            dp.add_edge! subgroup, group
          end
        end

        # Figure out if we have a good depedency graph
        dep_order = dp.topsort

        if dep_order.empty?
          raise GroupDependencyError unless @groups.empty?
        end

        dep_order
      end
299671
private void compute() {

        int n = graph.length;

        // the set 'S' contains the pairs of vertices adjacent to 'y'
        int[] s = new int[n];
        int sizeOfS;

        // order the vertices by degree
        int[] vertices = new int[n];
        for (int v = 0; v < n; v++) {
            vertices[ordering[v]] = v;
        }

        // if the graph is known to be a biconnected component (prepossessing)
        // and there is at least one vertex with a degree > 2 we can skip all
        // vertices of degree 2.
        //
        // otherwise the smallest possible cycle is {0,1,2} (no parallel edges
        // or loops) we can therefore don't need to do the first two shortest
        // paths calculations
        int first = biconnected && nDeg2Vertices < n ? nDeg2Vertices : 2;

        for (int i = first; i < n; i++) {
            final int r = vertices[i];

            ShortestPaths pathsFromR = new ShortestPaths(graph, null, r, limit / 2, ordering);

            // we only check the vertices which belong to the set Vr. this
            // set is vertices reachable from 'r' by only travelling though
            // vertices smaller then r. In the ShortestPaths API this is
            // name 'isPrecedingPathTo'.
            //
            // using Vr allows us to prune the number of vertices to check and
            // discover each cycle exactly once. This is possible as for each
            // simple cycle there is only one vertex with a maximum ordering.
            for (int j = 0; j < i; j++) {
                final int y = vertices[j];
                if (!pathsFromR.isPrecedingPathTo(y)) continue;

                // start refilling set 's' by resetting it's size
                sizeOfS = 0;

                // z is adjacent to y and belong to Vr
                for (final int z : graph[y]) {
                    if (!pathsFromR.isPrecedingPathTo(z)) continue;

                    final int distToZ = pathsFromR.distanceTo(z);
                    final int distToY = pathsFromR.distanceTo(y);

                    // the distance of the path to z is one less then the
                    // path to y. the vertices are adjacent, therefore z must
                    // also belong to the shortest path from r to y.
                    //
                    // we queue up (in 's') all the vertices adjacent to y for
                    // which this holds and then check these once we've processed
                    // all adjacent vertices
                    //
                    //  / ¯ ¯ z1 \          z1 and z2 are added to 's' and
                    // r          y - z3    checked later as p and q (see below)
                    //  \ _ _ z2 /
                    //
                    if (distToZ + 1 == distToY) {
                        s[sizeOfS++] = z;
                    }

                    // if the distances are equal we could have an odd cycle
                    // but we need to check the paths only intersect at 'r'.
                    //
                    // we check the intersect for cases like this, shortest
                    // cycle here is {p .. y, z .. p} not {r .. y, z .. r}
                    //
                    //           / ¯ ¯ y         / ¯ ¯ \ / ¯ ¯ y
                    //  r - - - p      |    or  r       p      |
                    //           \ _ _ z         \ _ _ / \ _ _ z
                    //
                    // if it's the shortest cycle then the intersect is just {r}
                    //
                    //  / ¯ ¯ y
                    // r      |
                    //  \ _ _ z
                    //
                    else if (distToZ == distToY && ordering[z] < ordering[y]) {
                        final int[] pathToY = pathsFromR.pathTo(y);
                        final int[] pathToZ = pathsFromR.pathTo(z);
                        if (singletonIntersect(pathToZ, pathToY)) {
                            Cycle cycle = new OddCycle(pathsFromR, pathToY, pathToZ);
                            add(cycle);
                        }
                    }
                }

                // check each pair vertices adjacent to 'y' for an
                // even cycle, as with the odd cycle we ensure the intersect
                // of the paths {r .. p} and {r .. q} is {r}.
                //
                //  / ¯ ¯ p \
                // r         y
                //  \ _ _ q /
                //
                for (int k = 0; k < sizeOfS; k++) {
                    for (int l = k + 1; l < sizeOfS; l++) {
                        int[] pathToP = pathsFromR.pathTo(s[k]);
                        int[] pathToQ = pathsFromR.pathTo(s[l]);
                        if (singletonIntersect(pathToP, pathToQ)) {
                            Cycle cycle = new EvenCycle(pathsFromR, pathToP, y, pathToQ);
                            add(cycle);
                        }
                    }
                }
            }
        }
    }
450472
function GraphNode() {
        this.position = new Float32Array(2);

        this.force = vec2.create();
        this.forcePrev = vec2.create();

        // If repulsionByDegree is true
        //  mass = inDegree + outDegree + 1
        // Else
        //  mass is manually set
        this.mass = 1;

        this.inDegree = 0;
        this.outDegree = 0;

        // Optional
        // this.size = 1;
    }
1009588
private void dfs(int v, int[] cc, int id) {
        cc[v] = id;
        for (int t = 0; t < n; t++) {
            if (graph[v][t] != 0.0) {
                if (cc[t] == -1) {
                    dfs(t, cc, id);
                }
            }
        }
    }
1121226
def get_c2ps(self):
        """"""
        c2ps = defaultdict(set)
        for goid_child, goid_parent in self.edges:
            c2ps[goid_child].add(goid_parent)
        return c2ps
741168
public <E extends Edge> double[] compute(Graph<E> g) {
        // Perform a quick test for whether the vertices of g are a contiguous
        // sequence starting at 0, which makes the vertex mapping trivial
        if (!hasContiguousVertices(g))
            throw new IllegalArgumentException(
                "Vertices must be in continugous order");
        
        double[] centralities = new double[g.order()];
        IntIterator vertexIter = g.vertices().iterator();
        while (vertexIter.hasNext()) {
            int s = vertexIter.nextInt();
            Deque<Integer> S = new ArrayDeque<Integer>();

            // Initialize P to an empty list for each vertex
            List<List<Integer>> P = new ArrayList<List<Integer>>(g.order());
            for (int i = 0; i < g.order(); ++i)
                P.add(new ArrayList<Integer>());

            double[] sigma = new double[g.order()];
            sigma[s] = 1;

            double[] d = new double[g.order()];
            Arrays.fill(d, -1);
            d[s] = 0;
            
            Queue<Integer> Q = new ArrayDeque<Integer>();
            Q.add(s);
            while (!Q.isEmpty()) {
                int v = Q.poll();
                S.offer(v);
                IntIterator neighborIter = g.getNeighbors(v).iterator();
                while (neighborIter.hasNext()) { 
                    int w = neighborIter.nextInt();
                    // Check whether this is the first time we've seen vertex w
                    if (d[w] < 0) {
                        Q.offer(w);
                        d[w] = d[v] + 1;
                    }
                    // Check whether the shortest path to w is through v
                    if (d[w] == d[v] + 1) {
                        sigma[w] += sigma[v];
                        P.get(w).add(v);
                    }
                }
            }
            double[] delta = new double[g.order()];
            // S as a stack returns vertices in order of their non-increasing
            // distance from vertex s
            while (!S.isEmpty()) {
                int w = S.pollLast(); // get the top of the stack
                for (int v : P.get(w)) {
                    delta[v] += (sigma[v] / sigma[w]) * (1 + delta[w]);
                }
                if (w != s) {
                    centralities[w] += delta[w];
                }            
            }
        }
        return centralities;
    }
994365
function graph(g) {
    init(g);

    var xs = [upperLeft(g), upperRight(g), lowerRight(g), lowerLeft(g)];

    g.nodes().forEach(function(u) {
      var xArray = [];
      for (var i = 0; i < xs.length; ++i) {
        xArray.push(xs[i][u]);
      }
      xArray.sort();
      g.node(u).x = (xArray[1] + xArray[2]) / 2;
    });
  }
1274955
def partition(args):
    
    allowed_format = ("png", "ps")
    p = OptionParser(partition.__doc__)
    p.add_option("--prefix", help="Add prefix to the name [default: %default]")
    p.add_option("--namestart", default=0, type="int",
                 help="Use a shorter name, starting index [default: %default]")
    p.add_option("--format", default="png", choices=allowed_format,
            help="Generate image of format [default: %default]")
    opts, args = p.parse_args(args)

    if len(args) != 2:
        sys.exit(not p.print_help())

    happyfile, graphfile = args
    bg = BiGraph()
    bg.read(graphfile, color="red")
    prefix = opts.prefix
    fp = open(happyfile)
    for i, row in enumerate(fp):
        nns = happy_nodes(row, prefix=prefix)
        nodes = set(nns)
        edges = happy_edges(row, prefix=prefix)

        small_graph = BiGraph()
        for (a, b, oa, ob), is_uncertain in edges:
            color = "gray" if is_uncertain else "black"
            small_graph.add_edge(a, b, oa, ob, color=color)

        for (u, v), e in bg.edges.items():
            # Grab edge if both vertices are on the same line
            if u in nodes and v in nodes:
                uv = (str(u), str(v))
                if uv in small_graph.edges:
                    e = small_graph.edges[uv]
                    e.color = "blue"  # supported by both evidences
                else:
                    small_graph.add_edge(e)

        print(small_graph, file=sys.stderr)

        pngfile = "A{0:02d}.{1}".format(i + 1, opts.format)
        telomeres = (nns[0], nns[-1])
        small_graph.draw(pngfile, namestart=opts.namestart,
                         nodehighlight=telomeres, dpi=72)

    legend = ["Edge colors:"]
    legend.append("[BLUE] Experimental + Synteny")
    legend.append("[BLACK] Experimental certain")
    legend.append("[GRAY] Experimental uncertain")
    legend.append("[RED] Synteny only")
    legend.append("Rectangle nodes are telomeres.")
    print("\n".join(legend), file=sys.stderr)
422294
def equiv_graph(self):
        
        eg = nx.Graph()
        for (u,v,d) in self.get_graph().edges(data=True):
            if d['pred'] == 'equivalentTo':
                eg.add_edge(u,v)
        return eg
472658
def get_minimal_subgraph(g, nodes):
    
    logging.info("Slimming {} to {}".format(g,nodes))
    # maps ancestor nodes to members of the focus node set they subsume
    mm = {}
    subnodes = set()
    for n in nodes:
        subnodes.add(n)
        ancs = nx.ancestors(g, n)
        ancs.add(n)
        for a in ancs:
            subnodes.add(a)
            if a not in mm:
                mm[a] = set()
            mm[a].add(n)

    # merge graph
    egraph = nx.MultiDiGraph()

    # TODO: ensure edge labels are preserved
    for a, aset in mm.items():
        for p in g.predecessors(a):
            logging.info(" cmp {} -> {} // {} {}".format(len(aset),len(mm[p]), a, p))
            if p in mm and len(aset) == len(mm[p]):
                egraph.add_edge(p, a)
                egraph.add_edge(a, p)
                logging.info("will merge {} <-> {} (members identical)".format(p,a))

    nmap = {}
    leafmap = {}
    disposable = set()
    for cliq in nx.strongly_connected_components(egraph):
        leaders = set()
        leafs = set()
        for n in cliq:
            is_src = False
            if n in nodes:
                logging.info("Preserving: {} in {}".format(n,cliq))
                leaders.add(n)
                is_src = True
                
            is_leaf = True
            for p in g.successors(n):
                if p in cliq:
                    is_leaf = False

            if not(is_leaf or is_src):
                disposable.add(n)
                
            if is_leaf:
                logging.info("Clique leaf: {} in {}".format(n,cliq))
                leafs.add(n)

                
        leader = None
        if len(leaders) > 1:
            logging.info("UHOH: {}".format(leaders))
        if len(leaders) > 0:
            leader = list(leaders)[0]
        else:
            leader = list(leafs)[0]
        leafmap[n] = leafs

    subg = g.subgraph(subnodes)
    fg = remove_nodes(subg, disposable)
    return fg
320971
def kruskal_mst(graph):
    
    edges_accepted = 0
    ds = DisjointSet()
    pq = PriorityQueue()
    accepted_edges = []
    label_lookup = {}

    nodes = graph.get_all_node_ids()
    num_vertices = len(nodes)
    for n in nodes:
        label = ds.add_set()
        label_lookup[n] = label

    edges = graph.get_all_edge_objects()
    for e in edges:
        pq.put(e['id'], e['cost'])

    while edges_accepted < (num_vertices - 1):
        edge_id = pq.get()

        edge = graph.get_edge(edge_id)
        node_a, node_b = edge['vertices']
        label_a = label_lookup[node_a]
        label_b = label_lookup[node_b]

        a_set = ds.find(label_a)
        b_set = ds.find(label_b)

        if a_set != b_set:
            edges_accepted += 1
            accepted_edges.append(edge_id)
            ds.union(a_set, b_set)

    return accepted_edges
89930
def ssp(V,E):
    
    model = Model("ssp")

    x = {}
    for i in V:
        x[i] = model.addVar(vtype="B", name="x(%s)"%i)

    for (i,j) in E:
        model.addCons(x[i] + x[j] <= 1, "Edge(%s,%s)"%(i,j))

    model.setObjective(quicksum(x[i] for i in V), "maximize")

    model.data = x
    return model
1266598
def _create_complete_graph(node_ids):
    
    g = nx.Graph()
    g.add_nodes_from(node_ids)
    for (i, j) in combinations(node_ids, 2):
        g.add_edge(i, j)
    return g
1145028
function betweennes(graph, oriented) {
  var Q = [],
    S = []; // Queue and Stack
  // list of predecessors on shortest paths from source
  var pred = Object.create(null);
  // distance from source
  var dist = Object.create(null);
  // number of shortest paths from source to key
  var sigma = Object.create(null);
  // dependency of source on key
  var delta = Object.create(null);

  var currentNode;
  var centrality = Object.create(null);

  graph.forEachNode(setCentralityToZero);
  graph.forEachNode(calculateCentrality);

  if (!oriented) {
    // The centrality scores need to be divided by two if the graph is not oriented,
    // since all shortest paths are considered twice
    Object.keys(centrality).forEach(divideByTwo);
  }

  return centrality;

  function divideByTwo(key) {
    centrality[key] /= 2;
  }

  function setCentralityToZero(node) {
    centrality[node.id] = 0;
  }

  function calculateCentrality(node) {
    currentNode = node.id;
    singleSourceShortestPath(currentNode);
    accumulate();
  }

  function accumulate() {
    graph.forEachNode(setDeltaToZero);
    while (S.length) {
      var w = S.pop();
      var coeff = (1 + delta[w])/sigma[w];
      var predecessors = pred[w];
      for (var idx = 0; idx < predecessors.length; ++idx) {
        var v = predecessors[idx];
        delta[v] += sigma[v] * coeff;
      }
      if (w !== currentNode) {
        centrality[w] += delta[w];
      }
    }
  }

  function setDeltaToZero(node) {
    delta[node.id] = 0;
  }

  function singleSourceShortestPath(source) {
    graph.forEachNode(initNode);
    dist[source] = 0;
    sigma[source] = 1;
    Q.push(source);

    while (Q.length) {
      var v = Q.shift();
      S.push(v);
      graph.forEachLinkedNode(v, toId, oriented);
    }

    function toId(otherNode) {
      // NOTE: This code will also consider multi-edges, which are often
      // ignored by popular software (Gephi/NetworkX). Depending on your use
      // case this may not be desired and deduping needs to be performed. To
      // save memory I'm not deduping here...
      processNode(otherNode.id);
    }

    function initNode(node) {
      var nodeId = node.id;
      pred[nodeId] = []; // empty list
      dist[nodeId] = -1;
      sigma[nodeId] = 0;
    }

    function processNode(w) {
      // path discovery
      if (dist[w] === -1) {
        // Node w is found for the first time
        dist[w] = dist[v] + 1;
        Q.push(w);
      }
      // path counting
      if (dist[w] === dist[v] + 1) {
        // edge (v, w) on a shortest path
        sigma[w] += sigma[v];
        pred[w].push(v);
      }
    }
  }
}
417031
def gcp(V,E,K):
    
    model = Model("gcp")
    x,y = {},{}
    for k in range(K):
        y[k] = model.addVar(vtype="B", name="y(%s)"%k)
        for i in V:
            x[i,k] = model.addVar(vtype="B", name="x(%s,%s)"%(i,k))

    for i in V:
        model.addCons(quicksum(x[i,k] for k in range(K)) == 1, "AssignColor(%s)"%i)

    for (i,j) in E:
        for k in range(K):
            model.addCons(x[i,k] + x[j,k] <= y[k], "NotSameColor(%s,%s,%s)"%(i,j,k))

    model.setObjective(quicksum(y[k] for k in range(K)), "minimize")

    model.data = x
    return model