Java to JavaScript Type Conversion Algorithm

Question

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.

.splice() is not a replacement for .remove() because it does not modify the array; it returns a new array. — Pointy
– Pointy, Commented Nov 12, 2016 at 21:46
Thanks for the tip but also I've noticed that the acc.push.apply(acc, enumerateEdges(unused,edges)) doesn't actually push edges to acc — cyberkronos
– cyberkronos, Commented Nov 12, 2016 at 22:01
@Pointy, splice does mutate the array like remove does. — trincot
– trincot, Commented Nov 12, 2016 at 23:23
@cyberkronos, the push.apply works, but the function result is always an empty array, because that is what you return (by error) in the first if statement. — trincot
– trincot, Commented Nov 12, 2016 at 23:24
@trincot oops you're right; I was thinking about .slice() :) One little "p". — Pointy
– Pointy, Commented Nov 13, 2016 at 0:08

trincot · Accepted Answer · 2016-11-14 09:52:18Z

2

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. I added the version using Map in a second snippet.

Edit: I would also suggest to change the condition length == 0 to length < 2, so the thing doesn't get into trouble when you pass it an odd number of nodes.

function enumerateEdges(nodes, edges) {
  if (nodes.length < 2) 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; }

For fun, here is a highly condensed version of it:

function enumerateEdges(nodes, edges) {
  return nodes.length < 2 ? edges
        : nodes.reduce( (acc, end, i) => (i<2 ? [] : acc).concat(
            enumerateEdges(nodes.slice(1, i).concat(nodes.slice(i+1)), 
                           [...edges, {start:nodes[0], end}])
          ) );
}

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

Alternative with Map:

function enumerateEdges(nodes, edges) {
  if (nodes.length < 2) return [...edges]; // return copy
  let start = nodes[0];
  let acc = [];
  for(let i = 1; i < nodes.length; i++) {
    let end = nodes[i];
    edges.set(start, end); // <-- Map method to add
    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.delete(start); // <-- Map method to remove
  }
  return acc;
}

let nodes = [1,2,3,4];
let edges = new Map(); // <-- use Map
let result = enumerateEdges(nodes, edges);
console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Note that the edges are now output as simple pair-arrays, like [1, 2], instead of {start: 1, end: 2}. This can of course be changed, but I left it like this -- it is the default way on how Maps are translated to arrays.

edited Nov 14, 2016 at 9:52

answered Nov 12, 2016 at 23:22

trincot

357k38 gold badges282 silver badges339 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

cyberkronos Over a year ago

Thanks for the detailed explanation! Helps a lot.

cyberkronos Over a year ago

I have a follow up question. Would this be scalable for say 100 nodes instead of 4. Is there were you can use a Map function instead?

trincot Over a year ago

I added a snippet that uses a Map. I don't think it matters much for scaling. I also adapted the test for length == 0 which would be problematic when the graph has an odd number of nodes. I do wonder however: the output puts all found edges in a flat array, without grouping them per configuration. From what I understand of the Java code, it is like that also in the Java version (addAll). You may want to change that.

Collectives™ on Stack Overflow

Java to JavaScript Type Conversion Algorithm

1 Answer 1

Alternative with Map:

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Alternative with Map:

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related