2
$\begingroup$

In a graph tree, is there any "smart/existing/efficient" algorithm to find linear segments of defined length?

For example given a tree graph:

g = {1 -> 2, 2 -> 4, 3 -> 6, 4 -> 8, 6 -> 12, 1 -> 3, 2 -> 5, 3 -> 7, 
   4 -> 9};
TreePlot[g, VertexLabeling -> True]

Tree graph

How can one find all linear segments of length 4. In this example this would be

1 2 4 8
1 2 4 9
1 3 6 12
2 1 3 7
2 1 3 6
9 4 2 5
...

This is probably a common problem, but I guess I have not yet found the right keywords for google. The naive implementation would be to visit every node, then recursively try to get four nodes away and delete all duplicated segments at the end...

$\endgroup$
5
  • 1
    $\begingroup$ What you call "linear segment" is called a path in graph theory. You are looking for all paths of length three/four (depending on whether you're counting edges or nodes). $\endgroup$
    – Raphael
    Commented Oct 7, 2014 at 5:31
  • 1
    $\begingroup$ By the way, if you are looking to implement this in Mathematica, there's a new function FindPath in Mathematica 10 that should be helpful. $\endgroup$
    – Juho
    Commented Oct 7, 2014 at 5:55
  • $\begingroup$ @Raphael thanks, now I did find similar problem solved in Perl (perlmonks.org/?node_id=522257). Will try to decipher:) $\endgroup$
    – Ajasja
    Commented Oct 7, 2014 at 8:12
  • $\begingroup$ @Juho Yup, but it finds all paths between two vertices. The final implementation will be in python, but mathematica was the quickest way to generate an image. $\endgroup$
    – Ajasja
    Commented Oct 7, 2014 at 8:14
  • $\begingroup$ @Ajasja You can also specify the function to find all paths of length $k$ between a pair of vertices. Using this, you can find all paths of length $k$. But this is a bit off-topic :) $\endgroup$
    – Juho
    Commented Oct 7, 2014 at 9:14

2 Answers 2

3
$\begingroup$

Idea: Root the tree in an arbitrary node. For every node, count

  • paths in its subtrees,
  • paths that start in a subtree and end in the root, and
  • paths that start in one subtree, traverse the root and end in another subtree.

That is, for a given node $v$ with children $u_1, \dots, u_m$, the number $p(v,k)$ of paths of length $k$ (counting nodes) in the subtree $T_v$ rooted in $v$ is

$\qquad\displaystyle\begin{align*} p(v,k) &= \sum_{i=1}^m \biggl[ p(u_i,k) \biggr] \\ &\ + \sum_{i=1}^m \biggl[ p_r(u_i,k-1) \biggr] \\ &\ + \sum_{i=1}^{m-1} \sum_{j=i+1}^m \sum_{l=1}^{k-2} \biggl[ p(u_i,l) \cdot p(u_j,k-1-l) \biggr] \end{align*}$

for $k \geq 2$; we anchor the recurrence in $p(v,1) = 1$ for all $v$. For the paths ending in the root, we get the (simpler) recurrence

$\qquad\begin{align*} p_r(v,k) &= \sum_{i=1}^m p_r(u_i,k-1) \end{align*}$

which also anchors in $p_r(v,1) = 1$.

These recurrences immediately imply a recursive algorithm (computing both simultaneously).

The runtime is in "$\Theta(m^2k)$" per node of degree $m$; hence, on trees with finitely bounded degree, the algorithm runs in time $\Theta(nk)$. Otherwise, it may take time $\Theta(n^2k)$ (e.g. on stars).

$\endgroup$
1
  • $\begingroup$ Okay, this algorithm only counts the paths; I hope it's clear how to adapt it so that the actual paths are constructed (read $+$ as $\cup$ and $\cdot$ as concatenation, and anchor in $p_{(r)}(v,1) = [v]$). As long as the node labels are pairwise distinct, this never generates the same path (as label sequence) twice. $\endgroup$
    – Raphael
    Commented Oct 7, 2014 at 5:54
2
$\begingroup$

Any linear segment goes up for some length, then goes down. (Once you start going down, you can't go back up again, because you'd re-visit a vertex you'd already visited).

So, any linear segment of length four consists of an upwards-heading segment of length $\ell$ (where $0 \le \ell \le 4$), followed by a downwards-heading segment of length $4-\ell$. Therefore, the following algorithm works:

  • For each vertex $v$ in the tree:

    • For each $\ell \in \{0,1,2,3,4\}$:

      • For each upwards-heading segment $s$ of length $\ell$ that has $v$ as its top vertex:

        • For each upwards-heading segment $t$ of length $4-\ell$ that has $v$ as its top vertex:

          • Output the concatenation of $s$ and $t$ (i.e., the reverse of $s$, followed by $t$).

To make this work, we need some way to enumerate all upwards-heading segments of length $\ell$ that end at a vertex $v$. This can be done by enumerating all children that are $\ell$ levels below $v$; for each such child $c$, we can go upwards $\ell$ times (following parent pointers), and that gives such a segment. Moreover, every such segment can be obtained in this way.

The overall running time will be $O(n^2)$, where $n$ is the number of vertices in your tree.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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