Finding unique edges in a list of edges

[Rishavs]

Hi

I am creating a procedural graph made up of points and lines connecting the said points.

I have created a list of edges/lines as;

Code: Select all

{
    {{a1, b1}, {x1, y1} },
    {{a2, b2}, {x2, y2} },
    ...
    ...
    {{an, bn}, {xn, yn} }
}

Now I want to find all the unique edges.
Ie. remove all edges that have same starting point and ending point.

For example,

Code: Select all

{{a7, b19}, {x12, y15}} 

is same as

Code: Select all

{{a7, b19}, {x12, y15}} 

(same edges coming up more than once in the list)
which is same as

Code: Select all

{{x12, y15}, {a7, b19}}

(points flipped to give essentially the same line)

I dont know how to go about this. Any ideas?

I am not really looking for the fastest way of doing it. Just the simplest so that i can understand it (not much of a programmer )

[mr_happy]

Three ideas spring to mind, (none of which are very elegant!):

Possibly the simplest way is to run through the existing list as you are about to add each edge and see if it's already included (in either form).

Alternatively, if the order isn't important, you could sort the list after construction and remove the duplicates.

Or you could do it on the fly/visually by allocating, say, a unique colour to each pair of points - if you were about to plot two points of a new edge (I'm assuming 2d) and find that those points are already occupied by points of the same colour you know it's a duplicate. (You'd need a list for each point so multiple points belonging to different edges could occupy the same space).

[ivan]

The first thing that comes to mind is reuse your point references:

Code: Select all

-- points
points = {}
-- generate N random points
-- todo-make sure all points are unique
for i = 1, N do points[i] = { math.random(), math.random() } end
-- edges
edges = {}
-- generate edges using existing references
edges[1] = { points[1], points[2] }

So now you can compare points by reference: assert(points[1] ~= points[2])

[pgimeno]

What Ivan said, and also if you add them in a "canonical" order (any order that is well defined will do, for example lexicographical order of an,bn and xn,yn) rather than arbitrary, you can later just look for duplicates and remove them.

To insert the edges in lexicographical order, you can do for example:

Code: Select all

function addEdge(a, b, x, y)
  if a > x or a == x and b > y then
    a, b, x, y = x, y, a, b
  end
  edges[#edges+1] = {{a, b}, {x, y}}
end

With Ivan's method:

Code: Select all

function addEdge(pointA, pointB)
  if pointA[1] > pointB[1] or pointA[1] == pointB[1] and pointA[2] > pointB[2] then
    pointA, pointB = pointB, pointA
  end
  edges[#edges+1] = {pointA, pointB}
end

For using Ivan's trick this way, you must have no duplicate points to start with, otherwise you can have points that compare different but have the same values.

You can use mr_happy's suggestion above too, and check if an edge is already in the list before inserting it. That would spare you from having to remove duplicates. But if you absolutely need to remove duplicates later, it can be done easily in O(n²) steps with two nested loops:

Code: Select all

-- this code assumes Ivan's trick, and that the edges are in some
-- canonical order, to spare us from having to compare A,B and B,A
function removeDupes()
  for i = #edges - 1, 1, -1 do
    local edge_i_1, edge_i_2 = edges[i][1], edges[i][2]
    for j = #edges, i + 1, -1 do
      if edge_i_1 == edges[j][1] and edge_i_2 == edges[j][2] then
        table.remove(edges, j)
      end
    end
  end
end

[Rishavs]

thanks everyone. lots of good ideas here. Gonna try them now.