Havel-Hakimi algorithm in C++
An algorithm in graph theory that resolves the graph realization problem is the Havel-Hakimi algorithm. In other words, it responds to the following query: Does a simple graph exist such that its degree sequence is the same as a finite list of nonnegative integers in non-increasing order? There are no loops or multiple edges in a basic graph. The degree sequence is a collection of numbers that represents the number of edges that incident to each vertex in the graph in a non-increasing order. The list of integers is called a graphic if there is a simple graph for the exact degree sequence that is provided. If a simple graph for the specified degree sequence exists, the Havel-Hakimi algorithm either builds a specific solution or establishes the impossibility of finding a positive answer. The foundation of this building is a recursive algorithm. Havel published the method in 1955, and Hakimi followed suit in 1962.
![Havel-Hakimi algorithm in C++](https://static.tutorialandexample.com/cpp/havel-hakimi-algorithm-in-cpp1.png)
Understanding graph realization problem:
A graph realization or graph creation issue asks if there is a finite simple graph such that d1, d2,..., dn represents the degrees of vertices of this graph for a given finite series (d1, d2,..., dn) of natural integers. Numerous theoretical studies have been conducted on the issue, providing the required and sufficient criteria for the development of a solution [8, 7, 5, 9]. Naturally, directed graphs can also pose this difficulty if two sets of natural integers are provided for the in- and out-degrees [13, 11, 12]. There are two possible approaches to solving the realization problem: identifying a graph that meets the requirements or identifying every graph that meets the requirements. If a series of nonnegative integers is the degree sequence of a graph, it is referred to as graphical. A list of pairs of nonnegative integers, denoted as (a1, b1), (a2, b2),..., (an, bn), is biographical if the vertices of a directed graph have ai as their out-degrees and bi as their in-degrees. As an illustration, consider the graphic sequence 4, 3, 3, 2, 2, 2.
Algorithm Overview:
If you are already familiar with this subject, you can move on to the linked graph algorithm (HH). Typically, the widely recognized Havel-Hakimi algorithm (HH) is used to construct a graph that realizes a certain degree sequence. The easiest way to understand the procedure is to imagine that each vertex has the same number of stubs as its degree. The next step is to join all of these stubs together to create a graph.
Implementation in C++:
Let us take an example to illustrate the Havel-Hakimi Algorithm in C++.
#include <iostream>
#include <deque>
#include <sstream>
#include <algorithm>
#include <functional>
#include <numeric>
using namespace std;
bool havel_hakimi(deque<int> degreeSequence) {
//Sort the input into non-increasing order.
sort(degreeSequence.begin(), degreeSequence.end(), greater<int>());
//If there is a an element with a value greater than the number of elements, return false.
//Since the container is sorted, we only need to inspect the first element.
if (degreeSequence.front() > degreeSequence.size())
return false;
//If there is a negative element, return false.
//Since the container is sorted, we only need to inspect the last element.
if (degreeSequence.back() < 0)
return false;
//If the container has all 0s, return true.
//Since the container is sorted and there are no negative values, we only need to inspect the first element.
if (!degreeSequence.front())
return true;
int sum = accumulate(degreeSequence.begin(), degreeSequence.end(), 0);
//If the sum of the elements is odd, return false.
if (sum % 2)
return false;
int front = degreeSequence.front();
degreeSequence.pop_front();
for (int i = 0; i < front; ++i)
--degreeSequence[i];
//Recursive call
return havel_hakimi(move(degreeSequence));
}
int main() {
cout << "Enter a space-separated degree sequence.\n";
string input;
getline(cin, input);
int temp;
deque<int> degreeSequence;
istringstream iss(input);
while (iss >> temp)
degreeSequence.push_back(temp);
cout << "There ";
cout << (havel_hakimi(degreeSequence) ? "exists " : "does not exist ");
cout << "a simple graph with the degree sequence [";
for (auto it = degreeSequence.begin(); it != degreeSequence.end() - 1; ++it)
cout << *it << ", ";
cout << *(degreeSequence.end() - 1) << "].\n";
return 0;
}
Output:
Enter a space-separated degree sequence.
1
There does not exist a simple graph with the degree sequence [1].
Conclusion:
In conclusion, this article discussed the Havel-Hakimi algorithm. The biggest degree in the degree sequence is removed repeatedly, and the matching vertex is added to the graph to connect it to its neighbors.lity of the code.