Optimize Havel-Hakimi Algorithm with Max-Heap for Improved Efficiency #2735

sunav1411 · 2025-03-22T14:24:22Z

This PR introduces an optimization to the Havel-Hakimi degree sequence realization algorithm by replacing redundant sorting operations with a max-heap implementation.

Optimize degree sequence realization by avoiding repeated sorting using qsort()

Added a git fetch --tags step to the workflow after the checkout process. This ensures that the build process can access version tags, preventing issues with missing or shallow clone history during version detecti

…sorting Extended Description: Replaced the repeated sorting operations with a max-heap implementation. This improves the efficiency of the Havel-Hakimi degree sequence realization by avoiding redundant sorting steps. The max-heap handles vertex selection efficiently, reducing the overall complexity and improving performance

Tagl · 2025-03-27T07:12:29Z

.github/workflows/stimulus.yml

        with:
          fetch-depth: 0

+      - name: Fetch tags


What is the reasoning for this change?

Sir, actually I added this to fetch all tags, but later realized the repo has no tags, so it's unnecessary.

Tagl · 2025-03-27T07:15:06Z

src/misc/degree_sequence.cpp

-
-
 // Choose vertices in the order of their IDs.
+#include <queue>


Is there a reason this is included here instead of at the top of the file?

Sir, actually I added it here while fixing an issue, but yeah, it makes more sense to have it at the top. I'll move it.

Tagl · 2025-03-27T07:15:18Z

src/misc/degree_sequence.cpp

-
 // Choose vertices in the order of their IDs.
+#include <queue>
+#include <vector>


vector is already included

Sir, my bad! It’s my first time, so I’m still learning and made this mistake. But I’ll be more careful next time and won’t repeat it. I will remove the duplicate.

Tagl · 2025-03-27T07:26:10Z

src/misc/degree_sequence.cpp

-             ++it, ++k) {
-            if (--(it->degree) < 0) {
-                goto fail;
+        std::vector<VertexDeg> remainingNodes;  


The vector should either be initialized of size degree or call reserve to prevent unnecessary reallocations.

Sir, thanks for pointing it out! I’m still learning and really appreciate the guidance. I will make sure to initialize the vector properly next time

Tagl · 2025-03-27T07:26:17Z

src/misc/degree_sequence.cpp


-    typedef std::list<vd_pair> vlist;
-    vlist vertices;
+    typedef std::pair<igraph_integer_t, igraph_integer_t> VertexDeg;  // (degree, vertex)


Why is the structure an std::pair now? A type for this is already defined and was used in the line you removed. A struct with names is preferable over an std::pair. You should also use using over typedef when possible in C++.

Sir, I changed it to std::pair while refactoring, but yeah, you’re right. A struct with proper names is better. I’ll fix it. Thanks for the help and guidance.

Tagl · 2025-03-27T07:29:03Z

src/misc/degree_sequence.cpp

-        if (vd.degree == 0) {
-            continue;
+        if (degree > maxHeap.size()) {
+            return IGRAPH_EINVAL;  // Return error code if the sequence is invalid


The comment is redundant as the code clearly says the same thing. The comment here should rather say why the sequence is invalid.

I will update the comment to explain why the sequence is invalid instead of just stating the obvious.

Tagl · 2025-03-27T07:29:59Z

src/misc/degree_sequence.cpp

+        // Connect the current vertex to its neighbors
+        for (igraph_integer_t i = 0; i < degree; ++i) {
+            if (maxHeap.empty()) {
+                return IGRAPH_EINVAL;  


A comment explaining why it is invalid at this step would be useful for fresh eyes.

I will add a clear comment explaining why it’s invalid at this step to make it easier for fresh eyes.

tests/unit/igraph_realize_degree_sequence.c

Tagl · 2025-03-27T07:49:31Z

tests/unit/igraph_realize_degree_sequence.c

-}
-
-
-int main(void) {


Why are all the tests deleted?

Since it is my first time, I made the mistake of deleting the tests unintentionally. I am learning from it and will be more careful moving forward.

stale · 2025-04-26T18:42:50Z

This issue has been automatically marked as stale because it has not had recent activity. It will be closed in 14 days if no further activity occurs. Thank you for your contributions.

sunav1411 added 4 commits March 20, 2025 01:55

Update igraph_realize_degree_sequence.c

97f280f

Optimize degree sequence realization by avoiding repeated sorting using qsort()

Merge branch 'master' into master

112c028

Fix: Added tag fetching step to workflow

e179301

Added a git fetch --tags step to the workflow after the checkout process. This ensures that the build process can access version tags, preventing issues with missing or shallow clone history during version detecti

Tagl suggested changes Mar 27, 2025

View reviewed changes

sunav1411 requested a review from Tagl March 27, 2025 10:56

sunav1411 closed this Mar 27, 2025

sunav1411 reopened this Mar 27, 2025

stale bot added the stale Issues that have been inactive for a long time; will be closed in the absence of further activity label Apr 26, 2025

szhorvat removed the stale Issues that have been inactive for a long time; will be closed in the absence of further activity label Apr 27, 2025

stale bot added the stale Issues that have been inactive for a long time; will be closed in the absence of further activity label Jul 19, 2025

igraph deleted a comment from stale bot Jul 20, 2025

szhorvat removed the stale Issues that have been inactive for a long time; will be closed in the absence of further activity label Jul 20, 2025



		// Choose vertices in the order of their IDs.
		#include <queue>

		}


		int main(void) {

Uh oh!

Optimize Havel-Hakimi Algorithm with Max-Heap for Improved Efficiency #2735

Are you sure you want to change the base?

Optimize Havel-Hakimi Algorithm with Max-Heap for Improved Efficiency #2735

Conversation

sunav1411 commented Mar 22, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

stale bot commented Apr 26, 2025

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants