# 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:

classDiagram Graph *-- a Graph *-- b Graph *-- c Graph *-- d Graph *-- e Graph *-- f a ..> b b ..> c c ..> d e ..> f b ..> e e ..> a c ..> c

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.