algorithms.graphs

get_edges(graph)

Function for calculating number of edges

Parameters:graph – graph representation as Example: {1: {2: 1, 3: 5}, 2: {3: 2}, 4: {1: 2}} Returns:edges of the graph

get_nodes(graph)

Function for calculating number of nodes in the graph

Parameters:graph – graph representation as Example: {1: {2: 1, 3: 5}, 2: {3: 2}, 4: {1: 2}} Returns:nodes of the graph

num_of_edges(graph)

Function for calculating number of edges

Parameters:graph – graph representation as Example: {1: {2: 1, 3: 5}, 2: {3: 2}, 4: {1: 2}} Returns:number of the edges in the graph

num_of_nodes(graph)

Function for calculating number of nodes in the graph

Parameters:graph – graph representation as Example: {1: {2: 1, 3: 5}, 2: {3: 2}, 4: {1: 2}} Returns:number of nodes in the graph

prepare_direct_graph(edges)

Function for converting list of edges to dict graph representation

Parameters:edges – list of tuples, example: [(1,2), (2,3)] Returns:that represent graph Return type:Defaultdict(list)

Examples

>>> prepare_direct_graph([(1, 2), (3, 4), (2, 4), (2, 3)])
defaultdict(list, {1: [2], 2: [1, 3, 4], 3: [2, 4], 4: [2, 3]})

prepare_undirect_graph(edges)

Function for converting list of edges to dict graph representation

Parameters:edges – list of tuples, example: [(1,2), (2,3)] Returns:that represent graph Return type:Defaultdict(list)

Examples

>>> prepare_undirect_graph([(1, 2), (3, 4), (2, 4), (2, 3)])
defaultdict(list, {1: [2], 2: [1, 3, 4], 3: [2, 4], 4: [2, 3]})

prepare_weighted_direct_graph(edges)

Function for conveting list of edges with weights to dict graph representation :param edges: list of tuples, example [(1, 2, 3), (3, 2, 1)]; [(node_a, node_b, weight)]

Returns:

>>> prepare_weighted_direct_graph([(1, 2, 1), (4, 1, 2), (2, 3, 2), (1, 3, 5)])
defaultdict(dict, {1: {2: 1, 3: 5}, 2: {3: 2}, 4: {1: 2}})

prepare_weighted_undirect_graph(edges)

Function for conveting list of edges with weights to dict graph representation :param edges: list of tuples, example [(1, 2, 3), (3, 2, 1)]; [(node_a, node_b, weight)]

Returns:

>>> prepare_weighted_undirect_graph([(1, 2, 1), (4, 1, 2), (2, 3, 2), (1, 3, 5) ])
defaultdict(<class 'dict'>, {1: {2: 1, 4: 2, 3: 5}, 2: {1: 1, 3: 2}, 4: {1: 2}, 3: {2: 2, 1: 5}})

reverse_graph(graph)

Function for reverting direction of the graph

Parameters:graph – graph representation as Example: [(1, 2), (3, 4), (2, 4), (2, 3)] Returns:reversed graph

Examples

>>> reverse_graph({1: [2], 2: [1, 3, 4], 3: [2, 4], 4: [2, 3]})
defaultdict(<class 'list'>, {2: [1, 3, 4], 1: [2], 3: [2, 4], 4: [2, 3]})

reverse_weighted_graph(graph)

Function for reverting direction of the graph (weights still the same)

Parameters:graph – graph representation as Example: {1: {2: 1, 3: 5}, 2: {3: 2}, 4: {1: 2}} Returns:reversed graph

Examples

>>> reverse_weighted_graph({1: {2: 1, 3: 5}, 2: {3: 2}, 4: {1: 2}})
defaultdict(<class 'dict'>, {2: {1: 1}, 3: {1: 5, 2: 2}, 1: {4: 2}})

BFS

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’) and explores the neighbor nodes first, before moving to the next level neighbours. [Wikipedia]

Worst-case performance: O(V + E) = O(b^d)

Worst-case space complexity O(V) = O(b^d)

https://wikipedia.org/wiki/Breadth-first_search

bfs_iterative(graph, root)

Iterative version of the BFS algorithm

Parameters:

• graph – dict representation of the graph
• root – start point

