Max Flow Skeleton, Tidied

_Max_Flow_Skeleton.md

Overview

A large number of car drivers regularly want to travel from the Hawthorns bus stop (the corner of St Michael’s Park and Woodland Road – call it 's') to the "Scotsman and his Pack" pub (the corner of St Michael’s Hill and Horfield Road - call it 't') - as shown in the map on the view.html page. Complete the following 3 tasks by implementing a number of algorithms in JavaScript function found in the controller.html file. This should be fairly straightforward, even if you have little experience of JavaScript (see the help sections at the end of this document for some tips).

Note, this exercise is fictional. In real life there are other possible routes from s to t, the road capacities are probably different, there are drivers on these roads with multiple different destinations most of time. Oh, and the app mentioned below doesn't actually exist!

Task 1

Bristol City Council has introduced a new congestion-management app. The app works out the routes between a driver's starting point and desired end point that have spare capacity (i.e. don't pass thorough a road that currently has a flow in either direction equal to the road's capacity). The app will recommend the route with the greatest static capacity. The algorithm does not incorporate current traffic flow along individual roads into its calculations (except that when a route is full to capacity, it is no longer recommended). Remember that a route is only as good as the most restricted edge along it's entire path. The maximum capacity of a route is the minimum value of the capacities, not the residual capacities of the roads on the route.

Complete the calcMaxFlow function in the controller.html file to simulate what will happen when the Bristol City Council app is used. The test graph will be automatically loaded from the file - you won't need to do anything to populate the system with data. Backwards edges will be created - however you should not make use of these in this particular task (since the city council don't consider them. You can assume that routes recommended by the app do not use any roads other than the ones listed. What is the greatest value of flow that is reached?

Task 2

A group of local residents have decided to protest about traffic congestion in this area, which seems to have gotten worse despite the introduction of the congestion-management app. They are planning to hold a sit-down protest in Tyndall Avenue, at the time of day when the large number of drivers travel from s to t. The sit-down will effectively reduce the Avenue's capacity to zero during that time. Simulate the effect of the protest on the traffic flow by editing the model.js file to remove the edge that runs along Tyndall Avenue (the edge between nodes "a" and "c"). Then re-run your simulation code. Is the protest likely to be successful in convincing the Council that the problem needs addressing?

Task 3

Implement a full max flow calculation for the above map using the Ford-Fulkerson algorithm. You don't need to insert backwards edges - these are all created automatically for you. You will however need to update them as the flow changes!

You may select the most appropriate search pattern for the task (i.e. breadth first, or depth first) It is possible to create equivalent recursive and simple-loop implementations. You may choose which you implement.

Extra Help - Javascript

Creating "objects" in JavaScript is a bit like a C structs:

var element = { graphNode: source, edgeFromParent: null, parentElement: null };

Arrays can be easily created as in the following example. The values need not all be of the same type.

var empty = [];
var occupied = [0,'1',"2","three",{}];

Arrays are indexed as usual:

var path = ['a->b','c->d','a->d'];
var edge = path[2]; // "a->d"

Finding the length of an array should also be familiar (note the use of var instead of int):

for (var i=0; i<path.length; i++) { ... }

Arrays can be used as queues or stacks by calling the following methods on them:

• .push(e1,e2,...): adds new elements to the back of the queue/top of the stack
• .pop(): pops the top element off the stack
• .shift(): pulls the next element off the head of the queue

Extra Help - API details

You may access the source and sink nodes using graph.source and graph.sink. All nodes have an array called "edges" which contains all edges eminating from that node. Each edge is a member of the class Edge, with backwards edges members of the subclass BackEdge. To tell you whether or not an edge is a backwards edge, either call .isBackEdge, or test for (edge instanceof BackEdge). Each node has a boolean property called "discovered" which you can use to keep track of whether an node has previously been visited in a path search.

Edges also have the following properties and methods:

