Find the strongly connected components in given graph.

@param g
the graph
@param toolkit
a GraphToolkit, used to create temporary graphs used by the
algorithm
966963
public void findStronglyConnectedComponents(GraphType g, GraphToolkit<GraphType, EdgeType, VertexType> toolkit) {

        // Perform the initial depth first search
        DepthFirstSearch<GraphType, EdgeType, VertexType> initialDFS = new DepthFirstSearch<>(g);
        if (m_vertexChooser != null) {
            initialDFS.setVertexChooser(m_vertexChooser);
        }
        initialDFS.search();

        // Create a transposed graph
        Transpose<GraphType, EdgeType, VertexType> t = new Transpose<>();
        GraphType transpose = t.transpose(g, toolkit);

        // Create a set of vertices in the transposed graph,
        // in descending order of finish time in the initial
        // depth first search.
        VisitationTimeComparator<VertexType> comparator = new VisitationTimeComparator<>(
                initialDFS.getFinishTimeList(), VisitationTimeComparator.DESCENDING);
        Set<VertexType> descendingByFinishTimeSet = new TreeSet<>(comparator);
        Iterator<VertexType> i = transpose.vertexIterator();
        while (i.hasNext()) {
            descendingByFinishTimeSet.add(i.next());
        }

        // Create a SearchTreeBuilder for transposed DFS
        SearchTreeBuilder<VertexType> searchTreeBuilder = new SearchTreeBuilder<>();

        // Now perform a DFS on the transpose, choosing the vertices
        // to visit in the main loop by descending finish time
        final Iterator<VertexType> vertexIter = descendingByFinishTimeSet.iterator();
        DepthFirstSearch<GraphType, EdgeType, VertexType> transposeDFS = new DepthFirstSearch<GraphType, EdgeType, VertexType>(
                transpose) {
            @Override
            protected VertexType getNextSearchTreeRoot() {
                while (vertexIter.hasNext()) {
                    VertexType vertex = vertexIter.next();
                    if (visitMe(vertex)) {
                        return vertex;
                    }
                }
                return null;
            }
        };
        if (m_vertexChooser != null) {
            transposeDFS.setVertexChooser(m_vertexChooser);
        }
        transposeDFS.setSearchTreeCallback(searchTreeBuilder);
        transposeDFS.search();

        // The search tree roots of the second DFS represent the
        // strongly connected components. Note that we call copySearchTree()
        // to make the returned search trees relative to the original
        // graph, not the transposed graph (which would be very confusing).
        Iterator<SearchTree<VertexType>> j = searchTreeBuilder.searchTreeIterator();
        while (j.hasNext()) {
            m_stronglyConnectedSearchTreeList.add(copySearchTree(j.next(), t));
        }
    }
180441
public void setGraphqlApis(java.util.Collection<GraphqlApi> graphqlApis) {
        if (graphqlApis == null) {
            this.graphqlApis = null;
            return;
        }

        this.graphqlApis = new java.util.ArrayList<GraphqlApi>(graphqlApis);
    }
627771
public final void build(GraphIterator<ST, PT> iterator, SubGraphBuildListener<ST, PT> listener) {
		assert iterator != null;
		final Set<ComparableWeakReference<PT>> reachedPoints = new TreeSet<>();
		GraphIterationElement<ST, PT> element;
		ST segment;
		PT point;
		PT firstPoint = null;

		this.parentGraph = new WeakReference<>(iterator.getGraph());
		this.segments.clear();
		this.pointNumber = 0;
		this.terminalPoints.clear();

		while (iterator.hasNext()) {
			element = iterator.nextElement();
			point = element.getPoint();
			segment = element.getSegment();

			// First reached segment
			if (this.segments.isEmpty()) {
				firstPoint = point;
			}

			this.segments.add(segment);
			if (listener != null) {
				listener.segmentAdded(this, element);
			}

			// Register terminal points
			point = segment.getOtherSidePoint(point);
			final ComparableWeakReference<PT> ref = new ComparableWeakReference<>(point);
			if (element.isTerminalSegment()) {
				if (!reachedPoints.contains(ref)) {
					this.terminalPoints.add(ref);
					if (listener != null) {
						listener.terminalPointReached(this, point, segment);
					}
				}
			} else {
				this.terminalPoints.remove(ref);
				reachedPoints.add(ref);
				if (listener != null) {
					listener.nonTerminalPointReached(this, point, segment);
				}
			}
		}

		if (firstPoint != null) {
			final ComparableWeakReference<PT> ref = new ComparableWeakReference<>(firstPoint);
			if (!reachedPoints.contains(ref)) {
				this.terminalPoints.add(ref);
			}
		}

		this.pointNumber = this.terminalPoints.size() + reachedPoints.size();

		reachedPoints.clear();
	}
