Ortholog node and edge iterator
489321
def orthologs_iterator(fo, version):
    """"""

    species_list = config["bel_resources"].get("species_list", [])

    fo.seek(0)
    with gzip.open(fo, "rt") as f:
        for line in f:
            edge = json.loads(line)
            if "metadata" in edge:
                source = edge["metadata"]["source"]
                continue

            if "ortholog" in edge:
                edge = edge["ortholog"]
                subj_tax_id = edge["subject"]["tax_id"]
                obj_tax_id = edge["object"]["tax_id"]

                # Skip if species not listed in species_list
                if species_list and subj_tax_id and subj_tax_id not in species_list:
                    continue
                if species_list and obj_tax_id and obj_tax_id not in species_list:
                    continue

                # Converted to ArangoDB legal chars for _key
                subj_key = arangodb.arango_id_to_key(edge["subject"]["id"])
                subj_id = edge["subject"]["id"]

                # Converted to ArangoDB legal chars for _key
                obj_key = arangodb.arango_id_to_key(edge["object"]["id"])
                obj_id = edge["object"]["id"]

                # Subject node
                yield (
                    arangodb.ortholog_nodes_name,
                    {
                        "_key": subj_key,
                        "name": subj_id,
                        "tax_id": edge["subject"]["tax_id"],
                        "source": source,
                        "version": version,
                    },
                )
                # Object node
                yield (
                    arangodb.ortholog_nodes_name,
                    {
                        "_key": obj_key,
                        "name": obj_id,
                        "tax_id": edge["object"]["tax_id"],
                        "source": source,
                        "version": version,
                    },
                )

                arango_edge = {
                    "_from": f"{arangodb.ortholog_nodes_name}/{subj_key}",
                    "_to": f"{arangodb.ortholog_nodes_name}/{obj_key}",
                    "_key": bel.utils._create_hash(f"{subj_id}>>{obj_id}"),
                    "type": "ortholog_to",
                    "source": source,
                    "version": version,
                }

                yield (arangodb.ortholog_edges_name, arango_edge)
1261728
def inc_edges(self, node):
        
        try:
            return list(self.nodes[node][0])
        except KeyError:
            raise GraphError('Invalid node %s' % node)

        return None
982308
def _identifier_filtered_iterator(graph):
    """"""
    for data in graph:
        for pair in _get_node_names(data):
            yield pair

        for member in data.get(MEMBERS, []):
            for pair in _get_node_names(member):
                yield pair

    for ((_, _, data), side) in itt.product(graph.edges(data=True), (SUBJECT, OBJECT)):
        side_data = data.get(side)
        if side_data is None:
            continue

        modifier = side_data.get(MODIFIER)
        effect = side_data.get(EFFECT)

        if modifier == ACTIVITY and effect is not None and NAMESPACE in effect and NAME in effect:
            yield effect[NAMESPACE], effect[NAME]

        elif modifier == TRANSLOCATION and effect is not None:
            from_loc = effect.get(FROM_LOC)
            if NAMESPACE in from_loc and NAME in from_loc:
                yield from_loc[NAMESPACE], from_loc[NAME]

            to_loc = effect.get(TO_LOC)
            if NAMESPACE in to_loc and NAME in to_loc:
                yield to_loc[NAMESPACE], to_loc[NAME]

        location = side_data.get(LOCATION)
        if location is not None and NAMESPACE in location and NAME in location:
            yield location[NAMESPACE], location[NAME]
13580
def _get_edgesobj(gosubdag, **kws):
    """"""
    # Keyword args (kws):
    #     1. dst_srcs_list  Used for edges pruned such that only GO terms
    #                       are retained which are between the sets of dst & srcs.
    #     2  traverse_parent & traverse_child
    #                       Used to generate a GoSubDag with all parent terms and/or
    #                       all child terms, without pruning any paths.
    # Call function, get_edgesobj, with:
    #     get_edgesobj(go2obj, dst_srcs_list=...)
    # Or any of:
    #     get_edgesobj(go2obj, go_sources=...)
    #     get_edgesobj(go2obj, go_sources=..., traverse_parent=...,)
    #     get_edgesobj(go2obj, go_sources=..., traverse_child=...,)
    #     get_edgesobj(go2obj, go_sources=..., traverse_parent=..., traverse_child=...,)
    dst_srcs_list = kws.get('dst_srcs_list', None)
    if dst_srcs_list is not None:
        return EdgesPath(gosubdag, dst_srcs_list)
    return EdgesRelatives(gosubdag,
                          kws.get('traverse_parent', True),
                          kws.get('traverse_child', False))
