Problem 45261. List every vertices neighbor indices

Created by Nicolas Douillet

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Input T is a</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://fr.mathworks.com/help/matlab/ref/triangulation.html\"><w:r><w:t>triangulation</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The purpose of this function is to query at once the cell array N of all vertex neighbor indices... of every vertices, nothing less (!)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Output N must be a cell array since of course each vertex may have a different number of neighbors.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For example, for an input filled octahedron whom triangulation is</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[T = [1, 2, 3;...\n 1, 3, 4;...\n 1, 4, 5;...\n 1, 2, 5;...\n 2, 3, 6;...\n 3, 4, 6;...\n 4, 5, 6;...\n 2, 5, 6;...\n 2, 3, 4;...\n 2, 4, 5;...\n 1, 2, 4;...\n 2, 4, 6],]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>then the output N is a 6x1 cell array of integers row vectors, such that :</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[N(1,1) = {[2, 3, 4, 5]};\nN(2,1) = {[1, 3, 4, 5, 6]};\nN(3,1) = {[1, 2, 4, 6]};\nN(4,1) = {[1, 2, 3, 5, 6]};\nN(5,1) = {[1, 2, 4, 6]};\nN(6,1) = {[2, 3, 4, 5]};]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Indeed vertex #2 is part of triangles [1, 2, 3], [1, 2, 5], [2, 3, 6], [2, 5, 6], [2, 3, 4], [2, 4, 5], [1, 2, 4], and [2, 4, 6], it then admit all the other vertices as neighbors ([1, 3, 4, 5, 6]).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Hypothesis / conditions :</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>a</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>vertex is the neighbor of another</w:t></w:r><w:r><w:t> if they are linked with an edge</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>in at least one same triangle</w:t></w:r><w:r><w:t>. A vertex is not neighbor of itself.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output N row order is crucial</w:t></w:r><w:r><w:t> since</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>row number actually corresponds to the vertex id / index.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Output N cells content order doesn't matter, but it doesn't admit any duplicated index / value.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Tip :</w:t></w:r><w:r><w:t> solving</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://fr.mathworks.com/matlabcentral/cody/players/8668631-nicolas-douillet/created\"><w:r><w:t>my previous problems</w:t></w:r></w:hyperlink><w:r><w:t>, and especially</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://fr.mathworks.com/matlabcentral/cody/problems/45256-query-a-vertex-neighbors\"><w:r><w:t>query_vertex_neighbors</w:t></w:r></w:hyperlink><w:r><w:t> will help you to fully understand and solve this one.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>NB : the question of unreferenced vertices is not tacled here. We just supposed there are not.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Good work Matlab-bro ! :)</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Input T is a <a href = "https://fr.mathworks.com/help/matlab/ref/triangulation.html">triangulation</a>.The purpose of this function is to query at once the cell array N of all vertex neighbor indices... of every vertices, nothing less (!)Output N must be a cell array since of course each vertex may have a different number of neighbors.For example, for an input filled octahedron whom triangulation is<pre class="language-matlab">T = [1, 2, 3;...
 1, 3, 4;...
 1, 4, 5;...
 1, 2, 5;...
 2, 3, 6;...
 3, 4, 6;...
 4, 5, 6;...
 2, 5, 6;...
 2, 3, 4;...
 2, 4, 5;...
 1, 2, 4;...
 2, 4, 6],
</pre>then the output N is a 6x1 cell array of integers row vectors, such that :<pre class="language-matlab">N(1,1) = {[2, 3, 4, 5]};
N(2,1) = {[1, 3, 4, 5, 6]};
N(3,1) = {[1, 2, 4, 6]};
N(4,1) = {[1, 2, 3, 5, 6]};
N(5,1) = {[1, 2, 4, 6]};
N(6,1) = {[2, 3, 4, 5]};
</pre>Indeed vertex #2 is part of triangles [1, 2, 3], [1, 2, 5], [2, 3, 6], [2, 5, 6], [2, 3, 4], [2, 4, 5], [1, 2, 4], and [2, 4, 6], it then admit all the other vertices as neighbors ([1, 3, 4, 5, 6]).Hypothesis / conditions :<ul><li>a vertex is the neighbor of another if they are linked with an edge in at least one same triangle. A vertex is not neighbor of itself.</li></ul><ul><li>Output N row order is crucial since row number actually corresponds to the vertex id / index.</li></ul><ul><li>Output N cells content order doesn't matter, but it doesn't admit any duplicated index / value.</li></ul>Tip : solving <a href = "https://fr.mathworks.com/matlabcentral/cody/players/8668631-nicolas-douillet/created">my previous problems</a>, and especially <a href = "https://fr.mathworks.com/matlabcentral/cody/problems/45256-query-a-vertex-neighbors">query_vertex_neighbors</a> will help you to fully understand and solve this one.NB : the question of unreferenced vertices is not tacled here. We just supposed there are not.Good work Matlab-bro ! :)

Input T is a <https://fr.mathworks.com/help/matlab/ref/triangulation.html triangulation>.

The purpose of this function is to query at once the cell array N of all vertex neighbor indices... of every vertices, nothing less (!)

Output N must be a cell array since of course each vertex may have a different number of neighbors.

For example, for an input filled octahedron whom triangulation is

T = [1, 2, 3;...
       1, 3, 4;...
       1, 4, 5;...
       1, 2, 5;...
       2, 3, 6;...
       3, 4, 6;...
       4, 5, 6;...
       2, 5, 6;...
       2, 3, 4;...
       2, 4, 5;...
       1, 2, 4;...
       2, 4, 6],

then the output N is a 6x1 cell array of integers row vectors, such that :

N(1,1) = {[2, 3, 4, 5]};
  N(2,1) = {[1, 3, 4, 5, 6]};
  N(3,1) = {[1, 2, 4, 6]};
  N(4,1) = {[1, 2, 3, 5, 6]};
  N(5,1) = {[1, 2, 4, 6]};
  N(6,1) = {[2, 3, 4, 5]};

Indeed vertex #2 is part of triangles [1, 2, 3], [1, 2, 5], [2, 3, 6], [2, 5, 6], [2, 3, 4], [2, 4, 5], [1, 2, 4], and [2, 4, 6], it then admit all the other vertices as neighbors ([1, 3, 4, 5, 6]).

*Hypothesis / conditions :*

* a *vertex is the neighbor of another* if they are linked with an edge *in at least one same triangle*. A vertex is not neighbor of itself.

* *Output N row order is crucial* since *row number actually corresponds to the vertex id / index.*

* Output N cells content order doesn't matter, but it doesn't admit any duplicated index / value.

*Tip :* solving <https://fr.mathworks.com/matlabcentral/cody/players/8668631-nicolas-douillet/created my previous problems>, and especially <https://fr.mathworks.com/matlabcentral/cody/problems/45256-query-a-vertex-neighbors query_vertex_neighbors> will help you to fully understand and solve this one.

NB : the question of unreferenced vertices is not tacled here. We just supposed there are not.

Good work Matlab-bro ! :)

Solve

Solution Stats

19 Solutions
9 Solvers

Last Solution submitted on Dec 18, 2022

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Nicolas Douillet on 10 Jan 2020

Pedagogic solution is available in position 2 (commented, same as solution 1 but more explicit thus suboptimal).

Problem Recent Solvers9

Problem Tags

Community Treasure Hunt

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

Start Hunting!