Tree Growth based Graph Algorithms

These class of algorithms takes a Graph as input, and generates Tree, which consists of some of edges of input Graph, which are selected according to particular criteria. Some examples are

  • DFS
  • BFS
  • Minimum Spanning Tree Problem (Prim’s and Kruskal’s Algorithm)
  • Single Source Shortest Path Problem (Dijkstra’s Algorithm)

Standard import statement

In [6]:
import openanalysis.tree_growth as TreeGrowth

Implementation Notes

  • The algorithm should be implemented as a method
  • The algorithm works on a networkx graph
  • All algorithms start building the tree from a given source, But if source is not given, select source as the first node of Graph
def algorithm_name(G,source = None):
    if source is None:
        source = G.nodes()[0]
    # do other work now
  • As soon as node v is visited from node u, yield the tuple containing them
# Assume that visiting is done
yield (u,v)
  • To make your life easy, some data structures which comes handy while working with Graphs are included in OpenAnalysis.base_data_structures

Example - Dijkstra’s Algorithm

Dijkstra’s Algorithm finds minimum spanning tree of a graph in greedy manner. The algorithm is given below

Dijkstra's Algorithm

Dijkstra’s Algorithm


Since we need a Priority Queue here, Let’s import it

In [7]:
from openanalysis.base_data_structures import PriorityQueue

Now, Let’s implement the algorithm

In [8]:
def dijkstra(G, source=None):                 # This signature is must
    if source is None: source = G.nodes()[0]  # selecting root as source
    V = G.nodes()
    dist, prev = {}, {}
    Q = PriorityQueue()
    for v in V:
        dist[v] = float("inf")
        prev[v] = None
        Q.add_task(task=v, priority=dist[v])
    dist[source] = 0
    Q.update_task(task=source, new_priority=dist[source])
    visited = set()
    for i in range(0, len(G.nodes())):
        u_star = Q.remove_min()
        if prev[u_star] is not None:
            yield (u_star, prev[u_star])    # yield the edge as soon as we visit the nodes
        for u in G.neighbors(u_star):
            if u not in visited and dist[u_star] + G.edge[u][u_star]['weight'] < dist[u]:
                dist[u] = dist[u_star] + G.edge[u][u_star]['weight']
                prev[u] = u_star
                Q.update_task(u, dist[u])

Note how implementation looks similiar to the algorithm, except the if block, which is used to yield the edges.

Visualizing the Algorithm

  • apply_to_graph(fun): Creates Random Geometric Graph of 100 nodes and applies fun on it to build the tree. After building the tree, it shows original graph and the tree side by side
  • tree_growth_visualizer(fun): Creates Random Geometric Graph of 100 nodes and applies fun on it to build the tree. Saves the animation of building the tree in output/ folder

Random Geometric Graph

Random Geometric Graph is created using two parameters. Number of nodes n, and radiuus r. n points are chosen randomly on plane. The edge between 2 nodes is created if and only if the distance between 2 nodes is less than r

import networkx as nx
G = nx.random_geometric_graph(100,2.3) # n,r
pos = nx.get_node_attribute('pos')
In [10]:

After executing


go to output/ directory to see mp4 files

Example File

You can see more examples at Github