Neo4j: Faster coloring / marking of subgraphs
I have a graph containing several small subgraphs. The goal is to mark all BLUE nodes in a subgraph as RED if and only if all nodes in that subgraph are BLUE. If one of the nodes in a subgraph has a different color, GREEN, then we will not change the color of the nodes in this subgraph.
This is the query I'm using:
MATCH (a:BLUE) WHERE NOT (a)-[*]-(:GREEN) WITH a LIMIT 10000 SET a:RED REMOVE a:BLUE
This is how it looks before and after the request:
The problem is that it is slow since it must traverse the same subgraph multiple times. For example:
To mark A as RED, he needs to pass ABC. Then again, to mark B, he must cross ABC. Again, the same for the C mark.
I would like to know if there is any way so that I can mark all the nodes in a subgraph in one go, instead of visiting the same subgraph over and over again. If possible, it will reduce the request time for many reasons.
source to share
I haven't used the Plot Algorithms plugin yet, but this can often be done faster than pure Cypher using APOC routines , although all nodes in all relevant subgraphs need to be processed to separate down to one line for the connected subgraph, as Neo4j has no built-in support for subgraph queries.
The procedure apoc.path.subgraphNodes()
is particularly useful for expanding to an entire subgraph from each node and will only compute one path to each node rather than evaluating all possible paths.
From there we can group by the minimum node in the subgraph and only keep one set of nodes representing the entire subgraph. This brings us to one line per subgraph, which allows our predicate to check the color of all nodes in the subgraph only once per subgraph.
Something like that:
MATCH (n:BLUE) // no need to get subgraphs that don't have blue nodes
CALL apoc.path.subgraphNodes(n, {}) YIELD node
WITH n, collect(node) as nodes, min(id(node)) as minId
WITH minId, head(collect(nodes)) as nodes // now only one row / subgraph
WHERE all(node in nodes where node:BLUE)
UNWIND nodes as node
SET node:RED
REMOVE node:BLUE
source to share