View License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
Toolbox Graph

4.5 | 35 ratings Rate this file 317 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, Laplacian Surface Editing 3 D, Gptoolbox, Simulation Of Breast Cancer, Code To Realize Olga Sorkine Paper, Icp Registration Using Efficient Variants And Multi Resolution Scheme, and Optimal Step Nonrigid Icp.

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 (52)
13 Aug 2016 Alexander Naitzat

25 Jul 2016 fxy

fxy (view profile)

26 Jun 2016 az

az (view profile)

I solved few bugs (out of bounds and divide by zero errors) that were in "compute_curvature".

Copy the following lines instead of lines 42-71:

% associate each edge to a pair of faces
i = [face(1,:) face(2,:) face(3,:)];
j = [face(2,:) face(3,:) face(1,:)];

L = sub2ind([n, n], i, j);
Q = ismember(L,b(a>1));
[i1, j1] = ind2sub([n, n], L(Q));
W = [i' j'];
R = ismember(W, [i1' j1'], 'rows');
J = find(R);
[Q, K] = sortrows(W(R,:));
J = J(K);
[~, ia, ~] = unique(Q, 'rows');
R = true(size(J));
R(ia) = false;
J = J(R);

s = [1:m 1:m 1:m];
s(J) = 0;
A = sparse(i,j,s,n,n); % if (i,j) are an edge at some face then A(i,j) is
% this face index.

[i,j,~] = find(A); % direct link

X = [i j];
Y = [j i];
[~, I1, ~]=intersect(X, Y, 'rows');
I = X(I1, :);
K1 = I(I(:,1) < I(:,2),:); % only directed edges
K2 = [K1(:,2) K1(:,1)];
[~, ~, s1]= find(A(sub2ind(size(A),K1(:,1), K1(:,2))));
[~, ~, s2]= find(A(sub2ind(size(A),K2(:,1), K2(:,2))));

% links edge->faces
E = [s1 s2];
ne = length(i); % number of directed edges

% normalized edge
e = vertex(:,j) - vertex(:,i);
d = sqrt(sum(e.^2,1));
d(d<eps) = 1;
e = e ./ repmat(d,3,1);
% avoid too large numerics
d = d./mean(d);

Comment only
16 Jun 2016 hariharan mahalingam

28 May 2016 Daniel Frisch

The test files don't run due to changed function names or syntax, as well as missing functions or input files. This is sad because these test files could give the users a quick overview about the capability of the toolbox.

Comment only
26 May 2016 Teng Long

Hi I tried to plot a mesh with its normals by 'plot_mesh(vertex,faces,options);' It returns an error saying"plot_mesh (line 145) Z and U must be the same size". I realized that the normals vector returned from compute_normal functions is of size 3*n. Currently I modified line 145 in plot_mesh function to "quiver3(vertex(sel,1),vertex(sel,2),vertex(sel,3),normal(1,sel)',normal(2,sel)',normal(3,sel)',normal_scaling);" and it worked. I'm just wondering why you have to return a list of normals from compute_normal function instead of a vector of normal?

Comment only
26 May 2016 Teng Long

20 May 2016 Duc Fehr

18 May 2016 Ghazal

Ghazal (view profile)

Super great Toolbox!

I need to have colored meshes on Matlab. I tried to read an object file using read_obj.m but don't succeed to plot it.
Do you have any idea how I can have a 3D mesh with a color value assigned to each face on Matlab?

17 May 2016 iMorrun

Pretty nice code.but I still met question when running the code.when I wanted to read a .ply file by using read_ply function,the system always gave error like this:error in read_ply at 16 vi = d.face.vertex.indices;...I am in pretty hurry,can any one help me solve this problem?By the way,does anyone know the website which can download .off file?

07 Apr 2016 Ego

Ego (view profile)

10 Oct 2015 Fritz

Fritz (view profile)

@az: test_curvature.m works fine for me with the 'mushroom', see results:

Probably it's related to your mesh? Can you upload an example?

Comment only
06 Oct 2015 az

az (view profile)

Has anyone solved the bug in "compute_curvature" - at line 75?

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 Jacobson

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