• .from: returns the node from which this edge eminates
• .to: returns the node to which this node travels
• .residualCapacity : returns the amount of flow capacity remaining (total capacity minus current flow value)
• .augment(value) : reduces the available spare capacity by a certain amount (increasing the flow value). To decrease, provide a negative value.

One other extra function that you might find useful:

• graph.undiscover(): Resets all of the "discovered" flags on all nodes

See the sample calcMaxFlow function in controller.js file that comes with the assignment to see how some of these features can be used.

Extra Help - Running your code

Open up both view.html and controller.html in Chrome in different windows side by side, or index.html to view them in a single window. The controller contains four buttons to control the execution of your code:

• Step: Steps through an edge at a time
• Run/Pause: Runs your code automatically. Click again to pause (use slider to adjust playback speed)
• Reset: Resets all of the flow to zero, and stops the execution
• Reset to FF/CC: Resets, then changes the global boolean variable useFF. This is useful for Task 3, where you implement the Ford-Fulkerson algorithm. In the example code, this variable is not used.

It is probably safer to use the "stepped" run mode when you first start to build and test your code (it is easier to stop when things go wrong!). As you get further on, you may wish to change to the "run" mode using an appropriate speed using the slider.

Transversing an edge (triggered with edge.read()) highlights that edge in black. Augmenting an edge's flow (by calling edge.augment()) highlights that edge in green/red for increasing/decreasing. Marking a node as discovered will colour it blue, unless otherwise coloured by an edge.

You can toggle between "normal" graph and "residual" graph by pressing the 'r' key with the view selected. You can also hide or reveal the back edges on the graph by pressing the 'b' key with the view selected.

controller.html

<!DOCTYPE html>
<html>
    <head>
        <script src="localStorage.js"></script>
        <script src="controller.js"></script>
        <script src="model.js"></script>
        <script src="graph.js"></script>
    </head>
    <body onload="reset()">
        <center>
            <p><input id="stepButton" type="button" style="width: 100px" value="Step" onclick="doStep()" /></p>
            <p><input id="runButton" type="button" style="width: 100px" value="Run" onclick="doRun()" /></p>
            <p><input type="range" style="width: 100px" min="1" max="100" value="50" id="speed" /></p>
            <p><input type="button" style="width: 100px" value="Reset" onclick="reset()" /></p>
            <p><input id="algoButton" type="button" style="width: 100px" value="Switch to FF" onclick="resetAlgo()" /></p>
        </center>
    </body>
</html>

controller.js

let doStep = () => {};

let stepping = true;

let nextStep = 0;

let sendProgress = true;
let useFF = false;

async function run(mode) {
    // Switch focus away from "stepped" button to prevent accidental restart of run
    document.getElementById("stepButton").blur();
    if (typeof mode !== "undefined") stepping = mode;
    graph.reset();
    await calcMaxFlow(stepping);
}

async function wait() {
    let delay = (100 - document.getElementById("speed").value) * 10;
    return new Promise((resolve,reject) => {
        if (!stepping) nextStep = setTimeout(resolve,delay);
        doStep = resolve;
    });
}

function reset() {
    clearTimeout(nextStep);
    doStep = run;
    stepping = true;
    graph.reset();
    document.getElementById("stepButton").disabled = false;
    document.getElementById("runButton").disabled = false;
    document.getElementById('runButton').value = "Run";
}

function resetAlgo() {
    reset();
    useFF = !useFF;
    document.getElementById('algoButton').value = "Switch to " + (useFF ? "CC" : "FF");
}

function toggleStepping() {
    document.getElementById("stepButton").disabled = stepping;
    document.getElementById('runButton').value = stepping ? "Pause" : "Run";
    return stepping = !stepping;
}

function doRun() {
    toggleStepping();
    if (!stepping) doStep();
    else clearTimeout(nextStep);
}

function doneRun() {
    document.getElementById("stepButton").disabled = true;
    document.getElementById("runButton").disabled = true;
    stepping = true;
}

