Jamgreen Jamgreen - 5 months ago 45
Javascript Question

Unique pair of nodes in graph

I have a graph with nodes A, B, C and multiple edges between these nodes.

How can I get the unique pairs (A, B), (A, C), (B, C)?

One algorithm could be to say

alreadyVisited = [];

for left in nodes:
for right in nodes:
if (left, right) not in alreadyVisited:
alreadyVisited.push((left, right))

but is this the most efficient algorithm to achieve this?


You could iterate the nodes and iterates in a nested loop only the rest of the nodes.

var nodes = ['A', 'B', 'C'],
    i, j,
    edges = [];

for (i = 0; i < nodes.length - 1; i++) {
    for (j = i + 1; j < nodes.length; j++) {
        edges.push([nodes[i], nodes[j]]);