Numbas.addExtension('graphs',['jme','base'],function(graphs) {
  var funcObj = Numbas.jme.funcObj
  var TDict = Numbas.jme.types.TDict
  var TList = Numbas.jme.types.TList
  var TNum = Numbas.jme.types.TNum
  var TBool = Numbas.jme.types.TBool
  var TMatrix = Numbas.jme.types.TMatrix
  var TString = Numbas.jme.types.TString
  var THTML = Numbas.jme.types.THTML
  


  
  var ngraphs = 0;
  var graphholder;
  $(document).ready(function() {
    graphholder = document.createElement('div');
    graphholder.id = 'graphholder';
    graphholder.setAttribute('class','invisible');
    graphholder.setAttribute('style','height:0; overflow-y: hidden;');
    document.body.appendChild(graphholder);
  });

  /**
   * Draw a graph
   */
  graphs.createGraphContainer = function(width,height){
      var container = document.createElement('div');
      container.style.margin='0 auto';
      container.id = 'graph'+(ngraphs++);
      container.classList.add("graph");
      container.style.width = width;
      container.style.height = height;
      graphholder.appendChild(container);
      return container
  }

  graphs.drawGraph = function(nodesD,edgesD,directed=true, style={}) {
      if(style['dimension']){
      var width = style['dimension'][0];
      var height = style['dimension'][1];
      }
    else
      {
      var width = '100%';
      var height ='100%';
      }
      var container = graphs.createGraphContainer(width,height);

      /* Find if we include the edge labels */
      var show_weights = edgesD.some(x => x['weight'] > 1.5)
      

      var promise = new Promise(function(resolve,reject){
        var attached_interval = setInterval(function() {
            var p = container;
            while(p && p!=document.body) {
                p = p.parentElement;
            }
            if(p) {
                clearInterval(attached_interval);
                var nodesList = [];
                var i = 0;
                for (var n of nodesD) {
                  let color = '#ffccaa'
                  if(style['vertices'])
                    if(style['vertices'].constructor === Array){
                      color = style['vertices'][i%(style['vertices'].length)]
                    }
                    else color = style['vertices']
                  let newNode = {id:++i, label:n, margin: 10, shape: "circle", font: "30px", color:color, physics: false}
                  nodesList.push(newNode); }
                
                var edgesList = [];
                for (const [i,e] of edgesD.entries()) {
                  let color = '#000000'
                  if(style['edges'])
                    if(style['edges'].constructor === Array){
                      color = style['edges'][i%(style['edges'].length)]
                    }
                    else color = style['edges']
                  var newEdge = {from:e['from']+1,to:e['to']+1, color: color,}
                  if(show_weights){newEdge['label'] = String(e['weight'])}
                  if(style['edgeweights']) {newEdge['value'] = Math.log(e['weight'])+1}
                  if (directed) newEdge["arrows"] = "to"
                  edgesList.push(newEdge)
                }
                
                var nodes = new vis.DataSet(nodesList);
                var edges = new vis.DataSet(edgesList); 
                var data = { nodes: nodes, edges: edges };
                var options = {
                  autoResize: true,
                  height: height,
                  width: width
                };
                if(style['fixvertices']){options['interaction'] = {"dragNodes": false}}
                var network = new vis.Network(container, data, options);
                network.fit();
                container.onclick = function(){network.fit()};
                resolve(network);
            }
        },10);
    });

    return new THTML(container);
  }

  
  graphs.draw = function(G, style={}){
    let V = G._vertices.map(x => x['label'])
    let E = G._edges.map(x => [x['from'], x['to']])
    if(V[0] === '') V = [...V.keys()].map(k => String.fromCharCode(k+97))
    return graphs.drawGraph(V, G._edges, false, style)
  }

  graphs.scope.addFunction(new funcObj('drawWithVisNetwork',['graph','[dict]'],THTML,
    graphs.draw,
    {unwrapValues:true}));

  graphs.scope.addFunction(new funcObj('drawGraph',[TList,TList,TBool],THTML,
    graphs.drawGraph,
    {unwrapValues:true}));
  
  graphs.scope.addFunction(new funcObj('generateEdges',[TList,TNum,TNum,TBool,TBool],TList,
    generateEdges,
    {unwrapValues:true}));
  
    graphs.scope.addFunction(new funcObj('newGraph',[TList,TNum],TList,
    newGraph,
    {unwrapValues:true}));

  graphs.scope.addFunction(new funcObj('adjacencyMatrix',[TList,TList,TBool],TList,
    adjacencyMatrix,
    {unwrapValues:true}));


});

