Implementation of hypergraph

In this tutorial, we will learn to implement a hypergraph in C.

Definition- A hypergraph is a special version of a graph. A single one of them can connect 2 or more vertices.

In a normal graph, a single edge can only connect 2 vertices, but a hypergraph is a generalization of the graph and can be used to connect more than 2 vertices with a single edge.

In a hypergraph, edges are called hyperedges. We can represent a hypergraph by H(E, V), where E is a hyperedge and v is a set of vertices connected by a single hyperedge.

Here, we implement a hypergraph.

Example

In the following example, we demonstrate the implementation of a hypergraph using the map data structure in C. In a map, we store edge names as keys and the set of vertices connected by the edges as values.

After that, we use the erase() method to delete "edge2" from the graph. Additionally, use the insert() method to insert "edge4" connecting 4 vertices into the graph.

Finally, we print all the edges of the graph and their connected vertices.

#include <bits/stdc++.h>
#include <iostream>
using namespace std;

void createHyperGraph() {
    // Creating the hypergraph
    map<string, vector<int>> h_graph = {{"edge1", {32, 21, 90}},
                                        {"edge2", {21, 47, 54}},
                                        {"edge3", {43, 76}}};
    // Removing edge from the hypergraph
    h_graph.erase("edge2");
    // Inserting a new edge in the hypergraph
    h_graph.insert({"edge4", {48, 61, 93, 52, 89}});
    cout << "The hypergraph is :-" << endl;
    for (auto ele : h_graph) {
        string edge = ele.first;
        cout << edge << " : ";
        vector<int> vert = ele.second;
        for (int v : vert) {
            cout << v << " ";
        }
        cout << endl;
    }
}
int main() {
    createHyperGraph();
    return 0;
}

Output

The hypergraph is :-
edge1 : 32 21 90 
edge3 : 43 76 
edge4 : 48 61 93 52 89

Time complexity - O(N) Traverse all edges.

Space complexity - O(N) to store N edges.

In the above example, we see that hyperedges can connect different vertices.

Real-life use cases for Hypergraph

When we look at the implementation of hypergraphs versus ordinary graphs, the first question is why we should use hypergraphs. Here we will see some real-world use cases where hypergraphs can be used.

• Social Network- We can use hypergraphs to represent social networks. In social networks, people may be connected to different relationships, such as friendships, colleagues, family, etc. Therefore, we can use each edge as a relationship and each person as a vertex of the graph. Now, we can consider that there may be more than two people in each relationship. For example, a family of 4 to 5 people and a group of 10 friends.

• Database Modeling- We can use hypergraph to model a database where we need to join multiple attributes of a table in a single relationship.

• Complex System Representation - Another use case of using hypergraphs is the development of complex systems such as transportation systems, biological interactions, etc.

Type of hypergraph

Here we will discuss 5 types of hypergraphs.

• Uniform Hypergraph: Each edge of a uniform hypergraph contains the same number of vertices.

• Bipartite hypergraph: In a bipartite hypergraph, each vertex is divided into two disjoint sets. Furthermore, each hyperedge contains vertices from both sets.

• Directed hypergraph: In a directed hypergraph, each hyperedge has a direction. Therefore, we need to consider the order in which each hyperedge connects vertices.

• Weighted hypergraph: We can assign a weight to each vertex connection, thus assigning different importance to each connection.

• Labeled Hypergraph: We can add labels to each connection of a vertex to convey more information about the vertex.

Here, we have implemented a basic hypergraph. However, in real-time development, a single hyperedge can connect hundreds of graph vertices. Additionally, we saw types of hypergraphs and real-life use cases.

The above is the detailed content of Implementation of hypergraph. For more information, please follow other related articles on the PHP Chinese website!