133004
private void checkForCycles(DefaultDirectedWeightedGraph<RuleProvider, DefaultEdge> graph)
    {
        CycleDetector<RuleProvider, DefaultEdge> cycleDetector = new CycleDetector<>(graph);

        if (cycleDetector.detectCycles())
        {
            // if we have cycles, then try to throw an exception with some usable data
            Set<RuleProvider> cycles = cycleDetector.findCycles();
            StringBuilder errorSB = new StringBuilder();
            for (RuleProvider cycle : cycles)
            {
                errorSB.append("Found dependency cycle involving: " + cycle.getMetadata().getID()).append(System.lineSeparator());
                Set<RuleProvider> subCycleSet = cycleDetector.findCyclesContainingVertex(cycle);
                for (RuleProvider subCycle : subCycleSet)
                {
                    errorSB.append("\tSubcycle: " + subCycle.getMetadata().getID()).append(System.lineSeparator());
                }
            }
            throw new RuntimeException("Dependency cycles detected: " + errorSB.toString());
        }
    }
97235
def find_biconnected_components(graph):
    

    list_of_components = []

    # Run the algorithm on each of the connected components of the graph
    components = get_connected_components_as_subgraphs(graph)
    for component in components:
        # --Call the internal biconnnected components function to find
        # --the edge lists for this particular connected component
        edge_list = _internal_get_biconnected_components_edge_lists(component)
        list_of_components.extend(edge_list)

    return list_of_components
950545
def get_dependency_graph(component):
    
    if component not in DEPENDENCIES:
        raise Exception("%s is not a registered component." % get_name(component))

    if not DEPENDENCIES[component]:
        return {component: set()}

    graph = defaultdict(set)

    def visitor(c, parent):
        if parent is not None:
            graph[parent].add(c)

    walk_dependencies(component, visitor)

    graph = dict(graph)

    # Find all items that don't depend on anything.
    extra_items_in_deps = _reduce(set.union, graph.values(), set()) - set(graph.keys())

    # Add empty dependencies where needed.
    graph.update(dict((item, set()) for item in extra_items_in_deps))

    return graph