async function calcMaxFlow() {
    // Visit all nodes accessible the source
    for (let edge of graph.source.edges) {
        edge.read();
        await wait();
    }

    // Use up 5 units of flow from each edge eminating from source
    for (let edge of graph.source.edges) {
        edge.augment(5);
        await wait();
    }

    // Give back 5 units of flow to each edge eminating from source
    for (let edge of graph.source.edges) {
        edge.augment(-5);
        await wait();
    }

    doneRun();
}

graph.js

const graph = new Graph(
    "map.jpg",
    [
        new Source("s", 147, 160),
        new Node("b", 383, 42), 
        new Node("c", 411, 112),
        new Node("d", 500, 218),
        new Node("a", 173, 230),
        new Node("e", 184, 294),
        new Node("f", 279, 442),
        new Node("g", 350, 458),
        new Node("h", 439, 382),
        new Node("i", 435, 290),
        new Node("j", 561, 330),
        new Sink("t", 625, 395)
    ],
    [
        new Edge("s", "a", 20),
        new Edge("s", "b", 15),
        new Edge("b", "c", 30),
        new Edge("c", "d", 20),
        new Edge("a", "c", 20),
        new Edge("a", "e", 30),
        new Edge("e", "f", 10),
        new Edge("f", "g", 10),
        new Edge("g", "h", 10),
        new Edge("h", "i", 10),
        new Edge("i", "d", 20),
        new Edge("d", "j", 35),
        new Edge("j", "t", 35)
    ]
);

index.html

<!DOCTYPE html>
<html>
    <head>
        <title>Max Flow Exercise</title>
        <script src="localChannel.js"></script>
        <script src="controller.js"></script>
        <script src="model.js"></script>
        <script src="graph.js"></script>
        <script src="view.js"></script>
        <style>
            html, body {
                height: 100%;
            }

            body {
                margin: 0;
                display: flex;
            }

            iframe {
                border: 0;
                height: 100%;
                width: 100%;
            }

            .view {
                flex: 1;
                text-align: center;
            }

            #canvas {
                border: 1px solid #000;
            }

            .controller {
                flex: 0 0 150px;
                text-align: center;
            }
        </style>
    </head>
    <body onload="setupView();reset();">
        <div class="view">
            <canvas id="canvas" width="700" height="500"></canvas>
            <div>
                [Flow in: <span style="font-size:18;" id="flowin"></span>] &nbsp;
                [Flow out: <span style="font-size:18;" id="flowout"></span>]
            </div>
        </div>
        <div class="controller">
            <p><input id="stepButton" type="button" style="width: 100px" value="Step" onclick="doStep()" /></p>
            <p><input id="runButton" type="button" style="width: 100px" value="Run" onclick="doRun()" /></p>
            <p><input type="range" style="width: 100px" min="1" max="100" value="50" id="speed" /></p>
            <p><input type="button" style="width: 100px" value="Reset" onclick="reset()" /></p>
            <p><input id="algoButton" type="button" style="width: 100px" value="Switch to FF" onclick="resetAlgo()" /></p>
        </div>
    </body>
</html>

localChannel.js

var channel = {
    updateFn() {},

    reset(graph) {
        this.flow = graph.toString();
        this.updateFn("","","");
    },

    augment(from, to, action, graph) {
        this.flow = graph.toString();
        this.updateFn(from, to, action);
    },

    read(from, to) {
        this.updateFn(from, to, "read");
    },
    
    set onUpdate(updateFn) {
        this.updateFn = updateFn;
        updateFn("","","");
    },

    getFlow() {
        return JSON.parse(this.flow);
    },
};

localStorage.js

