How to find APSP

Neo4j Graph Platform Graph Algorithms/Graph Data Science
1

Screenshot 2023-11-02 at 10.03.41 AM
Screenshot 2023-11-02 at 10.03.41 AM1388Ă—524 55.3 KB

I have to find the APSP between Subnet to subnet and remove all those paths which have tgw2 in their pathways.

Things I tried:
Projection:

CALL gds.graph.project(

'subAndTGWAndNet1',

['Subnet', 'Network','TGW'],

{

SUB_OF: {

type: 'SUB_OF',

orientation: 'UNDIRECTED'

},

connects_to: {

type: 'connects_to',

orientation: 'UNDIRECTED'

}

}

)

YIELD
graphName AS graph, nodeProjection, nodeCount AS nodes, relationshipCount AS rels

APSP
CALL gds.allShortestPaths.stream('subAndTGWAndNet1') YIELD sourceNodeId, targetNodeId, distance
WHERE gds.util.isFinite(distance) AND sourceNodeId <> targetNodeId

WITH gds.util.asNode(sourceNodeId) AS source, gds.util.asNode(targetNodeId) AS target, distance

WHERE NONE(n IN [source, target] WHERE n:TGW ) AND NONE(n IN [source, target] WHERE n:Network )

WITH source, target, distance, [(source)-[]-(node:TGW{name:"tgw1"})-[]-(target) | node] AS tgwNodes
WHERE all(x IN tgwNodes WHERE x IS NULL)

RETURN source.name AS source, target.name AS target, distance
ORDER BY distance DESC, source ASC, target ASC

but I am getting 0 paths

2

I am not sure about this condition.

WITH source, target, distance, [(source)-[]-(node:TGW{name:"tgw1"})-[]-(target) | node] AS tgwNodes
WHERE all(x IN tgwNodes WHERE x IS NULL)

It looks like you want only those pairs of source and target nodes that do not have the specified path between them. I believe if no paths exists, the pattern comprehension will return an empty set. Only if you used an “option match” would you get a null value for node. If so, I would replace the where predicate with either “size(tgwNodes)=0” Or “not exits( (source)--(node:TGW{name:"tgw1"})--(target) )”

3

As APSP doesn't return the actual paths, it won't work to inspect whether there exists a path between the source and target nodes that goes via tgw2—there can be many paths between two nodes where one path (perhaps the shortest) does not go via tgw2 and another goes via tgw2. Even if the procedure did return the paths, if you removed the shortest paths going via tgw2, you would remove pairs of nodes that still have a solution not going via tgw2.

To get the answer you are after, just remove tgw2 in your projection:

MATCH (src:Subnet|Network|TGW)-[r:SUB_OF|CONNECT_TO]->(trg:Subnet|Network|TGW)
WHERE src.name <> "tgw2" AND trg.name <> "tgw2"
WITH gds.graph.project(
    'subAndTGWAndNet1',
    src,
    trg,
    {relationshipType: type(r)},
    {undirectedRelationshipTypes: ['*']}) AS g
RETURN g.graphName, g.nodeProjection, g.nodeCount, g.relationshipCount

You can then simplify your call to APSP like so:

CALL gds.allShortestPaths.stream('subAndTGWAndNet1') 
YIELD sourceNodeId, targetNodeId, distance
WHERE gds.util.isFinite(distance) AND sourceNodeId < targetNodeId
WITH gds.util.asNode(sourceNodeId) AS source, 
     gds.util.asNode(targetNodeId) AS target, 
     distance
WHERE source:!(TGW|Network) AND target:!(TGW|Network)
RETURN source.name AS source, target.name AS target, distance
ORDER BY distance DESC, source ASC, target ASC
4

It's giving me APSP from subnet to subnet i.e. 28 paths but I don't want those paths in which there is tgw2 in the pathway. Ex: sub2---tgw2---sub8 this path has tgw2 in the pathway so I want to remove it. I am facing problem here.
2.) If you remove WHERE src.name <> "tgw2" AND trg.name <> "tgw2" you'll get the same answers.

5

I'm not sure I understand what you are trying to solve then. None of the 28 solutions that are returned go via tgw2, as that node has been removed from the projection.

Is the problem you are trying to solve: find the shortest paths with tgw2 in the graph; then remove any solutions that include tgw2, even though it will result in some node pairs will be excluded from the results? If that is the case, you would need to add that criteria to APSP, which is not a feature of that procedure.

If you are not actually doing cost-based path finding, then perhaps you should consider using plain Cypher shortestPath, which will allow you to specify additional constraints on the path.

1 Like