# Using two arrays to store undirected edges instead of a map

## Alec Jacobson

## November 07, 2014

I profiled some of the libigl code the other day and found a performance leak corresponding to the way I sometimes dealt with undirected edges. In a triangle mesh, each oriented triangle has three *directed* edges. It's sometimes useful to find other triangles with the same edges. So if my first triangle has an edge {i,j} I may want to find all other triangles who have either also an edge {i,j} or have the reverse edge {j,i}. The *slow* way of storing such a relationship is with a `std::map`

or `std::unordered_map`

. For example you might write,

```
std::map<std::pair<int,int>,std::vector<int>> edge_to_faces;
for each face f in F
{
for each edge {i,j} in F(f)
{
if(i<j)
{
edge_to_faces[make_pair<int,int>(i,j)].push_back(f);
}else
{
edge_to_faces[make_pair<int,int>(j,i)].push_back(f);
}
}
}
```

You can do slightly better using an `std::unordered_map`

(aka hash map) and writing a `compress(i,j)`

function which maps your {i,j} or {j,i} pair to a single number.

Turns out it's much faster to build *and to use* two arrays. One which maps each directed edge instance to a unique undirected edge and then an array for the data stored at each undirected edge. Libigl provides a way of getting this first array via the `igl::unique_edge_map`

function:

```
igl::unique_edge_map(F,E,uE,EMAP,uE2E);
```

Then the previous example looks like:

```
std::vector<int,std::vector<int>> uedge_to_faces;
for each face f in F
{
for each cth edge {i,j} in F(f)
{
uedge_to_faces[EMAP(f+c*m)].push_back(f);
}
}
```

Storing `EMAP`

and `uedge_to_faces`

is technically more memory than just `edge_to_faces`

, but not asymptotically more if the data we're storing for each undirected is O(#F), as is the case here. I think this boils down to memory access. The maps access is scattered but the array is contiguous. The price to build `EMAP`

is a sort: O(m log m), but it can be down in place once and for all, where as the map needs to maintain a sort while building and conduct O(log m) searches when accessing.