1150367
function nodes(){
    var nodeSet = {};
    Object.keys(edges).forEach(function (u){
      nodeSet[u] = true;
      edges[u].forEach(function (v){
        nodeSet[v] = true;
      });
    });
    return Object.keys(nodeSet);
  }
112604
private static void computeTreeGraph(SharedTreeSubgraph sg, SharedTreeNode node, byte[] tree, ByteBufferWrapper ab, HashMap<Integer, AuxInfo> auxMap,
                                         String names[], String[][] domains) {
        int nodeType = ab.get1U();
        int colId = ab.get2();
        if (colId == 65535) {
            float leafValue = ab.get4f();
            node.setPredValue(leafValue);
            return;
        }
        String colName = names[colId];
        node.setCol(colId, colName);

        int naSplitDir = ab.get1U();
        boolean naVsRest = naSplitDir == NsdNaVsRest;
        boolean leftward = naSplitDir == NsdNaLeft || naSplitDir == NsdLeft;
        node.setLeftward(leftward);
        node.setNaVsRest(naVsRest);

        int lmask = (nodeType & 51);
        int equal = (nodeType & 12);  // Can be one of 0, 8, 12
        assert equal != 4;  // no longer supported

        if (!naVsRest) {
            // Extract value or group to split on
            if (equal == 0) {
                // Standard float-compare test (either < or ==)
                float splitVal = ab.get4f();  // Get the float to compare
                node.setSplitValue(splitVal);
            } else {
                // Bitset test
                GenmodelBitSet bs = new GenmodelBitSet(0);
                if (equal == 8)
                    bs.fill2(tree, ab);
                else
                    bs.fill3(tree, ab);
                node.setBitset(domains[colId], bs);
            }
        }

        AuxInfo auxInfo = auxMap.get(node.getNodeNumber());

        // go RIGHT
        {
            ByteBufferWrapper ab2 = new ByteBufferWrapper(tree);
            ab2.skip(ab.position());

            switch (lmask) {
                case 0:
                    ab2.skip(ab2.get1U());
                    break;
                case 1:
                    ab2.skip(ab2.get2());
                    break;
                case 2:
                    ab2.skip(ab2.get3());
                    break;
                case 3:
                    ab2.skip(ab2.get4());
                    break;
                case 48:
                    ab2.skip(4);
                    break;  // skip the prediction
                default:
                    assert false : "illegal lmask value " + lmask + " in tree " + Arrays.toString(tree);
            }
            int lmask2 = (nodeType & 0xC0) >> 2;  // Replace leftmask with the rightmask

            SharedTreeNode newNode = sg.makeRightChildNode(node);
            newNode.setWeight(auxInfo.weightR);
            newNode.setNodeNumber(auxInfo.nidR);
            newNode.setPredValue(auxInfo.predR);
            newNode.setSquaredError(auxInfo.sqErrR);
            if ((lmask2 & 16) != 0) {
                float leafValue = ab2.get4f();
                newNode.setPredValue(leafValue);
                auxInfo.predR = leafValue;
            }
            else {
                computeTreeGraph(sg, newNode, tree, ab2, auxMap, names, domains);
            }
        }

        // go LEFT
        {
            ByteBufferWrapper ab2 = new ByteBufferWrapper(tree);
            ab2.skip(ab.position());

            if (lmask <= 3)
                ab2.skip(lmask + 1);

            SharedTreeNode newNode = sg.makeLeftChildNode(node);
            newNode.setWeight(auxInfo.weightL);
            newNode.setNodeNumber(auxInfo.nidL);
            newNode.setPredValue(auxInfo.predL);
            newNode.setSquaredError(auxInfo.sqErrL);
            if ((lmask & 16) != 0) {
                float leafValue = ab2.get4f();
                newNode.setPredValue(leafValue);
                auxInfo.predL = leafValue;
            }
            else {
                computeTreeGraph(sg, newNode, tree, ab2, auxMap, names, domains);
            }
        }
        if (node.getNodeNumber() == 0) {
          float p = (float)(((double)auxInfo.predL*(double)auxInfo.weightL + (double)auxInfo.predR*(double)auxInfo.weightR)/((double)auxInfo.weightL + (double)auxInfo.weightR));
          if (Math.abs(p) < 1e-7) p = 0;
          node.setPredValue(p);
          node.setSquaredError(auxInfo.sqErrR + auxInfo.sqErrL);
          node.setWeight(auxInfo.weightL + auxInfo.weightR);
        }
        checkConsistency(auxInfo, node);
    }
