Neo4j: Find all possible combinations

Question

I'm currently struggling with a problem regarding combinatorics.
For a prototype I wanted to try neo4j-ogm.

This is the domain model I designed so far:

@NodeEntity
public class Operand {

    @GraphId
    private Long graphId;

}

@NodeEntity
public class Option extends Operand {

    private Long id;

    private String name;

    @Relationship(type = "CONDITIONED_BY")
    private List<Rule> rules = new ArrayList<>();
}

@NodeEntity
public class Operation extends Operand {

    @Relationship(type = "COMPOSITION", direction = Relationship.INCOMING)
    private Rule composition;

    private Operation superOperation;

    private Boolean not;

    private List<Operand> operands = new ArrayList<>();
}

public class AndOperation extends Operation {
// Relationships named accordingly "AND"
}


public class OrOperation extends Operation {
// Relationships named accordingly "OR"
}


@NodeEntity
public class Rule {

    @GraphId
    private Long graphId;

    @Relationship(type = "COMPOSITION")
    private Operation composition;

    @Relationship(type = "CONDITIONED_BY", direction = Relationship.INCOMING)
    private Option option;
}

This is a snippet of my graph:

representing something like (167079 ^ ...) & (167155 ^ ...)

Is it possible to form a query in cypher resulting in all possible combinations?

167079, 167155
167079, 167092
...

I found this resource dealing with a distantly related problem so far.

Do you think this is a proper use case for neo4j?

Do you propose any changes in the domain model?

Do you suggest any other technology?

Edit:

The example graph only shows a small part of my original graph, I'd have to calculate the permutation with various depth and various encapsulated operations.

Answer 1

Yes, we can get this by collecting on each side the equation (two collections) and then unwinding each collection.

Assuming the two collections are passed in as parameters:

UNWIND {first} as first
UNWIND {second} as second
RETURN first, second

This should give you a cartesian product between elements of both collections.

EDIT

If know know how many AND branches you have (let's say 2 for example), you can form your query like this:

MATCH (first)<-[:OR*0..]-()<-[:AND]-(root)-[:AND]->()-[:OR*0..]->(second)
WHERE id(root) = 168153
RETURN first, second

(edit, the match itself will generate the cartesian product for you here)

As for operations where you don't know how many AND branches you have, I don't believe you can accomplish this using this approach with just Cypher, as I don't believe dynamic columns are supported.

You might be able to do this using collections, though the operations would be tricky.

A custom procedure to perform cross products given two collections would be very helpful in this case. If you could collect all collections of nodes along AND branches, you could run REDUCE() on that, applying the cross product procedure with each collection.

As far as more complex trees with more operations, I don't believe you'll be able to do this through Cypher. I'd highly recommend a custom procedure, where you'll have far more control and be able to use conditional logic, recursion, and method calls.