# How to avoid factorial (n!) path? **URL:** \ **Category:** Cypher\ **Tags:** performance, cypher\ **Created:** [January 24, 2022, 3:34am UTC](https://community.neo4j.com/t/how-to-avoid-factorial-n-path/50925 "2022-01-24T03:34:22Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![mengyunlong](https://sea1.discourse-cdn.com/flex021/user_avatar/community.neo4j.com/mengyunlong/32/21972_2.png) [@mengyunlong](https://community.neo4j.com/u/mengyunlong)\ **Post date:** [January 24, 2022, 3:34am UTC](https://community.neo4j.com/t/how-to-avoid-factorial-n-path/50925/1 "2022-01-24T03:34:22Z")
In my project, Neo4J stores staff nodes and relationships between staff. People who have been to the same place within A period of time will have A relationship. For example, A and B have arrived at the same scene within A day, and A and B will have an association relationship. I need to focus on any one person and find all the people within three degrees of path depth. My search statement is as follows: ` MATCH p = (x:user)-[r:REL*1..3]->(y:user) where x.user_id = '20121' UNWIND NODES(p) AS n WITH p, SIZE(COLLECT(DISTINCT n)) AS testLength WHERE testLength = LENGTH(p) + 1 RETURN p ` When the site is small, there is no problem in searching in this way, and the path is obtained: ![S41WE5QO@ULEM4QI~A(OU](https://us1.discourse-cdn.com/flex021/uploads/neo4jcommunity/original/3X/9/f/9fd54a0f1fd0d195c862483cb44b6fcea1f0ac5e.png) [p1-\>p2]、[p1-\>p3]、[p1-\>p4] [p1-\>p2-\>p5]、[p1-\>p3-\>p6]、[p1-\>p4-\>p7] [p1-\>p2-\>p5-\>p8]、[p1-\>p3-\>p6-\>p9]、[p1-\>p4-\>p7-\>p10] When there are more people in the place, the number of paths will change a lot. For example, when 10 people arrive at a place, the number of paths will be `10*9*8` : ![XB}IR0UFC)@LRUD(OK$@X](https://us1.discourse-cdn.com/flex021/uploads/neo4jcommunity/original/3X/6/c/6c2a98ca4628ed04e198fc09242b6683edf04472.png) When 10,000 people arrive at a site, the number of paths is `1000*999*988`, which is a disaster [p1-\>p2]...[p1-\>p10] [p1-\>p2-\>p3]...[p1-\>p2-\>p10] [p1-\>p3-\>p2]...[p1-\>p3-\>p10] .... [p1-\>p2-\>p3-\>p4]....[p1-\>p2-\>p3-\>p10].... [p1-\>p10-\>p9-\>p8]....[p1-\>p10-\>p9-\>p1].... .... I do not know how to deal with this situation, hope to get help This is my data script [export-1.txt](https://community.neo4j.com/uploads/short-url/9okvcHyqqvAwxlRD0KVHCiPUgLT.txt) (3.8 KB) [export-2.txt](https://community.neo4j.com/uploads/short-url/csVYeR02HJVbXCYREeomsRxzM98.txt) (16.7 KB) ---
**Author:** ![giuseppe\_villan](https://sea1.discourse-cdn.com/flex021/user_avatar/community.neo4j.com/giuseppe_villan/32/11871_2.png) [@giuseppe\_villan](https://community.neo4j.com/u/giuseppe_villan)\ **Post date:** [January 24, 2022, 8:58am UTC](https://community.neo4j.com/t/how-to-avoid-factorial-n-path/50925/2 "2022-01-24T08:58:18Z")
@mengyunlong I don't know if it's what you need, but If you can use APOC procedures maybe you could write your query like this: ```auto MATCH p = (x:user)-[r:REL*1..3]->(y:user) where x.user_id = '20121' with collect(NODES(p)) as nodes, collect(relationships(p)) as rels return apoc.coll.toSet(apoc.coll.flatten(nodes)) as nodes, apoc.coll.toSet(apoc.coll.flatten(rels)) as rels ``` or with a map return: ```auto return {nodes: apoc.coll.toSet(apoc.coll.flatten(nodes)), rels: apoc.coll.toSet(apoc.coll.flatten(rels))} ``` ---
**Author:** ![andrew\_bowman](https://sea1.discourse-cdn.com/flex021/user_avatar/community.neo4j.com/andrew_bowman/32/73_2.png) [@andrew\_bowman](https://community.neo4j.com/u/andrew_bowman)\ **Post date:** [January 24, 2022, 11:05pm UTC](https://community.neo4j.com/t/how-to-avoid-factorial-n-path/50925/3 "2022-01-24T23:05:50Z")
If your use case is to find distinct people within 3 degrees (and you don't actually care about distinct paths the way Cypher does) then you can use `apoc.path.subgraphNodes()`, a path expander procedure in APOC Procedures that is optimized for finding distinct nodes (and pruning any path found to a previously-encountered node). ```auto MATCH (x:user) WHERE x.user_id = '20121' CALL apoc.path.subgraphNodes(x, {maxLevel:3, relationshipFilter:'REL>', labelFilter:'>user'}) YIELD node as y RETURN y ``` This will only give distinct nodes back, it won't give back paths. If you want paths, then use `apoc.path.spanningTree()` instead, but be aware that it will only give back a single path per reached nodes, not multiple paths. ---
**Author:** ![mengyunlong](https://sea1.discourse-cdn.com/flex021/user_avatar/community.neo4j.com/mengyunlong/32/21972_2.png) [@mengyunlong](https://community.neo4j.com/u/mengyunlong)\ **Post date:** [January 25, 2022, 8:22am UTC](https://community.neo4j.com/t/how-to-avoid-factorial-n-path/50925/5 "2022-01-25T08:22:30Z")
Thank you for your help. Maybe I didn't express it clearly in my question. Is there any way to query only the shortest path, for example, query only [P1 -\>p2], [P1 -\>p3]... [p1 - \> p10] such a shortest path, exclude [p1 - \> p3 - \> p2], [p1 - \> p4 - \> p3 - \> p2] such a path ---
**Author:** ![mengyunlong](https://sea1.discourse-cdn.com/flex021/user_avatar/community.neo4j.com/mengyunlong/32/21972_2.png) [@mengyunlong](https://community.neo4j.com/u/mengyunlong)\ **Post date:** [January 25, 2022, 8:31am UTC](https://community.neo4j.com/t/how-to-avoid-factorial-n-path/50925/6 "2022-01-25T08:31:35Z")
Thanks for your help I need to find not only nodes, but also the shortest path between nodes. This is what I want: Nodes :[P2, P3, P4, P5, P6, P7, P8, P9, P10], rel: [p1 - \> p2], [p1 - \> p3], [p1 - \> p4], [p1 - \> p5], [p1 - \> p6], [p1 - \> p7], [p1 - \> p8], [p1 - \> p9], [p1 - \> p10] I do not know how to write such a statement, looking forward to your help ---
**Author:** ![andrew\_bowman](https://sea1.discourse-cdn.com/flex021/user_avatar/community.neo4j.com/andrew_bowman/32/73_2.png) [@andrew\_bowman](https://community.neo4j.com/u/andrew_bowman)\ **Post date:** [January 25, 2022, 3:34pm UTC](https://community.neo4j.com/t/how-to-avoid-factorial-n-path/50925/7 "2022-01-25T15:34:37Z")
In this case you'll need to use `apoc.path.spanningTree()`, which does `YIELD path` instead of node. The paths will automatically be shortest paths, since the procedure uses breadth-first expansion, and will only use the first path found to a node and no other. ---
**Author:** ![mengyunlong](https://sea1.discourse-cdn.com/flex021/user_avatar/community.neo4j.com/mengyunlong/32/21972_2.png) [@mengyunlong](https://community.neo4j.com/u/mengyunlong)\ **Post date:** [January 26, 2022, 3:08am UTC](https://community.neo4j.com/t/how-to-avoid-factorial-n-path/50925/8 "2022-01-26T03:08:51Z")
thanks a lot! The apoc.path.spanningTree() function solved my problem. thanks again!