Code covered by the BSD License  

Highlights from
Toolbox Graph


4.5 | 25 ratings Rate this file 313 Downloads (last 30 days) File Size: 2.87 MB File ID: #5355
image thumbnail

Toolbox Graph



26 Jun 2004 (Updated )

A toolbox to perform computations on graph.

| Watch this File

File Information

Graph theory toolbox
Copyright (c) 2007 Gabriel Peyre

This toolbox contains useful functions to deal with graph and triangulation.

The basic representation of a graph of n vertices is the adjacency matrix A where A(i,j)=1 if vertex i is linked to vertex j. A graph often comes with a geometric realization in R^d which an (d,n) matrix where vertex(:,i) is the position of the ith vertex.

A triangulation of m faces and n vertex is represented through:
* a set of faces which is a (3,m) matrix where face(:,i) are the vertices indexes of the ith face.
* a set of vertex which is a (d,n) matrix.
The toolbox contains function to deal more easily with a triangulation data structure, and allows to retrieve vertex and face 1-ring and switch from adjacency to faces.

The graph part of the toolbox contains function to creates synthetic graph and compute shortest path (dijkstra and isomap algorithm).

This toolbox contains a lot of function to deal with spectral theory of triangulation. You can load triangulations from files and then display the resulting mesh. It allows to compute various laplacian operator, and the to compute parameterization using spectral decomposition, harmonic mapping, free boundary harmonic mapping, and isomap.


This file inspired Local Depth Sift And Scale Invariant Spin Image Local Features For 3 D Meshes and Icp Registration Using Efficient Variants And Multi Resolution Scheme.

MATLAB release MATLAB 7 (R14)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (33)
19 Dec 2014 Helen

As others have pointed out, the compute_curvature function results in an index out of bounds error in some cases. So far, my untested and kind of random 'fix' was to comment out the code

%normal = normal'; (line 72) and
insert it again as
normal = normal'; (at line 146, after compute_normal()).

This seems to avoid the out of index error BUT I have no idea if it a right thing to do otherwise.

Some support from Gabriel, would be highly appreciated.

Thanks a lot for your efforts

(on line 75 "dp = sum( normal(:,E(:,1)) .* normal(:,E(:,2)), 1 );")

24 Nov 2014 Alec

Thanks for this library.

Just spent quite some time tracking down the same bug in `write_ply.m` as Chris Rorden found a year ago. Please fix it.

28 Oct 2014 dhara

great tool.. thnx...
but i m able to read this .wrl file cara1_abajo.wrl.. plz anybody help me.. it's urgent... i tried a lot but getting error in reshape command

05 Apr 2014 David

It seems to be a useful tool.
There might be a bug to generate ply files. I there is always a bug as follow.

Error using write_ply (line 22)
vertex does not have correct format.

However, I have strictly follow the input format for using this function. The vertex is 'nb.vert x 3' array, can you help me about that?

05 Apr 2014 Xu

Good tools.

21 Mar 2014 HAYOUNG

Many thanks to this great toolbox.
FYI, he also made comprehensive manual in his website ( re/matlab/graph/content.html), which is also nice.

21 Mar 2014 HAYOUNG

Many thanks to great toolbox.

21 Feb 2014 ness


Thanks for your code.

I have a question when i use plot_mesh i can visualize the 3D mesh, can i hold on the same figure a 2d image. when i use 'hold on' then 'imshow' it doesn't work.

03 Feb 2014 Ben

anyone solved the bug in the compute_curvature function (on line 75 "dp = sum( normal(:,E(:,1)) .* normal(:,E(:,2)), 1 );")? Thanks!

10 Jan 2014 Anass


I'm asking if the function " red_obj()" can read a model with texture?

I tried but it did not be able to read it.

Can you help please?

18 Jul 2013 David

There is some code to display geometry images. Does this toolbox provide code for producing a geometry image from a mesh?

04 Jul 2013 Chris Rorden

Lots of nice code. I did find a small bug with write_ply when creating files with more than 32767 faces. To fix this you need to change the lines
IntegerDataMin = [-128,0,-2^15,-2^31,0];
IntegerDataMax = [127,255,2^16-1,2^31-1,2^32-1];
to read
IntegerDataMin = [-128,0,-2^15,0,-2^31,0];
IntegerDataMax = [127,255,2^15-1,2^16-1, 2^31-1,2^32-1];

