cyberkronos cyberkronos - 20 days ago 6
Java Question

Java to JavaScript Type Conversion Algorithm

I have the following function that I would like to translate to JS (I am still new to JS, so having some difficulty):

It takes a complete graph of N nodes and enumerates all the unique pair matchings.

/**
*
* @param nodes The nodes still to be added to our edge list.
* @param edges The current edge list. This is mutated, so always return a clone!
*/
public static <N> List<Map<N,N>> enumerateEdges(List<N> nodes,Map<N,N> edges){
if(nodes.isEmpty()) // No more nodes to create edges from, so return our current edge list in a new list.
return Collections.singletonList(new HashMap<>(edges));


N start = nodes.get(0); //The start node of our next pair.

List<Map<N,N>> acc = new LinkedList<>(); //The accumulation of the EdgeLists

for(int i = 1; i<nodes.size(); ++i){
N end = nodes.get(i); //The end node of our pair
edges.put(start,end); //Add this pair to our edge list

List<N> unused = new ArrayList<>(nodes); // The nodes not used in our edge list.
unused.remove(i);
unused.remove(0);

acc.addAll(enumerateEdges(unused,edges));

edges.remove(start); //Remove this pair from our edge list.
}

return acc;
}


Called with:

List<Map<Integer,Integer>> results = enumerateEdges(Arrays.asList(0,1,2,3),new HashMap<>());


My current attempt at this doesn't work. It outputs empty arrays when doing a
console.log()
.

function enumerateEdges(nodes, edges) {
if (nodes.length == 0) return [];

let start = nodes[0];

let acc = [];

for(let i = 1; i < nodes.length; i++) {
let end = nodes[i];

edges = [ {start,end} ];

let unused = nodes.slice(0);
unused.splice(i,1);
unused.splice(0,1);

acc.push.apply(acc, enumerateEdges(unused,edges));

edges.splice(0, 1);
}
return acc;
}


Calling this with:

let nodes = [1,2,3,4];
let edges = [];
enumerateEdges(nodes, edges);


Does anyone have any ideas? Much appreciated.

Answer

The main issues are:

  • The end point of the recursion (when nodes.length == 0) should not return an empty array, but a copy of the edges array
  • edges = [ {start,end} ] completely overwrites whatever was in edges before. You need to push the pair on it. Furthermore
  • edges.splice(0, 1) removes the first element, but in the original code it must remove the element keyed by start, which in practice is the last element in the edges list.

Note that JavaScript has a Map constructor which you could use for edges, so it would be much like how the Java code works. But in this case I find its use overkill: an array will just work fine.

function enumerateEdges(nodes, edges) {
  if (nodes.length == 0) return [...edges]; // return copy
  let start = nodes[0];
  let acc = [];
  for(let i = 1; i < nodes.length; i++) {
    let end = nodes[i];
    edges.push({start, end}); // don't overwrite, but push 
    let unused = nodes.slice(0);
    unused.splice(i,1);
    unused.splice(0,1);
    // The spread operator will put each of the array elements as separate arguments
    // ... so no more need for the mysterious apply:
    acc.push(...enumerateEdges(unused, edges));
    edges.pop(); // in practice it is always the last element to be removed
  }
  return acc;
}

let nodes = [1,2,3,4];
let edges = [];
let result = enumerateEdges(nodes, edges);
console.log(result);
.as-console-wrapper { max-height: 100% !important; top: 0; }

Comments