299302
@Override
    protected void paintComponent(Graphics g) {
        final Graphics2D G2 = (Graphics2D) g.create();

        G2.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_ON);
        G2.setRenderingHint(RenderingHints.KEY_RENDERING, RenderingHints.VALUE_RENDER_QUALITY);
        G2.setRenderingHint(RenderingHints.KEY_STROKE_CONTROL, RenderingHints.VALUE_STROKE_NORMALIZE);
        G2.setRenderingHint(RenderingHints.KEY_TEXT_ANTIALIASING, RenderingHints.VALUE_TEXT_ANTIALIAS_ON);

        G2.translate(getInnerBounds().x, getInnerBounds().y);

        // Draw background
        if (sectionsVisible && !sections.isEmpty()) {
            for (int i = 0; i < sections.size(); i++) {
                if (Double.compare(lcdValue, sections.get(i).getStart()) >= 0 && Double.compare(lcdValue, sections.get(i).getStop()) <= 0) {
                    bgImage = sectionsBackground.get(i);
                    fgColor = sectionsForeground.get(i);
                    break;
                } else {
                    bgImage = lcdImage;
                    fgColor = lcdColor.TEXT_COLOR;
                }
            }

            if (bgImage == null) {
                bgImage = lcdImage;
                fgColor = null;
            }

        } else {
            bgImage = lcdImage;
            fgColor = null;
        }
        if (lcdBackgroundVisible) {
        G2.drawImage(bgImage, 0, 0, null);
        }

        // Draw bargraph
        if (bargraphVisible) {
            int activeSegments = (int) (lcdValue * bargraphSegmentFactor);
            for (int i = 0 ; i < 20 ; i++) {
                if (i < activeSegments) {
                    if (!sections.isEmpty()) {
                        for (int j = 0; j < sections.size(); j++) {
                            if (Double.compare(lcdValue, sections.get(j).getStart()) >= 0 && Double.compare(lcdValue, sections.get(j).getStop()) <= 0) {
                                Paint fill;
                                if (plainBargraphSegments) {
                                    fill = sections.get(j).getColor();
                                } else {
                                    fill = new RadialGradientPaint((float)bargraph.get(i).getBounds2D().getCenterX(), (float)bargraph.get(i).getBounds2D().getCenterY(), (float)bargraph.get(i).getBounds2D().getWidth() / 2, new float[]{0.0f, 1.0f}, new Color[]{sections.get(j).getColor().brighter(), sections.get(j).getColor().darker()});
                                }
                                G2.setPaint(fill);
                                break;
                            } else {
                                G2.setPaint(lcdColor.TEXT_COLOR);
                            }
                        }
                    } else {
                        G2.setPaint(lcdColor.TEXT_COLOR);
                    }
                    G2.fill(bargraph.get(i));
                }
            }
        }

        // Draw quality overlay
        if (qualityOverlayVisible && lcdValue > lcdMinValue) {
            G2.setPaint(qualityOverlayGradient);
            G2.fill(qualityOverlay);
        }

        // Draw lcd text
        if (fgColor == null) {
            if (lcdColor == LcdColor.CUSTOM) {
                G2.setColor(customLcdForeground);
            } else {
                G2.setColor(lcdColor.TEXT_COLOR);
            }
        } else {
            G2.setColor(fgColor);
        }

        if (lcdNnumericValues) {
            G2.setFont(lcdUnitFont);
            final double UNIT_STRING_WIDTH;
            final double digitalFontOffset = digitalFont ? lcdImage.getWidth() * 0.0625 : 0;
            // Draw unit string
            if (lcdUnitStringVisible && !lcdUnitString.isEmpty()) {
                unitLayout = new TextLayout(lcdUnitString, G2.getFont(), RENDER_CONTEXT);
                UNIT_BOUNDARY.setFrame(unitLayout.getBounds());
                if (lcdTextVisible) {
                G2.drawString(lcdUnitString, (int) ((lcdImage.getWidth() - UNIT_BOUNDARY.getWidth()) - lcdImage.getHeight() * 0.15f), (int) (lcdImage.getHeight() * 0.76f));
                }
                UNIT_STRING_WIDTH = UNIT_BOUNDARY.getWidth();
            } else {
                UNIT_STRING_WIDTH = 0;
            }

            // Draw value
            G2.setFont(lcdValueFont);
            switch (numberSystem) {
                case HEX:
                    valueLayout = new TextLayout(Integer.toHexString((int) lcdValue).toUpperCase(), G2.getFont(), RENDER_CONTEXT);
                    VALUE_BOUNDARY.setFrame(valueLayout.getBounds());
                    if (lcdTextVisible) {
                    G2.drawString(Integer.toHexString((int) lcdValue).toUpperCase(), (float) ((lcdImage.getMinX() + (lcdImage.getWidth() - UNIT_STRING_WIDTH - VALUE_BOUNDARY.getWidth() - digitalFontOffset) - lcdImage.getHeight() * 0.3)), (lcdImage.getHeight() * 0.76f));
                    }
                    break;

                case OCT:
                    valueLayout = new TextLayout(Integer.toOctalString((int) lcdValue), G2.getFont(), RENDER_CONTEXT);
                    VALUE_BOUNDARY.setFrame(valueLayout.getBounds());
                    if (lcdTextVisible) {
                    G2.drawString(Integer.toOctalString((int) lcdValue), (float) ((lcdImage.getMinX() + (lcdImage.getWidth() - UNIT_STRING_WIDTH - VALUE_BOUNDARY.getWidth() - digitalFontOffset) - lcdImage.getHeight() * 0.3)), (lcdImage.getHeight() * 0.76f));
                    }
                    break;

                case DEC:

                default:
                    valueLayout = new TextLayout(formatLcdValue(lcdValue), G2.getFont(), RENDER_CONTEXT);
                    VALUE_BOUNDARY.setFrame(valueLayout.getBounds());
                    if (lcdTextVisible) {
                    G2.drawString(formatLcdValue(lcdValue), (float)((lcdImage.getMinX() + (lcdImage.getWidth() - UNIT_STRING_WIDTH - VALUE_BOUNDARY.getWidth() - digitalFontOffset) - lcdImage.getHeight() * 0.3)), (lcdImage.getHeight() * 0.76f));
                    }
                    break;
            }

            // Draw lcd info string
            if (!lcdInfoString.isEmpty()) {
                G2.setFont(lcdInfoFont);
                infoLayout = new TextLayout(lcdInfoString, G2.getFont(), RENDER_CONTEXT);
                INFO_BOUNDARY.setFrame(infoLayout.getBounds());
                G2.drawString(lcdInfoString, 5f, (float) INFO_BOUNDARY.getHeight() + 2f);
            }
        } else {
            // Draw text instead of numbers
            G2.setFont(lcdValueFont);
            if (!lcdText.isEmpty()) {
                valueLayout = new TextLayout(lcdText, G2.getFont(), RENDER_CONTEXT);
                VALUE_BOUNDARY.setFrame(valueLayout.getBounds());
                if (!TEXT_SCROLLER.isRunning()) {
                    lcdTextX = (float) VALUE_BOUNDARY.getWidth();
                }
                G2.drawString(lcdText, lcdImage.getWidth() - lcdTextX  - lcdImage.getHeight() * 0.15f, (lcdImage.getHeight() * 0.76f));
            }
        }

        // Draw lcd threshold indicator
        if (numberSystem == NumberSystem.DEC && lcdThresholdVisible) {
            if (!lcdThresholdBehaviourInverted) {
                if (lcdValue >= lcdThreshold) {
                    G2.drawImage(lcdThresholdImage, 5, getHeight() - lcdThresholdImage.getHeight() - 5, null);
                }
            } else {
                if (lcdValue <= lcdThreshold) {
                    G2.drawImage(lcdThresholdImage, 5, getHeight() - lcdThresholdImage.getHeight() - 5, null);
                }
            }
        }

        if (glowVisible && glowing) {
            G2.drawImage(glowImageOn, 0, 0, null);
        }

        if (!isEnabled()) {
            G2.setColor(DISABLED_COLOR);
            G2.fill(disabledShape);
        }

        G2.dispose();
    }
