Shortest path via a particular node type

[jaketeyjake]

I would like to find the shortest path between two nodes that requires that a path be routed through a particular node type. Imagine the following situation:

• My world consists of villages, towns, and cities (node types)
• Roads can connect any two nodes, regardless of node type (relationships)
• All roads have equal weights/costs to traverse
• I want to find the shortest path/minimum hops between two villages that requires going through a city, even if there is a shorter path that skips a city

From my current understanding, none of the current shortest path algorithms would support this kind of condition, and I can't seem to find a way to formulate a Cypher query. Any thoughts from the Neo4j brain-trust?

Here is a more concrete example of the problem:

1. The set up

CREATE (a:City {name: 'Atlanta'}),
(b:City {name: 'Boston'}),
(c:City {name: 'Chicago'}),
(m:Town {name: 'Monroe'}),
(n:Town {name: 'Napier'}),
(u:Village {name: 'Unitas'}),
(v:Village {name: 'Vincennes'}),
(u)-[:ROAD]->(m),
(m)-[:ROAD]->(b),
(m)-[:ROAD]->(v),
(b)-[:ROAD]->(a),
(b)-[:ROAD]->(c),
(b)-[:ROAD]->(n),
(a)-[:ROAD]->(c),
(c)-[:ROAD]->(n),
(n)-[:ROAD]->(v)

leads to this graph structure:

2. The path I'd like to return is:
   

3. Cypher is too general but guarantees inclusion of the city:

MATCH pw = (u:Village {name:'Unitas'})-[*]->(q:City)-[*]->(v:Village {name:'Vincennes'})
RETURN pw

This above query returns the entire graph as defined by the setup (1).

4. The shortest path algorithm, as I understand it, just returns the shortest path and I don't see an obvious way to add the constraint of going through a city:

MATCH (u:Village {name: 'Unitas'}), (v:Village {name: 'Vincennes'})
CALL gds.alpha.shortestPath.stream({
	nodeProjection: ['City','Town','Village'],
    relationshipProjection: 'ROAD',
    startNode: u,
    endNode: v
})
YIELD nodeId, cost
RETURN gds.util.asNode(nodeId)

This just returns the actual shortest path:

(Unitas)->(Monroe)->(Vincennes)

Any thoughts and help appreciated!

BONUS:
I'd also like to be able to do something like the following pseudocode:

MATCH mypath = (startNode)-<ARBITRARY CYPHER QUERY MIDDLE>-(endNode)
CALL shortestPath {
   mypath, #contains the subgraph returned from the MATCH above
   startNode:startNode,
   endNode:endNode
}
YIELD ...
RETURN ...

Thanks in advance to the community!
-jake

[Bennu · Accepted solution]

Hi @jaketeyjake,

This query should do what you are aiming for. You can create the paths and then look for the one with less hops (w/o library).

The condition may change according your needs (any/all/single).

MATCH path = (u:Village {name:'Unitas'})-[*]->(v:Village {name:'Vincennes'})
with nodes(path) as pw
where any(n in pw WHERE n:City)
RETURN pw, size(pw)
order by size(pw) asc limit 1

H

[jaketeyjake]

Brilliant, thanks @Bennu!

Best,
Jake