Demo entry 6537614

Traffic Assignment

   

Submitted by anonymous on Jun 01, 2017 at 12:28
Language: JavaScript. Code size: 7.2 kB.

let N = 12;
let S, Q;

function build_graph () {
  let G = {};
  G.V = [];
  for (let i = 1; i <= N; i++) { // build G(V, E);
    G.V[i] = { // build V;
      id: i,
      p: null,
      d: Infinity,
      Adj: []
    } 
  }
  // build Adj
  for (let i = 1; i <= N; i++) {
    build_Adj(G, i);
  }
  return G;
}

function build_Adj (G, i) {
  let vtx = G.V[i];
  let b1 = i + 3, // branch 1
      b2 = i + 1, // branch 2
      b3 = i - 3, // branch 3
      b4 = i - 1; // branch 4
  /*
  1 ---- 4 ---- 7 -- 1 0
  |     |b4     |     |
  2--b3--5--b1--8 -- 1 1
  |     |b2     |     |
  3 ---- 6 ---- 9 -- 1 2
   */
  switch (i) {
    case 1:
     vtx.Adj = [b1 ,b2];
     break;

    case 2:
     vtx.Adj = [b1 ,b2, b4];
     break;

    case 3:
     vtx.Adj = [b1 ,b4];
     break;

    case 4:
    case 7:
     vtx.Adj = [b1 ,b2, b3];
     break;

    case 5:
    case 8:
     vtx.Adj = [b1 ,b2, b3, b4];
     break;

    case 6:
    case 9:
     vtx.Adj = [b1, b3, b4];
     break;

    case 10:
     vtx.Adj = [b2, b3];
     break;

    case 11:
     vtx.Adj = [b2, b3, b4];
     break;

    case 12:
     vtx.Adj = [b3, b4];
     break;

    default:
     break;
  }

  vtx.Adj.sort((a,b) => a-b);
}

function build_weight () {
  let w = [], // build weight matrix
      w0 = [];
  w0[1] = [3, 2];
  w0[2] = [3, 2, 1.5];
  w0[3] = [2, 1];
  w0[4] = [2, 2.5, 3];
  w0[5] = [1.5, 2.5, 1.5, 4];
  w0[6] = [1, 1.5, 2];
  w0[7] = [3, 0.5, 1];
  w0[8] = [4, 0.5, 3.5, 3];
  w0[9] = [2, 3.5, 3];
  w0[10] = [1, 1];
  w0[11] = [3, 1, 3.5];
  w0[12] = [3, 3.5];
  for (let i = 1; i <= N; i++) {// insert w0 to empty matrix
    w[i] = new Array(13).fill(0);
    for (let k = 0, len = G.V[i].Adj.length; k < len; k++) {
      let j = G.V[i].Adj[k];
      w[i][j] = w0[i][k];
    }
  }
  return w;
}

function build_weight_factor () {
  let wf = [],// build weight factor matrix
      wf0 = [];
  wf0[1] = [2, 1];
  wf0[2] = [2, 3, 5];
  wf0[3] = [3, 6];
  wf0[4] = [1, 4, 3];
  wf0[5] = [5, 4, 6, 4];
  wf0[6] = [6, 6, 5];
  wf0[7] = [3, 6, 2];
  wf0[8] = [4, 6, 4, 1];
  wf0[9] = [5, 4, 1];
  wf0[10] = [2, 5];
  wf0[11] = [1, 5, 3];
  wf0[12] = [1, 3];
  
  wf0.forEach( function(wf0_row, i) {
    for (let j = 0; j < wf0[i].length; j++) {
      wf0[i][j] /= 100; 
    }
  });

  for (let i = 1; i <= N; i++) {// insert wf0 to empty matrix
    wf[i] = new Array(13).fill(0);
    for (let k = 0, len = G.V[i].Adj.length; k < len; k++) {
      let j = G.V[i].Adj[k];
      wf[i][j] = wf0[i][k];
    }
  }
  return wf;
}

function update_weight(w, wf, f, wi) { // update weight matrix by flows and weight_fator
  w.forEach( function(weight_row, i) {
    weight_row.forEach( function(weight_cell, j) {
      weight_row[j] = wi[i][j] + wf[i][j] * f[i][j];
    });
  });
}

function build_flows () { // build empty flow matrix
  let f = [];
  for (let i = 1; i <= N; i++) {
    f[i] = new Array(13).fill(0);
  }
  return f;
}