var channel = {
    reset(graph) {
        localStorage.flow = graph.toString();
        localStorage.from = "";
        localStorage.to = "";
        localStorage.flowTimestamp = (new Date()).getTime();
    },

    augment(from, to, action, graph) {
        localStorage.from = from;
        localStorage.to = to;
        localStorage.action = action;
        localStorage.flow = graph.toString();
        localStorage.flowTimestamp = (new Date()).getTime();
    },

    read(from, to) {
        localStorage.from = from;
        localStorage.to = to;
        localStorage.action = "read";
        localStorage.flowTimestamp = (new Date()).getTime();
    },
    
    updateDelay: 0,

    lastUpdate: 0,

    set onUpdate(updateFn) {
        let update = () => {
            this.lastUpdate = localStorage.flowTimestamp;
            updateFn(localStorage.from, localStorage.to, localStorage.action);
        }
        update();
        clearInterval(this.updateDelay);
        this.updateDelay = setInterval(() => {
            if (this.lastUpdate < localStorage.flowTimestamp) update();
        }, 50);
    },

    getFlow() {
        return JSON.parse(localStorage.flow);
    },
};

map.jpg

Max_Flow_Skeleton.md

Overview

A large number of car drivers regularly want to travel from the Hawthorns bus stop (the corner of St Michael’s Park and Woodland Road – call it 's') to the "Scotsman and his Pack" pub (the corner of St Michael’s Hill and Horfield Road - call it 't') - as shown in the map on the view.html page. Complete the following 3 tasks by implementing a number of algorithms in JavaScript function found in the controller.html file. This should be fairly straightforward, even if you have little experience of JavaScript (see the help sections at the end of this document for some tips).

Note, this exercise is fictional. In real life there are other possible routes from s to t, the road capacities are probably different, there are drivers on these roads with multiple different destinations most of time. Oh, and the app mentioned below doesn't actually exist!

Task 1

Bristol City Council has introduced a new congestion-management app. The app works out the routes between a driver's starting point and desired end point that have spare capacity (i.e. don't pass thorough a road that currently has a flow in either direction equal to the road's capacity). The app will recommend the route with the greatest static capacity. The algorithm does not incorporate current traffic flow along individual roads into its calculations (except that when a route is full to capacity, it is no longer recommended). Remember that a route is only as good as the most restricted edge along it's entire path. The maximum capacity of a route is the minimum value of the capacities, not the residual capacities of the roads on the route.

Complete the calcMaxFlow function in the controller.html file to simulate what will happen when the Bristol City Council app is used. The test graph will be automatically loaded from the file - you won't need to do anything to populate the system with data. Backwards edges will be created - however you should not make use of these in this particular task (since the city council don't consider them. You can assume that routes recommended by the app do not use any roads other than the ones listed. What is the greatest value of flow that is reached?

Task 2

A group of local residents have decided to protest about traffic congestion in this area, which seems to have gotten worse despite the introduction of the congestion-management app. They are planning to hold a sit-down protest in Tyndall Avenue, at the time of day when the large number of drivers travel from s to t. The sit-down will effectively reduce the Avenue's capacity to zero during that time. Simulate the effect of the protest on the traffic flow by editing the model.js file to remove the edge that runs along Tyndall Avenue (the edge between nodes "a" and "c"). Then re-run your simulation code. Is the protest likely to be successful in convincing the Council that the problem needs addressing?

Task 3

Implement a full max flow calculation for the above map using the Ford-Fulkerson algorithm. You don't need to insert backwards edges - these are all created automatically for you. You will however need to update them as the flow changes!

You may select the most appropriate search pattern for the task (i.e. breadth first, or depth first) It is possible to create equivalent recursive and simple-loop implementations. You may choose which you implement.

Extra Help - Javascript

Creating "objects" in JavaScript is a bit like a C structs:

var element = { graphNode: source, edgeFromParent: null, parentElement: null };

Arrays can be easily created as in the following example. The values need not all be of the same type.

var empty = [];
var occupied = [0,'1',"2","three",{}];

Arrays are indexed as usual:

var path = ['a->b','c->d','a->d'];
var edge = path[2]; // "a->d"

Finding the length of an array should also be familiar (note the use of var instead of int):

for (var i=0; i<path.length; i++) { ... }

