Tutorial #2. Graphs with Cycles.

Tutorial updated to v.0.0.2

Let's solve the following coding interview problem:

You are given a directed graph in the form of a text string:

"andy>ben ben>carol carol>den katy>andy ben>carol andy>katy carol>carol"

Graph nodes are marked with words. The graph is directed, and is not necessary connected. Find if this graph has loops in it.
You can assume that the input string is always correct.

One of possible graph interview problems.

First let's define our data structures:

using sys {
    WeakArray
    Array
}
class Node {
    connections = WeakArray(Node)
    isVisited = false
    isActive = false
    name = ""
}
class Graph {
    nodes = Array(Node)
}

In this example the Graph object owns a collection of Nodes that arbitrary reference one another:

The Graph instance owns its nodes. That's why we use here a sys_Array - an array of owning @-pointers.
While the Nodes reference each other with non-owning &-references and they can be stored in the sys_WeakArray instance.

Our code should consist of two tasks:

• build a graph from a text,
• scan the graph in search of cycles.

So our main function will be:

log(Graph.fromStr("andy>ben ben>carol carol>den katy>andy ben>carol andy>katy carol>carol").hasLoop()
    ? "has some loop"
    : "has no loops");

Let's define a fromStr method:

class Graph {
    fromStr(s str) this { // 1
        byNames = WeakMap(String, Node) // 2
        in = s.cursor()  // 3
        getOrCreateNode = `term { // 4
            name = in.getTill(term) // 5
                   : ^fromStr // 6
            byNames[name] :  // 7
            nodes.append(Node.init(name)).{ // 8
                byNames[name] := &_  // 9
            }
        }
        loop { // 10
            f=getOrCreateNode('>') // 11
            t=getOrCreateNode(' ') // 12
            f.connections.append(&t) // 13
            false // 14
        }
    }    
}

In this code the fromStr is an initializer method returning this {line 1}.

First we create a byName {2} - temporary hash-map string->weak pointer to Node. We'll use it only while building the graph, so it's ok to have it temporary.

We also take a cursor that scans and parses out input string {3}.

Then we define a lambda-function {4} that reads a node name {5}, and if it failed (at the end of line, wich is checked with :-operator), it immediately leaves the whole fromStr function with far-break operator {6}. We store the result of string parsing in the variable name of type str (getTill returns optional-string, and the following :-operator removes this optionality converting absence of value into returning from parsing)

Then it checks if node with this name already exists (7) and again uses ":"-else operator which return result of array lookup out of getOrCreateNode lambda or executes its right-hand-side expression, which creates a new node instance, initializes it with newly extracted name {8} and before returning it use the colombo-operator exprA.{ exprB } takes its weak pointer and registers it the byNames map {9}.

This concludes the getOrCreateNode lambda (which parses name, breaks the loop, looks-up or creates, initializes and registers new node).

The main content of fromStr method - loops {10} while it can fetch pairs of nodes {11} and sets their interconnections {12}. The line {13} exists because of an error in the unreachable code detector in the compiler. It'll soon be fixed.

Now it's time to find some loops in our graph.
We'll need to scan all graph nodes, and try DFS from each node with keeping track of the nodes in the active path. If we see that active node again - we are in the loop.
To protect from multiple visit of each node, we can mark the node as already visited.

So, let's add one method to the graph:

class Graph {
    ...
    hasLoop() bool {
        nodes.contain\_.hasLoop()      // 1
    }

In line {1} we call the contain method of Array and pass it a lambda.

we can use another syntax as well:

• nodes.contain(`i { i.hasLoop() }) // pass lambda block with named parameter inside parameters list
• nodes.contain(`i i.hasLoop()) // single expression instead of block
• nodes.contain(\{_.hasLoop()}) // implicit lambda parameter, this works for single-parameter lambdas
• nodes.contain() `i i.hasLoop() // last lambda parameter can be passed outside of parameters parenthesis
• nodes.contain`i { i.hasLoop() } // the only lambda parameter can be passed instead of parameters parenthesis
• nodes.contain\_.hasLoop() // combine single lambda parameter passing with implicit lambda parameter

the contain method calls its predicate for each element and checks its result.
The contain method returns either:

• true if some predicate invocation returned true,
• or false when the container is scanned to the end.

In line {1} we check if the element's hasLoop method detects a loop.

The Node.hasLoop does the actual work:

class Node {
    hasLoop() bool {
        isActive ? ^hasLoop=true // 1
        isVisited ? ^hasLoop=false // 2
        isVisited := isActive := true // 3
        (connections.contain\_.hasLoop()) // 4
        .{ isActive := false } // 5
    }
}

In line {1} we check if the Node is seen in the active path, and if it is, it's the loop.
In line {2} we avoid going inside the already visited nodes. Operator `?` acts as if. Operator `^` breaks out of the function body with the result.
In line {3} we mark our node both as visited and in the active path. And of course we later remove isActive in line {5}. Using colombo "expr.{ actions }" operator. Colombo operator returns result of expr but before return executes actions, sometimes on this value, sometimes doing something else. This operator is equivalent to (`v {actions; v})(expr). It creates a lambda returning its own parameter, and immediately calls this lambda with expr result.
Line {4} is a recursive scan by all outgoing connections. It follows the already seen logic of Graph.hasLoop.

The full source code:

using sys {
    String
    WeakArray
    Array
    WeakMap
    log
}
using utils { existsInRange }
using string
using array

class Node {
    connections = WeakArray(Node)
    isVisited = false
    isActive = false
    name = ""

    init(s str) this {
        name := s
    }
    hasLoop() bool {
        isActive ? ^hasLoop=true
        isVisited ? ^hasLoop=false
        isVisited := isActive := true
        (connections.contain\_.hasLoop())
        .{ isActive := false }
    }
}

class Graph {
    nodes = Array(Node)

    fromStr(s str) this {
        byNames = WeakMap(String, Node)
        in = s.cursor()
        getOrCreateNode = `term {
            name = in.getTill(term) : ^fromStr
            byNames[name] :
            nodes.append(Node.init(name)).{
                byNames[name] := &_
            }
        }
        loop {
            f=getOrCreateNode('>')
            t=getOrCreateNode(' ')
            f.connections.append(&t)
            false
        }
    }    
    hasLoop() bool {
        nodes.contain(\{_.hasLoop()})
    }
}

log(Graph.fromStr("andy>ben ben>carol carol>den katy>andy ben>carol andy>katy carol>carol").hasLoop()
    ? "Has some loop"
    : "Has no loops"
)

This tutorial covered:

• Classes
• Arbitrary data structures.
• Owning pointers, weak references and their corresponding arrays.
• Usage of generics
• Lambdas
• Some operations on "optional" values, ? :
• Using strings as input streams.