Is there any file format or way to export the adjacency matrix describing the connectivity of vertices? Or is there any way I can do this easily?

**Edited by DevLiquidKnight, 08 February 2014 - 10:48 PM.**

Started by DevLiquidKnight, Feb 08 2014 10:19 PM

6 replies to this topic

Sponsor:

Posted 09 February 2014 - 12:09 AM

Basically if two vertices share the same edge the matrix entry would contain a 1 otherwise it would contain 0. Not much different then that used for a graph algorithm. I realize this isn't very common request I just wondered if anyone has any idea how I could go about doing this.

**Edited by DevLiquidKnight, 09 February 2014 - 12:10 AM.**

Posted 09 February 2014 - 01:05 AM

It's not usually stored since it takes a lot of space (in O(n^2) of the number of vertices) and is fairly cheap to recreate on demand. To create the matrix just create a square nxn matrix, and run through each entry (x, y), setting it to 1 if there exists an edge between the two vertices x and y. The "is there an edge" question may be hard to answer depending on your data format, so what format are your models in? What does your adjacency information look like in raw form (not matrix form)?

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

- *Pessimal Algorithms and Simplexity Analysis*

Posted 09 February 2014 - 01:36 AM

I could put them in any format something like blender supports? I was hoping to just use obj file format if possible. And you are right its a very large matrix hence why I would like to automate this process. I can see how to iterate through the matrix but the "is there a edge" question seems hardest to me.

**Edited by DevLiquidKnight, 09 February 2014 - 01:39 AM.**

Posted 09 February 2014 - 01:57 AM

I could put them in any format something like blender supports? I was hoping to just use obj file format if possible. And you are right its a very large matrix hence why I would like to automate this process. I can see how to iterate through the matrix but the "is there a edge" question seems hardest to me.

If you're using obj format then it's pretty much already done for you. The faces section of the file defines the list of triangles, read that in then for each vertex initialize a list which is then populated with every other vertex that shares a triangle with that vertex (by iterating over triangles). If that is so then the two are obviously adjacent. Once you're done, it's just a matter of interpreting the list of vertices to create the matrix, since the answer "is there an edge from u to v" then becomes "does list[u] contain v", or "does list[v] contain u" (if your edges are undirected).

Triangles aren't the only faces supported by the format, for arbitrary polygons you would triangulate it and proceed as usual. Though in practice I have yet to come across an obj file that used anything more complex than quads (four vertices per face) instead of NURBS or similar.

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

- *Pessimal Algorithms and Simplexity Analysis*

Posted 09 February 2014 - 09:04 AM

What are you trying to do?

Considering the (common?) case of a 2-manifold mesh the number of edges is actually O(number of vertices). So storing the adj. matrix seems like a waste of space. Consider adj. lists instead.

If you are interested in the connectivity of your mesh (eg. what are the adj. faces of this edge, loop through all edges of a face...) there

are more suitable data structures like the half edge DS.

If you really need the adj. matrix, ignore this post.