Return for one root of each connected component all
        the linked objects, and the mapping linking a connected component
        root with the roots that it contains.
320569
def connected_components(self) -> (dict, dict):
        """"""
        inclusions = utils.completed_graph(self.inclusions)  # allow bottom-up movement
        edges = utils.completed_graph(self.edges) if self.oriented else self.edges
        cc = {}  # maps cc root with nodes in the cc
        subroots = defaultdict(set)  # maps cc root with other roots of the cc
        walked_roots = set()  # all roots that have been walked already
        for root in self.roots:
            if root in walked_roots: continue  # this cc have been done already
            # walk in the graph starting at root
            cc[root] = set([root])
            walked = cc[root]
            stack = list(edges.get(root, ())) + list(inclusions.get(root, ()))
            while len(stack) > 0:
                *stack, curr = stack
                walked.add(curr)
                if curr in self.roots:  # don't do the walk for already found roots
                    walked_roots.add(curr)
                    subroots[root].add(curr)
                for succ in it.chain(edges.get(curr, ()), inclusions.get(curr, ())):
                    if succ not in walked:
                        stack.append(succ)
        return cc, dict(subroots)
1056542
def get_tree(cls, parent=None):
        
        if parent:
            depth = parent.get_depth() + 1
            results = [parent]
        else:
            depth = 1
            results = []
        cls._get_tree_recursively(results, parent, depth)
        return results
529117
public IntArrayList getConnectedComponentsT2() {
        boolean[] marked1 = new boolean[nodes1.size()];
        boolean[] marked2 = new boolean[nodes2.size()];
        
        IntArrayList roots = new IntArrayList();
        for (int t2=0; t2<nodes2.size(); t2++) {
            if (!marked2[t2]) {
                roots.add(t2);
                
                // Depth first search.
                dfs(t2, false, marked1, marked2, null);
            }
        }
        return roots;
    }
56254
def nested(self, format_callback=None):
        
        seen = set()
        roots = []
        for root in self.edges.get(None, ()):
            roots.extend(self._nested(root, seen, format_callback))
        return roots
902335
private static Map<String,List<Node>> getChildNodes(Node parent) {
		if (parent==null)
			return Collections.emptyMap();

		Map<String,List<Node>> children = new HashMap<String,List<Node>>();

		NodeList nodes = parent.getChildNodes();
		int nNodes = nodes.getLength();
		for (int i=0; i<nNodes; i++) {
			Node node = nodes.item(i);
			if (node.getNodeType()!=Node.ELEMENT_NODE)
				continue;

			String name = node.getNodeName();
			List<Node> namesakes = children.get(name);
			if (namesakes==null) {
				namesakes = new ArrayList<Node>();
				children.put(name, namesakes);
			}
			namesakes.add(node);
		}

		return children;
	}
468113
static List<Dependency> rootCycleAt(List<Dependency> cycle, Key<?> key) {
    for (int i = 0; i < cycle.size(); ++i) {
      if (key.equals(cycle.get(i).getSource())) {
        List<Dependency> returnValue = new ArrayList<Dependency>();
        returnValue.addAll(cycle.subList(i, cycle.size()));
        returnValue.addAll(cycle.subList(0, i));
        return returnValue;
      }
    }

    return cycle;
  }
1018052
def get_connected_components(graph):
    

    list_of_components = []
    component = []  # Not strictly necessary due to the while loop structure, but it helps the automated analysis tools

    # Store a list of all unreached vertices
    unreached = set(graph.get_all_node_ids())
    to_explore = deque()

    while len(unreached) > 0:
        # This happens when we reach the end of a connected component and still have more vertices to search through
        if len(to_explore) == 0:
            n = unreached.pop()
            unreached.add(n)
            to_explore.append(n)
            component = []
            list_of_components.append(component)

        # This is the BFS that searches for connected vertices
        while len(to_explore) > 0:
            n = to_explore.pop()
            if n in unreached:
                component.append(n)
                unreached.remove(n)
                nodes = graph.neighbors(n)
                for n in nodes:
                    if n in unreached:
                        to_explore.append(n)

    return list_of_components
147725
def root_and_children_to_graph(self,root):
     """"""
     g = Graph()
     g.add_node(root)
     edges = []
     edges += self.get_node_edges(root,"outgoing")
     for c in self.get_children(root):
           g.add_node(c)
           edges += self.get_node_edges(c,"outgoing")
     for e in edges: g.add_edge(e)
     return g
325986
def get_all_parent_edges(self):
        """"""
        all_parent_edges = set()
        for parent in self.parents:
            all_parent_edges.add((self.item_id, parent.item_id))
            all_parent_edges |= parent.get_all_parent_edges()
        return all_parent_edges
1313926
def get_roots(self):
    
    if self.__directionless:
      sys.stderr.write("ERROR: can't get roots of an undirected graph\n")
      sys.exit()
    outputids = self.__nodes.keys()
    #print outputids
    rootset  = set(outputids) -  set(self.__child_to_parent.keys())
    return [self.__nodes[x] for x in rootset]
