Assignment 14

Graphs

by Jenni Meiklejohn

HTML

<input type="button" onclick="createGraph();" value="Create Graph" />
<br/> Select from two nodes:
<br />From
<select id="from"></select>
To
<select id="to"></select>
<input type="button" onclick="calculate();" value="Calculate" />
<p id="edges"></p>
<p id="nodes"></p>
<p id="paths"></p>

JavaScript

var Node = function(_name) {
  this.name = _name;
  this.edges = [];
  return this;
}

var Edge = function(_cost) {
  this.from = null;
  this.to = null;
  this.cost = null;
  return this;
}

var Graph = function() {
  this.nodes = [];
  this.edges = [];
  this.paths = [];

  this.addNode = function(_name) {
   this.edges[_name] = []; 
    var node = new Node(_name);
    this.nodes.push(node);
    return node;
  };

  this.addEdge = function(_from, _to, _cost) {
    var edge = new Edge(_cost);
    edge.from = _from;
    edge.to = _to;
    edge.cost = _cost;
    this.edges.push(edge);
    this.edges[_from][_to] = _cost; 
    this.edges[_to][_from] = _cost; 
    return edge;
  }

  this.printNodes = function() {
    var s = "All Nodes in Graph: <br/>";
    for (var i = 0; i < this.nodes.length; i++) {
      s = s + "Node: " + i + "   Name: " + this.nodes[i].name + "</br>";
    }
    return s;
  }

	this.printEdges = function() {
    var s = "All Edges in Graph: <br/>";
    for (var i = 0; i < this.edges.length; i++) {
      s += "Edge: " + i + "   From: " + this.edges[i].from + "   To: " + 		this.edges[i].to + "   Cost: " + this.edges[i].cost + "</br>";
    }
    return s;
  }
  
  this.calculatePaths = function(_from, _to, _cost, _paths) {
    this.paths.push(_from);
    if (_from == _to) {
      this.printPaths(_paths, _cost);
    } else {
      for (var next in this.edges[_from]) {
        if (this.paths.includes(next) == false) {
          var runCost = this.edges[_from][next];
          var total = _cost + runCost;
          this.calculatePaths(next, _to, total, _paths);
        }
      }
    }
    this.paths.pop();
  }

  this.printPaths = function(_paths, _cost) {
    var str = this.paths[0];
    for (var i = 1; i < this.paths.length; i++) {
      str = str + ", " + this.paths[i];
    }
    str += ": " + _cost + "<br />";
    document.getElementById("paths").innerHTML += str;
  }
}

var nodeList = document.getElementById("nodes");
var graph = new...