2
$\begingroup$

I have a matrix that implements a periodic boundary conditions for a graph. Now, I am interested in the cycles in this graph. However, the cycles are not what I expect. To illustrate my point. When I plot the AdjacencyMatrix, or more precisely a hand version of it with full periodic boundary conditions. Then it looks like, enter image description here Primarily, there is an octagon (vertex numbered from 1 to 8) with outgoing links emanating from these vertices (numbered from 9 to 16). The periodic boundary shows how each of these protruding links (numbered from 9 to 16) are connected to other protruding links to take into account the periodic boundary conditions. That's why you will find repetition of numbers to show these periodicities.
Now the problem is, I would like to calculate the number of cycles in this (periodic graph). It maybe not apparent, there are total six cycles. Namely, the first one (1,2,3,4,5,6,7,8), second one (1,9,14,6,5,13,10,2), third one (2,10,15,7,..,3), fourth one (3,11,16,..,4), fifth one (4,12,9,...,,13,5), last one (9,12,15,10,13,16,11,14) (these are the compressed octagons seen coming out at the eight points above but all eight are essentially the same octagon, but cyclic orientations). However, if I use the FindCycle it gives all the wrong cycles that even doesn't contain the face. Is there a way to resolve this problem.
My MWE

octaperiodic={{0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0}, {1, 0, 1, 0, 0, 0, 
  0, 0, 0, 1, 0, 0, 0, 0, 0, 0}, {0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 
  0, 0, 0, 0}, {0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0}, {0, 
  0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 1, 0, 1, 
  0, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 
  0, 1, 0}, {1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1}, {1, 0, 
  0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 
  0, 0, 0, 0, 1, 0, 1, 0}, {0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 
  0, 1}, {0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 
  0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 1, 0, 0, 1, 
  0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 
  0}, {0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0}};

FindCycle[AdjacencyGraph[octaperiodic], Infinity, 8]
(* Solution is below *)
    {{1 \[UndirectedEdge] 8, 8 \[UndirectedEdge] 16, 
  16 \[UndirectedEdge] 13, 13 \[UndirectedEdge] 10, 
  10 \[UndirectedEdge] 15, 15 \[UndirectedEdge] 12, 
  12 \[UndirectedEdge] 9, 
  9 \[UndirectedEdge] 1}, {1 \[UndirectedEdge] 8, 
  8 \[UndirectedEdge] 16, 16 \[UndirectedEdge] 13, 
  13 \[UndirectedEdge] 10, 10 \[UndirectedEdge] 2, 
  2 \[UndirectedEdge] 3, 3 \[UndirectedEdge] 11, 
  11 \[UndirectedEdge] 14, 14 \[UndirectedEdge] 9, 
  9 \[UndirectedEdge] 1}, {1 \[UndirectedEdge] 8, 
  8 \[UndirectedEdge] 16, 16 \[UndirectedEdge] 13, 
  13 \[UndirectedEdge] 10, 10 \[UndirectedEdge] 15, 
  15 \[UndirectedEdge] 7, 7 \[UndirectedEdge] 6, 
  6 \[UndirectedEdge] 14, 14 \[UndirectedEdge] 9, 
  9 \[UndirectedEdge] 1}, {1 \[UndirectedEdge] 8, 
  8 \[UndirectedEdge] 16, 16 \[UndirectedEdge] 13, 
  13 \[UndirectedEdge] 10, 10 \[UndirectedEdge] 15, 
  15 \[UndirectedEdge] 7, 7 \[UndirectedEdge] 6, 
  6 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 4, 
  4 \[UndirectedEdge] 12, 12 \[UndirectedEdge] 9, 
  9 \[UndirectedEdge] 1}, {1 \[UndirectedEdge] 8, 
  8 \[UndirectedEdge] 16, 16 \[UndirectedEdge] 13, 
  13 \[UndirectedEdge] 10, 10 \[UndirectedEdge] 15, 
  15 \[UndirectedEdge] 12, 12 \[UndirectedEdge] 4, 
  4 \[UndirectedEdge] 3, 3 \[UndirectedEdge] 11, 
  11 \[UndirectedEdge] 14, 14 \[UndirectedEdge] 9, 
  9 \[UndirectedEdge] 1}, {1 \[UndirectedEdge] 8, 
  8 \[UndirectedEdge] 16, 16 \[UndirectedEdge] 13, 
  13 \[UndirectedEdge] 10, 10 \[UndirectedEdge] 15, 
  15 \[UndirectedEdge] 12, 12 \[UndirectedEdge] 4, 
  4 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 6, 
  6 \[UndirectedEdge] 14, 14 \[UndirectedEdge] 9, 
  9 \[UndirectedEdge] 1}, {1 \[UndirectedEdge] 8, 
  8 \[UndirectedEdge] 16, 16 \[UndirectedEdge] 13, 
  13 \[UndirectedEdge] 10, 10 \[UndirectedEdge] 15, 
  15 \[UndirectedEdge] 7, 7 \[UndirectedEdge] 6, 
  6 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 4, 4 \[UndirectedEdge] 3,
   3 \[UndirectedEdge] 11, 11 \[UndirectedEdge] 14, 
  14 \[UndirectedEdge] 9, 
  9 \[UndirectedEdge] 1}, {1 \[UndirectedEdge] 8, 
  8 \[UndirectedEdge] 16, 16 \[UndirectedEdge] 13, 
  13 \[UndirectedEdge] 10, 10 \[UndirectedEdge] 15, 
  15 \[UndirectedEdge] 7, 7 \[UndirectedEdge] 6, 
  6 \[UndirectedEdge] 14, 14 \[UndirectedEdge] 11, 
  11 \[UndirectedEdge] 3, 3 \[UndirectedEdge] 4, 
  4 \[UndirectedEdge] 12, 12 \[UndirectedEdge] 9, 
  9 \[UndirectedEdge] 1}}