Arrays can be used as queues or stacks by calling the following methods on them:

• .push(e1,e2,...): adds new elements to the back of the queue/top of the stack
• .pop(): pops the top element off the stack
• .shift(): pulls the next element off the head of the queue

Extra Help - API details

You may access the source and sink nodes using graph.source and graph.sink. All nodes have an array called "edges" which contains all edges eminating from that node. Each edge is a member of the class Edge, with backwards edges members of the subclass BackEdge. To tell you whether or not an edge is a backwards edge, either call .isBackEdge, or test for (edge instanceof BackEdge). Each node has a boolean property called "discovered" which you can use to keep track of whether an node has previously been visited in a path search.

Edges also have the following properties and methods:

• .from: returns the node from which this edge eminates
• .to: returns the node to which this node travels
• .residualCapacity : returns the amount of flow capacity remaining (total capacity minus current flow value)
• .augment(value) : reduces the available spare capacity by a certain amount (increasing the flow value). To decrease, provide a negative value.

One other extra function that you might find useful:

• graph.undiscover(): Resets all of the "discovered" flags on all nodes

See the sample calcMaxFlow function in controller.js file that comes with the assignment to see how some of these features can be used.

Extra Help - Running your code

Open up both view.html and controller.html in Chrome in different windows side by side, or index.html to view them in a single window. The controller contains four buttons to control the execution of your code:

• Step: Steps through an edge at a time
• Run/Pause: Runs your code automatically. Click again to pause (use slider to adjust playback speed)
• Reset: Resets all of the flow to zero, and stops the execution
• Reset to FF/CC: Resets, then changes the global boolean variable useFF. This is useful for Task 3, where you implement the Ford-Fulkerson algorithm. In the example code, this variable is not used.

It is probably safer to use the "stepped" run mode when you first start to build and test your code (it is easier to stop when things go wrong!). As you get further on, you may wish to change to the "run" mode using an appropriate speed using the slider.

Transversing an edge (triggered with edge.read()) highlights that edge in black. Augmenting an edge's flow (by calling edge.augment()) highlights that edge in green/red for increasing/decreasing. Marking a node as discovered will colour it blue, unless otherwise coloured by an edge.

You can toggle between "normal" graph and "residual" graph by pressing the 'r' key with the view selected. You can also hide or reveal the back edges on the graph by pressing the 'b' key with the view selected.

model.js

class Node {
    constructor(name, x, y) {
        this.discovered = false;
        this.edges = [];
        this.name = name;
        this.x = x;
        this.y = y;
    }

    toString() {
        return "\"" + this.name + "\":" + this.discovered;
    }
}

class Source extends Node {
    constructor(name, x, y) {
        super(name, x, y);
    }
}

class Sink extends Node {
    constructor(name, x, y) {
        super(name, x, y);
    }
}

class Edge {
    constructor(from, to, capacity) {
        this.inverse = undefined;
        this.flow = 0;
        this.from = from;
        this.to = to;
        this.capacity = capacity;
    }

    read() {
        channel.read(this.from.name,this.to.name);
    }
    
    get residualCapacity() {
        return this.capacity - this.flow;
    }

    augment(flow) {
        this.flow += flow;
        this.inverse.flow -= flow;
        let action = flow > 0 ? "increase" : "decrease";
        channel.augment(this.from.name, this.to.name, action, this.graph);
    }

    toString() {
        return "\"" + this.from.name + "->" + this.to.name + "\":" + this.flow;
    }

    get isBackEdge() {
        return false;
    }
}

class BackEdge extends Edge {
    constructor(inverse) {
        super(inverse.to, inverse.from, inverse.capacity);
        inverse.inverse = this;
        this.inverse = inverse;
        this.flow = inverse.flow;
    }

    get isBackEdge() {
        return true;
    }

    augment(flow) {
        this.inverse.augment(-flow);
    }
}