/**
 * Find the adjacency matrix of a graph.
 * @param {list} nodes - set of vertices.
 * @param {list} edges - set of edges.
 * @param {boolean} undirected - set to true when the graph is undirected.
 * @return {list} - the adjacency matrix as an array of arrays.
 */
function adjacencyMatrix(nodes,edges,undirected) {
  var M = []
  var nNodes = nodes.length
  for (var i=0;i<nNodes;i++) {
    M.push([])
    for (var j=0;j<nNodes;j++) {
      M[i].push(0)
    }
  }
  
  for (var e of edges) {
    var i = e[0]
    var j = e[1]
    M[i][j] += 1
    if (undirected && i!=j) M[j][i] += 1
  }
  return M
}

/**
 * Generate edges between nodes randomly.
 * @param{array} nodes - list of vertices.
 * @param{Float} p - density of the graph (probability that an edge appears).
 * @param{Int} maxEdges - maximum number of edges in the graph.
 * @param{boolean} allowLoops - True if the graph may contain loops.
 * @param{boolean} directed - True if the graph is directed.
 * @return{array} - a list of edges.
 */
function generateEdges(nodes,p,maxEdges,allowLoops,directed) {
  var edges = [];
 
  var lS = 1-Number(allowLoops) // 0 if loops are allowed, 1 otherwise.
  var sF = 1-Number(directed) // 0 if graph is directed, 1 otherwise.
  
  var nNodes = nodes.length;
  for (var i=0;i<nNodes;i++) {
    for (var j=sF*i+lS;j<nNodes;j++) {
      if(allowLoops || i!=j) {
        for(var k=0;k<maxEdges;k++) {
          /* We need to restrict the number of loops to 1
          because of vis.js not showing multiple loops*/
          if (i !=j || k==0) {
            if (Math.random() < p) {
              edges.push([i,j])
            }
          }
        }
      }
    }
  }
  return edges
}

/**
 * Generate an undirected graph randomly.
 * @param{list} vertices - list of vertices in the graph.
 * @param{Int} m - maximum degree of the vertices of the graph.
 * @return{list} - list of edges in the graph.
 */
function newGraph(vertices,m) {
  var edges = []
  var degrees = vertices.map(x => 0) /* We start with 0 edges, so degrees for all vertices is 0.*/
  for (var i=0;i<vertices.length-1;i++) {
    let deg = Math.floor(Math.random()*(m-degrees[i]-1)) + 1 /* How many edges do we add?*/
    if (vertices.length - i < deg) deg = vertices.length - i
    let adjacent = []
    let tries = 0;
    while(adjacent.length < deg && tries<3*deg) {
      let j = Math.floor(Math.random()*(vertices.length-i-1))+1
      if (!adjacent.includes(i+j) && degrees[i+j]<m) {adjacent.push(i+j)}
      tries++
    }
    for (j of adjacent) {
      edges.push([vertices[i],vertices[j]]);
      degrees[i] += 1;
      degrees[j] += 1;
    }
  }
  let maxdeg = Math.max(...degrees)
  while(maxdeg < m) {
    let i = degrees.indexOf(maxdeg)
    let j = vertices.find(x => (i !== x && !edges.includes([i,x]) && !edges.includes([i,x])))
    edges.push([vertices[i],j])
    degrees[i] += 1; degrees[j] += 1;
    maxdeg = Math.max(...degrees)
  }
  return edges
}