Most of them doesn't contain the faces and are more than six cycles of eight vertices. Here, faces refer to the faces in a planar graph. One can explicitly see them in the second figure shown below, numbered from 1 to 6. Other octagons mirror opposite are the same cycles. If this depends on the particular embedding, then I am interested in embedding the above graph on a genus 2 Torus.
How to resolve this problem? It even counts a cycle with six vertices, it is absurd, there are only octagons. Any help is of utmost importance!

The six cycles of eight vertices

$\endgroup$
12
  • 2
    $\begingroup$ "there are total six cycles" This is not true, as you can see from the result of FindCycles. "However, if I use the FindCycle it gives all the wrong cycles that even doesn't contain the face. Is there a way to resolve this problem." Can you explain in a mathematically precise way what you want to do? It sounds like it is not finding all cycles. Perhaps you want to find the faces of a planar graph, but note that those might depend on the embedding you choose (they are not in general uniquely defined). It is also unclear what you mean by "periodic boundary conditions". $\endgroup$ – Szabolcs May 16 at 17:53
  • $\begingroup$ I voted to close as "needs clarification". Please add the requested information, so people wouldn't spend time writing answers that you will not find useful anyway, as they are merely guessing/assuming what you are looking for. Note that the purpose of closing questions is not to discourage asking, but to keep this QA site on track and useful to everyone, including you. The best (preferred) outcome is if you clarify what you need, the question gets reopened, and you receive a useful answer. $\endgroup$ – Szabolcs May 17 at 9:16
  • $\begingroup$ @Szabolcs Apologies for getting back late. I agree there are more than six cycles with eight vertices. But, as I said they do not contain the face (of the graph). I also agree, the face is not well defined in my question. I am also find it hard to explain. But you're right, it is not finding all cycles. Yeah, the faces of the planar graph is far more close to what I want. If there are not uniquely defined in general but in my case, I can think of embedding on a torus of genus 2. Will it work now? $\endgroup$ – Shamina May 17 at 9:55
  • $\begingroup$ @Szabolcs Regarding the periodic boundary conditions, it is similar to what we do in case of lattices in solid-state. For instance, in square or hexagon, the opposite sides are glued together to give rise to a torus of genus 1. Here it is the same shown in my hand drawn picture. I hope it is clear. $\endgroup$ – Shamina May 17 at 9:56
  • 1
    $\begingroup$ @Szabolcs Please don't close the question, I am making it clear to the best of my abilities. $\endgroup$ – Shamina May 17 at 10:00
