Runs the inside algorithm on a hypergraph with the first-order expectation semiring.

@param graph The hypergraph.
@return The beta value for each Hypernode. Where beta[i] is the inside
score for the i'th node in the Hypergraph, graph.getNodes().get(i).
434155
public static void insideAlgorithmFirstOrderExpect(final Hypergraph graph, final HyperpotentialFoe w,
            final Algebra s, final Scores scores) {
        final int n = graph.getNodes().size();
        final double[] beta = new double[n];
        final double[] betaFoe = new double[n];
        // \beta_i = 0 \forall i
        Arrays.fill(beta, s.zero());
        Arrays.fill(betaFoe, s.zero());
        graph.applyTopoSort(new HyperedgeFn() {

            @Override
            public void apply(Hyperedge e) {
                // \beta_{H(e)} += w_e \prod_{j \in T(e)} \beta_j
                double prod = s.one();
                double prodFoe = s.zero();
                for (Hypernode jNode : e.getTailNodes()) {
                    int j = jNode.getId();
                    // prod = s.times(prod, beta[j]);
                    // prodFoe = s.plus(s.times(prod, betaFoe[j]), s.times(beta[j], prodFoe));
                    double p1 = prod;
                    double p2 = beta[j];
                    double r1 = prodFoe;
                    double r2 = betaFoe[j];
                    prod = s.times(p1, p2);
                    prodFoe = s.plus(s.times(p1, r2), s.times(p2, r1));
                }
                // prod = s.times(prod, w.getScore(e, s));
                // prodFoe = s.plus(s.times(prod, w.getScoreFoe(e, s)), s.times(w.getScore(e, s), prodFoe));
                double p1 = prod;
                double p2 = w.getScore(e, s);
                double r1 = prodFoe;
                double r2 = w.getScoreFoe(e, s);
                prod = s.times(p1, p2);
                prodFoe = s.plus(s.times(p1, r2), s.times(p2, r1));
                
                int i = e.getHeadNode().getId();
                //if (log.isTraceEnabled()) { log.trace(String.format("old beta[%d] = %f",  i, s.toReal(beta[i]))); }
                beta[i] = s.plus(beta[i], prod);
                betaFoe[i] = s.plus(betaFoe[i], prodFoe);
                assert !s.isNaN(beta[i]);
                assert !s.isNaN(betaFoe[i]);
                // log.debug(String.format("%s w_e=%f beta[%d] = %.3f betaFoe[%d] = %.3f", e.getLabel(), s.toReal(w.getScore(e, s)), i, s.toReal(beta[i]), i, s.toReal(betaFoe[i]))); 
            }
            
        });
        scores.beta = beta;
        scores.betaFoe = betaFoe;
    }
347146
public static int nvgraphSrSpmv(
        nvgraphHandle handle, 
        nvgraphGraphDescr descrG, 
        long weight_index, 
        Pointer alpha, 
        long x_index, 
        Pointer beta, 
        long y_index, 
        int SR)
    {
        return checkResult(nvgraphSrSpmvNative(handle, descrG, weight_index, alpha, x_index, beta, y_index, SR));
    }
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;
    }
8741
public String graph() {// throws Exception {
        StringBuffer text = new StringBuffer();

        text.append("digraph CobwebTree {\n");
        m_cobwebTree.graphTree(text);
        text.append("}\n");
        return text.toString();
    }
221635
public <NEW> Graph<K, VV, NEW> translateEdgeValues(TranslateFunction<EV, NEW> translator) throws Exception {
		return run(new TranslateEdgeValues<>(translator));
	}
742150
private <E extends Edge> double getConnectionSimilarity(
            Graph<E> graph, Edge e1, Edge e2) {
        int e1to = e1.to();
        int e1from = e1.from();
        int e2to = e2.to();
        int e2from = e2.from();
        if (e1to == e2to)
            return getConnectionSimilarity(graph, e1to, e1from, e2from);
        else if (e1to == e2from)
            return getConnectionSimilarity(graph, e1to, e1from, e2to);
        else if (e1from == e2to)
            return getConnectionSimilarity(graph, e1from, e1to, e2from);
        else if (e1from == e2from)
            return getConnectionSimilarity(graph, e1from, e1to, e2to);
        else
            return 0;
    }
