Graphs — In Python

Extremely Simple Algorithms in Python #PurePythonSeries — Episode #07

Graphs are networks consisting of nodes connected by edges or arcs.

In directed graphs, the connections between nodes have a direction, and are called arcs;

in undirected graphs, the connections have no direction and are called edges.

We mainly discuss directed graphs.

Algorithms in graphs include finding a path between two nodes, finding the shortest path between two nodes, determining cycles in the graph (a cycle is a non-empty path from a node to itself), finding a path that reaches all nodes (the famous “traveling salesman problem”), and so on.

Sometimes the nodes or arcs of a graph have weights or costs associated with them, and we are interested in finding the cheapest path.

Let’s Practice Graphs with Python :)

Find The Path of A to D:

graph = {

'A': ['B', 'C'],

'B': ['C', 'D'],

'C': ['D'],

'D': ['C'],

'E': ['F'],

'F': ['C']

}

A simple function to find the path:

def find_path(graph, start, end, path=[]):

    path = path + [start]

    if start == end:

        return path

    if not start in graph:

        return None

    for node in graph[start]:

    if node not in path:

        newpath = find_path(graph, node, end, path)

     if newpath: return newpath

         return None

Running it now:

find_path(graph, 'A', 'D')

['A', 'B', 'C', 'D']

Now, Find the Path E to D:

find_path(graph, 'E', 'D')

['E', 'F', 'C', 'D']

Finding ALL PATHS:

def find_all_paths(graph, start, end, path=[]):

    path = path + [start]

    if start == end:

        return [path]

    if not start in graph:

        return []

        paths = []

    for node in graph[start]:

        if node not in path:

        newpaths = find_all_paths(graph, node, end, path)

    for newpath in newpaths:

        paths.append(newpath)

        return paths

Running:

find_all_paths(graph, 'A', 'D')

[['A', 'B', 'C', 'D'], ['A', 'B', 'D'], ['A', 'C', 'D']]

Find The Path of 0 to 4:

graph = {

'0': ['1', '2'],

'1': ['0', '3'],

'2': ['0', '3'],

'3': ['1', '2', '4', '5'],

'4': ['3'],

'5': ['3']

}

Running:

find_all_paths(graph, '0', '4')

[['0', '1', '3', '4'], ['0', '2', '3', '4']]

Find the Shortest Path of 0 to 5:

def find_shortest_path(graph, start, end, path=[]):

    path = path + [start]

        if start == end:

            return path

        if not start in graph:

            return None

    shortest = None

for node in graph[start]:

    if node not in path:

        newpath = find_shortest_path(graph, node, end, path)

        if newpath:

            if not shortest or len(newpath) < len(shortest):

                shortest = newpath

return shortest

Running:

find_shortest_path(graph, '0', '5')

['0', '1', '3', '5']

That’s All, Folks o/

print("That's it! Have a nice day! Favorite it, if you like!")

That's it! Have a nice day! Favorite it, if you like!

Until next time!

👉Jupiter notebook link :)

👉or collab link

👉git

Credits And References

Vinicius Pozzobon Borin — PhD Student at UTFPR (CPGEI/LABSC — Wireless Communications) and Professor at UNINTER (face-to-face and distance ed.)

Related Posts

00#Episode#PurePythonSeries — Lambda in Python — Python Lambda Desmistification

01#Episode#PurePythonSeries — Send Email in Python — Using Jupyter Notebook — How To Send Gmail In Python

02#Episode#PurePythonSeries — Automate Your Email With Python & Outlook — How To Create An Email Trigger System in Python

03#Episode#PurePythonSeries — Manipulating Files With Python — Manage Your Lovely Photos With Python!

04#Episode#PurePythonSeries — Pandas DataFrame Advanced — A Complete Notebook Review

05#Episode#PurePythonSeries — Is This Leap Year? Python Calendar — How To Calculate If The Year Is Leap Year and How Many Days Are In The Month

06#Episode#PurePythonSeries — List Comprehension In Python — Locked-in Secrets About List Comprehension

07#Episode#PurePythonSeries —Graphs — In Python — Extremely Simple Algorithms in Python (this one)

08#Episode#PurePythonSeries — Decorator in Python — How To Simplifying Your Code And Boost Your Function