Dtjytyk

Drawing spherical mirrors

An adverb for when you're not exaggerating

What is the meaning of 'breadth' in breadth first search?

Crossing US/Canada Border for less than 24 hours

Random body shuffle every night—can we still function?

AppleTVs create a chatty alternate WiFi network

preposition before coffee

Why does it sometimes sound good to play a grace note as a lead in to a note in a melody?

What order were files/directories output in dir?

What are the discoveries that have been possible with the rejection of positivism?

How does Belgium enforce obligatory attendance in elections?

1-probability to calculate two events in a row

How to compare two different files line by line in unix?

What is an "asse" in Elizabethan English?

What is the difference between a "ranged attack" and a "ranged weapon attack"?

Co-worker has annoying ringtone

Misunderstanding of Sylow theory

How many time has Arya actually used Needle?

Strange behavior of Object.defineProperty() in JavaScript

Amount of permutations on an NxNxN Rubik's Cube

How many morphisms from 1 to 1+1 can there be?

Is there hard evidence that the grant peer review system performs significantly better than random?

How to report t statistic from R

Why are vacuum tubes still used in amateur radios?

How to find nodes that are in any cycle in a UNdirected graph?

0

$begingroup$

Let's say the adjacency matrix of a undirected graph $A$ is given by

$$A = begin{bmatrix}0
& 1& 0& 1 \ 1& 0& 1& 1 \ 0& 1& 0& 1 \ 1& 1& 1& 0end{bmatrix}$$

Then the nodes in any cycle are:

$$1 (1rightarrow2to3)\2 (2to3to4)$$

Is there a efficient way to get the list of nodes in any cycle?

I know summing up $A,A^2,A^3,A^4dots$ and searching up for non-zero diagonal works, but I am working on a high-dimensional matrix and it takes too long.

Thank you.

Solution from this theme does not work with undirected graph.

graph-theory matlab cyclic-groups

share|cite|improve this question

edited Mar 25 at 18:30

Brian

1,499416

asked Mar 25 at 17:22

Андрей СологубовАндрей Сологубов

12

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Try Depth-First Search? I don't think adjacency matrices are great for finding cycles.
  $endgroup$
  – Don Thousand
  Mar 25 at 17:56
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How use this procedure in matlab for my task? Could you give me some example?
  $endgroup$
  – Андрей Сологубов
  Mar 25 at 18:46
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  That is outside the confines of this stackexchange. Try searching for answers elsewhere.
  $endgroup$
  – Don Thousand
  Mar 25 at 18:47
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I do not quite understand how using this algorithm, I can get a list of nodes in a loop.
  $endgroup$
  – Андрей Сологубов
  Mar 25 at 19:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Ok, I understood about how the algorithm from the previous topic works. But I do not quite understand how I get the right path between two adjacent nodes. For example, there is a 1-2-3 circuit, but with the help of the shorttestpath command, I get 1-2, not 1-2-3. It is clear that this is really the shortest distance, but I want to get a contour - how to do it?
  $endgroup$
  – Андрей Сологубов
  Mar 25 at 19:33
  

  
  
  
  

 | 
show 1 more comment

0

$begingroup$

Let's say the adjacency matrix of a undirected graph $A$ is given by

$$A = begin{bmatrix}0
& 1& 0& 1 \ 1& 0& 1& 1 \ 0& 1& 0& 1 \ 1& 1& 1& 0end{bmatrix}$$

Then the nodes in any cycle are:

$$1 (1rightarrow2to3)\2 (2to3to4)$$

Is there a efficient way to get the list of nodes in any cycle?

I know summing up $A,A^2,A^3,A^4dots$ and searching up for non-zero diagonal works, but I am working on a high-dimensional matrix and it takes too long.

Thank you.

Solution from this theme does not work with undirected graph.

graph-theory matlab cyclic-groups

share|cite|improve this question

edited Mar 25 at 18:30

Brian

1,499416

asked Mar 25 at 17:22

Андрей СологубовАндрей Сологубов

12

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Try Depth-First Search? I don't think adjacency matrices are great for finding cycles.
  $endgroup$
  – Don Thousand
  Mar 25 at 17:56
  
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  How use this procedure in matlab for my task? Could you give me some example?
  $endgroup$
  – Андрей Сологубов
  Mar 25 at 18:46
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  That is outside the confines of this stackexchange. Try searching for answers elsewhere.
  $endgroup$
  – Don Thousand
  Mar 25 at 18:47
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I do not quite understand how using this algorithm, I can get a list of nodes in a loop.
  $endgroup$
  – Андрей Сологубов
  Mar 25 at 19:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Ok, I understood about how the algorithm from the previous topic works. But I do not quite understand how I get the right path between two adjacent nodes. For example, there is a 1-2-3 circuit, but with the help of the shorttestpath command, I get 1-2, not 1-2-3. It is clear that this is really the shortest distance, but I want to get a contour - how to do it?
  $endgroup$
  – Андрей Сологубов
  Mar 25 at 19:33
  

  
  
  
  

 | 
show 1 more comment

$begingroup$

Let's say the adjacency matrix of a undirected graph $A$ is given by

$$A = begin{bmatrix}0
& 1& 0& 1 \ 1& 0& 1& 1 \ 0& 1& 0& 1 \ 1& 1& 1& 0end{bmatrix}$$

Then the nodes in any cycle are:

$$1 (1rightarrow2to3)\2 (2to3to4)$$

Is there a efficient way to get the list of nodes in any cycle?

I know summing up $A,A^2,A^3,A^4dots$ and searching up for non-zero diagonal works, but I am working on a high-dimensional matrix and it takes too long.

Thank you.

Solution from this theme does not work with undirected graph.

graph-theory matlab cyclic-groups

share|cite|improve this question

edited Mar 25 at 18:30

Brian

1,499416

asked Mar 25 at 17:22

Андрей СологубовАндрей Сологубов

12

$endgroup$

share|cite|improve this question

edited Mar 25 at 18:30

Brian

1,499416

asked Mar 25 at 17:22

Андрей СологубовАндрей Сологубов

12

share|cite|improve this question

edited Mar 25 at 18:30

Brian

1,499416

asked Mar 25 at 17:22

Андрей СологубовАндрей Сологубов

12

edited Mar 25 at 18:30

Brian

1,499416

edited Mar 25 at 18:30

Brian

1,499416

asked Mar 25 at 17:22

Андрей СологубовАндрей Сологубов

12

asked Mar 25 at 17:22

Андрей СологубовАндрей Сологубов

12