Take Breadth-First Search/tree.js (shown below) as an example. The i

<a class="user-mention notranslate" data-hovercard-type="user" data-hovercard-url="/us

Enforce the consistency between function parameters and algorithm input,about algorithm-visualizer/algorithms

Comments (4)

64json commented on July 22, 2024 1

Makes sense and feel free to contribute yourself.

FYI none of us are actively maintaining the project. You don't need to tag us on every issue, we will take a look when we get time.

from algorithms.

unfode commented on July 22, 2024

@64json @MarkKoz @nem035 @duaraghav8 @TornjV

from algorithms.

unfode commented on July 22, 2024

Got it. I won't tag you in future issues.

And I will rewrite some algorithm code and make pull requests :-)

from algorithms.

unfode commented on July 22, 2024

Here's a related issue: where should we place code for tracer initialization and tracer.set()?

To me it seems more natural to place tracer code inside the algorithm function. For Breadth-First Search/tree.js, it would be

 // import visualization libraries { 
 const { Tracer, GraphTracer, LogTracer, Layout, VerticalLayout } = require('algorithm-visualizer'); 
 // } 
  
 const G = [ // G[i][j] indicates whether the path from the i-th node to the j-th node exists or not 
   [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0], 
   [0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0], 
   [0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0], 
   [0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0], 
   [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1], 
   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
   [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
 ]; 

 function BFS(G, s) { // s = start node 

   // define tracer variables { 
   const tracer = new GraphTracer(); 
   const logger = new LogTracer(); 
   tracer.log(logger); 
   Layout.setRoot(new VerticalLayout([tracer, logger])); 
   tracer.set(G); 
   tracer.layoutTree(0); 
   Tracer.delay(); 
   // } 

   const Q = []; 
   Q.push(s); // add start node to queue 
   // visualize { 
   tracer.visit(s); 
   Tracer.delay(); 
   // } 
   while (Q.length > 0) { 
     const node = Q.shift(); // dequeue 
     for (let i = 0; i < G[node].length; i++) { 
       if (G[node][i]) { // if current node has the i-th node as a child 
         Q.push(i); // add child node to queue 
         // visualize { 
         tracer.visit(i, node); 
         Tracer.delay(); 
         // } 
       } 
     } 
   } 
 } 
  
 BFS(G, 0);

The reason is that we may want to trace, say, an array declared inside the algorithm function.

A case in point is the array S in Dijkstra's Shortest Path/code.js (shown below). If we enforce the correspondence between algorithm and function, S should be declared inside the algorithm function, which requires (at least) tracerS.set(S) be placed inside the function.

algorithms/Greedy/Dijkstra's Shortest Path/code.js

Lines 1 to 88 in fe3adcf

 // import visualization libraries { 

 const { Tracer, Array1DTracer, GraphTracer, LogTracer, Randomize, Layout, VerticalLayout } = require('algorithm-visualizer'); 

 // } 

 const G = Randomize.Graph({ N: 5, ratio: 1, directed: false, weighted: true }); 

 const MAX_VALUE = Infinity; 

 const S = []; // S[end] returns the distance from start node to end node 

 for (let i = 0; i < G.length; i++) S[i] = MAX_VALUE; 

 // define tracer variables { 

 const tracer = new GraphTracer().directed(false).weighted(); 

 const tracerS = new Array1DTracer(); 

 const logger = new LogTracer(); 

 Layout.setRoot(new VerticalLayout([tracer, tracerS, logger])); 

 tracer.log(logger); 

 tracer.set(G); 

 tracerS.set(S); 

 Tracer.delay(); 

 // } 

 function Dijkstra(start, end) { 

 let minIndex; 

 let minDistance; 

 const D = []; // D[i] indicates whether the i-th node is discovered or not 

 for (let i = 0; i < G.length; i++) D.push(false); 

 S[start] = 0; // Starting node is at distance 0 from itself 

 // visualize { 

 tracerS.patch(start, S[start]); 

 Tracer.delay(); 

 tracerS.depatch(start); 

 tracerS.select(start); 

 // } 

 let k = G.length; 

 while (k--) { 

 // Finding a node with the shortest distance from S[minIndex] 

 minDistance = MAX_VALUE; 

 for (let i = 0; i < G.length; i++) { 

 if (S[i] < minDistance && !D[i]) { 

 minDistance = S[i]; 

 minIndex = i; 

 } 

 } 

 if (minDistance === MAX_VALUE) break; // If there is no edge from current node, jump out of loop 

 D[minIndex] = true; 

 // visualize { 

 tracerS.select(minIndex); 

 tracer.visit(minIndex); 

 Tracer.delay(); 

 // } 

 // For every unvisited neighbour of current node, we check 

 // whether the path to it is shorter if going over the current node 

 for (let i = 0; i < G.length; i++) { 

 if (G[minIndex][i] && S[i] > S[minIndex] + G[minIndex][i]) { 

 S[i] = S[minIndex] + G[minIndex][i]; 

 // visualize { 

 tracerS.patch(i, S[i]); 

 tracer.visit(i, minIndex, S[i]); 

 Tracer.delay(); 

 tracerS.depatch(i); 

 tracer.leave(i, minIndex); 

 Tracer.delay(); 

 // } 

 } 

 } 

 // visualize { 

 tracer.leave(minIndex); 

 Tracer.delay(); 

 // } 

 } 

 // logger { 

 if (S[end] === MAX_VALUE) { 

 logger.println(`there is no path from ${start} to ${end}`); 

 } else { 

 logger.println(`the shortest path from ${start} to ${end} is ${S[end]}`); 

 } 

 // } 

 } 

 const s = Randomize.Integer({ min: 0, max: G.length - 1 }); // s = start node 

 let e; // e = end node 

 do { 

 e = Randomize.Integer({ min: 0, max: G.length - 1 }); 

 } while (s === e); 

 // logger { 

 logger.println(`finding the shortest path from ${s} to ${e}`); 

 Tracer.delay(); 

 // } 

 Dijkstra(s, e);

from algorithms.

Enforce the consistency between function parameters and algorithm input about algorithms HOT 4 OPEN

Comments (4)

Related Issues (3)

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent

	// import visualization libraries {
	const { Tracer, Array1DTracer, GraphTracer, LogTracer, Randomize, Layout, VerticalLayout } = require('algorithm-visualizer');
	// }

	const G = Randomize.Graph({ N: 5, ratio: 1, directed: false, weighted: true });
	const MAX_VALUE = Infinity;
	const S = []; // S[end] returns the distance from start node to end node
	for (let i = 0; i < G.length; i++) S[i] = MAX_VALUE;

	// define tracer variables {
	const tracer = new GraphTracer().directed(false).weighted();
	const tracerS = new Array1DTracer();
	const logger = new LogTracer();
	Layout.setRoot(new VerticalLayout([tracer, tracerS, logger]));
	tracer.log(logger);
	tracer.set(G);
	tracerS.set(S);
	Tracer.delay();
	// }

	function Dijkstra(start, end) {
	let minIndex;
	let minDistance;
	const D = []; // D[i] indicates whether the i-th node is discovered or not
	for (let i = 0; i < G.length; i++) D.push(false);
	S[start] = 0; // Starting node is at distance 0 from itself
	// visualize {
	tracerS.patch(start, S[start]);
	Tracer.delay();
	tracerS.depatch(start);
	tracerS.select(start);
	// }
	let k = G.length;
	while (k--) {
	// Finding a node with the shortest distance from S[minIndex]
	minDistance = MAX_VALUE;
	for (let i = 0; i < G.length; i++) {
	if (S[i] < minDistance && !D[i]) {
	minDistance = S[i];
	minIndex = i;
	}
	}
	if (minDistance === MAX_VALUE) break; // If there is no edge from current node, jump out of loop
	D[minIndex] = true;
	// visualize {
	tracerS.select(minIndex);
	tracer.visit(minIndex);
	Tracer.delay();
	// }
	// For every unvisited neighbour of current node, we check
	// whether the path to it is shorter if going over the current node
	for (let i = 0; i < G.length; i++) {
	if (G[minIndex][i] && S[i] > S[minIndex] + G[minIndex][i]) {
	S[i] = S[minIndex] + G[minIndex][i];
	// visualize {
	tracerS.patch(i, S[i]);
	tracer.visit(i, minIndex, S[i]);
	Tracer.delay();
	tracerS.depatch(i);
	tracer.leave(i, minIndex);
	Tracer.delay();
	// }
	}
	}
	// visualize {
	tracer.leave(minIndex);
	Tracer.delay();
	// }
	}
	// logger {
	if (S[end] === MAX_VALUE) {
	logger.println(`there is no path from ${start} to ${end}`);
	} else {
	logger.println(`the shortest path from ${start} to ${end} is ${S[end]}`);
	}
	// }
	}

	const s = Randomize.Integer({ min: 0, max: G.length - 1 }); // s = start node
	let e; // e = end node
	do {
	e = Randomize.Integer({ min: 0, max: G.length - 1 });
	} while (s === e);
	// logger {
	logger.println(`finding the shortest path from ${s} to ${e}`);
	Tracer.delay();
	// }
	Dijkstra(s, e);