6

I am trying to illustrate DFS with tikz like http://www.cse.unsw.edu.au/~billw/Justsearch1.gif does.

I have come up with

\documentclass[border=10pt]{standalone}

\usepackage{forest}

\begin{document}

\begin{forest}
for tree={circle,draw,fill=white,align=center}
[$a$
    [$b$
        [$d$
            [$h$]
            [,phantom]
        ]
        [$e$
            [$i$]
            [$j$]
        ]
    ]
    [$c$
        [$f$
            [,phantom]
            [$k$]
        ]
        [$g$]
    ]
]
\end{forest}

\end{document}

but I don't know how to draw the lines/arrows across the tree like it's done in the picture.

7

The answers posted so far do the job. However, they do not make full use of the way Forest works. Forest already knows how to walk a tree depth-first or breadth-first. Indeed, it knows several other ways to walk a tree as well. Moreover, if required, further paths through the tree can be defined as long nodewalk steps and then used in the same way.

This answer illustrates a way to trace a search path through your tree using each of the six methods Forest knows out-of-the-box:

  1. depth-first (tree)
  2. breadth-first (tree breadth-first)
  3. children-first (tree children-first)
  4. depth-first reversed (tree reversed)
  5. breadth-first reversed (tree breadth-first reversed)
  6. children-first reversed (tree children-first reversed)

This requires a little work to set things up in the preamble but makes it very easy to trace paths through trees afterwards.

Here is the final code to trace the six demonstration paths:

\begin{treerow}
  \tracetree
  \tracetree[tree breadth-first]
  \tracetree[tree children-first]
\end{treerow}
\begin{treerow}
  \tracetree[tree reversed]
  \tracetree[tree breadth-first reversed]
  \tracetree[tree children-first reversed]
\end{treerow}

tree tracing

treerow is just a throw-away environment to enable me to make rows of trees with standalone. It doesn't do anything.

\newenvironment{treerow}{}{}
\standaloneenv{treerow}

\tracetree[] is just a wrapper which repeats your tree for different search paths.

\newcommand*\tracetree[1][tree]{%
  \begin{forest}
    circles tree,
    tracing tree=#1,
    [$a$
      [$b$
          [$d$
              [$h$]
              [,phantom]
          ]
          [$e$
              [$i$]
              [$j$]
          ]
      ]
      [$c$
          [$f$
              [,phantom]
              [$k$]
          ]
          [$g$]
      ]
    ]
  \end{forest}
}

Note that there should really be a % following \end{forest} but Okular really, really doesn't like the PDF if I include it. (I don't know why but its response makes my eyes go funny.)

The substantive stuff is all in the style

  • tracing tree=<nodewalk step i.e. search path>

circles tree is just your style with circles etc.

Here's the configuration:

\forestset{%

We use a keylist to hold the list of nodes in the search path.

  declare keylist register={through},
  through={},

Here's your style.

  circles tree/.style={%
    for tree={circle, draw, fill=white, align=center},
  },

Here's tracing tree.

  tracing tree/.style={%

We wait until the tree is parsed so Forest knows what nodes there are.

    delay={%

#1 is the argument specifying the search path which is a long nodewalk step.

      for #1={%

We walk the tree in the specified order, adding each node to our keylist unless it is a phantom node, when we want to skip it.

        if phantom={}{through+/.option=name},
      }
    },

Wait again. We could do this earlier, but no real reason to.

    before drawing tree={%

We set things up so that Forest will do some tikz stuff after the tree is drawn. This works through the nodes in our keylist, through, and draws a dashed arrow between each node and the previous one (except when there is no previous one, of course).

      tikz+/.wrap pgfmath arg={%
        \foreach \i [count=\j, remember=\i as \k] in {##1} \ifnum\j>1 \draw [densely dashed, -Stealth] (\k.west) -- (\i.west)\fi;
      }{(through)}
    },
  }

And that's it.

}

Obviously, this could be fine-tuned to improve the spacing etc., but using what Forest already knows about search paths through trees should save a great deal of work in specifying them.

Complete code:

\documentclass[border=10pt]{standalone}
\usepackage{forest}
\usetikzlibrary{arrows.meta}
\forestset{%
  declare keylist register={through},
  through={},
  circles tree/.style={%
    for tree={circle, draw, fill=white, align=center},
  },
  tracing tree/.style={%
    delay={%
      for #1={%
        if phantom={}{through+/.option=name},
      }
    },
    before drawing tree={%
      tikz+/.wrap pgfmath arg={%
        \foreach \i [count=\j, remember=\i as \k] in {##1} \ifnum\j>1 \draw [densely dashed, -Stealth] (\k.west) -- (\i.west)\fi;
      }{(through)}
    },
  }
}
\newcommand*\tracetree[1][tree]{%
  \begin{forest}
    circles tree,
    tracing tree=#1,
    [$a$
      [$b$
          [$d$
              [$h$]
              [,phantom]
          ]
          [$e$
              [$i$]
              [$j$]
          ]
      ]
      [$c$
          [$f$
              [,phantom]
              [$k$]
          ]
          [$g$]
      ]
    ]
  \end{forest}
}
\newenvironment{treerow}{}{}
\standaloneenv{treerow}
\begin{document}
\begin{treerow}
  \tracetree
  \tracetree[tree breadth-first]
  \tracetree[tree children-first]
\end{treerow}
\begin{treerow}
  \tracetree[tree reversed]
  \tracetree[tree breadth-first reversed]
  \tracetree[tree children-first reversed]
\end{treerow}
\end{document}
  • I was waiting for you to show up with this solution. :) – Alan Munn Oct 3 '16 at 2:49
  • @AlanMunn Why? I mean, why didn't you post this solution in that case? I'm afraid it was too tempting to ignore this question since the desired function is pretty much what Forest does already. – cfr Oct 3 '16 at 16:08
  • I didn't post this solution because I don't have anywhere near your facility with the more sophisticated workings of forest. I knew that it could be done this way, but my quick attempt didn't didn't work, and I knew you'd come through. :) Bounty on the way! – Alan Munn Oct 3 '16 at 16:14
  • @AlanMunn I'm not sure about that. You do things in Forest I can't. However, I see what you mean: 'this solution' means 'this approach' rather than 'this implementation'. Actually, I initially tried to do something else, but I couldn't make it work. Then I thought of this way as a workaround. Eventually I realised that this was actually better because my original idea wouldn't account for the phantom nodes properly. So a bit circuitous. – cfr Oct 3 '16 at 16:19
  • I have tried this, but it does not work. I am using ShareLaTeX, so at first I thought the preinstalled package was outdated, but I have tried adding the newest forest package to my document (to override the preinstalled package), but I still get errors. I get these errors: pastebin.com/9xAJbM8T – mortensen Dec 30 '16 at 7:56
4

You can refer to forest node with (!r) for root and (!1),(!2) for nodes in level 1 with anticlockwise direction. For level 2 you can refer to nodes with (!11), (!12), and so on.

Here an attempt with some help from the calc library.

\documentclass[border=10pt]{standalone}
\usepackage{forest}
\usetikzlibrary{arrows.meta,calc}
\begin{document}

\tikzset{-->/.style={dashed,->,arrows=-Latex},
         refract1/.style={to path={-- ++(-0.5,-.5)-- (\tikztotarget)}},
         refract2/.style={to path={-- ($(\tikztotarget)+(120:7mm)$)--(\tikztotarget)}}}

\begin{forest}
for tree={circle,draw,fill=white,align=center,edge={arrows=-Latex}}
[$a$
    [$b$
        [$d$
            [$h$]
            [,phantom]
        ]
        [$e$
            [$i$]
            [$j$]
        ]
    ]
    [$c$
        [$f$
            [,phantom]
            [$k$]
        ]
        [$g$]
    ]
]
\path [-->]
          (!r.west) edge (!1.north)
               (!1) edge (!2)
           (!2.200) edge ($(!11)+(120:7mm)$)
($(!11)+(120:7mm)$) edge[refract1] (!11)
              (!11) edge (!12)
              (!12) edge (!21)
              (!21) edge (!22)
          (!22.220) edge[refract2] (!111)
             (!111) edge (!121) 
             (!121) edge (!122)
             (!122) edge (!212);
\end{forest}

\end{document}

enter image description here

3

You can name the nodes of the tree and then use the names in \draw commands, like this.

\documentclass[border=10pt]{standalone}
\usepackage{forest}
\begin{document}
\begin{forest}
for tree={circle,draw,fill=white,align=center}
[$a$,name=a
    [$b$,name=b
        [$d$,name=d
            [$h$,name=h]
            [,phantom]
        ]
        [$e$,name=e
            [$i$,name=i]
            [$j$,name=j]
        ]
    ]
    [$c$,name=c
        [$f$,name=f
            [,phantom]
            [$k$,name=k]
        ]
        [$g$,name=g]
    ]
]
\draw[->,dotted,thick,relative,red] (a) to[out=-20,in=200] (b);
\begin{scope}[->,dashed,thick,blue]
  \draw ([shift={(-0.1,0.1)}]a.north west) -- ([shift={(-0.1,0.1)}]b.north west);
  \draw ([shift={(-0.1,0.1)}]b.north west) -- ([shift={(-0.1,0.1)}]d.north west);
\end{scope}
\end{forest}
\end{document}

enter image description here

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.