Code covered by the BSD License  

Highlights from
Toolbox Graph

4.5 | 26 ratings Rate this file 330 Downloads (last 30 days) File Size: 2.87 MB File ID: #5355 Version: 1.4
image thumbnail

Toolbox Graph


Gabriel Peyre (view profile)


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, Icp Registration Using Efficient Variants And Multi Resolution Scheme, Gptoolbox, Simulation Of Breast Cancer, and Code To Realize Olga Sorkine Paper.

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 (39)
07 Jul 2015 Shahnawaz

I solved this problem :) One more issue. Can I read .ply file as mesh instead of .off file?

Comment only
23 Mar 2015 Broni

Broni (view profile)

Hi! thanks for the nice toolbox.
I want to create a graph for HD image (1080x1920), but the build_graph... returns error because it goes out of memory when initializing the very large graph matrix.
Do you maybe have any suggestions how to tackle this issue. I want to implement a gaphcuts algorithm for HD images or larger resolutions.

11 Mar 2015 EL OIRRAK

How can iniatilize OPTIONS ???

Comment only
19 Feb 2015 kijo maken

to fix the problem with quiver at plot_mesh, you just need to scroll to line 139 and change the code to quiver3(vertex(sel,1),vertex(sel,2),vertex(sel,3),normal(1,sel)',normal(2,sel)',normal(3,sel)',normal_scaling);

Comment only
16 Feb 2015 Richard Kennaway

The function select3d contained in this toolbox no longer works in 2014b and 2015a (pre-release). It contains a function local_Data2PixelTransform, which tries to obtain the properties 'x_RenderTransform', 'x_RenderOffset', and 'x_RenderScale' of an axes object. These properties no longer exist.

Comment only
14 Jan 2015 EL OIRRAK

how to use compute_curvature

Comment only
19 Dec 2014 Helen

Helen (view profile)

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 );")

Comment only
24 Nov 2014 Alec

Alec (view profile)

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.

Comment only
28 Oct 2014 dhara

dhara (view profile)

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

David (view profile)

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

Xu (view profile)

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.

Comment only
21 Mar 2014 HAYOUNG

Many thanks to great toolbox.

21 Feb 2014 ness

ness (view profile)


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

Ben (view profile)

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

Comment only
10 Jan 2014 Anass

Anass (view profile)


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

David (view profile)

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

Eitan (view profile)

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?

Comment only
20 Nov 2009 Ged Ridgway

Ged Ridgway (view profile)

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);

Comment only
17 Nov 2009 Peter

Peter (view profile)

12 Nov 2009 kamel

kamel (view profile)

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

Ofra (view profile)

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

Comment only
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


Comment only
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 1.1


27 Jun 2009 1.2

Update of Licence

19 Jul 2009 1.4

Modified license.

Contact us