1082255
private static Set<ProjectModel> getAllApplications(GraphContext graphContext)
    {
        Set<ProjectModel> apps = new HashSet<>();
        Iterable<ProjectModel> appProjects = graphContext.findAll(ProjectModel.class);
        for (ProjectModel appProject : appProjects)
            apps.add(appProject);
        return apps;
    }
999411
def graphkit(*args)
		if args.size == 0
			conts = @last_contours
		else
			conts = contours(*args)
		end
		graphs = conts.map do |val, cons|
			unless cons[0]
				nil
			else
				(cons.map do |con|
	# 				p con
					contour = con.transpose
					kit = CodeRunner::GraphKit.autocreate({x: {data: contour[0]}, y: {data: contour[1], title: val.to_s}})
					kit.data[0].with = "l"
					kit
				end).sum
			end
		end
		graphs.compact.reverse.sum
	end
936074
private Set<SNode> getMatchedNodes(SDocumentGraph graph) {

    Set<SNode> matchedNodes = new HashSet<>();

    for (SNode node: graph.getNodes()) {
       if (node.getFeature(AnnisConstants.ANNIS_NS, AnnisConstants.FEAT_MATCHEDNODE) != null)
         matchedNodes.add(node);
    }

    return matchedNodes;
  }
394074
public static List<String> getProblems(Graph g) {
        List<String> problems = new ArrayList<>();
        int nodes = g.getNodes();
        int nodeIndex = 0;
        NodeAccess na = g.getNodeAccess();
        try {
            EdgeExplorer explorer = g.createEdgeExplorer();
            for (; nodeIndex < nodes; nodeIndex++) {
                double lat = na.getLatitude(nodeIndex);
                if (lat > 90 || lat < -90)
                    problems.add("latitude is not within its bounds " + lat);

                double lon = na.getLongitude(nodeIndex);
                if (lon > 180 || lon < -180)
                    problems.add("longitude is not within its bounds " + lon);

                EdgeIterator iter = explorer.setBaseNode(nodeIndex);
                while (iter.next()) {
                    if (iter.getAdjNode() >= nodes) {
                        problems.add("edge of " + nodeIndex + " has a node " + iter.getAdjNode() + " greater or equal to getNodes");
                    }
                    if (iter.getAdjNode() < 0) {
                        problems.add("edge of " + nodeIndex + " has a negative node " + iter.getAdjNode());
                    }
                }
            }
        } catch (Exception ex) {
            throw new RuntimeException("problem with node " + nodeIndex, ex);
        }

//        for (int i = 0; i < nodes; i++) {
//            new BreadthFirstSearch().start(g, i);
//        }
        return problems;
    }
