Assignment 14

Graphs

by aren_anderson

HTML

<h1>
  Assignment 14: "Graphs"
</h1>
<h2>
Select two nodes:
</h2>
From
<select id="from">
    <option value='A'>A</option>
    <option value='B'>B</option>
    <option value='C'>C</option>
    <option value='D'>D</option>
    <option value='E'>E</option>
    <option value='F' selected>F</option>
    <option value='G'>G</option>
</select>To
<select id="to">
    <option value='A'>A</option>
    <option value='B'>B</option>
    <option value='C' selected>C</option>
    <option value='D'>D</option>
    <option value='E'>E</option>
    <option value='F'>F</option>
    <option value='G'>G</option>
</select>

<input type="button" id="click" onclick="calculate();" value="Calculate" />
<br/>
<br/><span id="result" />

CSS

#click {
  background-color: black;
  color: white;
  margin-top: 8px;
  margin-bottom: 8px;
  width: 10em;
}

JavaScript

function graph() {
    this.edges = {};
}

// function to add a new node into this graph
graph.prototype.add_node = function (label) {
    // an adjacent list is used to store the edges between nodes
    this.edges[label] = {};
};

graph.prototype.add_edge = function (from, to, cost) {
    // undirected graph
    this.edges[from][to] = cost;
    this.edges[to][from] = cost;
};

graph.prototype.calculate_paths = function (from, to, cost, paths) {
    paths.push(from);
    // permutate and display all the paths (and costs) between
    // the two given nodes
    if (from == to) {
        // reach the destination, display it in the result span
        display_path(paths, cost);
    } else {
        // enumerate the adjacent nodes
        for (var connected in this.edges[from]) {
            if (paths.indexOf(connected) < 0) { // not visited yet
                var thiscost = this.edges[from][connected];
                this.calculate_paths(connected, to, cost + thiscost, paths);
            }
        }
    }
    paths.pop();
};


function display_path(paths, cost) {
    // convert the paths into a string
    var value = paths[0];
    for (var i = 1; i < paths.length; i++) {
        value = value + ", " + paths[i];
    }
    value += ": " + cost;

    // add to the page
    var result = document.getElementById('result');
    result.innerHTML += value + "<br />";
}

window.calculate = function () {
    // this function calculates and displays the costs
    // of all paths between two nodes.
    var result = document.getElementById('result');
    result.innerHTML = "";

    // get the source and destination nodes from user input
    var from = document.getElementById('from').value;
    var to = document.getElementById('to').value;

    // construct the object to store the graph
    var g = new graph();

    // add nodes A-G
    g.add_node('A');
    g.add_node('B');
    g.add_node('C');
    g.add_node('D');
    g.add_node('E');
    g.add_node('F');
    g.add_node('G');

...