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!

Get J3’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

👉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