Thread Subject:

computing the list of triangles out of the list of edges of a graph

Hello,
I posted recently a message that wasn't clear enough. Here is a better one I hope: I am looking for a program that computes the list of triangles (and tetrahedrons) out of the list of edges of a graph. My input is a list of pairs of vertexes of a graph, that is to say a list of edges. And what I am looking for as an output is a list of triads of vertices (triangles) that are computed from the list of edges. This graph has 300 vertices and 6000 edges, and will probably have a few hundreds triangles. The purpose is to build simplexes for this graph.
Best regards,
Florent

"florent.dieterlen@bluewin.ch" <florent.dieterlen@bluewin.ch> wrote in message <15614240.1237979990406.JavaMail.jakarta@nitrogen.mathforum.org>...
> Hello,
> I posted recently a message that wasn't clear enough. Here is a better one I hope: I am looking for a program that computes the list of triangles (and tetrahedrons) out of the list of edges of a graph. My input is a list of pairs of vertexes of a graph, that is to say a list of edges. And what I am looking for as an output is a list of triads of vertices (triangles) that are computed from the list of edges. This graph has 300 vertices and 6000 edges, and will probably have a few hundreds triangles. The purpose is to build simplexes for this graph.
> Best regards,
> Florent

Merely knowing the list of edges is not sufficient to
turn this into a unique tessellation. For example,
suppose I give you the four corners of a square,
along with the corresponding four edges. There
are two possible ways to triangulate the square
from this information.

Do you know that the edges arise from a complete
triangulation? If so, then all you must do is to find
all cycles of length such that there are exactly 3
edges before returning to the starting node. Just
build a tree that starts from each vertex. Those
branches that return to the start point in exactly 3
steps are triangles.

In 3-d, knowing only the list of edges is even of
less help.

John

Hi John,
I again didn't explain myself properly: i get a triangle if i have the three edges, therefore there is no ubiquity.
Florent.dieterlen@bluewin.ch

"florent.dieterlen@bluewin.ch" <florent.dieterlen@bluewin.ch> wrote in message <15614240.1237979990406.JavaMail.jakarta@nitrogen.mathforum.org>...
> I am looking for a program that computes the list of triangles (and tetrahedrons) out of the list of edges of a graph. .....

  I would think the way to proceed would be to first build the upper part of an adjacency matrix, A, from your list. If your vertices are numbered from 1 to n, this should be a straightforward task. Starting from all 0's in A, for each entry pair (i,j) in your list, ordered with i<j, you set A(i,j) to 1.

  Then within the matrix, for each i<j with A(i,j) equal to 1 you seek k, j<k with both A(i,k) and A(j,k) equal to 1. Each of these gives a new unique triangle.

  This would be an order n^3 algorithm which could be realized using nested for-loops. I see no difficulties in any of this. Something like this:

 % After A is created
 for i = 1:n-2
  for j = i+1:n-1
   if A(i,j)
    for k = j+1:n
     if A(i,k) & A(j,k)
      "add (i,j,k) to triangle list"
     end
    end
   end
  end
 end

  For tetrahedrons, the nesting has to go one step further.

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gqdrhe$s8q$1@fred.mathworks.com>...
> "florent.dieterlen@bluewin.ch" <florent.dieterlen@bluewin.ch> wrote in message <15614240.1237979990406.JavaMail.jakarta@nitrogen.mathforum.org>...
> > I am looking for a program that computes the list of triangles (and tetrahedrons) out of the list of edges of a graph. .....
>
> I would think the way to proceed would be to first build the upper part of an adjacency matrix, A, from your list. If your vertices are numbered from 1 to n, this should be a straightforward task. Starting from all 0's in A, for each entry pair (i,j) in your list, ordered with i<j, you set A(i,j) to 1.
>
> Then within the matrix, for each i<j with A(i,j) equal to 1 you seek k, j<k with both A(i,k) and A(j,k) equal to 1. Each of these gives a new unique triangle.
>
> This would be an order n^3 algorithm which could be realized using nested for-loops. I see no difficulties in any of this. Something like this:
>
> % After A is created
> for i = 1:n-2
> for j = i+1:n-1
> if A(i,j)
> for k = j+1:n
> if A(i,k) & A(j,k)
> "add (i,j,k) to triangle list"
> end
> end
> end
> end
> end
>
> For tetrahedrons, the nesting has to go one step further.
>
> Roger Stafford

This is basically what I described as a tree.
Start out at any vertex of the graph, and
follow along any edge that connects to that
vertex.

In 3-d however, it is not just one additional
step. For a tetrahedron to exist, based only
on the edges, there are 6 edges. You need
to verify that all 6 edges exist.

So it is more than just one step further.

John