version 1.4.0.0 (2.87 MB) by
Gabriel Peyre

A toolbox to perform computations on graph.

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.

Gabriel Peyre (2021). Toolbox Graph (https://www.mathworks.com/matlabcentral/fileexchange/5355-toolbox-graph), MATLAB Central File Exchange. Retrieved .

Created with
R14

Compatible with any release

- Sciences > Physics > Networks >
- MATLAB > Mathematics > Graph and Network Algorithms > Construction >

**Inspired:**
gptoolbox, Code to realize Olga Sorkine paper, simulation of breast cancer, laplacian_surface_editing_3D, ICP Registration using Efficient Variants and Multi-Resolution Scheme, Optimal Step Nonrigid ICP, Local Depth SIFT and Scale Invariant Spin Image local features for 3D meshes

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!Create scripts with code, output, and formatted text in a single executable document.

Diego HensHello, this is fantastic, thank you. I have a question regarding the mesh parameterization (it's exactly what I need!). Is there a way to recover the stl file from the parameterized disc? If there is a given parameterized disc, how could I go in the other direction and get the three-dimensional body?

jane kooperPerfect,

Thanks

Michael WJayant SharmaMohsin ShahThe "compute_curvature(veretx, face, options)" function give the following error:

Index exceeds matrix dimensions.

Error in compute_curvature (line 74)

dp = sum( normal(:,E(:,1)) .* normal(:,E(:,2)), 1 );

How to fix this error?

pravin kharatmy code is giving me warning like

Warning: Problem in reading vertices.

> In read_off (line 32)

In my (line 4)

Warning: Problem in reading faces.

> In read_off (line 39)

In my (line 4)

and at the output its shows empty vertices and faces please help me to solve my problem

filippHi there, even though compute_curvature is very easy to implement it seems that its output is not completely reliable. I computed curvature for a cube and get different curvature values for parallel edges of the cube - even though they are exactly the same (just translated in space). Other curvature algorithms (that are however showing other problems) produce the same values for these parallel edges. Any idea why this happens?

Thanks!

Berthe Emmanuelle Kamga Monayoumi get this error by vtk function ; 'Warning: Problem in reading vertices.'

Suwoong HeoCool! Can someone recommend me a textbook or paper related to the theory of this toolbox?

Thomas Atta-FosuHere's a workaround to the error in 'compute_curvature' at line 75: "dp = sum( normal(:,E(:,1)) .* normal(:,E(:,2)), 1 );

Copy and paste the following code into 'compute_curvature' right after line 47, i.e after the line "s = [1:m 1:m 1:m];" and right before "A = sparse(i,j,s,n,n)"

[u,ui,~] = unique([i' j'],'rows','stable');

s = s(:,ui);

i = u(:,1);

j = u(:,2);

isfzadeSébastien HerbertHi, thanks for your submission.

I think there is a small bug in the read_ply.m function. When I run it, I get this error

Reference to non-existent field 'vertex_indices'.

Error in read_ply (line 16)

vi = d.face.vertex_indices;

It appears several field names are possible line 460 but not tested afterward

PropertyName = {'vertex_indices','vertex_indexes','vertex_index','indices','indexes'};

In my case, the error could easily be solved by changing the line 26 to

if isfield(d.face,'vertex_indices')

vi = d.face.vertex_indices;

elseif isfield(d.face,'vertex_index')

vi = d.face.vertex_index;

end

Sébastien HerbertJinnyFor read_vtk function, what should be for 'verbose' input? If I don't put any value for I gets 'Warning: Problem in reading vertices.'

chao lei@az why i modify the code using your method,but the compute_normal made some wrong?

Maria CharalampidoumarcSeems good !

Jingwei Zhuanglilian yangThanks for this library.

But I met question when running the following code:

options.method = 'flattening';

xy2 = compute_parameterization(vertex,faces,options);

options.method = 'isomap';

xy3 = compute_parameterization(vertex,faces,options);

% display

clf;

subplot(1,2,1);

plot_graph(A,xy2,'k.-'); axis tight;

title('Laplacian eigenmaps');

subplot(1,2,2);

plot_graph(A,xy3,'k.-'); axis tight;

title('Isomap');

The error is:

The subscript index must be a positive integer type or a logical type.

Error perform_dijkstra_propagation_slow>dijkstra_init (line 110)

data.A(start_verts) = 0;

Error perform_dijkstra_propagation_slow (line 42)

data = dijkstra_init(W, start_verts);

Error perform_dijkstra (line 66)

[D,S] = perform_dijkstra_propagation_slow(W',start_points-1,end_points-1,nb_iter_max, H); % use transposate

Error compute_distance_graph (line 34)

[d,S] = perform_dijkstra(W, point_list(i));

Error isomap (line 101)

D = compute_distance_graph(Ws, points_list);

Error compute_parameterization (line 78)

vertex1 = isomap(D,ndim, options);

lilian yangZhenyi WangAlexander NaitzatfxyazI 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))));

% links edge->faces

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

hariharan mahalingamDaniel FrischThe 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.

Teng LongHi 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?

Teng LongDuc FehrGhazalSuper 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?

iMorrunPretty 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?

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

http://imgur.com/a/OA4xY

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

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

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

BroniHi! 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.

EL OIRRAKHow can iniatilize OPTIONS ???

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

Richard KennawayThe 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.

EL OIRRAKhow to use compute_curvature

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

Alec JacobsonThanks 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.

dharagreat 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

DavidIt 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?

XuGood tools.

HAYOUNGMany 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.

HAYOUNGMany thanks to great toolbox.

nessHi

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.

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

AnassHi,

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?

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

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

EitanVery 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.

wikimenWoko wikkJulian Xueis there a method here to just plot an adjacency matrix?

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

PeterkamelVery 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

Raymond ChengThanks for your sharing.

YUANCHUN WANGVery 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!

europe leetest_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.

OfraVery useful.

Is there a Matlab 2008b version ?

Axel zhengCool!!!

David SJust 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

David SVery 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.

anup vibhutevery useful

bahram ghvery useful

Ben abdallah youssefVery helpful toolbox!!

Will LiuEdo urragood

Khaled KhairyAttila Altay YavuzVery useful

lolo@loli.li loPerfect