2
$\begingroup$

Do I misunderstand your question? You write: "there are total six cycles". Why do you think that there are only 6 cycles of length 8? There are many more as you can see e.g. from (I restricted the number to 9):

g = AdjacencyGraph[octaperiodic, 
  GraphLayout -> "SpringElectricalEmbedding", VertexLabels -> "Name"];
HighlightGraph[g, # ] & /@ FindCycle[g, Infinity, 9]

enter image description here

And you write: "It even counts a cycle with six vertices, it is absurd, there are only octagons." There are even a lot of cycles with length 6 as you can see (I again restricted the number):

HighlightGraph[g, # ] & /@ FindCycle[g, 6, 6]

enter image description here

$\endgroup$
3
  • $\begingroup$ Many thanks for your answer!! Apologies for getting back late. I realize, I was not clear in my question. That resulted in some confusion. I agree with you that there are more than six cycles with eight vertices. But, as I said they do not contain the face (of the planar graph). I also agree, the face is not well defined in my question. I am also finding it hard to explain. To be more clear, the faces of the planar graph is far more close to what I want. I can think of embedding the above planar graph on a torus of genus 2. Will it work now? To find the specific cycles? Billion thanks! $\endgroup$ – Shamina May 17 at 9:59
  • $\begingroup$ Hi Shamina, I am still not sure what you want. Dow you want all cycles of length 8 that contain at least one edges of the octagon with vertices 1...8? There are 29 of these. Or do you want such cycles with a length of at most 8, There are 53 of them. Or do you want cycles of any length containing an octagon edge, there are 399? $\endgroup$ – Daniel Huber May 17 at 10:42
  • $\begingroup$ I don't want all cycles of length 8. But cycles that contain exactly two vertices of the inside polygon vertices 1...8, let us say consecutively, shown in italics e.g., 2,1,9,14,6,5,13,10. And the one that only contains the outer polygon vertices 9...16. Lastly, that only contains the inner polygon vertices 1...8. Sorry for being unclear. I hope it may be little clear now. If not please don't hesitate, I will try my best to clear it up. $\endgroup$ – Shamina May 17 at 10:55
1
$\begingroup$

I now assume that we are looking for cycles of length 8 that contain exactly 2 vertices from the octagon with vertices 1...8. This can be done by first calculating all cycles of length 8 and then select the ones we want:

cyc = FindCycle[AdjacencyGraph[octaperiodic], {8}, 100];
res = Select[cyc, 
  Length[Intersection[Range[8], VertexList[#]]] == 2 &]

enter image description here

We may plot these graphs:

g = AdjacencyGraph[octaperiodic, 
   GraphLayout -> "SpringElectricalEmbedding", VertexLabels -> "Name"];
HighlightGraph[g, #] & /@ res

enter image description here

$\endgroup$
1
  • $\begingroup$ This goes closet to my answer now. I am extremely thankful to you for you invaluable time and effort in answering this very unclear question! However, I have ultimately cleared my question (I hope so :). I edited my question, please have a look. And you will find the six cycles numbered inside the circles in the new figure that I referred to in the question, and that are of great interest to me. They are then repeated, i.e., the opposite exterior octagons are the same cycle. Can we get only these ones? Apologies for all the confusions :( $\endgroup$ – Shamina May 17 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.