Question: Take a set of formulas and order them based on their dependencies. If they are cyclic in nature Exit If not display the dependency order. Test for some big formula sets, the below examples will give some hint. Use Efficient Data structures to store the formula. Use Efficient techniques to find dependencies.
• Examples 1 :
INPUT C = F + G – H A = B + C + D + E B = I + J * K / L
Output Valid Formula – Dependency order is A = B + C + D + E B = I + J * K / L C = F + G – H
• Examples 2 :
INPUT C = F + G – H A = B + C + D + E B = A + J * K / L
Output Is not a valid Formula, Cyclic in Nature (As A is dependent on B and B is dependent on A) Approach Note:
Storage: the input in a map of pair. A pair consist of vector of dependent nodes and formula.
unordered_map<Node, pair<vector<string>,string formula>>
Example B=I+J +k
C=L*M/N
A=G+H-B
| Node | Vec[0] | Vec[1] | vec[2] | Formula |
| B | I | J | K | B = I+J+K |
| C | L | M | N | C = L*M/N |
| A | G | H | B | A=G+H-B |
Detect the cycle :
DFS traversal is implemented and visited nodes are kept track of
Visited node map looks like this:
unordered_map<string node, bool >
| B | false |
| I | false |
| J | false |
| K | false |
| C | false |
| L | false |
| M | false |
| N | false |
| A | false |
| G | false |
| H | false |
Every time a node is visited it is made true in the table.
When a node has being traversed and a node is already marked as visited then there is a cycle detected.
Formula dependency list:
A visited list like the one above is created for formula dependency. I have assumed time complexity to be a higher priority than space complexity.
List to store the dependency order:
| A | B | C |
To compute the list DFS traversal is used.
Sample Inputs tested:
Cycle:
A=B+C
C=D-W
B=K/L
D=J-A
D=J-A
A=B+C
C=D-W
B=K/L
A=B+X B=C+Y C=D+W+Z D=A+I+H
No Cycle:
A=B+X
B=C+Y
C=D+W+Z
D=I+H
E=D+H
E=A+B+C Y=U+V X=L+1 L=F-G R=E+Y+X
B=I+J C=L*M A=G+H-B+C
D=J+W A=M+B+C+V C=D+X B=K/L
Source Code:
#include<formuladepedency.h>
using namespace std;
typedef std::pair<vector<string>, string> pairListFormula;
typedef unordered_map<string,pairListFormula> mapFormula;
typedef unordered_map<string,bool> mapVisitedNodes;
typedef list<string> listDepedencies;
typedef list<string>::iterator listDepedenciesItr;
class graphDS
{
listDepedencies m_listFormulaDependency;
mapFormula m_mapFormulaGraph;
mapVisitedNodes m_mapVisitedNodesForCycle;
mapVisitedNodes m_mapVisitedNodesForDepedency;
string m_strMainParent;
public:
void removeOperators(char *);
bool detectCycleInGraph(string , string,int);
bool hasCycle();
void depedencyList();
void computeDepedency(string, string ,int);
void RecomputeList(string,string, int);
void PrintDepedencyList();
};
//Prints the list with formula and depdency below
void graphDS::PrintDepedencyList()
{
string strFormula;
for (listDepedenciesItr it=m_listFormulaDependency.begin(); it != m_listFormulaDependency.end(); ++it)
{
//Look up the node in map
mapFormula::iterator itr = m_mapFormulaGraph.find(*it);
strFormula = get<1>(itr->second);//gets the formula
cout<<strFormula<<endl;
}
}
//Keeps the dependency list up to date
void graphDS::RecomputeList(string node,string parent, int flag)
{
listDepedencies::iterator listItNode;
listDepedencies::iterator listItParent;
//Node is visited inside the same parent
if((m_mapVisitedNodesForDepedency[node] == true)&&(flag == 0))//already present
{
if(m_mapFormulaGraph.find(node) != m_mapFormulaGraph.end())
{
listDepedencies tempList = m_listFormulaDependency;
listItNode = std::find(m_listFormulaDependency.begin(), m_listFormulaDependency.end(),node );
listItParent = std::find(m_listFormulaDependency.begin(), m_listFormulaDependency.end(),parent );
int posNode = distance(m_listFormulaDependency.begin(), listItNode);
int posParent = distance(m_listFormulaDependency.begin(), listItParent);
//Parent is being inserted after the child node then splice the list and attach
//before child node
if(posParent > posNode)
{
//insert at listITnode, from m_listFormulaDependency to m_listFormulaDependency
//in the range from listItParent to end of m_listFormulaDependency
m_listFormulaDependency.splice(listItNode,m_listFormulaDependency,listItParent,m_listFormulaDependency.end());
}
}
}
else
{
//Mark node as visited
m_mapVisitedNodesForDepedency[node] = true;
if(m_mapFormulaGraph.find(node) != m_mapFormulaGraph.end())
{
//Add only the formulas that exist in the input and not all nodes
m_listFormulaDependency.push_back(node);
}
}
}
//Depth first search of nodes to compute dependencies
void graphDS::computeDepedency(string node, string parentNode,int flag)
{
vector<string> vec1 ;
string strParent;
vector<string>::iterator vec1Itr ;
if(flag == 1)
{
m_strMainParent = node;
}
RecomputeList(node,parentNode,flag);
mapFormula::iterator itr = m_mapFormulaGraph.find(node);
//if node found in formula map
if(itr != m_mapFormulaGraph.end())
{
strParent = itr->first;
vec1 = get<0>(itr->second);//gets the vectr
if(vec1.size()>0)
{
for(vec1Itr = vec1.begin(); vec1Itr <vec1.end();++vec1Itr)
{
if((m_mapVisitedNodesForDepedency[*vec1Itr]) == false)
{
computeDepedency(*vec1Itr,strParent,0);
}
else
{
RecomputeList(*vec1Itr,m_strMainParent,0);
}
}
}
}
}
//Iterate through the storage map and compute dependency if not visited
void graphDS::depedencyList()
{
for(auto it = m_mapFormulaGraph.begin();it!=m_mapFormulaGraph.end();++it)
{
if(m_mapVisitedNodesForDepedency[it->first] == false)
{
computeDepedency(it->first,"",1);
}
}
}
//Depth first search of nodes to check for cycles
bool graphDS::detectCycleInGraph(string node,string strParentNode,int flag)
{
m_mapVisitedNodesForCycle[node] = true;
mapFormula::iterator itr = m_mapFormulaGraph.find(node);
vector<string> vec1 ;
string strParent;
vector<string>::iterator vec1Itr ;
if(flag == 1)
{
m_strMainParent = node;
}
//if node found in formula map
if(itr != m_mapFormulaGraph.end())
{
strParent = itr->first;
vec1 = get<0>(itr->second);//gets the vectr
if(vec1.size()>0)
{
//mapFormula::iterator tempItr = m_mapFormulaGraph.find(vec1.back());
//Iterate through the children of the node
for(vec1Itr = vec1.begin(); vec1Itr <vec1.end();++vec1Itr)
{
mapFormula::iterator tempItr;
if((m_mapVisitedNodesForCycle[*vec1Itr]) == false)
{
if(detectCycleInGraph(*vec1Itr,strParent,0) == true)
{
return true;
}
}
//flag is used to indicate if the computation is happening within a
//single node which results in a cycle.
else if((*vec1Itr != strParent)&&(flag == 0))
{
tempItr = m_mapFormulaGraph.find(*vec1Itr);
if(tempItr != m_mapFormulaGraph.end())
{
vector<string> vec2 = get<0>(tempItr->second);
string nodeTraversed = vec2.back();
if(m_mapVisitedNodesForCycle[nodeTraversed] ==false)
{
//return false;
return true;
}
}
}
}
}
}
return false;
}
//Iterate through the storage map and compute dependency if not visited
bool graphDS::hasCycle()
{
for(auto it = m_mapFormulaGraph.begin();it!=m_mapFormulaGraph.end();++it)
{
if(m_mapVisitedNodesForCycle[it->first] == false)
{
if(detectCycleInGraph(it->first,"",1))
{
return true;
}
}
}
return false;
}
// Function to remove all spaces from a given string
void removeSpaces(char *str)
{
int count = 0;
for (int i = 0; str[i]; i++)
if (str[i] != ' ')
str[count++] = str[i];
str[count] = '\0';
}
//Input: A = B+ C
//output: out = {a,b,c}
//Insertion of the input into a map.
//unordered_map<Node, pair<vector<string>,string formula>>
void graphDS::removeOperators(char *input)
{
int length = (int)strlen(input);
string lhs;
string leftOperand;
vector<string> out;
//mapFormula mapformulaGraph;
mapFormula::iterator it;
mapVisitedNodes::iterator mapitrVisitedNodes;
//Remove white spaces to avoid nodes being wrongly inserted
removeSpaces(input);
for(int i=0;i<length;i++)
{
if((isalpha(input[i]))&&(i != length-1))
{
leftOperand += input[i];
}
else
{
//Node becomes the key in the map
if(input[i] == '=')
{
//insert parent LHS node
lhs = leftOperand;
leftOperand.clear();
}
//End character of the formula will not have operator
if(isalpha(input[i])&&(i==length-1))
{
leftOperand += input[i];
}
if(leftOperand.length() != 0 )
{
string formula(input); //convert char* to string
//Look for the entry in map if not present
it = m_mapFormulaGraph.find(lhs);
out.push_back(leftOperand);
if( it != m_mapFormulaGraph.end() )
{
//update the existing map
m_mapFormulaGraph[lhs] = make_pair(out,formula);
//out.clear();
}
else{
//insert the operands without operator as children of
//parent node
pairListFormula tempPair = make_pair(out,formula);
m_mapFormulaGraph.insert(make_pair(lhs,tempPair));
//out.clear();
//Create visited node vector for cycle detection and
//dependency computation. Initialize all node values to
//false to indicate not visited
m_mapVisitedNodesForCycle.insert(make_pair(lhs,false));
m_mapVisitedNodesForDepedency.insert(make_pair(lhs,false));
}
mapitrVisitedNodes = m_mapVisitedNodesForCycle.find(leftOperand);
if( mapitrVisitedNodes == m_mapVisitedNodesForCycle.end() )
{
vector<string> vecChildren;
m_mapVisitedNodesForCycle.insert(make_pair(leftOperand,false));
m_mapVisitedNodesForDepedency.insert(make_pair(leftOperand,false));
}
leftOperand.clear();
}
}
}
}
int main(int argc,char *argv[])
{
try {
graphDS g;
bool isCycle;
if(argc == 2)
{
cout<<argv[1]<<endl;
}
else
{
for(int i =1;i<argc;i++)
{
vector<string> output;
//Creates a graph data structure
g.removeOperators(argv[i]);
}
isCycle = g.hasCycle();
if(isCycle)
{
printf("Cycle is detected\n");
}
else
{
g.depedencyList();
g.PrintDepedencyList();
}
}
}
catch (exception& e) {
cout<<"An Exception occurred:"<<e.what()<<endl;
}
return 0;
}