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.
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.
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
Top comments (7)
Confused why every SDE/SWE
role requires DSA when
day-to-day mundane work
might not even need it?
I thought because most super big companies use their own framework and hence your framework knowledge wouldnt work there so it is better to test something universal which doesnt change.
Thank you for your insight. Yes so I have heard.
What I meant was that some people find it ridiculous that why do they need to know concept 'X' why they are never gonna use it. I felt the same way about graph algorithms in general.
Fair enough. I didnt meant to say youre wrong or anything
just my two cents on why we have DSA and algo based interviews
Thank you
Where to learn DSA for free? I can't afford paid courses as I am poor.
You can search up DSA series' on YouTube. There are amazing collection of tutorials.
ok thanks