How to run a Python BFS Algorithm on a dataset in Memgraph

How can I run the Breadth-First Search (BFS) Algorithm in python in Memgraph on karate club friendship network dataset?

1 Like

Hi @anberarif :smile:

First, you need a driver to connect to Memgraph from a Python script. I suggest the open-source library GQLAlchemy (official documentation) as it contains a lot of useful features for developing graph applications in Python.

Once you connect with GQLAlchemy and load the dataset through Memgraph Lab, you can run the BFS algorithm using the Cypher query language. For example:

results = memgraph.execute_and_fetch(
    "MATCH path=({id: "0"})-[:FRIENDS_WITH *bfs]-({id: "33"}) RETURN path;"
)

You can find more BFS examples in the documentation.

Hi @idespot, thank you for your support.

I’m stuck at the point where we return the results after loading the dataset. I am uploading the result via the following command;

with open('dataset.csv') as dataset:
    csv_reader = csv.reader(dataset, delimiter=' ')
    for row in csv_reader:
        memgraph.execute(f"""MERGE (p1:Person {{id: {row[0]}}})
                             MERGE (p2:Person {{id: {row[1]}}})
                             CREATE (p1)-[:FRIENDS_WITH]->(p2)""")

The above command reads a dataset (karate.csv) and creates a connection (edge) between each pair.
The head of the dataset is as follows:

image

results = memgraph.execute_and_fetch(
    """
    MATCH path=({id: "23"})-[:FRIENDS_WITH *bfs]-({id: "34"}) RETURN path;
    """
)

Now, when I try to run the BFS algorithm using the above command as you mentioned in the reply, it returns an empty list. Kindly have a look at it and let me know how can I solve it.

1 Like

Are you sure that your dataset was loaded correctly and that it contains the nodes with ids “23” and “34”? Can you maybe share the dataset.csv file which you are using to import the data?

Also, the variable results contains a generator which means that you have to call list(results) in order to get a list of the results returned from the database.

Hi @idespot the problem was resolved and I got the results.
Thank you :smile:

Hello @anberarif,
Can you please share the python script here as I want to implement the DFS algorithm on a csv dataset? I’ll appreciate your help. Thanks

Hi @asadiqbal :grinning:
Below is my python script and the dataset on which I applied the BFS algorithm.

1 Like

Thanks @anberarif,
It was a great help :slight_smile:

Hi @idespot,

I checked we use below to execute BFS algorithm:

results = memgraph.execute_and_fetch(
“”"
MATCH path=((p1 {id: 1})-[edge_list:FRIENDS_WITH *bfs]-(p2 {id: 34})) RETURN path;
“”"
)

What do we use to implement Depth-first search (DFS) graph algorithm? I checked memgraph documentation but couldn’t find anything. Please guide.

1 Like

Did you try relationship traverslals without specifying BFS as the method? This should result in a DFS traversal of the nodes and relationships. You can also specify the depth using the parameters minHops and maxHops:

MATCH ({name: 'United Kingdom'})<-[:LIVING_IN*1..2]-(n)
RETURN n;

Here is a link to the documentation.