This content originally appeared on DEV Community and was authored by Kirk Shillingford
Prelude
This is a very short article which talks about using graph theory to solve my latest code challenge.
Every two weeks my online community group, Virtual Coffee picks a new challenge for us to work on together.
This fortnight we've been working on the Dominoes problem on https://www.exercism.io.
I tried to solve this previously in F# without having to do any recursion or traversals and that almost worked.
While looking at other implementations I stumbled upon this solution which proposed that you could solve the problem by modelling the dominoes as a Graph. I liked the approach conceptually, but didn't want to just recreate the answer in F# again so I figured I'd try it with Typescript.
So without further ado, let's dive in.
INTRODUCTION
Problem
Paraphrasing exercism.io, "Write a function canChain to determine whether a set of dominoes (an array of tuples)
can be chained."
e.g. The dominoes
(1, 2), (1, 3), (2, 3)
can be chained together as
(1, 2) (2, 3) (3, 1)
where each domino is joined at matching number terminals.
Conversely the dominoes
(1, 2), (1, 3), (4, 4)
cannot be chained because there is no domino
that can connect to (4, 4).
Some extra rules:
- Empty arrays should return true
- The ends of the domino set should also match (making a perfect loop)
Thus
canChain([[1, 2], [1, 3], [2, 3]]) // true
canChain([[1, 2], [1, 3], [4, 4]]) // false
canChain([]) // true
canChain([1, 2]) // false
canChain([3, 3]) // true
Methodology
We can model our set of dominoes as a graph where each domino represents two nodes (one for each number on the domino) and the edge/line/arrow that connects them.
When two dominoes have the same number, that means at least one of their nodes overlap and they can be chained.
Thus we can rephrase the problem of "Can the dominoes chain?" to "Do these nodes all connect?" and "Can we get from any node to every other node and back to the start?"
It turns out, in graph theory, this type of configuration already has a name: A Euler Graph.
A Euler graph has a Eulerian cycle, which is exactly what we just described:
a Eulerian cycle is a path starting and ending on the same vertex) that visits each edge exactly once? - Wikipedia
So all we need to do to prove if our dominoes can chain is to prove that the graph those dominoes
represent has a Euler cycle.
And THAT it turns out, also has a formal definition, Euler's Theorem:
"A Connected graph has an Euler cycle if and only if every vertex has even degree".
So our solution now has two parts:
Check if every vertex (number) in our set of dominoes has an even degree (appears as a multiple of two).
Check if the dominoes can be converted to a Connected graph
Implementation
Establishing our domain
Since it's Typescript, we'll start the way we always do by defining the types that establish the domain we're working with. We want to define what a Domino is (in this implementation) as well as some of the data structures related to Graph modelling.
type NodeNumber = 0 | 1 | 2 | 3 | 4 | 5 | 6;
type Domino = [NodeNumber, NodeNumber];
type EdgeSet = Domino[]; // A representation of the set of edges in a graph
type AdjacencyMatrix = MatrixValue[][]; // Representation of a graph as a matrix of filled/unfilled cells
type AdjacencyList = number[][]; // Representation as a list of connected nodes
type MatrixValue = "Filled" | "Empty";
type NodeStatus = "Visited" | "Not Visited";
type EulerCondition = (_: EdgeSet) => boolean; // Functions that test our Euler's theory
The three types above, EdgeSet, AdjacencyMatrix, and AdjacencyList represent three common ways of representing graphs. Our list of dominoes is passed into our code as an EdgeSet; a sequence representing pairs of connected nodes.
However to determine if we have a Eulerian cycle, we'll have to convert our EdgeSet to an AdjacencyMatrix and then convert that to an AdjacencyList.
So let's define some functions to do just that.
Creating our conversion functions
First we need to define two small helper functions
const id = (x: any) => x; // yes, this returns itself.
// simplifies an edgeset down to its unique nodes by converting to and from a set
type GetNodes = (_: EdgeSet) => NodeNumber[];
const getNodes: GetNodes = (dominoes) => [...new Set(dominoes.flatMap(id))];
Now we can define a function that converts an EdgeSet into the appropriate AdjacencyMatrix
type ToMatrix = (_: EdgeSet) => AdjacencyMatrix;
const toMatrix: ToMatrix = (dominoes) => {
const nodes = getNodes(dominoes);
const nodeToBool = (digit: NodeNumber) =>
nodes.findIndex((node) => node === digit);
// initial graph of all false values
const initMatrix: AdjacencyMatrix = Array.from(Array(nodes.length), () =>
[...new Array(nodes.length)].map((_) => "Empty")
);
const addToMatrix = (graph: AdjacencyMatrix, domino: Domino) => {
const [x, y] = domino;
graph[nodeToBool(x)]![nodeToBool(y)] = "Filled";
graph[nodeToBool(y)]![nodeToBool(x)] = "Filled";
return graph;
};
return dominoes.reduce(addToMatrix, initMatrix);
};
and a function that turns an AdjacencyMatrix into an AdjacencyList
type ToAdjacencyList = (_: AdjacencyMatrix) => AdjacencyList;
const toAdjacencyList: ToAdjacencyList = (graph) =>
graph.map(
(row) =>
row
.map((val, index): [number, MatrixValue] => [index, val]) // add indexes
.filter(([_, val]) => val === "Empty") // filter unfilled cells
.map(([index, _]) => index) // keep indexes
);
We won't dive too deep into the code behind these functions except to say that what matters most to us is the AdjacencyList. An Adjacent List is a way of representing finite graphs where each node in the list contains the set of nodes adjacent to that node.
e.g. Earlier, we had the dominoes
(1, 2), (1, 3), (4, 4)
We said that we could represent these in typescript as the EdgeSet
[[1, 2], [1, 3], [4, 4]].
But we could also put them in the shape of the AdjacencyList
[[2, 3], [1], [1], []].
In this represantation, each item in the outer list represents a node, and each inner list is the the adjacent nodes to that one.
So we can read this adjacency list as:
- Node 1 has nodes 2 and 3 adjacent to it
- Node 2 has node 1 adjacent to it
- Node 3 has node 1 adjacent to it
- Node 4 has no nodes adjacent to it
And this corresponds perfectly to what we see looking at the original dominoes.
Implementing our search function
Now that we have a data structure showing our nodes and who they're adjacent to, we need a function that actually checks to see whether we can get to every node from any one starting node.
There are a few options for what we can use to do this but here we'll be applying the Depth-First Search, a well known algorithm for traversing tree/graph data structures.
Depth-first means it will travel all the way to the end of a 'tree' from the root before backtracking (unlike its counterpart, _Breadth-first search, which will check all paths on one level before going lower).
So our depth-first search (dfs) function will (recursively) go from node to adjacent nodes as defined in our Adjacency list. To help it, we'll make an array representing all the nodes it's seen so far called visited. Every time the dfs meets a node it hasn't encountered before it will update the array of visited nodes.
If the dfs visits all available nodes as it traverses through the adjacenct list, then voila, that means the graph must be connected.
type DFS = (_: AdjacencyList, __: NodeStatus[], ___: number) => void;
const depthFirstSearch: DFS = (graph, visited, node) => {
visited[node] = "Visited";
graph[node]!.filter((adjacent) => !visited[adjacent]) // get unvisited nodes
.forEach((unvisitedNode) =>
depthFirstSearch(graph, visited, unvisitedNode)
);
};
Note that this implementation of dfs doesnt return a value, it simply updates the array of visited nodes. Then it checks to see if the current node has any adjacent nodes that haven't been visited, and recursively calls itself with those.
Defining our Euler Conditions
Now that we've defined our data structures and our search function, it's finally time to put it together and create the function that will actually check to see if our Eulerian cycle exist. Each one is designed to accept the original list of dominoes and return whether our conditions were satisfied or not.
First our isConnected function which uses the code we defined above to determine if the domino array representing the EdgeSet of a graph is a connected graph by checking if every node in the visited array .
const isConnected: EulerCondition = (dominoes) => {
const nodes = getNodes(dominoes);
const visited: boolean[] = [...new Array(nodes.length)].map((_) => false);
const graph = toAdjencyList(toMatrix(dominoes));
// time to spelunk
depthFirstSearch(graph, visited, 0);
return visited.every((x) => x === true);
};
Next we make a function allEvenDegree to see if our edges all have an even number of representations. We do this by folding the array of dominoes into a Map (object) of keys representing our nodes, and values representing the amount of times they appear in the array.
const allEvenDegree: EulerCondition = (dominoes) => {
const isEven = (n: number) => n % 2 === 0;
// adds to map of numbers in the domino set and how many times they appear
const addToMap = (m: Map<NodeNumber, number>, key: NodeNumber) =>
m.has(key) ? m.set(key, m.get(key)! + 1) : m.set(key, 1);
const nodeCounts: number[] = [
...dominoes
.flatMap(id) // concat + flatten
.reduce(addToMap, new Map()) // fold into a map
.values()
]; // back to array
return nodeCounts.every(isEven);
};
Putting it all together
Finally, after all that, all that remains is to define our canChain function that assembles all our logic into one conveniently exposed function. canChain checks to see if a set or dominoes has all even degree and (&&) is a connected graph.*
export const canChain: EulerCondition = (dominoes) =>
dominoes.length === 0 || (allEvenDegree(dominoes) && isConnected(dominoes));
*If you remember, we said at the beginning that empty arrays should all evaluate to true, so we used an or (||) operation to stick that clause onto the rest of our canChain operation.
Conclusion and Resources
If you've made it this far, thank you for reading about my little exploration of graphs with Typescript. I just want to leave you with a few extra resources if this topic piqued your interests.
- Here is a link to full solution (with full notes)
- This video does a good job in my opinion of explaining all the basic Graph Theory terminology we touched on here.
- And this video walks through using how to use an Adjacency list and depth-first search to find out if a graph is connected or not.
Please leave a comment if you have an questions, queries, concerns, qualms, or critiques.
Thank you for your time. :)
This content originally appeared on DEV Community and was authored by Kirk Shillingford
Kirk Shillingford | Sciencx (2021-04-07T13:20:07+00:00) Solving the Dominoes problem with Graph Theory and Typescript. Retrieved from https://www.scien.cx/2021/04/07/solving-the-dominoes-problem-with-graph-theory-and-typescript/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.