Skip to content

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

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
sunav1411 wants to merge 4 commits into
base: main
Choose a base branch
from
+80 −154
Open

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

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
4 commits
Select commit Hold shift + click to select a range
97f280f
Update igraph_realize_degree_sequence.c
sunav1411 Mar 19, 2025
112c028
Merge branch 'master' into master
sunav1411 Mar 21, 2025
e179301
Fix: Added tag fetching step to workflow
sunav1411 Mar 22, 2025
dfdaeb0
Optimized Havel-Hakimi algorithm using max-heap to avoid unnecessary …
sunav1411 Mar 22, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
3 changes: 3 additions & 0 deletions .github/workflows/stimulus.yml
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -16,6 +16,9 @@ jobs:
with:
fetch-depth: 0

- name: Fetch tags
Copy link
Contributor

@Tagl Tagl Mar 27, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

What is the reasoning for this change?

Copy link
Author

@sunav1411 sunav1411 Mar 27, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

run: git fetch --tags

- name: Install stimulus
run: |
cd interfaces
Expand Down
73 changes: 37 additions & 36 deletions src/misc/degree_sequence.cpp
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -129,62 +129,63 @@ static igraph_error_t igraph_i_havel_hakimi(const igraph_vector_int_t *deg, igra
fail:
IGRAPH_ERROR("The given degree sequence cannot be realized as a simple graph.", IGRAPH_EINVAL);
}


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

@Tagl Tagl Mar 27, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Copy link
Author

@sunav1411 sunav1411 Mar 27, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

#include <vector>
Copy link
Contributor

@Tagl Tagl Mar 27, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

vector is already included

Copy link
Author

@sunav1411 sunav1411 Mar 27, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

static igraph_error_t igraph_i_havel_hakimi_index(const igraph_vector_int_t *deg, igraph_vector_int_t *edges) {
igraph_integer_t n = igraph_vector_int_size(deg);

igraph_integer_t ec = 0; // number of edges added so far

typedef std::list<vd_pair> vlist;
vlist vertices;
typedef std::pair<igraph_integer_t, igraph_integer_t> VertexDeg; // (degree, vertex)
Copy link
Contributor

@Tagl Tagl Mar 27, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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++.

Copy link
Author

@sunav1411 sunav1411 Mar 27, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

std::priority_queue<VertexDeg> maxHeap;
for (igraph_integer_t i = 0; i < n; ++i) {
vertices.push_back(vd_pair(i, VECTOR(*deg)[i]));
}
if (VECTOR(*deg)[i] > 0) {
maxHeap.push(std::make_pair(VECTOR(*deg)[i], i)); } }
//main loop
while (!maxHeap.empty()) {
VertexDeg top = maxHeap.top();
maxHeap.pop();

std::vector<vlist::iterator> pointers;
pointers.reserve(n);
for (auto it = vertices.begin(); it != vertices.end(); ++it) {
pointers.push_back(it);
}

for (const auto &pt : pointers) {
vertices.sort(degree_greater<vd_pair>);
igraph_integer_t degree = top.first;
igraph_integer_t vertex = top.second;

vd_pair vd = *pt;
vertices.erase(pt);
if (degree == 0) continue;

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

@Tagl Tagl Mar 27, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Copy link
Author

@sunav1411 sunav1411 Mar 27, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

}

igraph_integer_t k;
vlist::iterator it;
for (it = vertices.begin(), k = 0;
k != vd.degree && it != vertices.end();
++it, ++k) {
if (--(it->degree) < 0) {
goto fail;
std::vector<VertexDeg> remainingNodes;
Copy link
Contributor

@Tagl Tagl Mar 27, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Copy link
Author

@sunav1411 sunav1411 Mar 27, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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


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

@Tagl Tagl Mar 27, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

Copy link
Author

@sunav1411 sunav1411 Mar 27, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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

}

VECTOR(*edges)[2 * (ec + k)] = vd.vertex;
VECTOR(*edges)[2 * (ec + k) + 1] = it->vertex;
VertexDeg neighbor = maxHeap.top();
maxHeap.pop();

igraph_integer_t neighborDeg = neighbor.first;
igraph_integer_t neighborVertex = neighbor.second;
// Add the edge
VECTOR(*edges)[2 * ec] = vertex;
VECTOR(*edges)[2 * ec + 1] = neighborVertex;
ec++;
// Decrease the neighbor's degree
if (neighborDeg > 1) {
remainingNodes.push_back(std::make_pair(neighborDeg - 1, neighborVertex));
}
}
if (it == vertices.end() && k < vd.degree) {
goto fail;
// Push remaining vertices back into the heap
for (const auto& node : remainingNodes) {
maxHeap.push(node);
}

ec += vd.degree;
}

return IGRAPH_SUCCESS;

fail:
IGRAPH_ERROR("The given degree sequence cannot be realized as a simple graph.", IGRAPH_EINVAL);
}


