newton.sim.color_graph#

newton.sim.color_graph(num_nodes, graph_edge_indices, balance_colors=True, target_max_min_color_ratio=1.1, algorithm=ColoringAlgorithm.MCS)[source]#

A function that generates coloring for a graph, which is represented by the number of nodes and an array of edges. It returns a list of np.array with dtype`=`int. The length of the list is the number of colors and each np.array contains the indices of vertices with this color.

Parameters:
  • num_nodes – The number of the nodes in the graph

  • graph_edge_indices (array(ndim=2, dtype=int32)) – A wp.array of shape (number_edges, 2)

  • balance_colors (bool) – Whether to apply the color balancing algorithm to balance the size of each color

  • target_max_min_color_ratio (float) – the color balancing algorithm will stop when the ratio between the largest color and the smallest color reaches this value

  • algorithm (ColoringAlgorithm) – Value should an enum type of ColoringAlgorithm, otherwise it will raise an error. ColoringAlgorithm.mcs means using the MCS coloring algorithm, while ColoringAlgorithm.ordered_greedy means using the degree-ordered greedy algorithm. The MCS algorithm typically generates 30% to 50% fewer colors compared to the ordered greedy algorithm, while maintaining the same linear complexity. Although MCS has a constant overhead that makes it about twice as slow as the greedy algorithm, it produces significantly better coloring results. We recommend using MCS, especially if coloring is only part of the preprocessing stage.e.

Note

References to the coloring algorithm: MCS: Pereira, F. M. Q., & Palsberg, J. (2005, November). Register allocation via coloring of chordal graphs. In Asian Symposium on Programming Languages and Systems (pp. 315-329). Berlin, Heidelberg: Springer Berlin Heidelberg. Ordered Greedy: Ton-That, Q. M., Kry, P. G., & Andrews, S. (2023). Parallel block Neo-Hookean XPBD using graph clustering. Computers & Graphics, 110, 1-10.