Returns:

in order of visiting vertices

Return type:

list

Examples:

DFS

Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’) and explores the neighbor nodes first, before moving to the next level neighbours. [Wikipedia]

Worst-case performance: O(V + E) = O(b^d)

Worst-case space complexity O(V) = O(b^d)

https://wikipedia.org/wiki/Breadth-first_search

bfs_iterative(graph, root)

Iterative version of the BFS algorithm

Parameters:

• graph – dict representation of the graph
• root – start point

Returns:

in order of visiting vertices

Return type:

list

Examples:

Dijkstra

Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later [Wikipedia]

Worst-case Performance: O(|E|+|V| log |V|)

dijkstra(graph, start, target)

Solves shortest path problem using Dijkstra algorithm :param graph: graph representation :param start: start node :param target: target node

Returns:distance between start and target nodes Return type:int

Examples

>>> graph = prepare_weighted_undirect_graph(
[(1, 2, 7), (1, 3, 9), (1, 6, 14), (6, 3, 2), (6, 5, 9), (3, 2, 10), (3, 4, 11),
(2, 4, 15), (6, 5, 9), (5, 4, 6)])

>>> dijkstra(graph, 1, 6)
11

Bidirectional Dijkstra

Bidirectional search is a graph search algorithm that finds a shortest path from an initial vertex to a goal vertex in a directed graph. It runs two simultaneous searches: one forward from the initial state , and one backward from the goal, stopping when the two meet in the middle. [Wikipedia]

bidi_dijkstra(graph, start, target)

Calculate shortest path via Dijkstra algorithm, with bidirectional optimization which means that we start from target and start points and swith between them each step

Parameters:

• graph – graph representation
• start – start node
• target – target node

Returns:

lengths of the shortest path between start and target nodes

Return type:

int

Examples: >>> graph = prepare_weighted_undirect_graph( [(1, 2, 7), (1, 3, 9), (1, 6, 14), (6, 3, 2), (6, 5, 9), (3, 2, 10), (3, 4, 11), (2, 4, 15), (6, 5, 9), (5, 4, 6)])

>>> dijkstra(graph, 1, 6)
11

Cycle detection (DFS)

AStar

class AStar(n, adj, cost, x, y)

Bases: object

clear()

potential(v, t)

query(s, t)

visit(q, v, dist, measure)

readl()

Bellman-Ford (shortest path with negative arbitrage)

Kruskal

Bellman-Ford (with negative cycle detection)

Bipartite

In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V. Vertex sets U and V are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles. [Wikipedia]

bipartite(graph)

Function checks if graph is bipartite

Parameters:graph – graph representation Returns:True if bipartite , False otherwise Return type:bool

BST check

Function tor check if the tree is correct Binary Search Tree (BST)

check_if_bst(node, mini=-inf, maxi=inf)

Check if the given tree is Binary Search Tree (BST)

Parameters:

• node – root node of the Tree. node arg must have .left, .right and .data variables
• mini – min value - should be omitted
• maxi – max value - should be omitted

Returns:

bool - True if it’s BST and False if not

Examples

Precondition:

>>> class Node:
...     def __init__(self, data):
...         self.data = data
...         self.left = None
...         self.right = None
>>> root = Node(4)
>>> root.left = Node(2)
>>> root.right = Node(6)
>>> root.left.left = Node(1)
>>> root.left.right = Node(3)
>>> root.right.left = Node(5)
>>> root.right.right = Node(7)

Example itself:

>>> check_if_bst(root)
True

Strongly connected components

In the mathematical theory of directed graphs, a graph is said to be strongly connected or diconnected if every vertex is reachable from every other vertex.

class StronglyConnected(graph)

Bases: object

strongly_connected_components()

Function finds, and return list of SCC in the graph

Returns:SCC Return type:list

Examples

>>> graph = prepare_direct_graph([(0, 2), (2, 1), (1, 0), (0, 3), (3, 4)])
>>> StronglyConnected(graph).strongly_connected_components()
[[0, 1, 2], [3], [4]]

Topological sort

In the field of computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. [Wikipedia]

class TopologicalSort(edges)

Bases: object

sort()

Function do a topological sorting Returns: topologically sorted list of vertices