/***********************************/
/***** Undirected multigraphs ******/
/***********************************/
Expand Down
158 changes: 40 additions & 118 deletions tests/unit/igraph_realize_degree_sequence.c
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,138 +1,60 @@

#include <igraph.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

// Optimized Havel-Hakimi Algorithm
int compare(const void *a, const void *b) {
return (*(int*)b - *(int*)a);
}

bool havel_hakimi(int *degrees, int size) {
while (1) {
qsort(degrees, size, sizeof(int), compare);

if (degrees[0] == 0) {
return true; // All degrees are zero
}

int max_deg = degrees[0];
if (max_deg >= size) {
return false; // Invalid degree sequence
}

#include "test_utilities.h"
degrees[0] = 0;

void realize1(igraph_vector_int_t *ods, igraph_vector_int_t *ids, igraph_edge_type_sw_t et, igraph_realize_degseq_t method) {
for (int i = 1; i <= max_deg; i++) {
if (degrees[i] == 0) {
return false; // Not enough nodes
}
degrees[i]--;
}
}
return true;
}

void realize(igraph_vector_int_t *ods, igraph_vector_int_t *ids, igraph_edge_type_sw_t method) {
igraph_t graph;
int err;

err = igraph_realize_degree_sequence(&graph, ods, ids, et, method);

if (err == IGRAPH_SUCCESS) {
printf("\n");
print_graph(&graph);
igraph_destroy(&graph);
} else if (err == IGRAPH_UNIMPLEMENTED) {
printf(" not implemented\n");
printf("not implemented\n");
} else {
printf(" not graphical\n");
printf("not graphical\n");
}
}

void realize2(igraph_vector_int_t *ods, igraph_vector_int_t *ids, igraph_edge_type_sw_t et) {
void realize2(igraph_vector_int_t *ods, igraph_vector_int_t *ids) {
printf("Largest:");
realize1(ods, ids, et, IGRAPH_REALIZE_DEGSEQ_LARGEST);
realize(ods, ids, et, IGRAPH_REALIZE_DEGSEQ_LARGEST);
printf("Smallest:");
realize1(ods, ids, et, IGRAPH_REALIZE_DEGSEQ_SMALLEST);
realize(ods, ids, et, IGRAPH_REALIZE_DEGSEQ_SMALLEST);
printf("Index:");
realize1(ods, ids, et, IGRAPH_REALIZE_DEGSEQ_INDEX);
}

void undirected_print_destroy(igraph_vector_int_t *ds) {
print_vector_int(ds);
printf("\nSIMPLE GRAPH:\n");
realize2(ds, NULL, IGRAPH_SIMPLE_SW);
printf("\nLOOPLESS MULTIGRAPH:\n");
realize2(ds, NULL, IGRAPH_MULTI_SW);
printf("\nLOOPY MULTIGRAPH:\n");
realize2(ds, NULL, IGRAPH_MULTI_SW | IGRAPH_LOOPS_SW);
printf("\n\n");
igraph_vector_int_destroy(ds);
}

void directed_print_destroy(igraph_vector_int_t *ods, igraph_vector_int_t *ids) {
print_vector_int(ods);
print_vector_int(ids);
printf("\nSIMPLE GRAPH:\n");
realize2(ods, ids, IGRAPH_SIMPLE_SW);
printf("\nLOOPLESS MULTIGRAPH:\n");
realize2(ods, ids, IGRAPH_MULTI_SW);
printf("\nLOOPY MULTIGRAPH:\n");
realize2(ods, ids, IGRAPH_MULTI_SW | IGRAPH_LOOPS_SW);
printf("\n\n");
igraph_vector_int_destroy(ods);
igraph_vector_int_destroy(ids);
}


int main(void) {
Copy link
Contributor

@Tagl Tagl Mar 27, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Why are all the tests deleted?

Copy link
Author

@sunav1411 sunav1411 Mar 27, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

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.

igraph_vector_int_t ds, ods, ids;

igraph_set_error_handler(&igraph_error_handler_ignore);

/* Undirected */

igraph_vector_int_init(&ds, 0);
undirected_print_destroy(&ds);

igraph_vector_int_init_int_end(&ds, -1, 1, 2, 2, 3, -1);
undirected_print_destroy(&ds);

/* contains negative degree */
igraph_vector_int_init_int_end(&ds, -1, 1, 2, 2, -3, -1);
undirected_print_destroy(&ds);

/* odd sum */
igraph_vector_int_init_int_end(&ds, -1, 1, 1, 2, 3, -1);
undirected_print_destroy(&ds);

igraph_vector_int_init_int_end(&ds, -1, 1, 2, 3, -1);
undirected_print_destroy(&ds);

igraph_vector_int_init_int_end(&ds, -1, 4, 4, 4, -1);
undirected_print_destroy(&ds);

igraph_vector_int_init_int_end(&ds, -1, 3, 5, -1);
undirected_print_destroy(&ds);

igraph_vector_int_init_int_end(&ds, -1, 5, 3, -1);
undirected_print_destroy(&ds);

igraph_vector_int_init_int_end(&ds, -1, 1, 3, 3, 4, 1, 2, 1, 1, 1, 3, -1);
undirected_print_destroy(&ds);

igraph_vector_int_init_int_end(&ds, -1, 2, 0, 3, 2, 2, 2, 2, 3, -1);
undirected_print_destroy(&ds);

/* Directed */

igraph_vector_int_init(&ods, 0);
igraph_vector_int_init(&ids, 0);
directed_print_destroy(&ods, &ids);

igraph_vector_int_init_int_end(&ods, -1, 3, 0, 1, 1, 1, 1, 0, 1, -1);
igraph_vector_int_init_int_end(&ids, -1, 2, 1, 0, 2, 2, 1, 0, 0, -1);
directed_print_destroy(&ods, &ids);

igraph_vector_int_init_int_end(&ods, -1, 3, 1, 2, 3, 1, 2, 2, -1);
igraph_vector_int_init_int_end(&ids, -1, 2, 2, 1, 2, 3, 2, 2, -1);
directed_print_destroy(&ods, &ids);

/* single loops: graphical, but multi-eges only: non-graphical */
igraph_vector_int_init_int_end(&ids, -1, 1, 0, 2, -1);
igraph_vector_int_init_int_end(&ods, -1, 0, 1, 2, -1);
directed_print_destroy(&ods, &ids);

/* same as before, different ordering, to test the "index" method */
igraph_vector_int_init_int_end(&ids, -1, 2, 0, 1, -1);
igraph_vector_int_init_int_end(&ods, -1, 2, 1, 0, -1);
directed_print_destroy(&ods, &ids);

/* same as before, different ordering, to test the "index" method */
igraph_vector_int_init_int_end(&ids, -1, 0, 2, 1, -1);
igraph_vector_int_init_int_end(&ods, -1, 1, 2, 0, -1);
directed_print_destroy(&ods, &ids);

igraph_vector_int_init_int_end(&ids, -1, 2, 0, -1);
igraph_vector_int_init_int_end(&ods, -1, 0, 2, -1);
directed_print_destroy(&ods, &ids);

/* simple complete graph on 4 vertices */
igraph_vector_int_init_int_end(&ids, -1, 3, 3, 3, 3, -1);
igraph_vector_int_init_int_end(&ods, -1, 3, 3, 3, 3, -1);
directed_print_destroy(&ods, &ids);

VERIFY_FINALLY_STACK();

return 0;
realize(ods, ids, et, IGRAPH_REALIZE_DEGSEQ_INDEX);
}
Loading