1002296
def all(self, components_in_and=True):
        ''''''
        self.components_in_and = components_in_and
        return [obj for obj in iter(self)]
216712
def get_ancestors(self, include_self=False, depth=None):
        """"""
        if self.is_root_node():
            if not include_self:
                return self._toplevel().objects.none()
            else:
                # Filter on pk for efficiency.
                return self._toplevel().objects.filter(pk=self.pk)

        params = {"%s__child" % self._closure_parentref():self.pk}
        if depth is not None:
            params["%s__depth__lte" % self._closure_parentref()] = depth
        ancestors = self._toplevel().objects.filter(**params)
        if not include_self:
            ancestors = ancestors.exclude(pk=self.pk)
        return ancestors.order_by("%s__depth" % self._closure_parentref())
222493
private Map<String, Component> getComponents(JsonNode componentsNode) {
        Iterator<JsonNode> it = componentsNode.iterator();
        Map<String, Component> components = Maps.newHashMap();

        while(it.hasNext()){
            JsonNode componentNode = it.next();
            JsonNode pathNode = componentNode.path("path");
            JsonNode moduleNode = componentNode.path("moduleKey");
            components.put(componentNode.path("key").asText(),
                    new Component(pathNode.asText(), moduleNode.isMissingNode()?null:moduleNode.asText()));
        }

        return components;
    }
522223
def get_connected_components_as_subgraphs(graph):
    
    components = get_connected_components(graph)

    list_of_graphs = []

    for c in components:
        edge_ids = set()
        nodes = [graph.get_node(node) for node in c]
        for n in nodes:
            # --Loop through the edges in each node, to determine if it should be included
            for e in n['edges']:
                # --Only add the edge to the subgraph if both ends are in the subgraph
                edge = graph.get_edge(e)
                a, b = edge['vertices']
                if a in c and b in c:
                    edge_ids.add(e)
        # --Build the subgraph and add it to the list
        list_of_edges = list(edge_ids)
        subgraph = make_subgraph(graph, c, list_of_edges)
        list_of_graphs.append(subgraph)

    return list_of_graphs
229407
def connected_subgraphs(self, directed=True, ordered=False):
    '''
    '''
    num_ccs, labels = self.connected_components(directed=directed)
    # check the trivial case first
    if num_ccs == 1:
      yield self
      raise StopIteration
    if ordered:
      # sort by descending size (num vertices)
      order = np.argsort(np.bincount(labels))[::-1]
    else:
      order = range(num_ccs)

    # don't use self.subgraph() here, because we can reuse adj
    adj = self.matrix('dense', 'csr', 'csc')
    for c in order:
      mask = labels == c
      sub_adj = adj[mask][:,mask]
      yield self.__class__.from_adj_matrix(sub_adj)
818952
private static Collection<Set<Fragment>> getConnectedFragmentSets(Set<Fragment> allFragments) {
        // TODO this could be implemented in a more readable way (eg. using a graph + BFS etc.)
        final Map<Integer, Set<Variable>> varSetMap = new HashMap<>();
        final Map<Integer, Set<Fragment>> fragmentSetMap = new HashMap<>();
        final int[] index = {0};
        allFragments.forEach(fragment -> {
            Set<Variable> fragmentVarNameSet = Sets.newHashSet(fragment.vars());
            List<Integer> setsWithVarInCommon = new ArrayList<>();
            varSetMap.forEach((setIndex, varNameSet) -> {
                if (!Collections.disjoint(varNameSet, fragmentVarNameSet)) {
                    setsWithVarInCommon.add(setIndex);
                }
            });

            if (setsWithVarInCommon.isEmpty()) {
                index[0] += 1;
                varSetMap.put(index[0], fragmentVarNameSet);
                fragmentSetMap.put(index[0], Sets.newHashSet(fragment));
            } else {
                Iterator<Integer> iterator = setsWithVarInCommon.iterator();
                Integer firstSet = iterator.next();
                varSetMap.get(firstSet).addAll(fragmentVarNameSet);
                fragmentSetMap.get(firstSet).add(fragment);
                while (iterator.hasNext()) {
                    Integer nextSet = iterator.next();
                    varSetMap.get(firstSet).addAll(varSetMap.remove(nextSet));
                    fragmentSetMap.get(firstSet).addAll(fragmentSetMap.remove(nextSet));
                }
            }
        });
        return fragmentSetMap.values();
    }
925504
private Set<DagNode<T>> getAncestorNodes(Set<DagNode<T>> dagNodes) {
    Set<DagNode<T>> ancestorNodes = new HashSet<>();
    for (DagNode<T> dagNode : dagNodes) {
      LinkedList<DagNode<T>> nodesToExpand = Lists.newLinkedList(this.getParents(dagNode));
      while (!nodesToExpand.isEmpty()) {
        DagNode<T> nextNode = nodesToExpand.poll();
        ancestorNodes.add(nextNode);
        nodesToExpand.addAll(this.getParents(nextNode));
      }
    }
    return ancestorNodes;
  }