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