All possible triangles in terms of edges in RCCP

Question

NB: This question was first posted in Stack Overflow, it has been moved here on suggestion.

I'm stuck on finding an efficient algorithm to the following problem:

Given a complete undirected graph G with n nodes, the objective is to find all possible triangles in G in terms of edge indexes.

For example, with n = 3:

• 1, 2, 3

With n = 4, there are 4 triangles:

• 1, 2, 4
• 1, 3, 5
• 2, 3, 6
• 4, 5, 6

So the final triangle consists of edges nr 4, 5 and 6.

Currently my solution is quite inefficient, it works by calculating all 3-combinations to find triangles, and all 2-combinations to find pairs of nodes. Then I iterate over each triangle and search for the correct pairs and report the indexes.

Here is my current solution in RCPP:

// [[Rcpp::export]]
IntegerMatrix getallTriangles(size_t& n) {
  IntegerVector vals = seq(0, n-1);
  
  // comb_n() works as R's utils::combn()
  IntegerMatrix edges = comb_n(vals, 2);
  IntegerMatrix triangles = comb_n(vals, 3);
  
  size_t nEdges = edges.ncol();
  size_t nTriangles = triangles.ncol();
  
  // Output matrix
  IntegerMatrix out(3, nTriangles);

  for(size_t i = 0; i < nTriangles; i++) {
      
    IntegerVector triangle = triangles(_, i);
    // Get all edges in this triangle
    IntegerMatrix triangleCombn = comb_n(triangle, 2);
    
    for(size_t j = 0; j < 3; j++) {
      
      // Take an edge from the triangle
      IntegerMatrix::Column col = triangleCombn(_, j);
      
      // And compare it to all known edges
      for(size_t k = 0; k < nEdges; k++) {
        
        IntegerMatrix::Column edge = edges(_, k);
        
        if(col[0] == edge[0] && col[1] == edge[1]) {
            // We have found the edge
            out(j, i) = k + 1;
            // Stop searching
            break;
        }
      }
    }
  }
  
  return out;
}

Calling this function in R:

> getallTriangles(4)
     [,1] [,2] [,3] [,4]
[1,]    1    1    2    4
[2,]    2    3    3    5
[3,]    4    5    6    6

My gut says there has got to be a better way to do this, or is there really no better solution than to do a search?

EDIT

Based on the answers given below, here is a working rcpp version:

// [[Rcpp::export]]
IntegerMatrix getallTriangles(size_t& n) {
  
  IntegerVector vals = seq(1, n);
  IntegerMatrix triangles = comb_n(vals, 3);
  
  size_t nTriangles = triangles.ncol();
  
  // Output matrix
  IntegerMatrix out(3, nTriangles);
  
  for(size_t i = 0; i < nTriangles; i++) {
    for(size_t j = 0; j < 2; j++) {
      for(size_t k = j + 1; k < 3; k++) {

        // Take an edge from the triangle
        size_t a = triangles(j, i);
        size_t b = triangles(k, i);
        
        out(j + k - 1, i) = (a - 1) * n - a * (a + 1) / 2 + b;
      }
    }
  }
  
  return out;
}

Maybe this will be of use to someone.

Cheers

Answer 1

I think I understand what you're doing, but I'm not fully sure, so let's start with a description of what I think the problem is.

you have a complete graph $K_n$, with nodes numbered from 1-n, and edges numbered in lexicographic order based on their two end nodes. You seek all the triangles in the graph, given as a list of edges.

You already have it set up to give you the triangles as comb_n(vals, 3), so I'll skip that part and get to the meat: you need to find the edge, based on the nodes, without a long search.

Fortunately, this isn't hard. Given two node indices $a < b$:

$$e = \frac{n \times (n-1)}{2} - \frac{(n-a)\times(n-a+1)}{2}+b-a=an-n-\frac{a^2}{2}-\frac{a}{2}+b$$

Answer 2

This seems to be a complete graph (i.e. there is an edge joining each pair of nodes/vertices). If so, there are ${n \choose 3}$ triangles: just choose $3$ nodes/vertices and the corresponding three edges from a triangle. You seem to be using R's combn function to label the edges and triangles, starting at $1$ (you might find it easier to start counting vertices from $1$ too).

If so, the following R code works

verticestoedge <- function(a, b, n){   #presumes 1 <= a < b <= n
    (a - 1) * n - a * (a + 1) / 2 + b 
    }
alltriangleedges <- function(n){
    trianglevertices <- utils::combn(1:n, 3)
    rbind(verticestoedge(trianglevertices[1, ], trianglevertices[2, ], n), 
          verticestoedge(trianglevertices[1, ], trianglevertices[3, ], n), 
          verticestoedge(trianglevertices[2, ], trianglevertices[3, ], n))
    }

and for example

alltriangleedges(4)  

gives

     [,1] [,2] [,3] [,4]
[1,]    1    1    2    4
[2,]    2    3    3    5
[3,]    4    5    6    6

Now seeing Dan Uznanski's answer, his expression is the same as verticestoedge here