0
$\begingroup$

I am trying to find a better way to find all leaf nodes in my undirected waypoint graph.

This is how I define a leaf node:

A leaf node is a node that is never part of a cycle and so has to meet one of these two criteria:

  1. It has only one connection

Or

  1. The node's total connections minus the total leaves connected to said node is less than 2

Here is a visual example:

enter image description here

My current approach doesn't feel too efficient, I loop through all nodes and mark those nodes that meet criteria 1.

I loop again and again and mark every node that meets criteria 2. I do this until no further nodes are marked - then I exit the function.

Here is the logic:

int count;
do
{
    count = 0;
    foreach (node in allNodes)
    {
        //leaves is a hashset of marked nodes
        if (leaves.Contains(node)) // already marked as leaf
            continue;

        if (IsLeaf(node))
        {
            leaves.Add(nodes);
            count = 1;
        }
    }
} while (count > 0);

My IsLeaf function has:

bool IsLeaf(node)
{
    total = node.Connections;

    // only has 1 or less connections, so it must be a leaf
    if (total < 2) 
        return true;

    //count all leaves connected to the node
    totalLeaves = 0;
    foreach (segment in node)
    {
        node2 = segment.GetOtherNode();
            
        if (_leaves.Contains(node2))
            totalLeaves ++;
    }

    //A node is a leaf when it has less than 2 connections to non-leaf nodes
    return (total - totalLeaves ) < 2;
}

I am wondering if there is a more performant way to go about this other than looping all the nodes over and over until all leaves have been found?

$\endgroup$
4
  • $\begingroup$ I'm not sure I understand the definition of "leaf". Part of the problem might be that you are using standard terminology with a different meaning, and part of the problem is that the definition seems recursive. Can check that the following formal definition is correct? Given a graph $G$ on $n$ vertices, define $L_1$ as the set of vertices of degree $1$. Then, for $i > 1$, iteratively define $L_i$ as a function of $L_{i-1}$. In particular, $L_i$ contains all vertices that have exactly $0$ or $1$ neighbors not in $L_{i-1}$ (notice that $L_i \supseteq L_{i-1}$). A "leaf" is a vertex in $L_n$. $\endgroup$
    – Steven
    Apr 30 at 8:18
  • $\begingroup$ @Steven well i am self taught so i don't know the notation you are using so well, but i presume criteria 2 you are most confused with since criteria 1 is quite obvious? If a node N has 5 connections to other nodes, and 4 of these other nodes are known to be leaf nodes, it must be the case then that N is also a leaf node - that is what criteria 2 basically means. You will find in the image the leaf node that has 5 connections fits this criteria. $\endgroup$
    – WDUK
    Apr 30 at 8:29
  • $\begingroup$ I am trying to say that, since $N$ is a leaf node, this will possibly cause a bunch of other nodes to become leaves too. In turn, these new leaves will create even more leaves, etc... (of course this process of adding leaves will eventually stop). I want to make sure that this is what you intended. Think, for example of a graph that is a path. All the nodes are leaves: Only the endpoints of the path satisfy condition 1, then their neighbors satisfy condition $2$, then their neighbors' neighbors also satisfy condition $2$, and so on until every node becomes a leaf. $\endgroup$
    – Steven
    Apr 30 at 8:32
  • $\begingroup$ Yeah if you mark a leaf its possible the nodes connecting to it will also become leaves as well by the 2nd criteria. My algorithm currently works starting from singularly connected nodes - then works its way "inwards" if that makes sense. It iterates through all the nodes again and again. Which is where I feel the performance could be improved. $\endgroup$
    – WDUK
    Apr 30 at 8:34

1 Answer 1

1
$\begingroup$

You can compute the set of "leaves" in linear time. I will color the vertices of $G$ as either white or black. Initially all vertices are white. At the end of the algorithm the leaves will be exactly the vertices colored black. I will additionally associate, to each vertex $v$, a quantity $w(v)$ representing its "white degree", i.e., the current number of white neighbors of $v$. Initially each $w(v)$ is initialized to the degree of $v$. Finally, we keep a "bucket" (e.g., a list) $B$ containing all white vertices $v$ such that $w(v) \le 1$ (this is initialized to contain all vertices with degree $0$ or $1$).

The algorithm repeats the following until $B$ is empty. It extracts one arbitrary vertex $v$ from $B$, and colors $v$ black. Then, it examines each edge $(v,u)$ incident to $v$ and decreases $w(u)$ by $1$. If $u$ is white and $w(u)$ is now exactly $1$ (i.e., the value of $w(v)$ just went from $2$ to $1$), it also adds $u$ to $B$.

To upper bound the time complexity notice that, except for constant multiplicative and additive factors, it is upper bounded by the number of vertices of $G$ (to initialize $w(\cdot)$ and $B$, and to account for the time spent extracting and inserting each vertex into $B$, if needed) plus the overall number of times the edges $(v,u)$ are examined. This latter quantity can be at most twice the number of edges of $G$.

Edit: (the complement of) what you want has a name. You are interested in the vertices not in the $2$-core of $G$. Wikipedia even has a similar algorithm to the one above.

$\endgroup$
1
  • 1
    $\begingroup$ The number of edges examined is in $O(n)$, since there are only $O(n)$ edges outside the 2-core and only those edges have to be examined. So the algorithm runs in linear time $O(n)$ if the degrees $w(v)$ can be determined in $O(1)$ each (not by counting). So in this case, the total running time is in $O(n)$. $\endgroup$
    – Bastian J
    Apr 30 at 20:49

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.