bfsdfsastar.js

// create a graph class

class Graph {
	// defining vertex array and
	// adjacent list
	constructor()
	{
		this.AdjList = new Map();
	}

	// functions to be implemented

	// add vertex to the graph
addVertex(v)
{
	// initialize the adjacent list with a
	// null array
	this.AdjList.set(v, []);
}

	// add edge to the graph
addEdge(v, w,weight=1,directed=false)
{
	// get the list for vertex v and put the
	// vertex w denoting edge between v and w
    if(!this.AdjList.get(v))this.addVertex(v);
    if(!this.AdjList.get(w))this.addVertex(w);
	this.AdjList.get(v).push({e:w,w:weight});
    if(!directed)
	// Since graph is undirected,
	// add an edge from w to v also
	this.AdjList.get(w).push({e:v,w:weight});
}

	// Prints the vertex and adjacency list
printGraph()
{
	// get all the vertices
	var get_keys = this.AdjList.keys();

	// iterate over the vertices
	for (var i of get_keys)
{
		// great the corresponding adjacency list
		// for the vertex
		var get_values = this.AdjList.get(i);
		var conc = "";

		// iterate over the adjacency list
		// concatenate the values into a string
		for (var j of get_values)
			conc += j.e + " ("+ j.w+") ";

		// print the vertex and its adjacency list
		console.log(i + " -> " + conc);
	}
}


	// bfs(v)
	// dfs(v)
}
function dfs(start, target,graph) {
    var stack=[];
    stack.push([start,[start]]);
    var visited=[start];
    while(stack.length){
    console.log({node:node,stack:stack.map(a=>a[1].join('')).join(',')})
    var [node,path]=stack.pop();
    //console.log("Visiting Node " + node);
    if (node === target) {
        // We have found the goal node we we're searching for
        console.log("Found the node we're looking for!");
		console.log("path:",path)
        console.log("stack:",stack)
		console.log('Visited length',visited.length)
        return node;
    }
	var children=graph.AdjList.get(node).map(a=>a.e).reverse()
     for (var i = 0; i < children.length; i++) {
       if(!visited.includes(children[i])){
            visited.push(children[i]);
            stack.push([children[i],path.concat(children[i])])
        }else{console.log("ignore:",path.concat(children[i]))}
		stack=stack.sort()
    }    
    }   
    // We've gone through all children and not found the goal node
    console.log("Went through all children of " + start + ", returning to it's parent.");
    return null;
};

function bfs(start, target,graph) {
    var stack=[];
    stack.unshift([start,[start]]);
    var visited=[start];
    while(stack.length){
    console.log({node:node,queue:stack.map(a=>a[1].join('')).join(',')})
    var [node,path]=stack.shift();
    if (node === target) {
        // We have found the goal node we we're searching for
        console.log("Found the node we're looking for!");
		console.log("path:",path)
        console.log("stack:",stack)
		console.log('Visited length',visited.length)
        return node;
    }
	var children=graph.AdjList.get(node).map(a=>a.e)
     for (var i = 0; i < children.length; i++) {
       if(!visited.includes(children[i])){
            visited.push(children[i]);
            stack.push([children[i],path.concat(children[i])])
       }else{console.log("ignore:",path.concat(children[i]))}
    }
    }   
    // We've gone through all children and not found the goal node
    console.log("Went through all children of " + start + ", returning to it's parent.");
    return null;
};
var comparerFromFun=f=>(_a,_b)=>f(_a)-f(_b);
function bab(start, target,graph) {
    var stack=[];
    stack.unshift([{e:start,w:0},[start]]);
    var visited=[{e:start,w:0}];
    while(stack.length){
    console.log({node:node,queue:stack.map(a=>a[1].join('')+"("+a[0].w+")").join(',')})
    var [node,path]=stack.shift();
    if (node.e === target) {
        // We have found the goal node we we're searching for
        console.log("Found the node we're looking for!");
		console.log('Visited length',visited.length)
        return node;
    }
	var children=graph.AdjList.get(node.e)
     for (var i = 0; i < children.length; i++) {
		 (({w,e})=>{  
		 let finde=(_=>_.e==e);
		 let num=_=>_[0].w
		 let alph=_=>strtofloat(_[1].join(''))
		 sortstrategy=comparerFromFun(alph)
		 w+=node.w;
         if((!visited.find(finde))){
            visited.push({e,w});
            stack.push([{e,w},path.concat(e)])
		 }else if(visited.find(finde).w>w){
			console.log("throw out:",stack.splice(stack.map(_=>_[0]).findIndex(finde),1));
			visited.find(finde).w=w;
		    stack.push([{e,w},path.concat(e)]);
		 }else{console.log("ignore:",path.concat(e).join('')+`(${w})`)}
		    stack.sort(sortstrategy);
		 })(children[i])
    }
    }   
    // We've gone through all children and not found the goal node
    console.log("Went through all children of " + start + ", returning to it's parent.");
    return null;
};