30 Jun 2011 Eitan

Very useful tool.
I noticed that compute_curvature tries to enforce Cmin<=Cmax. In case of negative Cmax, it can cause abs(Cmin)>abs(Cmax), which I think is not right. IMHO these lines can be removed from the function.

08 Jun 2011 wikimenWoko wikk  
28 Jul 2010 Julian Xue

is there a method here to just plot an adjacency matrix?

20 Nov 2009 Ged Ridgway

Looks really useful. However, isomap seems to fail:
>> xy = isomap(dat);
??? Undefined command/function 'compute_nn_graph'.
Error in ==> isomap at 85
D = compute_nn_graph(X,options);

17 Nov 2009 Peter  
12 Nov 2009 kamel

Very useful
compute_curvature will generate an error on line 75 ("dp = sum( normal(:,E(:,1)) .* normal(:,E(:,2)), 1 );") for SOME surfaces.
what's the solution of this bug

18 Oct 2009 Raymond Cheng

Thanks for your sharing.


Very useful.

But I have a question: when I tried to use the function "perform_mesh_simplification" to make the simplificatino for mesh. Matlab said that QSlim is not a command. And here is the command where situates the problem: "system(['QSlim tmp.smf -o tmp1.smf -s ' num2str(nface)]);"

I'm afraid this is because the qslim.exe was missed?

thanks for your explaination!

09 Jun 2009 europe lee

test_diffusion_wavelet.m file did not work!
Because it miss some functions, such as MakeDiffusion function.
Although I download and install diffusion wavelet code from MAURO MAGGIONI, I find that MakeDiffusion in his code is different from yours,like parameter called 'gauss' in your MakeDiffusion was not included in Mauro's MakeDiffusion.

20 May 2009 Ofra

Very useful.
Is there a Matlab 2008b version ?

07 Apr 2009 Axel zheng


03 Mar 2009 David S

Just wanted to add that the error I mentioned is caused by the flipping of the sign of the surface normal of just one face by rearranging the order of the vertices in the face matrix

03 Mar 2009 David S

Very useful, except for a bug in the compute_curvature function:

compute_curvature will generate an error on line 75 ("dp = sum( normal(:,E(:,1)) .* normal(:,E(:,2)), 1 );") for SOME surfaces. The error stems from E containing indices that are out of range which is caused by line 48 ("A = sparse(double(i),double(j),s,n,n);") where A's values eventually entirely make up the E matrix. The problem occurs when the i and j vectors create the same ordered pair twice in which case the sparse function adds the two s vector elements together for that matrix location resulting in a value that is too large to be used as an index on line 75. For example, if i = [1 1] and j = [2 2] and s = [3 4] then A(1,2) will equal 3 + 4 = 7.

The i and j vectors are created here:
i = [face(1,:) face(2,:) face(3,:)];
j = [face(2,:) face(3,:) face(1,:)];

The fact that your code seems to depend on the order of the vertices in the faces matrix worries me because the curvature should be the same regardless of the order, obviously. To be fair, I don't completely understand how your code works so perhaps the way it is written it works out to not matter except that it does certainly matter when it results in an index out of bounds error as previously described.

02 Jun 2008 anup vibhute

very useful

30 May 2007 bahram gh

very useful

22 Feb 2007 Ben abdallah youssef

Very helpful toolbox!!

08 Sep 2006 Will Liu  
29 Mar 2006 Edo urra


26 Mar 2005 Khaled Khairy  
11 Dec 2004 Attila Altay Yavuz

Very useful

10 Sep 2004 lo


13 Jul 2004

Added dual graph support.

26 Oct 2004

Now in zip format.

11 Feb 2005

Added support for various file formats (VRML,PLY,SMF).
Added support for geometry images display (gim generation soon to come).
Added some test files for spectral graph drawing, isomap flattening, spectral graph compression.

18 Jan 2007

Added free boundary parameterization.

27 Apr 2007

GPL license.

02 Oct 2007

Added heat diffusion on meshes, clean definition of laplacians.

06 Nov 2007

Added curvature computation on meshes.

21 Nov 2007

Fixed a few bugs.

01 Feb 2008

Added support for tetrahedral meshes.

15 Feb 2008

Added image approximation using refinement.

18 Aug 2008

Added html help files.

25 Jun 2009
27 Jun 2009

Update of Licence

19 Jul 2009

Modified license.

Contact us