Code covered by the BSD License

### Highlights from Toolbox Graph

4.52941
4.5 | 34 ratings Rate this file 259 Downloads (last 30 days) File Size: 2.87 MB File ID: #5355 Version: 1.4

# Toolbox Graph

### Gabriel Peyre (view profile)

26 Jun 2004 (Updated )

A toolbox to perform computations on graph.

File Information
Description

Graph theory toolbox

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.

Acknowledgements
MATLAB release MATLAB 7 (R14)
25 Jul 2016 fxy

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);
[a,b]=hist(L,unique(L));
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))));

E = [s1 s2];
i=K2(:,1);
j=K2(:,2);
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

### hariharan mahalingam (view profile)

28 May 2016 Daniel Frisch

### Daniel Frisch (view profile)

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

### Teng Long (view profile)

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

### Teng Long (view profile)

20 May 2016 Duc Fehr

### Duc Fehr (view profile)

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

### iMorrun (view profile)

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:
http://imgur.com/a/OA4xY

Comment only
06 Oct 2015 az

### az (view profile)

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

07 Jul 2015 Shahnawaz

### Shahnawaz (view profile)

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

### EL OIRRAK (view profile)

How can iniatilize OPTIONS ???

Comment only
19 Feb 2015 kijo maken

### kijo maken (view profile)

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

### Richard Kennaway (view profile)

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

### EL OIRRAK (view profile)

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

### HAYOUNG (view profile)

Many thanks to this great toolbox.
FYI, he also made comprehensive manual in his website (https://www.ceremade.dauphine.fr/~pey re/matlab/graph/content.html), which is also nice.

Comment only
21 Mar 2014 HAYOUNG

### HAYOUNG (view profile)

Many thanks to great toolbox.

21 Feb 2014 ness

### ness (view profile)

Hi

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)

Hi,

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.

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

### Chris Rorden (view profile)

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

### wikimenWoko wikk (view profile)

28 Jul 2010 Julian Xue

### Julian Xue (view profile)

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
thanks

18 Oct 2009 Raymond Cheng

### Raymond Cheng (view profile)

26 Aug 2009 YUANCHUN WANG

### YUANCHUN WANG (view profile)

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?

09 Jun 2009 europe lee

### europe lee (view profile)

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

### Axel zheng (view profile)

Cool!!!

03 Mar 2009 David S

### David S (view profile)

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

### David S (view profile)

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

08 Sep 2006 Will Liu
29 Mar 2006 Edo urra

good

Comment only
26 Mar 2005 Khaled Khairy
11 Dec 2004 Attila Altay Yavuz

Very useful

10 Sep 2004 lolo@loli.li lo

Perfect

13 Jul 2004

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

27 Apr 2007

02 Oct 2007

Added heat diffusion on meshes, clean definition of laplacians.

06 Nov 2007

21 Nov 2007

Fixed a few bugs.

01 Feb 2008

15 Feb 2008

18 Aug 2008

25 Jun 2009 1.1

n/a

27 Jun 2009 1.2

Update of Licence

19 Jul 2009 1.4