CODEWITHSUNDEEP
neo4j
Monta
Monta

Reputation: 1180

find distinct paths in neo4j database

I have a graph in which nodes of type "User" can be connected (or not) to other "User" nodes using "SIMILAR" relationship.

I want to find all the sub-graphs (interconnected "User" nodes) ordered by the number of their nodes.

Example: Imagine I have these nodes (relationship is always of type "SIMILAR")

A -> B,
A -> C,
D -> B,
E -> F,
Z

I'd like to get :

[A,B,C,D];
[E,F];
[Z];

Using Cypher or traversals.

Upvotes: 1

Views: 1766

Answers (1)

Michael Hunger
Michael Hunger

Reputation: 41676

In cypher it will be expensive.

Something like this query:

MATCH m WITH collect(m) as all
MATCH n
RETURN distinct [x in all WHERE (n)-[*0..]-(x) | x.name] as cluster

This would work too, but is probably equally expensive :)

MATCH n-[*0..]-m
WITH n, m
ORDER BY id(m)
WITH n, collect(m.name) as cluster
RETURN distinct cluster

In Java it could look something like this:

@Test
public void testSimpleCluster() throws Exception {
    createData();
    try (Transaction tx = db.beginTx()) {
        TraversalDescription traversal = db.traversalDescription().depthFirst().uniqueness(Uniqueness.NODE_GLOBAL);
        Map<Node, Set<Node>> clusters = new HashMap<>();
        GlobalGraphOperations ops = GlobalGraphOperations.at(db);
        for (Node node : ops.getAllNodes()) {
            if (inCluster(node, clusters) != null) continue;
            clusters.put(node, IteratorUtil.addToCollection(traversal.traverse(node).nodes(), new HashSet<Node>()));
        }
        System.out.println("clusters = " + clusters.values());
        tx.success();
    }
}

private Node inCluster(Node node, Map<Node, Set<Node>> clusters) {
    for (Map.Entry<Node, Set<Node>> entry : clusters.entrySet()) {
        if (entry.getValue().contains(node)) return entry.getKey();
    }
    return null;
}

private void createData() {
    try (Transaction tx = db.beginTx()) {
        Node a = node("a");
        Node b = node("b");
        Node c = node("c");
        Node d = node("d");
        Node e = node("e");
        Node f = node("f");
        Node z = node("z");
        connect(a, b);
        connect(a, c);
        connect(d, b);
        connect(e, f);
        tx.success();
    }
}

private void connect(Node a, Node b) {
    a.createRelationshipTo(b, SIMILAR);
}

private Node node(String name) {
    Node node = db.createNode();
    node.setProperty("name", name);
    return node;
}

Upvotes: 4

Related Questions