884803
def fuse(args):
    
    from jcvi.algorithms.graph import BiGraph

    p = OptionParser(fuse.__doc__)
    opts, args = p.parse_args(args)

    if len(args) < 1:
        sys.exit(not p.print_help())

    bedfiles = [x for x in args if x.endswith(".bed")]
    anchorfiles = [x for x in args if x.endswith(".anchors")]

    # TODO: Use Markov clustering to sparsify the edges
    families = Grouper()
    for anchorfile in anchorfiles:
        af = AnchorFile(anchorfile)
        for a, b, block_id in af.iter_pairs():
            families.join(a, b)

    allowed = set(families.keys())
    logging.debug("Total families: {}, Gene members: {}"
                  .format(len(families), len(allowed)))

    # TODO: Use C++ implementation of BiGraph() when available
    # For now just serialize this to the disk
    G = BiGraph()
    for bedfile in bedfiles:
        bed = Bed(bedfile, include=allowed)
        #add_bed_to_graph(G, bed, families)
        print_edges(G, bed, families)
419146
private void topologicalSortVisit(V n, List<V> L, Set<V> visited, LinkedHashSet<V> sequence) throws CycleException, EX {
		//    if n has not been visited yet then
		//        mark n as visited
		if(visited.add(n)) {
			//        for each node m with an edge from n to m do
			for(Edge<V> e : (isForward ? graph.getEdgesFrom(n) : graph.getEdgesTo(n))) {
				V m = isForward ? e.getTo() : e.getFrom();
				//            visit(m)
				if(!sequence.add(m)) {
					List<V> vertices = new ArrayList<>();
					boolean found = false;
					for(V seq : sequence) {
						if(!found && seq.equals(m)) found = true;
						if(found) vertices.add(seq);
					}
					vertices.add(m);
					throw new CycleException(AoCollections.optimalUnmodifiableList(vertices));
				}
				topologicalSortVisit(m, L, visited, sequence);
				sequence.remove(m);
			}
			//        add n to L
			L.add(n);
		}
	}
128163
def dominator_tree(graph):
    
    todo = Queue()
    done = set()
    dominator = Tree(None)
    nodes = list(graph.nodes)

    while True:
        # FIGURE OUT NET ITEM TO WORK ON
        if todo:
            node = todo.pop()
        elif nodes:
            node = nodes.pop()
            if len(nodes) % 1000 == 0:
                Log.note("{{num}} nodes remaining", num=len(nodes))
        else:
            break
        if node in done:
            continue

        parents = graph.get_parents(node) - {node}
        if not parents:
            # node WITHOUT parents IS A ROOT
            done.add(node)
            dominator.add_edge(Edge(ROOTS, node))
            continue

        not_done = parents - done
        if not_done:
            # THERE ARE MORE parents TO DO FIRST
            more_todo = not_done - todo
            if not more_todo:
                # ALL PARENTS ARE PART OF A CYCLE, MAKE node A ROOT
                done.add(node)
                dominator.add_edge(Edge(LOOPS, node))
            else:
                # DO THE PARENTS BEFORE node
                todo.push(node)
                for p in more_todo:
                    todo.push(p)
            continue

        # WE CAN GET THE DOMINATORS FOR ALL parents
        if len(parents) == 1:
            # SHORTCUT
            dominator.add_edge(Edge(list(parents)[0], node))
            done.add(node)
            continue

        paths_from_roots = [
            list(reversed(dominator.get_path_to_root(p)))
            for p in parents
        ]

        if any(p[0] is ROOTS for p in paths_from_roots):
            # THIS OBJECT CAN BE REACHED FROM A ROOT, IGNORE PATHS FROM LOOPS
            paths_from_roots = [p for p in paths_from_roots if p[0] is ROOTS]
            if len(paths_from_roots) == 1:
                # SHORTCUT
                dom = paths_from_roots[0][-1]
                dominator.add_edge(Edge(dom, node))
                done.add(node)
                continue

        # FIND COMMON PATH FROM root
        num_paths = len(paths_from_roots)
        for i, x in enumerate(zip_longest(*paths_from_roots)):
            if x.count(x[0]) != num_paths:
                dom = paths_from_roots[0][i-1]
                if dom is LOOPS:
                    # CAN BE REACHED FROM MORE THAN ONE LOOP, PICK ONE TO BLAME
                    dom = paths_from_roots[0][-1]
                break
        else:
            # ALL PATHS IDENTICAL
            dom = paths_from_roots[0][-1]

        dominator.add_edge(Edge(dom, node))
        done.add(node)

    return dominator
