Directed acyclic graph

Question

In questions like, when asked to find the edges or nodes in the DAG of following expression,

a=a+b*c-(a+b)+(b*c)

do we also consider "=" as a node and its related edges?

Comments

for this 3 address code will be

t₁ = b *c

t₂ = b + a

t₃ = t₁ - t₂

t₄ = t₃ + t₁

t₅ = t₄ + a

a = t₅

now u can draw DAG easily.

Answer 1

No, usually we don't consider "=" during DAG drawing, but in options if "=" is given then yes we have to consider it. Then no of nodes and edges also increase accordingly. 

 

DAG of the following expression: (by creating 3 Address code) 

 

 

And We can draw the DAG without creating 3-Address Code also: 

 

 

So in both the cases we are getting  ​​​​​​8 Nodes & 10 Edges.

Answer 2

No,you should not conisder "=" while finding minimum nodes,but if in options you should not find any option without "=",then you may try using "=".

Please refer 

https://gateoverflow.in/2068/gate2014-3_34?show=2068#q2068

https://cs.nyu.edu/~gottlieb/courses/2000s/2006-07-fall/compilers/lectures/lecture-14.html

Comments

Thanks :)

Answer 3

No we dont consider the equal sign , The answer for it will be , Number of Nodes = 8 , number of edges = 10.

Answer 4

NODES → 8 

EDGES → 10