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:

"a>b b>c c>d e>f b>e e>a c>c"

Graph nodes are marked with letters a-z. 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:

class Node {
    connections = WeakArray(Node);
    isVisited = false;
    isActive = false;
}
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("a>b b>c c>d e>f b>e e>f c>f").hasLoop()
    ? "has some loop"
    : "has no loops");

Let's define a fromStr method:

class Graph {
    ...
    fromStr(in String) this {                     // {1}
        loop {                                    // {2}
            from = getOrCreateNode();             // {3}
            in.getCh() != '>' ? terminate(-2);    // {4}
            from.connections.append(&getOrCreateNode());  // {5}
            in.getCh() == 0 // try skip ' '       // {6}
        }
    }
}

In this code the fromStr is an initializer method returning this (line {1}).
It iterates by the input string codepoints until it reaches the end-of-string.
In line {2} the built-in loop construction iterates its argument until it returns true.
So the condition in line {6} actually controls the loop.
Method in.getCh() extracts one code-point from the beginning of the string.
Code points are numbers in range 0..0x10ffff where 0 means the end-of-text.
So Argentum strings act as input text streams with full Unicode support.

At first we need to take a character and find or create a Node for that character, and we need to do it twice for each "a>b" record. This is performed by the getOrCreateNode helper function which we call twice - in lines {3} and {5}.

At line {4} we skip the '>' character. Although we don't need to check for input correctness, I added some checking code just for illustration purposes.

The line {5} needs more explanation. The getOrCreateNode function returns a temporary pointer to Node. When we add it to the from.connections WeakArray, it we need a WeakPointer. We use a &-operator to make this type of pointers.

Let's implement this helper getOrCreateNode function.
I prefer it to be a lambda inside the fromStr method.

Also we need to keep a (character->Node) mapping having the following properties:

1. It is needed only for the duration of the string->graph conversion, so it should be a local variable inside the fromStr method.
2. Since the keys are characters 'a'-'z', for simplicity it can be a simple array, not a map.
3. Since our nodes are owned by the Graph instance, this mapping needs to be non-owning.

fromStr(in String) this {
        nodesByNames = WeakArray(Node).resize('z' + 1);       // {1}
        getOrCreateNode = () {                                // {2}
            name = in.get();                                  // {3}
            nodesByNames[name] : {                            // {4}
                r = nodes.append(Node);                       // {5}
                nodesByNames[name] := &r;                     // {6}
                r                                             // {7}
            }
        };
        loop {
           ...
        }
    }
}

In line {1} we create and resize the WeakArray to accommodate all a..z names. WeakArray is a generic class. Here we declare that this array will store weak pointers to Nodes.
In line {2} we create the getOrCreate lambda function.
In line {3} we fetch a codepoint from the input string. Please note that being a lambda the getOrCreate function has the full access to all parameters, locals, this-bounded names from all outer scopes. And unlike C++/Java etc. it doesn't lead to heap allocations, object wrappers and other heavyweight cavalry. Lambdas are extremely simple in Argentum - it's one pointer to a stack frame.
In line {4} we check if our byNames map already contains the Node, and if it does, this will be the function result. The else-operator ":" requires its LHS to be optional(T), and if it is not empty, its inner value will be the result of ":". Otherwise (if it was empty), the RHS part is executed to create the result of ":".
In lines {5-6-7} we

• create a new Node instance,
• append it to the end of the this.nodes array,
• put a weak-link to it into byNames container,
• and return it as a getOrCreateNode result.

So the full code that creates the graph out of a text string is as follows:

class Graph {
    nodes = Array(Node);
    fromStr(in String) this {
        nodesByNames = WeakArray.resize('z' + 1);
        getOrCreateNode = () {
            name = in.get();
            nodesByNames[name] : {      // peek it from nodesByNames or else...
               r = nodes.append(Node);
               nodesByNames[name] := &r;
               r
            }
        };
        loop {
            from = getOrCreateNode();
            in.get();
            from.connections.append(&getOrCreateNode());
            in.get() == 0
        }
    }
}

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(           // {1}
            n \ n.hasLoop()      // {2}
        )
    }

In line {1} 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 {2} we check if the element's hasLoop method detects a loop.

The Node.hasLoop does the actual work:

class Node {
    connections = WeakArray(Node);
    isVisited = false;
    isActive = false;

    hasLoop() bool {
        isActive || (!isVisited && {                      // {1}
            isVisited := isActive := true;                // {2}
            r = connections.contain(                      // {3}
                c \ c.hasLoop()
            );
            isActive := false;                            // {4}
            r                                             // {5}
        })
    }
}

In line {1} we check if the Node is seen in the active path, and if it is, it's the loop.
Also in line {1} we avoid going inside the already visited nodes with the help of the && operator.
In line {2} we mark our node both as visited and in the active path. And of course we remove isActive in line {4}.
Line {3} is a recursive scan by all outgoing connections. It follows the logic Graph.hasLoop.
Line {5} returns the result of recursive scan.
In total, the result of Node.hasLoop is combined from three sources - isActive, isVisited, DFS.

The full source code:

using sys { WeakArray, Array, String, log }
using string;
using array;

class Node {
    connections = WeakArray(Node);
    isVisited = false;
    isActive = false;

    hasLoop() bool {
        isActive || (!isVisited && {
            isVisited := isActive := true;
            r = connections.contain(c \ c.hasLoop());
            isActive := false;
            r
        })
    }
}
class Graph {
    nodes = Array(Node);
    fromStr(in String) this {
        byNames = WeakArray(Node).resize('z' + 1);
        getOrCreateNode = () {
            name = in.get();
            nodesByNames[name] : {
               r = nodes.append(Node);
               nodesByNames[name] := &r;
               r
            }
        };
        loop {
            from = getOrCreateNode();
            in.get();
            from.connections.append(&getOrCreateNode());
            in.get() == 0
        }
    }    
    hasLoop() bool {    
        nodes.contain(n \ n.hasLoop())
    }
}

log(Graph.fromStr("a>b b>c c>d e>f b>e e>a c>c").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.