1011165
@Override
    public float calculatePriority(int node) {
        CalcShortcutsResult calcShortcutsResult = calcShortcutCount(node);

        // # huge influence: the bigger the less shortcuts gets created and the faster is the preparation
        //
        // every adjNode has an 'original edge' number associated. initially it is r=1
        // when a new shortcut is introduced then r of the associated edges is summed up:
        // r(u,w)=r(u,v)+r(v,w) now we can define
        // originalEdgesCount = σ(v) := sum_{ (u,w) ∈ shortcuts(v) } of r(u, w)
        int originalEdgesCount = calcShortcutsResult.originalEdgesCount;

        // # lowest influence on preparation speed or shortcut creation count
        // (but according to paper should speed up queries)
        //
        // number of already contracted neighbors of v
        int contractedNeighbors = 0;
        int degree = 0;
        CHEdgeIterator iter = remainingEdgeExplorer.setBaseNode(node);
        while (iter.next()) {
            degree++;
            if (iter.isShortcut())
                contractedNeighbors++;
        }

        // from shortcuts we can compute the edgeDifference
        // # low influence: with it the shortcut creation is slightly faster
        //
        // |shortcuts(v)| − |{(u, v) | v uncontracted}| − |{(v, w) | v uncontracted}|
        // meanDegree is used instead of outDegree+inDegree as if one adjNode is in both directions
        // only one bucket memory is used. Additionally one shortcut could also stand for two directions.
        int edgeDifference = calcShortcutsResult.shortcutsCount - degree;

        // according to the paper do a simple linear combination of the properties to get the priority.
        return params.edgeDifferenceWeight * edgeDifference +
                params.originalEdgesCountWeight * originalEdgesCount +
                params.contractedNeighborsWeight * contractedNeighbors;
    }
1140422
protected int compatibilityGraphCEdgeZero() throws IOException {

        int compGraphNodesCZeroListSize = compGraphNodesCZero.size();
        cEdges = new ArrayList<Integer>(); //Initialize the cEdges List
        dEdges = new ArrayList<Integer>(); //Initialize the dEdges List

        for (int a = 0; a < compGraphNodesCZeroListSize; a += 4) {
            int indexA = compGraphNodesCZero.get(a);
            int indexAPlus1 = compGraphNodesCZero.get(a + 1);
            for (int b = a + 4; b < compGraphNodesCZeroListSize; b += 4) {
                int indexB = compGraphNodesCZero.get(b);
                int indexBPlus1 = compGraphNodesCZero.get(b + 1);

                // if element atomCont !=jIndex and atoms on the adjacent sides of the bonds are not equal
                if ((a != b) && (indexA != indexB) && (indexAPlus1 != indexBPlus1)) {

                    IBond reactantBond = null;
                    IBond productBond = null;

                    reactantBond = source.getBond(source.getAtom(indexA), source.getAtom(indexB));
                    productBond = target.getBond(target.getAtom(indexAPlus1), target.getAtom(indexBPlus1));

                    if (reactantBond != null && productBond != null) {
                        addCZeroEdges(reactantBond, productBond, a, b);
                    }

                }
            }
        }

        //Size of C and D edges of the compatibility graph
        cEdgesSize = cEdges.size();
        dEdgesSize = dEdges.size();
        return 0;
    }
252735
protected KeyedGraph<V, E> prepareGraph() throws SQLException {
        LOGGER.info("Loading graph into memory...");
        final long start = System.currentTimeMillis();
        // Initialize the graph.
        KeyedGraph<V, E> graph;
        if (!globalOrientation.equals(GraphFunctionParser.Orientation.UNDIRECTED)) {
            if (weightColumn != null) {
                graph = new DirectedWeightedPseudoG<V, E>(vertexClass, edgeClass);
            } else {
                graph = new DirectedPseudoG<V, E>(vertexClass, edgeClass);
            }
        } else {
            if (weightColumn != null) {
                graph = new WeightedPseudoG<V, E>(vertexClass, edgeClass);
            } else {
                graph = new PseudoG<V, E>(vertexClass, edgeClass);
            }
        }
        final Statement st = connection.createStatement();
        final ResultSet edges = st.executeQuery("SELECT * FROM " +
                TableUtilities.parseInputTable(connection, inputTable));
        // Initialize the indices.
        initIndices(edges);
        try {
            // Add the edges.
            while (edges.next()) {
                loadEdge(graph, edges);
            }
            logTime(LOGGER, start);
            return graph;
        } catch (SQLException e) {
            LOGGER.error("Could not store edges in graph.", e);
            return null;
        } finally {
            edges.close();
            st.close();
        }
    }
173418
private static double getEdgeFragmentCost(Node node, Arborescence<Node> arborescence,
                                              Map<Node, Map<Node, Fragment>> edgeToFragment) {

        Fragment fragment = getEdgeFragment(node, arborescence, edgeToFragment);
        if (fragment != null) return fragment.fragmentCost();

        return 0D;
    }