807814
private Graph<Module> buildGraph(Map<Module, Set<Module>> edges) {
        Graph.Builder<Module> builder = new Graph.Builder<>();
        Set<Module> visited = new HashSet<>();
        Deque<Module> deque = new LinkedList<>();
        edges.entrySet().stream().forEach(e -> {
            Module m = e.getKey();
            deque.add(m);
            e.getValue().stream().forEach(v -> {
                deque.add(v);
                builder.addEdge(m, v);
            });
        });

        // read requires transitive from ModuleDescriptor
        Module source;
        while ((source = deque.poll()) != null) {
            if (visited.contains(source))
                continue;

            visited.add(source);
            builder.addNode(source);
            Module from = source;
            requiresTransitive(from).forEach(m -> {
                deque.add(m);
                builder.addEdge(from, m);
            });
        }
        return builder.build();
    }
822737
public static Map<IssueCategoryModel, List<ProblemSummary>> getProblemSummaries(
            GraphContext graphContext,
            Set<ProjectModel> projectModels,
            Set<String> includeTags,
            Set<String> excludeTags)
    {
        return getProblemSummaries(graphContext, projectModels, includeTags, excludeTags, false, false);
    }
52871
private Collection<Key<?>> getRequiredSourcesTargeting(
      DependencyGraph graph, Iterable<Key<?>> targets) {
    Collection<Key<?>> requiredSources = new LinkedHashSet<Key<?>>();
    for (Key<?> target : targets) {
      for (Dependency edge : graph.getDependenciesTargeting(target)) {
        if (!edge.isOptional()) {
          PrettyPrinter.log(logger, TreeLogger.DEBUG, "Removing the key %s because of %s",
              edge.getSource(), edge);
          requiredSources.add(edge.getSource());
        }
      }
    }
    return requiredSources;
  }
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
1150438
def resolve(self, graph):
        
        cached = graph.get(self.scoped_key)
        if cached:
            return cached

        component = self.create(graph)
        graph.assign(self.scoped_key, component)
        return component
521926
public boolean isConnectedInDirection(
      DiGraphNode<N, E> dNode1,
      Predicate<E> edgeMatcher,
      DiGraphNode<N, E>  dNode2) {
    // Verify the nodes.
    List<DiGraphEdge<N, E>> outEdges = dNode1.getOutEdges();
    int outEdgesLen = outEdges.size();
    List<DiGraphEdge<N, E>> inEdges = dNode2.getInEdges();
    int inEdgesLen = inEdges.size();
    // It is possible that there is a large assymmetry between the nodes, so pick the direction
    // to search based on the shorter list since the edge lists should be symmetric.
    if (outEdgesLen < inEdgesLen) {
      for (int i = 0; i < outEdgesLen; i++) {
        DiGraphEdge<N, E> outEdge = outEdges.get(i);
        if (outEdge.getDestination() == dNode2
            && edgeMatcher.apply(outEdge.getValue())) {
          return true;
        }
      }
    } else {
      for (int i = 0; i < inEdgesLen; i++) {
        DiGraphEdge<N, E> inEdge = inEdges.get(i);
        if (inEdge.getSource() == dNode1
            && edgeMatcher.apply(inEdge.getValue())) {
          return true;
        }
      }
    }

    return false;
  }