function astar(start, target,graph,heuristikmap) {
	mergeCompareStrategies=(_1,_2)=>(_a,_b)=>{let r=_1(_a,_b);if(r==0){return _2(_a,_b)}else return r;}
    var stack=[];
    stack.unshift([{e:start,w:heuristikmap.get(start)},[start]]);
    var visited=[{e:start,w:0}];
    while(stack.length){
    console.log({node:node,queue:stack.map(a=>a[1].join('')+"("+a[0].w+")").join(',')})
    var [node,path]=stack.shift();
    if (node.e === target) {
        // We have found the goal node we we're searching for
        console.log("Found the node we're looking for!");
		console.log('Visited length',visited.length)
        return node;
    }
	var children=graph.AdjList.get(node.e)
     for (var i = 0; i < children.length; i++) {
		 (({w,e})=>{  
		 let finde=(_=>_.e==e);
		 let num=_=>_[0].w
		 let alph=_=>strtofloat(_[1].join(''))
		 sortstrategy=[comparerFromFun(num),comparerFromFun(alph)].reduce(mergeCompareStrategies);
		 w+=node.w-heuristikmap.get(node.e);
         if((!visited.find(finde))){
            visited.push({e,w});
            stack.push([{e,w:w+heuristikmap.get(e)},path.concat(e)])
		 }else if(visited.find(finde).w>w){
			//console.log(stack.map(_=>_[0]).findIndex(finde))
			//console.log({w,e},JSON.stringify(visited),JSON.stringify(stack))
			console.log("throw out:",stack.filter(_=>_[1].includes(e)),e);
			stack=stack.filter(_=>!_[1].includes(e));
			visited.find(finde).w=w;
		    stack.push([{e,w:w+heuristikmap.get(e)},path.concat(e)]);
		 }else{console.log("ignore:",path.concat(e).join(''))}
		    stack.sort(sortstrategy);
		 })(children[i])
    }
    }   
    // We've gone through all children and not found the goal node
    console.log("Went through all children of " + start + ", returning to it's parent.");
    return null;
};
function recurseTree(graph,node,callback,blacknode,depth=0){
if(node==blacknode)return;
var children=graph.AdjList.get(node).map(a=>a.e);
callback(node,depth);
  for (var i = 0; i < children.length; i++) {
  recurseTree(graph,children[i],callback,blacknode,depth+1)
  }
}
function alphabeta(start, [alpha,beta],graph,values) {
function backtrack(path,onode,value){
var p=path.slice();
var ismax=(p.length%2);
var node=p.pop();
//if(node=="c6"){console.log(JSON.stringify(values.get(node)),value,)}
    if(node){
    nodeo=values.get(node);
    nodeo[["b","a"][ismax]]=Math[["min","max"][ismax]](nodeo[["b","a"][ismax]],value)
    //var c=graph.AdjList.get(node).map(a=>a.e);
    nodeo.c=nodeo.c||{};
    nodeo.c[onode]=value
    //if(c[c.length-1]==onode)
    nodeo.v=Math[["min","max"][ismax]].apply(null,Object.values(nodeo.c))
    recurseTree(graph,node,_=>{let x;if((x=values.get(_))){x.b=Math.min(nodeo.b,x.b);x.a=Math.max(nodeo.a,x.a)}},onode);
    backtrack(p,node,nodeo.v)
    }
}
    var v,stack=[];
    stack.unshift([start,[start]]);
    var visited=[start];
   // values.set(start,{a:alpha,b:beta})
    while(stack.length){
   // console.log(values.get('b2'))
    //console.log({node:node,queue:stack.map(a=>a[1].join('')).join(',')})
    var [node,path]=stack.shift();
    var ismax=(path.length%2)
    if ((v=values.get(node))==undefined) {
        values.set(node,{v:[beta,alpha][ismax],a:alpha,b:beta})
    }else{// update parent
     // console.log(node,JSON.stringify(path))
//if(node=="e1")debugger;
      console.log(v.a>=v.b?"prune":"leaf",node)
      backtrack(path,null,v.v)
    }
	var children=graph.AdjList.get(node).map(a=>a.e)
     for (var i = 0; i < children.length; i++) {
       if(!visited.includes(children[i])){
            var alph=values.get(node)
           // console.log(node,children[i],alph,JSON.stringify(Array.from(values.entries())))
          //  if(alph.a>=alph.b)console.log("prune",children[i])
            visited.push(children[i]);
            stack.push([children[i],path.concat(children[i])])
       }else{console.log("ignore:",path.concat(children[i]))}
    }
    }   
    // We've gone through all children and not found the goal node
    console.log("Went through all children of " + start + ", returning to it's parent.");
    return null;
};

recurseTree(g,"a1",(node,d)=>{g.AdjList.set(node,(s=>(d%2)?s:s.reverse())(g.AdjList.get(node).sort(comparerFromFun(_=>v.get(_.e).v))))})
console.log(`a,b,4,false
d,a,3,true
b,e,4,false
e,c,9,true
c,f,5,false
c,g,4,true
d,e,4,true
d,h,6,true
e,i,6,false
i,f,5,true
f,j,8,true
g,j,4,true
g,k,5,true
h,i,6,true
i,j,12,true`.split('\n').map(a=>a.split(',')).map(a=>`g.addEdge("${a[0]}","${a[1]}",${a[2]},${a[3]})`).join('\n'))

console.log(`d,20
a,22
b,18
c,15
e,18
h,10
i,5
f,6
j,0
g,4
k,5`.split('\n').map(_=>_.split(',')).map(([a,b])=>`h.set("${a}",${b})`).join('\n'))

console.log(`a1,b1
a1,b2
a1,b3
b1,c1
b1,c2
b2,c3
b2,c4
b3,c5
b3,c6
c1,d1
c1,d2
c2,d3
c2,d4
c3,d5
c3,d6
c5,d7
c5,d8
c6,d9
c6,da
d1,e1
d1,e2
d2,e3
d2,e4
d3,e5
d3,e6
d4,e7
d4,e8
d5,e9
d5,ea
d7,eb
d7,ev
d8,ed
d8,ee
d9,ef
d9,eg
da,eh
da,ei`.split('\n').map(a=>a.split(',')).map(a=>`g.addEdge("${a[0]}","${a[1]}",true)`).join('\n'))