Myth: DSA is Required Only To Crack Interviews #Busted | Netlist Generation Using DFS

Kaustuv K Chattopadhyay — Mon, 02 Aug 2021 21:03:47 +0000

Confused why every SDE/SWE
role requires DSA when
day-to-day mundane work
might not even need it?

You are on the right article!

In this article we will take a look at particularly interesting instance of web-dev where DFS, a well known graph algorithm fit the problem just too well.

Although day to day activities usually doesn't require such knowledge of graph algorithms, however, once in a blue moon comes about a problem, which demands an efficient solution which is next to impossible without graph theory.

Problem Statement

Given a electrical circuit annotate its nodes. 

Rules: 
1. Equipotential points must given same names. 
2. No two nodes having different potential must have same names. 
3. A node is an endpoint of an circuit element. 
For e.g. each resistor has 2 nodes marked 1 and 2 in Fig 1.
4. N nodes are given to you. The graph is given to you in terms of edges(u,v) in a graph G, where u and v are the nodes.

_Fig 1: Voltage Divider_

Analysis

We know 2 points not having a potential drop between them must lie at the same potential.

Naming nodes is very easy when you have two or more nodes in the picture joined together, and none of the adjacent nodes are connected to any other nodes. One can simply name all the adjacent nodes node_X and go about their day. No worries. Looks good. Yay!

Right?

Wrong. Only if it was that simple. * sighs *

Presenting Fig 2, where it is clearly visible that a single node might not only be connected to another node but also multiple such nodes. Which further can be connected more such nodes. All these nodes must be named the same.

_Fig 2: Astable Multivibrator_

Therefore, we must be able to figure out a way to first find all nodes connected to a particular node. Then give all these nodes the same name.

People familiar with graph theory and algorithms might be getting ideas by now ;)

So lets look at the solution now

Solution

A straight out of the wardrobe solution is Depth First Search a.k.a DFS on each unvisited node, finding out the the connected nodes recursively and naming them with node_x for each connected segment.

And just like that, a complex problem turns into a trivial application of DSA. Tada!

Here is a piece of related code from the repo. The piece of code below creates separate sets of nodes which are at the same potential. The circuit's graphical representation is made using mxgraph.

    var NODE_SETS = []
    // console.log('dfs init')
    var ptr = 1
    var mp = Array(5000).fill(0)
    NODE_SETS[0] = new Set() // Defining ground
    for(var property in list){
        if(list[property].Component === true && list[property].symbol !== 'PWR'){
            mxCell.prototype.ConnectedNode = null
            var component = list[property]
            if (component.children !== null) {
              // pins
              for (var child in component.children) {
                  var pin = component.children[child];

                  if (pin != null &&  pin.vertex === true && pin.connectable) {
                    if (pin.edges !== null || pin.edges.length !== 0) {
                      if(mp[(pin.id)] === 1){                                
                          continue                      
                      }
                      var stk = new Stack()
                      var cur_node
                      var cur_set = []
                      var contains_gnd = 0                     

                      stk.push(pin)      
                      // console.log('exploring connected nodes of', pin)                    
                      while(!stk.isEmpty()){
                          cur_node = stk.peek()
                          stk.pop();
                          mp[cur_node.id] = 1
                          cur_set.push(cur_node)
                          stk.print()
                          for (var wire in cur_node.edges) {
                            console.log(cur_node.edges[wire])
                            if (cur_node.edges[wire].source !== null && cur_node.edges[wire].target !== null) {
                              if (cur_node.edges[wire].target.ParentComponent !== null) {
                                if(cur_node.edges[wire].target.ParentComponent.symbol === 'PWR'){
                                    contains_gnd = 1
                                }
                              }
                              if(cur_node.edges[wire].target.vertex == true){
                                if (!mp[(cur_node.edges[wire].target.id)] && (cur_node.edges[wire].target.id !== cur_node.id)){
                                  stk.push(cur_node.edges[wire].target)
                                }
                              }
                              if(cur_node.edges[wire].source.vertex == true){
                                if(!mp[(cur_node.edges[wire].source.id)] && (cur_node.edges[wire].source.id !== cur_node.id)){
                                    stk.push(cur_node.edges[wire].source)
                                }
                              }
                              // Checking for wires which are connected to another wire(s), Comment out 
                              // the if conditions below if edge connections malfunction
                              var conn_vertices = [];
                              if (cur_node.edges[wire].edges && cur_node.edges[wire].edges.length > 0) {
                                for (const ed in cur_node.edges[wire].edges) {
                                  if (!mp[cur_node.edges[wire].edges[ed].id]) {
                                    conn_vertices = conn_vertices.concat(...traverseWire(cur_node.edges[wire].edges[ed], mp))
                                  }
                                }
                              }
                              if (cur_node.edges[wire].source.edge == true) {
                                if (!mp[(cur_node.edges[wire].source.id)] && (cur_node.edges[wire].source.id !== cur_node.id)) {
                                  conn_vertices = conn_vertices.concat(...traverseWire(cur_node.edges[wire].source, mp))
                                }
                              }
                              if (cur_node.edges[wire].target.edge == true) {
                                if (!mp[(cur_node.edges[wire].target.id)] && (cur_node.edges[wire].target.id !== cur_node.id)) {
                                  conn_vertices = conn_vertices.concat(...traverseWire(cur_node.edges[wire].target, mp))
                                }
                              }
                              // console.log("CONN EDGES", conn_vertices)
                              conn_vertices.forEach((elem) => {
                                stk.push(elem)
                              })
                            }
                          }
                        if(contains_gnd === 1){
                            for(var x in cur_set)
                                NODE_SETS[0].add(cur_set[x])
                        }
                          // console.log("Set of nodes at same pot:", cur_set)   
                      }
                    } 
                    if (!contains_gnd){
                        NODE_SETS.push(new Set(cur_set))
                    }
                  }
              }
            }
        }
    }

This wouldn't have been possible without the help of @kumanik5661. A big shoutout to him.

Frontend is usually not associated with data processing. However, the fact that this algorithm was run in the front-end really changed my notions on that. Frontend devs Beware!

P.S.: Feel free to visit the project repo at: https://github.com/frg-fossee/eSim-Cloud/tree/develop
Project Name: eSim-Cloud

Forem: Kaustuv K Chattopadhyay

Myth: DSA is Required Only To Crack Interviews #Busted | Netlist Generation Using DFS

You are on the right article!

Problem Statement

Analysis

Solution