Tarjan’s Cycle Enumeration Algorithm – Python Implementation

from copy import deepcopy

G = []
cycles = []

point_stack = []
marked = []
marked_stack = []

def tarjan(s, v):
    global cycles
    f = False
    point_stack.append(v)
    marked[v] = True
    marked_stack.append(v)
    for w in G[v]:
        if w < s:
            G[w] = []
        elif w == s:
            points_keeper = list(deepcopy(point_stack))
            if points_keeper not in cycles:
                cycles.append(points_keeper)
            f = True
        elif marked[w] == False:
            g = tarjan(s,w)
            f = f or g

    if f == True:
        while marked_stack[len(marked_stack) - 1] != v:
            u = marked_stack.pop()
            marked[u] = False
        marked_stack.pop()
        marked[v] = False

    point_stack.pop()
    return f

def entry_tarjan(G_):
    global G, cycles, marked, marked_stack, point_stack
    G = []
    cycles = []

    point_stack = []
    marked = []
    marked_stack = []

    G = deepcopy(G_)

    marked = [False for x in xrange(0, len(G_))]

    for i in range(len(G)):
        tarjan(i, i)
        while marked_stack:
            u = marked_stack.pop()
            marked[u] = False

    return cycles

Tarjan’s Cycle Enumeration Algorithm – Go Implementation

package main

import "fmt"

var (
	G            [][]int
	point_stack  []int
	marked       []bool
	marked_stack []int
)

func main() {
	//Example graph - adjacency list
	G = [][]int{[]int{1}, []int{10}, []int{0}, []int{0}, []int{3}, []int{8}, []int{9}, []int{4, 5}, []int{2}, []int{6}, []int{7}}
	entry_tarjan(G)
}

func entry_tarjan(G [][]int) {
	marked = make([]bool, len(G))

	for i := 0; i < len(G); i++ {
		tarjan(i, i)
		for len(marked_stack) > 0 {
			u := marked_stack[len(marked_stack)-1]
			marked_stack = marked_stack[:len(marked_stack)-1]
			marked[u] = false
		}
	}
}

func tarjan(s int, v int) bool {
	f := false
	point_stack = append(point_stack, v)
	marked[v] = true
	marked_stack = append(marked_stack, v)

	for _, w := range G[v] {
		cb := make(chan bool, len(G[v]))
		go branch(s, v, w, cb)
		f = <-cb
	}

	if f == true {
		for marked_stack[len(marked_stack)-1] != v {
			u_ := marked_stack[len(marked_stack)-1]
			marked_stack = marked_stack[:len(marked_stack)-1]
			marked[u_] = false
		}
		marked_stack = marked_stack[:len(marked_stack)-1]
		marked[v] = false
	}

	point_stack = point_stack[:len(point_stack)-1]
	return f
}

func branch(s int, v int, w int, cb chan bool) {
	f_ := false
	if w < s {
		G[w] = []int{}
	} else if w == s {
		fmt.Println(point_stack)
		f_ = true
	} else if marked[w] == false {
		g_ := tarjan(s, w)
		f_ = f_ || g_
	}

	cb <- f_
}

SAS LOCF For Multiple Variables

It is often necessary to replace missing measurements with the closest, previous measurement. This technique is referred to as LOCF (last observation carried forward).

In this example, we will create a dataset with 4 columns: subject ID, visit number, body weight, and systolic blood pressure.

data have;
	input ID VISIT WT SBP;
	cards;
1 10 85 125
1 20 84 .
1 30 86 .
1 40 . 130
1 50 . 128
1 60 85 .
2 10 . 110
2 20 90 .
2 30 91 .
2 40 91 123
2 50 . .
2 60 . 130
;
run;
Input dataset, with subject ID, visit number, body weight, and systolic blood pressure

Thereafter, we will sort the dataset to ensure it is in the order we expect. Never assume that your input will be appropriately sorted.

proc sort data=have;
	by id visit;
run;

Now we will define 2 macro variables, which are simply lists of variables. The first contains the original variables available in the dataset, which will not be altered, and the second names the variables which will contain the LOCF values.

%let origvars = %str(WT  SBP);
%let locfvars = %str(WT_ SBP_);

This brings us to our final block of code. The lists of variables defined above are loaded into arrays and a loop performs the LOCF operation across all the variables defined.

data want(drop = j);
	set have;
	by id visit;

	/*Create arrays of the variable lists*/
	array orig[*] &origvars.;
	array locf[*] &locfvars.;
	retain 	      &locfvars.;

	do j = 1 to dim(orig);
		if first.id then do;
			/*Set a placeholder value for initial missings*/
			if orig(j) = . then locf(j) = -99;
		end;

		/*Replace retained value with latest non-missing value*/
		if not missing(orig(j)) then locf(j) = orig(j);
	end;
run;
The final dataset with LOCF’ed variables, WT_ and SBP_