# R/graph_utils.R In kirillseva/ruigi: Ruigi

#### Defines functions topological_sort

```## [Who would have thought that data structures are useful](http://en.wikipedia.org/wiki/Topological_sorting)
## Topological sorting is the key to proper orchestrating of the tasks.
## It provides a linear order in which tasks should be executed, and also
## is useful if we want to plot a dependency graph.
topological_sort <- function(graph) {
stopifnot(is(graph, 'graph'))
sorted <- list(nodes = list(), edges = graph\$edges)
graph <- graph

g_visit <- function(idx) {
if (! is.null(graph\$nodes[[idx]]\$mark)) {
if (graph\$nodes[[idx]]\$mark == "temporary") stop("You have cyclic dependencies!")
if (graph\$nodes[[idx]]\$mark == "marked") return()
}
graph\$nodes[[idx]]\$mark <<- "temporary"
for (i in seq_along(graph\$edges)) {
if (graph\$edges[[i]]\$from == graph\$nodes[[idx]]\$id) {
to <- graph\$edges[[i]]\$to
for (j in seq_along(graph\$nodes)) {
if (graph\$nodes[[j]]\$id == to) g_visit(j)
}
}
}
graph\$nodes[[idx]]\$mark <<- "marked"
sorted\$nodes <<- append(list(graph\$nodes[[idx]]), sorted\$nodes)
}

repeat {
node_i <- (function (nodes) {
for (i in seq_along(nodes)) {
if (!is.null(nodes[[i]]\$mark)) {
if (nodes[[i]]\$mark != "marked") return(i)
} else return(i)
}
})(graph\$nodes)
## no unmarked nodes left
if (is.null(node_i)) break
## visit(node)
g_visit(node_i)
}

class(sorted) <- c("graph", class(sorted))
sorted
}
```
kirillseva/ruigi documentation built on May 18, 2017, 8:36 p.m.