In[]:=
Clear[NestGraphTagged]
In[]:=
NestGraphStep[fun_,{nodessofar_,edgesofar_,newnodes_}]:={Union[nodessofar,newnodes],Union[Flatten[Join[edgesofar,Function[n,MapIndexed[DirectedEdge[n,#1,First[#2]]&,fun[n]]]/@newnodes]]],Complement[Flatten[fun/@newnodes],nodessofar]}
In[]:=
NestGraphTagged[fun_,init_List,t_Integer]:=Graph[Nest[NestGraphStep[fun,#]&,{{},{},init},t][[2]]]
In[]:=
NestGraphTagged[fun_,init_List,t_Integer,styles_]:=With[{g=NestGraphTagged[fun,init,t]},Graph[Style[#[[1]],#[[2]]]&/@Transpose[{EdgeList[g],styles[[EdgeTags[g]]]}]]]
In[]:=
NestGraph[xIf[x[[1]]<2,{1,x[[2]]},{x-{1,1},x-{2,1}}],{{10,10}},4,VertexLabelsAutomatic]
Out[]=