File Exchange

image thumbnail

Toolbox Graph

version 1.4 (2.87 MB) by

A toolbox to perform computations on graph.

205 Downloads

Updated

View License

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.

Comments and Ratings (64)

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

isfzade

isfzade (view profile)

Hi, 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

Jinny

Jinny (view profile)

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

marc

marc (view profile)

Seems good !

lilian yang

Thanks 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 yang

Zhenyi Wang

fxy

fxy (view profile)

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

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

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.

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?

Teng Long

Duc Fehr

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?

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?

Ego

Ego (view profile)

Fritz

Fritz (view profile)

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

az

az (view profile)

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

Shahnawaz

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

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.

EL OIRRAK

How can iniatilize OPTIONS ???

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

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.

EL OIRRAK

how to use compute_curvature

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

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.

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

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?

Xu

Xu (view profile)

Good tools.

HAYOUNG

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.

HAYOUNG

Many thanks to great toolbox.

ness

ness (view profile)

Hi

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.

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!

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.

Can you help please?

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?

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

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.

Julian Xue

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

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

Peter

Peter (view profile)

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

Raymond Cheng

Thanks for your sharing.

YUANCHUN WANG

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!

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.

Ofra

Ofra (view profile)

Very useful.
Is there a Matlab 2008b version ?

Axel zheng

Cool!!!

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

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.

anup vibhute

very useful

bahram gh

very useful

Ben abdallah youssef

Very helpful toolbox!!

Will Liu

Edo urra

good

Khaled Khairy

Attila Altay Yavuz

Very useful

lolo@loli.li lo

Perfect

Updates

1.4

Modified license.

1.2

Update of Licence

1.1

n/a

Added html help files.

Added image approximation using refinement.

Added support for tetrahedral meshes.

Fixed a few bugs.

Added curvature computation on meshes.

Added heat diffusion on meshes, clean definition of laplacians.

GPL license.

Added free boundary parameterization.

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.

Now in zip format.

Added dual graph support.

MATLAB Release
MATLAB 7 (R14)

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

» Watch video

toolbox_graph/

toolbox_graph/tests/

toolbox_graph/toolbox/