class Graph {
    constructor(image,nodes,edges) {
        this.background = image;
        this.nodes = nodes;
        this.source = nodes.find(node => node instanceof Source);
        this.sink = nodes.find(node => node instanceof Sink);
        for (let edge of edges) {
            let from = this.getNode(edge.from);
            let to = this.getNode(edge.to);
            let forward = new Edge(from, to, edge.capacity);
            forward.graph = this;
            let backward = new BackEdge(forward);
            backward.graph = this;
            from.edges.push(forward);
            to.edges.push(backward);
        }
    }
    
    getNode(name) {
        return this.nodes.find(node => node.name == name);
    }

    toString() {
        var edges = [];
        for (let node of this.nodes) {
            edges.push(...node.edges);
        }
        return '{' + edges.join(',') + ',' + this.nodes.join(',') + '}';
    }

    reset() {
        for (let node of this.nodes) {
            for (let edge of node.edges) {
                edge.flow = edge instanceof BackEdge ? edge.capacity : 0;
            }
        }
        this.undiscover();
        channel.reset(this);
    }

    undiscover() {
        for (let node of this.nodes) {
            node.discovered = false;
        }
    }
}

view.html

<!DOCTYPE html>
<html>
    <head>
        <script src="localStorage.js"></script>
        <script src="model.js"></script>
        <script src="graph.js"></script>
        <script src="view.js"></script>
        <style>
            body {
                text-align: center;
            }

            #canvas {
                border: 1px solid #000;
            }
        </style>
    </head>
    <body onload="setupView()">
        <canvas id="canvas" width="700" height="500"></canvas>
        <div>
            [Flow in: <span style="font-size:18;" id="flowin"></span>] &nbsp;
            [Flow out: <span style="font-size:18;" id="flowout"></span>]
        </div>
    </body>
</html>

view.js

let lastUpdate = 0;
let showBackEdges = true;
let showResidualFlows = false;
let nodeSize = 12;
let background;
let canvas;
let graphics;
const grey = "LightSlateGray";

async function setupView() {
    background = new Image();
    let loadedImage = new Promise(resolve => background.onload = resolve);
    background.src = graph.background;
    canvas = document.getElementById("canvas");
    canvas.addEventListener("click", mouseClicked);
    window.addEventListener("keydown", keyPressed);
    graphics = canvas.getContext("2d");
    graphics.textBaseline = "middle"; 
    graphics.textAlign = "center"; 
    await loadedImage;
    channel.onUpdate = draw;
}

function draw(from, to, action) {
    if (from === undefined) [from, to, action] = draw.lastDrawn; 
    else draw.lastDrawn = [from,to,action];
    updateFlow();
    graphics.clearRect(0, 0, canvas.width, canvas.height);
    graphics.drawImage(background, 0, 0);
    graphics.fillStyle = "rgba(255, 255, 255, 0.3)";
    graphics.fillRect(0, 0, canvas.width, canvas.height);
    for (let node of graph.nodes) {
        graphics.translate(node.x,node.y);
        for (let edge of node.edges) {
            // If it's a forward edge, then always draw it
            // Only draw backwards edges if "showBackEdges" is enabled
            if (showBackEdges || !edge.isBackEdge) {
                let edgeAction = "";
                if (edge.from.name == from && edge.to.name == to) {
                    edgeAction = action;
                }
                drawEdge(edge, edgeAction);
            }
        }
        drawNode(node, node.name == from || node.name == to ? action : "");
        graphics.translate(-node.x,-node.y)
    }
    document.getElementById("flowin").innerHTML = calcFlowIn();
    document.getElementById("flowout").innerHTML = calcFlowOut();
}

function calcFlowIn() {
    let total = 0;
    for (let edge of graph.source.edges) total += edge.flow;
    return total;
}

function calcFlowOut() {
    let total = 0;
    for (let edge of graph.sink.edges) total += edge.inverse.flow;
    return total;
}

