• 追加された行はこのように表示されます。
  • 削除された行はこのように表示されます。
{{category analysis}}
{{category software}}
!!!Ring Statistics Algorithm
{{ref countrings3.py}}
2009-2-3 New program written in python.
!!Counting policy
*Count only irreducible rings (rings not having shortcut bridges).
*Count rings purely topologically. Do not use geometrical information.
*Edge direction is not considered. (Undirected graph)
!!Algorithm
+Choose 3 successive nodes along the network.
+Find the smallest rings passing the three nodes.
+The ring must not have shotcuts, i.e. path connecting two vertices on the ring which is shorter than the path along the ring. (Using Dijkstra's algorithm.)
+Put the ring in the list.
+Repeat 1 .. 4 until all sets of 3 successive nodes are tested.
+Eliminate the permutations of a ring in the list.
+(Optional) Remove "crossing rings".
!!Usage
Input data must be in @NGPH format. Output data will be in @RNGS format.
 % ./countrings3.py 8 < test.ngph > test.rngs
 % ./countrings3.py 8 < test.ngph | ./crossingrings.pl > test2.rngs

!!Sample
The following is the expression of a cubic graph, which should have six 4-cycles.
 @NGPH
 8
 0 1
 1 2
 2 3
 3 0
 4 5
 5 6
 6 7
 7 4
 0 4
 1 5
 2 6
 3 7
 -1 -1
You can pick up many samples at the Vitrite database:
http://vitrite.chem.okayama-u.ac.jp

!!Known Problems
!Sample 1
{{ref_image sample1.png}}
Number of rings in this kind of graph consisting of N bows is counted as N (N-1) / 2. It happens because of the lack of 3-dimentional geometrical information.
!Sample 2
{{ref_image sample2.png}}
It is a smaller version of sample 1 consisting of 4 bows. As you see, surface rings of this structure seems to be 4, while the algorithm counts as 6, because it also counts the “crossing rings” (diagonal red and blue rings). These sample topologies rarely appear in the network of water at low temperature because the z-index at the top and bottom nodes is too large. 

While, there is another sample containing crossing rings but still undistorted.
!Sample 3
{{ref_image sample3.png}}
!!Walkarounds
The small Perl program “crossingrings.pl” looks up all the crossing rings in the ring list (in @RNGS format) and remove one of them randomly until the crossing is avoided. With the use of 3-dimentional geometrical information, there might be better walkarounds.
!!ChangeLogs
:2009-2-3:Old fortran and C programs are replaced by python one. With python, the program size becomes less than 5k bytes. It is slower than the previous ones, but much easier to understand. One can easily translate it into C++.
!!Comments and Suggestions
Any comments and questions are welcome at mailto:vitroid@gmail.com
//{{comment}}
{{timestamp 1218010419}}
All the contents are moved to the [GitHub|http://github.com/vitroid/CountRings].

メニュー

岡山大学

関連ページ

<< 2021-1 >>
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31

検索

キーワード

class

gallery

research

water

analysis

fractal noise

risk

lifehack

雑記

survey

software

links

あしあと



最新

2019/8/29

2019/5/28

2019/5/13

2018/12/9

2018/10/11

Add