Week 12 Sample Solution

A. Search Algorithms

1. What is the difference between the above DFS and the DFS in lecture notes?

Refer to Week 11 lecture slides

1. Test the above DFS algorithm on the graph provided in Slide 45 (Example: DFS)

Test it by yourself.

Secnoria: Siri is currently in Arad and she wants to drive to Bucharest.

1. What is the solution for BFS?

Arad->Sibiu->Fagaras->Bucharest

1. What is the solution for A*? The heuristic function is the straight-line distance to Bucharest.

Arad->Sibiu->Rimnicu Vilcea->Pitesti->Bucharest

B. Neo4j

Task 2

Write a LOAD CSV statement that imports the roads into your database. Remember, the Countries have already been created, so after LOAD CSV you'll need to run a MATCH statement to find the countries listed in each row of roads.csv, and only CREATE a road between those two countries. Don't forget the distance property, which should also be a float.

// Load data from CSV
LOAD CSV WITH HEADERS FROM "file:///roads.csv" AS row
MATCH (country1:Country), (country2:Country)
WHERE country1.name = row.country_1 AND country2.name = row.country_2
CREATE (country1)-[r:ROAD {distance: toFloat(row.distance)}]->(country2)

Task 4

Task 4.1

Change the query to be a depth-first search (DFS) and run it. Are the results the same, or different - and why?

// DFS
MATCH (source: Country {name: "Spain"})
CALL gds.dfs.stream("Countries", {
    sourceNode: source
    })
YIELD path
RETURN path

The results between BFS and DFS will differ in the order they visit nodes.

Task 4.2

Try running the A* source-target shortest path algorithm to find the shortest path between Spain and India.

#Clean the environment
CALL gds.graph.drop('Countries')

#Create a new project
CALL gds.graph.project('Transport','Country',{ROAD:{orientation: 'UNDIRECTED'}},
{relationshipProperties:'distance',
nodeProperties:['latitude','longitude']})

#Running the A* algorithm
MATCH (source: Country {name: 'Spain'}), (target: Country {name: 'India'})
CALL gds.shortestPath.astar.stream('Transport', {
    sourceNode: source,
    targetNode: target,
    latitudeProperty: 'latitude',
    longitudeProperty: 'longitude',
    relationshipWeightProperty: 'distance'
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs, path
RETURN
    index,
    gds.util.asNode(sourceNode).name AS sourceNodeName,
    gds.util.asNode(targetNode).name AS targetNodeName,
    totalCost,
    [nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS nodeNames,
    costs,
    nodes(path) AS path
ORDER BY index

Task 4.3

Create relationships of the type MINST between the Canada and every country reachable from Canada. Write a Cypher query to display the minimum spanning tree. Hint: the relationship type is MINST, not ROAD!

MATCH (c:Country{name:'Canada'})
CALL gds.beta.spanningTree.write('Transport', {
  sourceNode: id(c),
  relationshipWeightProperty: 'distance',
  writeRelationshipType: 'MINST',
  writeProperty: 'writeCost'
})
YIELD preProcessingMillis, computeMillis, writeMillis, effectiveNodeCount
RETURN preProcessingMillis,computeMillis, writeMillis, effectiveNodeCount;

MATCH (c1:Country)-[m:MINST]->(c2:Country) RETURN c1, m, c2