365039
static <T, S extends Iterable<T>> String printTreeForGraphViz(SuffixTree<T, S> tree, boolean printSuffixLinks) {
        LinkedList<Node<T, S>> stack = new LinkedList<>();
        stack.add(tree.getRoot());
        Map<Node<T, S>, Integer> nodeMap = new HashMap<>();
        nodeMap.put(tree.getRoot(), 0);
        int nodeId = 1;

        StringBuilder sb = new StringBuilder(
            "\ndigraph suffixTree{\n node [shape=circle, label=\"\", fixedsize=true, width=0.1, height=0.1]\n");

        while (stack.size() > 0) {
            LinkedList<Node<T, S>> childNodes = new LinkedList<>();
            for (Node<T, S> node : stack) {

                // List<Edge> edges = node.getEdges();
                for (Edge<T, S> edge : node) {
                    int id = nodeId++;
                    if (edge.isTerminating()) {
                        childNodes.push(edge.getTerminal());
                        nodeMap.put(edge.getTerminal(), id);
                    }

                    sb.append(nodeMap.get(node)).append(" -> ").append(id)
                        .append(" [label=\"");

                    for (T item : edge) {
                        //if(item != null)
                        sb.append(item.toString());
                    }
                    sb.append("\"];\n");
                }
            }
            stack = childNodes;
        }
        if (printSuffixLinks) {
            // loop again to find all suffix links.
            sb.append("edge [color=red]\n");
            for (Map.Entry<Node<T, S>, Integer> entry : nodeMap.entrySet()) {
                Node n1 = entry.getKey();
                int id1 = entry.getValue();

                if (n1.hasSuffixLink()) {
                    Node n2 = n1.getSuffixLink();
                    Integer id2 = nodeMap.get(n2);
                    // if(id2 != null)
                    sb.append(id1).append(" -> ").append(id2).append(" ;\n");
                }
            }
        }
        sb.append("}");
        return (sb.toString());
    }
309375
public void addNodes(NodeIterator iterator)
  {

    if (!m_mutable)
      throw new RuntimeException(XSLMessages.createXPATHMessage(XPATHErrorResources.ER_NODESET_NOT_MUTABLE, null)); //"This NodeSet is not mutable!");

    if (null != iterator)  // defensive to fix a bug that Sanjiva reported.
    {
      Node obj;

      while (null != (obj = iterator.nextNode()))
      {
        addElement(obj);
      }
    }

    // checkDups();
  }
1113385
function visit(rootNodes, graph) {
    const result = {};
    const queue = rootNodes;
    rootNodes.forEach((node) => {
        result[node] = true;
    });
    while (queue.length > 0) {
        const el = queue.shift();
        const myEdges = graph[el] || [];
        myEdges.forEach((toNode) => {
            if (!result[toNode]) {
                result[toNode] = true;
                queue.push(toNode);
            }
        });
    }
    return result;
}
986968
def tree_iterator(self, visited=None, path=None):
        '''
        
        '''
        if visited is None:
            visited = set()

        if self not in visited:
            if path and isinstance(path, list):
                path.append(self)

            visited.add(self)
            yield self

            if not hasattr(self, 'dterms'):
                yield

            for dterm in self.dterms:
                if hasattr(self, dterm):
                    child = getattr(self, dterm)
                    if hasattr(child, 'dterms') or hasattr(child, 'terms'):
                        for node in child.tree_iterator(visited):
                            yield node
120477
def iter_children(graph, node: BaseEntity) -> Iterable[BaseEntity]:
    """"""
    return (
        node
        for node, _, d in graph.in_edges(node, data=True)
        if d[RELATION] == IS_A
    )
795
function createEdgeIterator(graph, type) {
  if (graph.size === 0)
    return Iterator.empty();

  let iterator;

  if (type === 'mixed') {
    iterator = graph._edges.values();

    return new Iterator(function next() {
      const step = iterator.next();

      if (step.done)
        return step;

      const data = step.value;

      const value = [
        data.key,
        data.attributes,
        data.source.key,
        data.target.key,
        data.source.attributes,
        data.target.attributes
      ];

      return {value, done: false};
    });
  }

  iterator = graph._edges.values();

  return new Iterator(function next() {
    const step = iterator.next();

    if (step.done)
      return step;

    const data = step.value;

    if ((data instanceof UndirectedEdgeData) === (type === 'undirected')) {
      const value = [
        data.key,
        data.attributes,
        data.source.key,
        data.target.key,
        data.source.attributes,
        data.target.attributes
      ];

      return {value, done: false};
    }

    return next();
  });
}
1265479
def initial_edges(self) -> iter:
        """"""
        nodes_in = lambda n: ([n] if self.is_node(n) else self.nodes_in(n))
        for node, succs in self.edges.items():
            twos = tuple(two for succ in succs for two in nodes_in(succ))
            for one in nodes_in(node):
                for two in twos:
                    yield one, two
119635
def all_edges(self, node):
        
        return set(self.inc_edges(node) + self.out_edges(node))