Assignment 14

Graphs

by F Fornos

HTML

Select two nodes:
<br />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" onclick="calculate();" value="Calculate" />
<br/>
<br/><span id="result" />

JavaScript

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

graph.prototype.add_node = function(label) {
  this.edges[label] = {};
};

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

graph.prototype.calculate_paths = function(from, to, cost, paths) {
  paths.push(from);
  if (from == to) {
    display_path(paths, cost);
  } else {
    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) {
  var value = paths[0];
  for (var i = 1; i < paths.length; i++) {
    value = value + ", " + paths[i];
  }
  value += ": " + cost;

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

window.calculate = function() {
  var result = document.getElementById('result');
  result.innerHTML = "";


  var from = document.getElementById('from').value;
  var to = document.getElementById('to').value;

  var g = new graph();
  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');

  g.add_edge('A', 'B', 2);
  g.add_edge('A', 'C', 1);
  g.add_edge('B', 'D', 1);
  g.add_edge('B', 'G', 1);
  g.add_edge('C', 'D', 1);
  g.add_edge('C', 'E', 1);
  g.add_edge('D', 'E', 2);
  g.add_edge('D', 'F', 1);
  g.add_edge('D', 'G', 2);

  result.innerHTML = from + " to " + to + "<br />";
  g.calculate_paths(from, to, 0, []);
};