function drawEdge(edge, edgeAction) {
    let angle;
    let xdiff = edge.to.x - edge.from.x;
    let ydiff = edge.to.y - edge.from.y;
    if (ydiff >= 0) angle = -Math.atan(xdiff/ydiff) + Math.PI/2;
    else angle = -Math.atan(xdiff/ydiff) - Math.PI/2;
    let xpos = Math.sqrt((xdiff*xdiff) + (ydiff*ydiff)) - nodeSize;
    graphics.rotate(angle);
    graphics.strokeStyle = actionColour(edgeAction);
    if (showResidualFlows) {
        if (edge.isBackEdge) {
            drawArrow(xpos, 10, true, edge.capacity - edge.flow);
        } else drawArrow(xpos, 0, false, edge.capacity - edge.flow);
    }
    else {
        if (edge.isBackEdge) {
            drawArrow(xpos, 10, true, edge.flow + "/" + edge.capacity);
        } else drawArrow(xpos, 0, false, edge.flow + "/" + edge.capacity);
    }
    graphics.lineWidth = 1.75;
    graphics.rotate(-angle);
}

function drawArrow(xoffset, yoffset, isBackEdge, label) {
    graphics.beginPath();
    if (isBackEdge) graphics.setLineDash([3,3]);
    else graphics.setLineDash([0,0]);
    graphics.moveTo(xoffset,yoffset);
    graphics.lineTo(0,yoffset);
    graphics.stroke();
    graphics.beginPath();
    graphics.setLineDash([]);
    graphics.moveTo(xoffset,yoffset);
    graphics.lineTo(xoffset-12,yoffset-6);
    graphics.moveTo(xoffset,yoffset);
    graphics.lineTo(xoffset-12,yoffset+6);
    graphics.stroke();
    graphics.translate(xoffset/2, yoffset*2)
    if (isBackEdge) graphics.rotate(Math.PI);
    drawShadowText(label, "14px Arial", 0, 0);
    if (isBackEdge) graphics.rotate(-Math.PI);
    graphics.translate(-xoffset/2, -yoffset*2)
}

function drawNode(node, nodeAction) {
    graphics.beginPath();
    graphics.arc(0, 0, nodeSize, 0, 2 * Math.PI, true);
    graphics.strokeStyle = actionColour(nodeAction, node.discovered);
    graphics.lineWidth = 1.75;
    graphics.fillStyle = "white";
    graphics.fill();
    graphics.stroke();
    // Steal the line colour for the font size
    graphics.fillStyle = graphics.strokeStyle;
    graphics.font = "14px Arial";
    graphics.fillText(node.name, 0, 0);
}

function actionColour(action, discovered) {
    switch (action) {
        case "increase": return "limegreen";
        case "decrease": return "red";
        case "read": return "black";
        default:
            if (discovered) return "blue";
            else return grey;
    }
}

function drawShadowText(label, font, x, y) {
    // Cheeky little hack to give text a white shadow
    graphics.font = font;
    graphics.fillStyle = "white";
    graphics.fillText(label, x-2, y);
    graphics.fillText(label, x+2, y);
    graphics.fillText(label, x, y-2);
    graphics.fillText(label, x, y+2);
    // Steal the line colour for the font size
    graphics.fillStyle = graphics.strokeStyle;
    graphics.fillText(label, x, y);
}


function updateFlow() {
    let flowValues = channel.getFlow();
    for (let node of graph.nodes) {
        for (let edge of node.edges) {
            edge.flow = flowValues[edge.from.name + "->" + edge.to.name];
        }
    }
}

function mouseClicked(event) {
    let rect = canvas.getBoundingClientRect();
    let x = Math.round(event.clientX - rect.left);
    let y = Math.round(event.clientY - rect.top);
    console.log("Mouse clicked at: " + x + "," + y);
}

function keyPressed(event) {
    if (String.fromCharCode(event.keyCode) == 'B') showBackEdges = !showBackEdges;
    if (String.fromCharCode(event.keyCode) == 'R') showResidualFlows = !showResidualFlows;
    draw();
}