Mixed-Language Programming with XcalableMP
155
R n,d = n − 1 −
K n,d −1
i=1
d(d − 1)
i−1
Figures 6 and 7 show examples of graphs with n = 10 and d = 3 and their
distance matrices. The distance matrix indicates the shortest hop count between
vertices. The diameter is the maximum value of the elements in the distance matrix.
ASPL is the value obtained by dividing the total value of all elements by the number
of elements (n 2 − n)/2. While the graph in Fig. 6 has random edges, the graph in
Fig. 7 has edges optimized by our algorithm, which is described in Sect. 4.2. The
diameter and ASPL of Fig. 7 are theoretical lower bounds.
In an effort to expand the order/degree problem into open science, the National
Institute of Informatics has held a “Graph Golf” competition every year since 2015
to search for the smallest diameter and ASPL. A combination of several vertices and
degrees is provided in each of those events. The competition has two categories: one
is the General Graph Category, where vertices are placed freely, and the other is the
Grid Graph Category, where vertices are placed on a two-dimensional grid. This
section deals with the General Graph Category. Table 3 shows the combination of
vertices and degrees used in 2017.
A python program “create-random.py” for the order/degree problem is available
on the official Graph Golf website. The program outputs follow from the number of
vertices and degrees. These calculations use the Python networkx package (https://
networkx.github.io).
• Initial graph with random edges (the graph of Fig. 6 is created by this function)
• Calculation of diameter and ASPL
• Graph figure in Portable Network Graphics (PNG) format (the graphs shown
Figs. 6 and 7 are created by this function)
4.2 Implementation
The “create-random.py” does not search out the smallest diameter and ASPL.
Moreover, to obtain diameter and ASPL of a graph, it is necessary to calculate all
of the shortest paths among its vertices. Although the “create-random.py” calculates
the shortest paths using the shortest_path_length method of the networkx package,
this method requires a significant amount of time.
To search for the smallest diameter and ASPL, we developed a GraphGolf code
in both Python and XMP/C based on “create-random.py.” A Simulated Annealing
(SA) [21, 22] algorithm is used for optimization. The shortest paths calculation
is parallelized by XMP directives. Figure 8 shows a flow chart for the algorithm.
While Python is used to create initial graph and output the figure, XMP/C is used to
implement other parts.
155
R n,d = n − 1 −
K n,d −1
i=1
d(d − 1)
i−1
Figures 6 and 7 show examples of graphs with n = 10 and d = 3 and their
distance matrices. The distance matrix indicates the shortest hop count between
vertices. The diameter is the maximum value of the elements in the distance matrix.
ASPL is the value obtained by dividing the total value of all elements by the number
of elements (n 2 − n)/2. While the graph in Fig. 6 has random edges, the graph in
Fig. 7 has edges optimized by our algorithm, which is described in Sect. 4.2. The
diameter and ASPL of Fig. 7 are theoretical lower bounds.
In an effort to expand the order/degree problem into open science, the National
Institute of Informatics has held a “Graph Golf” competition every year since 2015
to search for the smallest diameter and ASPL. A combination of several vertices and
degrees is provided in each of those events. The competition has two categories: one
is the General Graph Category, where vertices are placed freely, and the other is the
Grid Graph Category, where vertices are placed on a two-dimensional grid. This
section deals with the General Graph Category. Table 3 shows the combination of
vertices and degrees used in 2017.
A python program “create-random.py” for the order/degree problem is available
on the official Graph Golf website. The program outputs follow from the number of
vertices and degrees. These calculations use the Python networkx package (https://
networkx.github.io).
• Initial graph with random edges (the graph of Fig. 6 is created by this function)
• Calculation of diameter and ASPL
• Graph figure in Portable Network Graphics (PNG) format (the graphs shown
Figs. 6 and 7 are created by this function)
4.2 Implementation
The “create-random.py” does not search out the smallest diameter and ASPL.
Moreover, to obtain diameter and ASPL of a graph, it is necessary to calculate all
of the shortest paths among its vertices. Although the “create-random.py” calculates
the shortest paths using the shortest_path_length method of the networkx package,
this method requires a significant amount of time.
To search for the smallest diameter and ASPL, we developed a GraphGolf code
in both Python and XMP/C based on “create-random.py.” A Simulated Annealing
(SA) [21, 22] algorithm is used for optimization. The shortest paths calculation
is parallelized by XMP directives. Figure 8 shows a flow chart for the algorithm.
While Python is used to create initial graph and output the figure, XMP/C is used to
implement other parts.