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
One of possible graph interview problems.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.
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:
- It is needed only for the duration of the string->graph conversion, so it should be a local variable inside the fromStr method.
- Since the keys are characters 'a'-'z', for simplicity it can be a simple array, not a map.
- 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
returns either:contain
method
true
if some predicate invocation returnedtrue
,- 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.