Recursion with DAGs

(Textbook: Section 16.2)

Definitions

Graph

A graph is a set of nodes, with edges between some of them.

Directed Graph

A directed graph is a set of nodes with arrows between some of them.

Path

A path in a directed graph is a sequence of nodes, where each node is connected to the next node by an arrow:

\(n_1 \rightarrow n_2 \rightarrow \ldots \rightarrow n_m\)

Cycle

A cycle is a path that begins and ends at the same node.

Directed Acyclic Graph (DAG)

A directed acyclic graph is a directed graph that has no cycles.

Note: Sometimes DAGS are called trees, but in the mathematics of graph theory a tree is a slightly different thing.

Parent/Child/Descendent

If there is an arrow from node \(a\) to node \(b\):

\(a \rightarrow b\)

then \(b\) is said to be a child of \(a\) and \(a\) is said to be a parent of \(b\).

If there is a path from node \(a\) to node \(b\), then \(b\) is said to be a descendant of \(a\).

Root/Leaf

In a directed graph, a root node is a node that has no parents. A leaf node is a node that has no children.

Assumptions

In our work with DAGs, we will assume that the DAG has finitely many nodes, and that there is exactly one root node.

Weighted Graphs

A weighted graph is a graph where each node is assigned a numerical value, called its weight.

We will work with weighted directed acyclic graphs (WDAGs).

Example of a WDAG

Recursive Structure

In a WDAG, any node together will all of its descendants forms another WDAG.

Accordingly, you can readily determine many features of a WDAG using recursive functions.

Making WDAGS

Packages Needed

library(bcscr)
library(DiagrammeR)

Making a Random WDAG

The function make_val_tree() from the bcscr packages make WDAGS with a bit of randomness to them.

Example

Code

tr <- make_val_tree(
  min_children = 1,
  max_children = 3,
  min_depth = 3,
  values = -2:5,
  seed = 4949
)

tr

               levelName
1  R: 5                 
2   °--a: -2            
3       ¦--a: 3         
4       ¦   ¦--a: 2     
5       ¦   ¦   ¦--a: -2
6       ¦   ¦   °--b: 1 
7       ¦   ¦--b: 4     
8       ¦   °--c: -1    
9       °--b: 4         
10          °--a: 2

library(DiagrammeR)
plot(tr)

Node Properties

Each node in a WDAG has two properties:

value: the numerical value associated with the node;
children: a list of the nodes that are its children (NULL if the node is a leaf).

Examples

tr$children

$`a: -2`
          levelName
1 a: -2            
2  ¦--a: 3         
3  ¦   ¦--a: 2     
4  ¦   ¦   ¦--a: -2
5  ¦   ¦   °--b: 1 
6  ¦   ¦--b: 4     
7  ¦   °--c: -1    
8  °--b: 4         
9      °--a: 2

Examples

tr$children[[1]]$children

$`a: 3`
      levelName
1 a: 3         
2  ¦--a: 2     
3  ¦   ¦--a: -2
4  ¦   °--b: 1 
5  ¦--b: 4     
6  °--c: -1    

$`b: 4`
  levelName
1  b: 4    
2   °--a: 2

Recursive Functions for WDAGS

Basic Idea

When you want to compute something recursively in a WDAG:

Leaves will be base cases;
for other nodes, we make recursive calls on their children.

Example: Max-Weight Path

Problem: Given a WDAG, what path from the root node to a leaf has the maximum sum of weights?

Weight of the max-weight path is \(5 + (-2) + 3 + 4 = 10.\)

Max-Path Function

max_path <- function(node) {
  if (is.null(node$children)) return(node$value)
  kids <- node$children
  path_values <- numeric(length = length(kids))
  for (i in 1:length(kids)) {
    path_values[i] <- Recall(kids[[i]])
  }
  return(node$value + max(path_values))
}

max_path(node = tr)

[1] 10

Example: Max-Weight Subtree

A sub-tree of a DAG is a node of the DAG together with all of its descendants.

Problem: For any given WDAG, find a sub-tree whose total weight is as large as possible.

A DAG

Let’s make a WDAG with which to work:

tr2 <- make_val_tree(
  min_children = 2,
  max_children = 2, 
  min_depth = 3,
  values = -8:10, seed = 5050
)

The Max-Weight Subtree

The Recursive Function

max_subtree <- function(node) {
  if (is.null(node$children)) {
    return(
      list(
        sum = node$value,
        m = node$value
      )
    )
  }
  kids <- node$children
  st_vals <- top_vals <- numeric(length = length(kids))
  for (i in 1:length(kids)) {
    res <- Recall(kids[[i]])
    st_vals[i] <- res$sum
    top_vals[i] <- res$m
  }
  return(
    list(
      sum = node$value + sum(st_vals),
      m = max(node$value + sum(st_vals), top_vals)
    )
  )
}

Try It Out

max_subtree(tr2)

$sum
[1] 68

$m
[1] 75

The weight of the entire WDAG is 68.
The weight of the maximal sub-tree is 75.