543957
public void runPostProcessing(boolean multiRoot) {
        // make identical vertices have the same set of properties
        // two vertices are identical if they have the same address value.
        // Id for every vertex is unique, so this is not a flag here
        for (Set<ExecutionGraphVertex> vs : this.addressToVertices.values()) {

            // the logic below is very fragile and based on some empirical model
            // and may not work for other type of graphs
            if (vs != null && vs.size() > 1) {
                for (ExecutionGraphVertex vertex : vs) {
                    if (CELL_WITH_FORMULA == vertex.properties().getType() || null != vertex.properties().getAlias()) {
                        copyProperties(vertex, vs);
                        break;
                    }
                }
            }
        }

        // copy or link subgraphs to identical vertices and modify Formula field with additional values
        Map<String, AtomicInteger> adressToCount = new HashMap<>();

        for (ExecutionGraphVertex vertex : this.graph.getVertices()) {

            // restore/add subgraphs to identical vertices
            Type type = vertex.properties().getType();

            if (isCell(type)) {
                String address = vertex.properties().getName();

                adressToCount.putIfAbsent(address, new AtomicInteger(0));

                if (adressToCount.get(address).incrementAndGet() > 1) { // count > 1
                    // need to link
                    Set<ExecutionGraphVertex> subgraphTops = new HashSet<>();

                    this.graph.getVertices().stream()
                                            .filter(v -> address.equals(v.properties.getName())) // check for subgraph
                                            .forEach(v -> this.graph.getIncomingEdgesOf(v).forEach(e -> subgraphTops.add(this.graph.getEdgeSource(e))));

                    for (ExecutionGraphVertex subVertex : subgraphTops) {
                        if (!this.addressToVertices.containsKey(address)) { continue; }
                        this.addressToVertices.get(address).forEach(v -> this.graph.addEdge(subVertex, v));
                    }
                }
            }

            if (RANGE == type) { connectValuesToRange(vertex, this); }

            /* Adding IF Value */
            if (IF == type) {
                Collection<ExecutionGraphEdge> two = this.graph.getIncomingEdgesOf(vertex);
                if (two.size() != 2) { throw new CalculationEngineException("IF must have only two incoming edges."); }

                Object ifBranchValue = null;
                for (ExecutionGraphEdge e : two) {
                    ExecutionGraphVertex oneOfTwo = this.graph.getEdgeSource(e);
                    if (!isCompareOperand(oneOfTwo.getName())) {
                        ifBranchValue = oneOfTwo.properties().getValue();
                        break;
                    }
                }
                vertex.properties().setValue(ifBranchValue);
            }
        }

        if (this.config.getDuplicatesNumberThreshold() != -1) { removeAllDuplicates(this); }
    }
1106890
private void interiorLineExteriorLine_(int half_edge, int id_a, int id_b,
			int predicate) {
		if (m_matrix[predicate] == 1)
			return;

		int parentage = m_topo_graph.getHalfEdgeParentage(half_edge);

		if ((parentage & id_a) != 0 && (parentage & id_b) == 0)
			m_matrix[predicate] = 1;
	}
1355034
public static void outsideAlgorithm(final Hypergraph graph, final Hyperpotential w, final Semiring s,
            final Scores scores) {
        scores.alpha = outsideAlgorithm(graph, w, s, scores.beta);
    }
1126983
@Override
	public DataSet<Result<K>> runInternal(Graph<K, VV, EV> input)
			throws Exception {
		// u, v, w, bitmask
		DataSet<TriangleListing.Result<K>> triangles = input
			.run(new TriangleListing<K, VV, EV>()
				.setParallelism(parallelism));

		// u, edge count
		DataSet<Tuple2<K, LongValue>> triangleVertices = triangles
			.flatMap(new SplitTriangles<>())
				.name("Split triangle vertices");

		// u, triangle count
		DataSet<Tuple2<K, LongValue>> vertexTriangleCount = triangleVertices
			.groupBy(0)
			.reduce(new CountTriangles<>())
			.setCombineHint(CombineHint.HASH)
				.name("Count triangles")
				.setParallelism(parallelism);

		// u, deg(u)
		DataSet<Vertex<K, Degrees>> vertexDegree = input
			.run(new VertexDegrees<K, VV, EV>()
				.setIncludeZeroDegreeVertices(includeZeroDegreeVertices.get())
				.setParallelism(parallelism));

		// u, deg(u), triangle count
		return vertexDegree
			.leftOuterJoin(vertexTriangleCount)
			.where(0)
			.equalTo(0)
			.with(new JoinVertexDegreeWithTriangleCount<>())
				.setParallelism(parallelism)
				.name("Clustering coefficient");
	}
401685
@SuppressWarnings("unchecked")
    private Set<Integer> getPredecessors(Graph g, Integer vertex) {
        // The DirectedGraph cast seems to change the return type of the set
        // from Set<Integer> to just Set
        if (g instanceof DirectedGraph) {
            DirectedGraph<?> dg = (DirectedGraph)g;
            return dg.predecessors(vertex);
        }
        else {
            return g.getNeighbors(vertex);
        }
    }
202855
public org.tensorflow.framework.CostGraphDef.NodeOrBuilder getNodeOrBuilder(
      int index) {
    return node_.get(index);
  }
110269
public static <T> Set<Set<Node<T>>> compute(final Graph<T> graph) {
    final Set<Set<Node<T>>> connectedComponents = new LinkedHashSet<>();
    final Set<Node<T>> unmarkedNodes = new LinkedHashSet<>(graph.nodes());

    while (!unmarkedNodes.isEmpty()) {
      Set<Node<T>> connectedComp = new LinkedHashSet<>();
      deepFirstSearch(unmarkedNodes.iterator().next(), connectedComp, unmarkedNodes);
      connectedComponents.add(connectedComp);
    }

    return connectedComponents;
  }