/**
 * Wrapper function to draw a graph from the container id.
 * @param{list} nodesD - list of vertices.
 * @param{list} edgesD - list of edges.
 * @param{string} id - the id of the html element containing the graph.
 * @param{boolean} directed - true of the graph is directed.
 **/
function dg2(nodesD,edgesD,id,directed) {
  if (!id) {id='graphbox'}
  select = '#'+id
  cont = $(select)
  network = dg(nodesD,edgesD,$(select),directed);
  //network = dg(nodesD,edgesD,document.getElementById(id),directed);
}

/**
 * Draw a graph in a html container using vis.js.
 * @param{list} nodesD - list of vertices.
 * @param{list} edgesD - list of edges.
 * @param{container} id - the html element containing the graph.
 * @param{boolean} directed - true if the graph is directed.
 * @return{html} - the graph html element.
 **/
function dg(nodesD,edgesD,directed) {
  var nodesList = []
  var i = 0
  for (var n of nodesD) {
    nodesList.push({id:++i, label:n})
  }
  
  var edgesList = []
  for (var e of edgesD) {
    var newEdge = {from:e[0]+1,to:e[1]+1}
    if (directed) newEdge["arrows"] = "to"
    edgesList.push(newEdge)
  }
  
  var nodes = new vis.DataSet(nodesList);

  // create an array with edges
  var edges = new vis.DataSet(edgesList);  // create a network
  //var container = document.getElementById(id);
  var data = {
    nodes: nodes,
    edges: edges
  };
  var options = {
    autoResize: true,
   /* height: 400+'px',
    width: 400+'px'*/
  };
  var network = new vis.Network(container[0], data, options);

  container.click(function(){network.fit()})
  return network;
}

/**
 * Return all the neighbours of a vertex in a graph.
 * @param {string} v - label of the vertex of the graph.
 * @param {list} G - list of edges in the graph.
 * @return {list} - the list of neighbours of v in the graph G.
 **/
function neighbours(v,G) {
  let nset = []
  for(let e of G) {
    let i = e.indexOf(v)
    if(i > -1) {nset.push(e[1-i])}
  }
  return nset
}

function sum(L) {
  /*Find the sum of the elements in a list.*/
  let s=0
  for (let x of L) { s+=x }
  return s
}

/**
 * Checks if a graph is a tree.
 * @param {list} vert - list of the vertices of the graph.
 * @param {list} G - list of edges in the graph.
 * @return {integer} - 0 is the graph is a tree, -1 if the graph contains a loop, 1 if it is not connected.
 */
function isTree(vert,G) {
  let visited = []
  let next = [vert[0]]
  while(next.length>0) {
    let v = next.pop()
    let nset = neighbours(v,G)
    if (sum(nset.map(x=>visited.includes(x))) > 1) {return -1}
    visited.push(v)
    for(let n of nset) {if(!visited.includes(n)) next.push(n)}
   }
   if(visited.length === vert.length) return 1
   else return 0
}

/**
 * Find a spanning tree in a graph.
 * @param {list} vert - list of the vertices of the graph.
 * @param {list} G - list of edges in the graph.
 * @return {list} - a list of edges in the spanning tree.
 */
function spanningTree(vert,G) {
  let visited = []
  let edges = []
  let next = [vert[0]]
  while(next.length>0) {
    let v = next.pop()
    let nset = neighbours(v,G)
    for(var x of nset) {
      if(!visited.includes(x) && !next.includes(x)) edges.push([v,x])
    }
    visited.push(v)
    for(let n of nset) {if(!visited.includes(n) && !next.includes(n)) next.push(n)}
   }
   if(visited.length === vert.length) return edges
   else return []
}