Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- function pathFinder(startNode,endNode,sourceGraph) {
- var copyGraph = sourceGraph;
- var sNode = copyGraph.nodes[copyGraph.nodes.indexOf(startNode)];
- var eNode = copyGraph.nodes[copyGraph.nodes.indexOf(endNode)];
- var ALGORITHM = true;
- var TDISTANCE = 0;
- for (var n in copyGraph) {
- if (n instanceof Node) {
- n.distance = Infinity;
- n.visited = false;
- }
- }
- sNode.distance = 0;
- var unvisited = copyGraph.nodes;
- unvisited.splice(unvisited.indexOf(sNode),1);
- var path = [];
- var previous = [];
- var currentNode = sNode;
- while (ALGORITHM) {
- var connectedNodes = [];
- for (var i=0;i<currentNode.edges.length;i++) {
- var length = currentNode.edges[i].v;
- if (currentNode.edges[i].c1 != currentNode && !currentNode.edges[i].c1.visited) {
- if (currentNode.distance+length < currentNode.edges[i].c1.distance) {
- currentNode.edges[i].c1.distance = currentNode.distance+length;
- }
- connectedNodes.push(currentNode.edges[i].c1);
- } else if (currentNode.edges[i].c2 != currentNode && !currentNode.edges[i].c2.visited) {
- if (currentNode.distance+length < currentNode.edges[i].c2.distance) {
- currentNode.edges[i].c2.distance = currentNode.distance+length;
- }
- connectedNodes.push(currentNode.edges[i].c2);
- }
- }
- var bestConnected = connectedNodes.sort(function(a,b) { return a.distance-b.distance; })[0];
- unvisited.splice(unvisited.indexOf(currentNode),1);
- currentNode.visited = true;
- currentNode = best;
- path.push(currentNode);
- if (currentNode == eNode) {
- ALGORITHM = false;
- break;
- }
- }
- return path;
- }
- //
- var Node = function(name) { this.n = name; this.distance = 0, this.visited = false, this.edges = []; };
- Node.prototype.setAsEdge = function(edge) { this.edges.push(edge); };
- var gNode = function(node,x,y,radius) { this.node = node, this.x = x, this.y = y, this.radius = radius; };
- var Edge = function(connect1, connect2, value) { this.c1 = connect1; this.c2 = connect2; this.v = value; connect1.setAsEdge(this); connect2.setAsEdge(this); };
- var gEdge = function(edge,x1,y1,x2,y2,midpoint) { this.edge = edge, this.endPoints = [[x1,y1],[x2,y2]], this.m = midpoint};
- var Graph = function(nodes,edges) { this.nodes = nodes; this.edges = edges; };
- var gGraph = function(graph, canvas, canvasContext) { this.graph = graph; this.canvas = canvas; this.ctxt = canvasContext; this.graphicalNodes = [], this.graphicalEdges = []; };
- gGraph.prototype.draw = function(c) {
- var NODE_RADIUS = 7;
- for (var i=0;i<this.graph.nodes.length;i++) {
- var x = Math.floor((Math.random()*(this.canvas.width-14))+14);
- var y = Math.floor((Math.random()*(this.canvas.height-14))+14);
- c.beginPath();
- c.arc(x,y,NODE_RADIUS,0,2*Math.PI);
- c.stroke();
- c.fillText(String(this.graph.nodes[i].n),x-3,y+3);
- this.graphicalNodes.push(new gNode(this.graph.nodes[i],x,y,NODE_RADIUS));
- }
- for (var i=0;i<this.graph.edges.length;i++) {
- var x1 = this.graphicalNodes[this.graph.nodes.indexOf(this.graph.edges[i].c1)].x + NODE_RADIUS;
- var y1 = this.graphicalNodes[this.graph.nodes.indexOf(this.graph.edges[i].c1)].y + NODE_RADIUS/2;
- var x2 = this.graphicalNodes[this.graph.nodes.indexOf(this.graph.edges[i].c2)].x + NODE_RADIUS;
- var y2 = this.graphicalNodes[this.graph.nodes.indexOf(this.graph.edges[i].c2)].y + NODE_RADIUS/2;
- var m = [(x1+x2)/2,(y1+y2)/2];
- c.beginPath();
- c.moveTo(x1,y1);
- c.lineTo(x2,y2);
- c.stroke();
- c.fillText(String(this.graph.edges[i].v),m[0],m[1]);
- this.graphicalEdges.push(new gEdge(this.graph.edges[i],x1,y1,x2,y2,m));
- }
- }
- //
- var simpleGraph = new Graph([],[]);
- var simpleGraphicalGraph;
- function runMe() {
- for (var i=0;i<6;i++) {
- simpleGraph.nodes.push(new Node(i+1));
- }
- simpleGraph.edges.push(new Edge(simpleGraph.nodes[0],simpleGraph.nodes[5],14));
- simpleGraph.edges.push(new Edge(simpleGraph.nodes[0],simpleGraph.nodes[2],9));
- simpleGraph.edges.push(new Edge(simpleGraph.nodes[0],simpleGraph.nodes[1],7));
- simpleGraph.edges.push(new Edge(simpleGraph.nodes[1],simpleGraph.nodes[2],10));
- simpleGraph.edges.push(new Edge(simpleGraph.nodes[1],simpleGraph.nodes[3],15));
- simpleGraph.edges.push(new Edge(simpleGraph.nodes[2],simpleGraph.nodes[5],2));
- simpleGraph.edges.push(new Edge(simpleGraph.nodes[2],simpleGraph.nodes[3],11));
- simpleGraph.edges.push(new Edge(simpleGraph.nodes[3],simpleGraph.nodes[4],6));
- simpleGraph.edges.push(new Edge(simpleGraph.nodes[5],simpleGraph.nodes[4],9));
- simpleGraphicalGraph = graphToGraphicalGraph(simpleGraph,document.getElementById('theCanvas'));
- simpleGraphicalGraph.draw(simpleGraphicalGraph.ctxt);
- }
- function graphToGraphicalGraph(graph,canvasElement) {
- return new gGraph(graph,canvasElement,canvasElement.getContext('2d'));
- }
- //
- window.addEventListener('load',runMe,false);
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement