private Set fusiformSimilarityForVertex()

in hugegraph-core/src/main/java/org/apache/hugegraph/traversal/algorithm/FusiformSimilarityTraverser.java [89:190]
91 lines of code
18 McCabe index (conditional complexity)

    private Set<Similar> fusiformSimilarityForVertex(
                         HugeVertex vertex, Directions direction,
                         String label, int minNeighbors, double alpha,
                         int minSimilars, int top, String groupProperty,
                         int minGroups, long degree, long capacity,
                         boolean withIntermediary) {
        boolean matched = this.matchMinNeighborCount(vertex, direction, label,
                                                     minNeighbors, degree);
        if (!matched) {
            // Ignore current vertex if its neighbors number is not enough
            return ImmutableSet.of();
        }
        Id labelId = this.getEdgeLabelId(label);
        // Get similar nodes and counts
        Iterator<Edge> edges = this.edgesOfVertex(vertex.id(), direction,
                                                  labelId, degree);
        Map<Id, MutableInt> similars = newMap();
        MultivaluedMap<Id, Id> intermediaries = new MultivaluedHashMap<>();
        Set<Id> neighbors = newIdSet();
        while (edges.hasNext()) {
            Id target = ((HugeEdge) edges.next()).id().otherVertexId();
            if (neighbors.contains(target)) {
                continue;
            }
            neighbors.add(target);
            checkCapacity(capacity, ++this.accessed, "fusiform similarity");

            Directions backDir = direction.opposite();
            Iterator<Edge> backEdges = this.edgesOfVertex(target, backDir,
                                                          labelId, degree);
            Set<Id> currentSimilars = newIdSet();
            while (backEdges.hasNext()) {
                Id node = ((HugeEdge) backEdges.next()).id().otherVertexId();
                if (currentSimilars.contains(node)) {
                    continue;
                }
                currentSimilars.add(node);
                if (withIntermediary) {
                    intermediaries.add(node, target);
                }

                MutableInt count = similars.get(node);
                if (count == null) {
                    count = new MutableInt(0);
                    similars.put(node, count);
                    checkCapacity(capacity, ++this.accessed,
                                  "fusiform similarity");
                }
                count.increment();
            }
        }
        // Delete source vertex
        assert similars.containsKey(vertex.id());
        similars.remove(vertex.id());
        if (similars.isEmpty()) {
            return ImmutableSet.of();
        }
        // Match alpha
        double neighborNum = neighbors.size();
        Map<Id, Double> matchedAlpha = newMap();
        for (Map.Entry<Id, MutableInt> entry : similars.entrySet()) {
            double score = entry.getValue().intValue() / neighborNum;
            if (score >= alpha) {
                matchedAlpha.put(entry.getKey(), score);
            }
        }
        if (matchedAlpha.size() < minSimilars) {
            return ImmutableSet.of();
        }

        // Sorted and topN if needed
        Map<Id, Double> topN;
        if (top > 0) {
            topN = topN(matchedAlpha, true, top);
        } else {
            topN = matchedAlpha;
        }
        // Filter by groupCount by property
        if (groupProperty != null) {
            Set<Object> values = newSet();
            // Add groupProperty value of source vertex
            values.add(vertex.value(groupProperty));
            for (Id id : topN.keySet()) {
                Vertex v = graph().vertices(id).next();
                values.add(v.value(groupProperty));
            }
            if (values.size() < minGroups) {
                return ImmutableSet.of();
            }
        }
        // Construct result
        Set<Similar> result = InsertionOrderUtil.newSet();
        for (Map.Entry<Id, Double> entry : topN.entrySet()) {
            Id similar = entry.getKey();
            double score = entry.getValue();
            List<Id> inters = withIntermediary ?
                              intermediaries.get(similar) :
                              ImmutableList.of();
            result.add(new Similar(similar, score, inters));
        }
        return result;
    }