Enforce the consistency between function parameters and algorithm input

[unfode]

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

The input to the BFS algorithm is a graph (or tree) and a starting node, while the BFS function only takes the starting node s as parameter, leaving the graph G as a global variable. In my humble opinion, it would be better to avoid such mismatch, which can potentially confuse learners.

Note: This mismatch also appears in some other algorithm code.

algorithms/Brute Force/Breadth-First Search/tree.js

Lines 1 to 50 in fe3adcf

	// 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],
	];
	// 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();
	// }
	function BFS(s) { // s = start node
	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(0);

[unfode]

@64json @MarkKoz @nem035 @duaraghav8 @TornjV

[64json]

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.

[unfode]

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

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

[unfode]

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);