function build_OD () { // import OD matrix
  let od = [],
      od0 = [];
      od_point = [1, 3, 10, 12]; 
  od0[1] = [0, 300, 400, 500];
  od0[2] = [300, 0, 100, 250];
  od0[3] = [400, 100, 0, 600];
  od0[4] = [500, 250, 600, 0];
  for (let i = 1, len = od_point.length; i <= len; i++) {
    let m = od_point[i-1];
    od[m] = [];
    for (let j = 0, len = od_point.length; j < len; j++) {
      let n = od_point[j];
      od[m][n] = od0[i][j];
    }
  }
  return od;
}

function split_OD (od, portion/*=0.n*/) { // split OD to sub_OD by portion factor
  let sub_od = [];
  od.forEach( function(od_row, i) {
    sub_od[i] = [];
    od_row.forEach( function(od_cell, j) {
      sub_od[i][j] = od_cell * portion;
    });
  });
  return sub_od;
}

function initialize (G, s) { // initialize Graph for dijsktra
  for (let i in G.V) {
    G.V[i].p = null;
    G.V[i].d = Infinity;
  }
  s.d = 0;
}

function relax (u, v, w) {
  if (v && v.d > u.d + w[u.id][v.id]) {
    v.d = u.d + w[u.id][v.id];
    v.p = u;
  }
}

function extract_min(Q) { // pop the minimum of Q
  let d_min = 100,
      index;
  Q.forEach( function(vtx, i) {
    if (i > 0 && vtx.d < d_min) {
      d_min = vtx.d;
      index = i;
    }
  });
  return Q.splice(index, 1).pop();
}

function dijsktra (G, w, s) {
  initialize(G, s);
  S = []; // to save vertices traversed
  Q = JSON.parse( JSON.stringify(G.V, cencor_out), 
                  cencor_in); // deepcopy G.V to Q
  Q.filter((value) => value !== null);
  while (Q.length > 1) {
    let u = extract_min(Q);
    S.push(u);
    for (let i = 0; i < u.Adj.length; i++) {
      let v;
      Q.forEach( function(vertex, index) {
        if (vertex && vertex.id === u.Adj[i]) {
          v = vertex;
        }
      });
      relax(u, v, w);
    }
  }

}

function cencor_out (key, value) {
  return value === Infinity ? "Infinity" : value;
}

function cencor_in (key, value) {
  return value === "Infinity" ? Infinity : value;
}

function print_path_inner (G, s, v) {
  if (s === v) {
    editor.write(s.id + ' ');
  } else if (v.p === null) {
    editor.write("there's no path from s to v");
  } else {
    print_path_inner(G, s, v.p);
    editor.write(v.id + ' ');
  }
}

function print_path (G, s, v) {
  s = by_id(G, s);
  v = by_id(G, v);
  print_path_inner(G, s, v);
  editor.writeln('');
}

function increasement_innner (G, f, od, s, v, src, dst) {
  if (s === v) {
    
  } else if (v.p === null) {
    editor.write("there's no path from s to v");
  } else {
    increasement_innner(G, f, od, s, v.p, src, dst); // recurse to add flow from s to v 
    f[v.p.id][v.id] += od[src][dst];                 // to flow matrix
  }
}

function increasement (G, f, od, s, v) {
  src = s, 
  dst = v;
  s = by_id(G, s);
  v = by_id(G, v);
  increasement_innner(G, f, od, s, v, src, dst);
}

function assignment (G, w, f, od) {
  od.forEach( function(od_row, i) {
    dijsktra (G, w, G.V[i]);
    od_row.forEach( function(od_cell, j) {
      if (i !== j) {
        increasement(S, f, od, i, j);
        print_path(S, i, j);
      }
    });
    editor.writeln('');
  });
  editor.writeln('------------');
}

function incre_assignment (G, w, wf, f, od, wi) {
  let portions = [0.4, 0.3, 0.2, 0.1];
  //let portions = new Array(1000).fill(1/1000);
  portions.forEach( function(portion, index) {
    let sub_od = split_OD(od, portion);
    assignment(G, w, f, sub_od);
    update_weight(w, wf, f, wi);
    //print_matrix(f);
  });
}

function print_matrix (m) {
  m.forEach( function(m_row, index) {
    editor.write(m_row);
    editor.write('\n');
  });
}

function by_id (S, id) { // get node by id
  let node;
  S.forEach( function(element, index) {
    if (id === element.id) {
      node = element;
    }
  });
  return node;
}

let G = build_graph();
let wi = build_weight(); // weight initial
let w = build_weight();
let f = build_flows();
let od = build_OD();
let wf = build_weight_factor();

incre_assignment(G, w, wf, f, od, wi);

console.log(f);
console.log(w);

This snippet took 0.03 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).