Graph algorithms using python

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Implementation of graph algorithms in Python.

License

vsaveris/graph-algorithms

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Implementation of graph algorithms in python (file: graphalgorithms.py )

• Depth-first search (DFS): DFS algorithm is an algorithm for revealing a wealth of information about a graph G = (V,E). The time complexity of the algorithm is O(|V|+|E|).
• Breadth-first search (BFS): BFS algorithm is an algorithm for finding the shortest paths in any graph G = (V,E) whose edges have unit length. The time complexity of the algorithm is O(|V|+|E|).
• Dijkstra’s Algorithm: Dijkstra’s algorithm is an algorithm for finding the shortest paths in any graph G = (V,E) whose edges lengths are positive numbers. The time complexity of the algorithm is O((|V|+|E|)log|V|), when using a priority queue.
• Bellman-Ford Algorithm: Bellman-Ford algorithm is an algorithm for finding the shortest paths in any graph G = (V,E) whose edges lengths can be also negative numbers. The time complexity of the algorithm is O((|V||E|).
• Kruskal Algorithm: Kruskal algorithm is an algorithm for finding MSTs in an undirected graph G = (V,E). The time complexity of the algorithm is O((|E|log|V|).
• Prim’s Algorithm: Prim’s algorithm is an algorithm for finding MSTs in an undirected graph G = (V,E). The time complexity of the algorithm is O((|V|+|E|)log|V|).

Inside the demo folder there is a demonstration script ( demoga.py ), including usage examples for the GraphAlgorithms class.

$python demoga.py -h usage: demoga.py [-h] -a algorithm Demonstration script for the Graph Algorithms optional arguments: -h, --help show this help message and exit -a algorithm demonstration algorithm Supported values for 'algorithm' are ('dfs', 'bfs', 'dijkstra', 'bellman_ford', 'kruskal', 'prim') Example: python demoga.py -a dijkstra 

The graphs used in each algorithm case for the demonstration purposes are shown below.

In the running example, the DFS algorithm reveals all the connected components of the given graph together with the first discovery and last departure times for each node. The output of the algorithm is:

$python demoga.py -a dfs DFS output for the given graph: node 'A': first_discovery_time = 1,last_departure_time = 10, connected_component = 1 node 'B': first_discovery_time = 2,last_departure_time = 3, connected_component = 1 node 'C': first_discovery_time = 11,last_departure_time = 22, connected_component = 2 node 'D': first_discovery_time = 12,last_departure_time = 21, connected_component = 2 node 'E': first_discovery_time = 4,last_departure_time = 9, connected_component = 1 node 'F': first_discovery_time = 23,last_departure_time = 24, connected_component = 3 node 'G': first_discovery_time = 16,last_departure_time = 19, connected_component = 2 node 'H': first_discovery_time = 13,last_departure_time = 20, connected_component = 2 node 'I': first_discovery_time = 5,last_departure_time = 8, connected_component = 1 node 'J': first_discovery_time = 6,last_departure_time = 7, connected_component = 1 node 'K': first_discovery_time = 17,last_departure_time = 18, connected_component = 2 node 'L': first_discovery_time = 14,last_departure_time = 15, connected_component = 2 connected component 1: ['A', 'B', 'E', 'I', 'J'] connected component 2: ['C', 'D', 'H', 'L', 'G', 'K'] connected component 3: ['F'] 

In the running example, the BFS algorithm calculates all the shortest paths from the starting node B . The output of the algorithm is:

$python demoga.py -a bfs BFS shortest paths for the given graph, where starting node is 'B': Shortest path from 'B' to 'A' is: ['B', 'A'] with cost 1 Shortest path from 'B' to 'C' is: ['B', 'C'] with cost 1 Shortest path from 'B' to 'D' is: ['B', 'A', 'S', 'D'] with cost 3 Shortest path from 'B' to 'E' is: ['B', 'A', 'S', 'E'] with cost 3 Shortest path from 'B' to 'S' is: ['B', 'A', 'S'] with cost 2 

Dijkstra Demonstration Graph

In the running example, the Dijkstra’s algorithm calculates all the shortest paths from the starting node A . The output of the algorithm is:

$python demoga.py -a dijkstra Dijkstra shortest paths for the given graph, where starting node is 'A': Shortest path from 'A' to 'B' is: ['A', 'C', 'B'] with cost 3 Shortest path from 'A' to 'C' is: ['A', 'C'] with cost 2 Shortest path from 'A' to 'D' is: ['A', 'C', 'B', 'D'] with cost 5 Shortest path from 'A' to 'E' is: ['A', 'C', 'B', 'E'] with cost 6 

Bellman-Ford Demonstration Graph

In the running example, the Bellman-Ford algorithm calculates all the shortest paths from the starting node S . The output of the algorithm is:

$python demoga.py -a bellman_ford Bellman-Ford shortest paths for the given graph, where starting node is 'S': Shortest path from 'S' to 'A' is: ['S', 'G', 'F', 'A'] with cost 5 Shortest path from 'S' to 'B' is: ['S', 'G', 'F', 'A', 'E', 'B'] with cost 5 Shortest path from 'S' to 'C' is: ['S', 'G', 'F', 'A', 'E', 'B', 'C'] with cost 6 Shortest path from 'S' to 'D' is: ['S', 'G', 'F', 'A', 'E', 'B', 'C', 'D'] with cost 9 Shortest path from 'S' to 'E' is: ['S', 'G', 'F', 'A', 'E'] with cost 7 Shortest path from 'S' to 'F' is: ['S', 'G', 'F'] with cost 9 Shortest path from 'S' to 'G' is: ['S', 'G'] with cost 8 

Kruskal Demonstration Graph

In the running example, the Kruskal algorithm finds one of the MSTs for the input graph. The output of the algorithm is:

$python demoga.py -a kruskal Kruskal Minimum Spanning Tree, for the given graph: MST: MST total weight: 14 

Prim’s Demonstration Graph

In the running example, the Prim’s algorithm finds one of the MSTs for the input graph. The output of the algorithm is:

$python demoga.py -a prim Prim's Minimum Spanning Tree, for the given graph: MST: MST total weight: 14 

1. Introduction to Algorithms, 3rd Edition. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Chapter VI, Graph Algorithms
2. Algorithms. S. Dasgupta, C. Papadimitriou, U. Vazirani. Chapter 3, Decompositions of Graphs
3. Algorithms. S. Dasgupta, C. Papadimitriou, U. Vazirani. Chapter 4, Paths in Graphs
4. Algorith Design, 1st Edition. J. Kleinberg, E. Tardos. Chapter 3, Graphs
5. Algorithms. S. Dasgupta, C. Papadimitriou, U. Vazirani. Chapter 5, Greedy Algorithms

About

Implementation of graph algorithms in Python.

Источник

Python — Graph Algorithms

Graphs are very useful data structures in solving many important mathematical challenges. For example computer network topology or analysing molecular structures of chemical compounds. They are also used in city traffic or route planning and even in human languages and their grammar. All these applications have a common challenge of traversing the graph using their edges and ensuring that all nodes of the graphs are visited. There are two common established methods to do this traversal which is described below.

Depth First Traversal

Also called depth first search (DFS),this algorithm traverses a graph in a depth ward motion and uses a stack to remember to get the next vertex to start a search, when a dead end occurs in any iteration. We implement DFS for a graph in python using the set data types as they provide the required functionalities to keep track of visited and unvisited nodes.

Example

class graph: def __init__(self,gdict=None): if gdict is None: gdict = <> self.gdict = gdict # Check for the visisted and unvisited nodes def dfs(graph, start, visited = None): if visited is None: visited = set() visited.add(start) print(start) for next in graph[start] - visited: dfs(graph, next, visited) return visited gdict = < "a" : set(["b","c"]), "b" : set(["a", "d"]), "c" : set(["a", "d"]), "d" : set(["e"]), "e" : set(["a"]) >dfs(gdict, 'a')

Output

When the above code is executed, it produces the following result −

Breadth First Traversal

Also called breadth first search (BFS),this algorithm traverses a graph breadth ward motion and uses a queue to remember to get the next vertex to start a search, when a dead end occurs in any iteration. Please visit this link in our website to understand the details of BFS steps for a graph.

We implement BFS for a graph in python using queue data structure discussed earlier. When we keep visiting the adjacent unvisited nodes and keep adding it to the queue. Then we start dequeue only the node which is left with no unvisited nodes. We stop the program when there is no next adjacent node to be visited.

Example

import collections class graph: def __init__(self,gdict=None): if gdict is None: gdict = <> self.gdict = gdict def bfs(graph, startnode): # Track the visited and unvisited nodes using queue seen, queue = set([startnode]), collections.deque([startnode]) while queue: vertex = queue.popleft() marked(vertex) for node in graph[vertex]: if node not in seen: seen.add(node) queue.append(node) def marked(n): print(n) # The graph dictionary gdict = < "a" : set(["b","c"]), "b" : set(["a", "d"]), "c" : set(["a", "d"]), "d" : set(["e"]), "e" : set(["a"]) >bfs(gdict, "a")

Output

When the above code is executed, it produces the following result −

Источник