> For the complete documentation index, see [llms.txt](https://csse-uwa.gitbook.io/data-warehousing-lab-sheets/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://csse-uwa.gitbook.io/data-warehousing-lab-sheets/week-12-graph-data-science/week-12-sample-solution.md).

# Week 12 Sample Solution

## A. Search Algorithms

**Scenario: Siri is currently in Arad, and she wants to drive to Bucharest.**

<figure><img src="/files/l3XKAXUbpvvcUs5jFOPA" alt=""><figcaption></figcaption></figure>

1. **What is the solution for BFS?**

Arad->Sibiu->Fagaras->Bucharest

2. **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.**

```cypher
// 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?**

```cypher
// 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.**

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

```cypher
#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`!**

```cypher
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;
```

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


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://csse-uwa.gitbook.io/data-warehousing-lab-sheets/week-12-graph-data-science/week-12-sample-solution.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.