• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

Qiskit / rustworkx / 9301444525
94%

Build:
DEFAULT BRANCH: main
Ran 30 May 2024 11:16AM UTC
Jobs 1
Files 102
Run time 1min
Badge
Embed ▾
README BADGES
x

If you need to use a raster PNG badge, change the '.svg' to '.png' in the link

Markdown

Textile

RDoc

HTML

Rst

30 May 2024 11:03AM UTC coverage: 95.818% (-0.2%) from 96.059%
9301444525

push

github

web-flow
Add "saturation first" and "independent set" greedy node coloring strategies (#1138)

This PR adds two more standard coloring strategies to greedy node/edge coloring functions graph_greedy_color and graph_greedy_edge_color.

In the literature the first strategy is known as "saturation", "DSATUR" or "SLF". We dynamically choose the vertex that has the largest number of different colors already assigned to its neighbors, and, in case of a tie, the vertex that has the largest number of uncolored neighbors.

The second strategy is known as "greedy independent sets" or "GIS". We greedily find independent subsets of the graph, and assign a different color to each of these subsets.

This addresses #1137, modulo the fact that there are quadrillions of different greedy node coloring algorithms, and each comes with trillion variations.

Both new strategies can be combined with preset_color_fn (for node coloring).

There is also a new Rust enum GreedyStrategy exposed as a python class that allows to specify which of the three currently supported greedy strategies is used. This is, calling the functions from the Python code would be as follows:

import rustworkx as rx

graph = rx.generators.generalized_petersen_graph(5, 2)

coloring = rx.graph_greedy_color(graph, greedy_strategy=rx.GreedyStrategy.Degree)
coloring = rx.graph_greedy_color(graph, greedy_strategy=rx.GreedyStrategy.Saturation)
coloring = rx.graph_greedy_color(graph, greedy_strategy=rx.GreedyStrategy.IndependentSet)
coloring = rx.graph_greedy_color(graph)
coloring = rx.graph_greedy_edge_color(graph)
coloring = rx.graph_greedy_edge_color(graph, greedy_strategy=rx.GreedyStrategy.Degree)
coloring = rx.graph_greedy_edge_color(graph, greedy_strategy=rx.GreedyStrategy.Saturation)
coloring = rx.graph_greedy_edge_color(graph, greedy_strategy=rx.GreedyStrategy.IndependentSet)

The greedy_graph_edge_color function has been also extended to support the preset_color_fn argument (though in ... (continued)

191 of 200 new or added lines in 3 files covered. (95.5%)

42 existing lines in 2 files now uncovered.

17254 of 18007 relevant lines covered (95.82%)

1174014.85 hits per line

New Missed Lines in Diff

Lines Coverage ∆ File
1
98.9
-1.1% src/coloring.rs
8
90.02
-9.98% rustworkx-core/src/coloring.rs

Uncovered Existing Lines

Lines Coverage ∆ File
6
95.53
-3.35% src/shortest_path/all_pairs_bellman_ford.rs
36
90.02
-9.98% rustworkx-core/src/coloring.rs
Jobs
ID Job ID Ran Files Coverage
1 9301444525.1 30 May 2024 11:16AM UTC 102
95.82
GitHub Action Run
Source Files on build 9301444525
  • Tree
  • List 102
  • Changed 29
  • Source Changed 3
  • Coverage Changed 4
Coverage ∆ File Lines Relevant Covered Missed Hits/Line
  • Back to Repo
  • Github Actions Build #9301444525
  • 8af19f0f on github
  • Prev Build on main (#9259965164)
  • Next Build on main (#9331316840)
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2025 Coveralls, Inc