|
hglib
|
hglib is an open-source C++ library to manipulate hypergraphs. A hypergraph is a generalization of a graph where an edge can join any number of vertices.
hglib allows to associate user defined properties to vertices, hyperedges/hyperarcs and to the hypergraph itself. Thus, it can be used in a wide range of problems arising e.g. in operations research, computer science, and computational biology.
hglib is available for download from source only, see the "Git repository" section below
The git repository of the hglib library can be found at https://gitlab.inria.fr/kirikomics/hglib.git.
Type the following on the command line to get a copy of the repository:
git clone https://gitlab.inria.fr/kirikomics/hglib.git
The documentation is available at https://kirikomics.gitlabpages.inria.fr/hglib/
You can find information concerning the development of the hglib library in doc/devGuide.md
hglib is distributed under the GNU AGPLv3 license. Please see the LICENSE file for more details.
By default a directed hypergraph contains vertices of type DirectedVertex and hyperarcs of type DirectedHyperedge. A directed hypergraph can be declared as follows:
#include "path_to_hglib/hglib.h"
#include <iostream>
int main( int argc, const char* argv[] ) {
hglib::DirectedHypergraph<> dhg;
// Add vertices with given name
dhg.addVertex("A"); // vertex id = 0
dhg.addVertex("B"); // vertex id = 1
dhg.addVertex("Foo"); // vertex id = 2
dhg.addVertex("Bar"); // vertex id = 3
dhg.addVertex(""); // vertex id = 4
dhg.addVertex("6"); // vertex id = 5
// Add vertices with default name
dhg.addVertex(); // vertex id = 6
dhg.addVertex(); // vertex id = 7
// add hyperarcs using the vertex names
dhg.addHyperarc(hglib::NAME, {{"A"}, {"Foo"}});
dhg.addHyperarc(hglib::NAME, {{"A", "B"}, {"Bar", ""}});
dhg.addHyperarc(hglib::NAME, {{"6"}, {""}});
// add hyperarcs using the vertex ids
dhg.addHyperarc({{0, 1}, {2, 3}});
dhg.addHyperarc({{3}, {6, 7}});
// print the directed hypergraph
std::cout << dhg << std::endl;
return 0;
}
In the following code example we declare a directed hypergraph using named directed hyperedges. It is also shown how to iterate over the vertices and hyperarcs of the hypergraph.
#include "path_to_hglib/hglib.h"
int main( int argc, const char* argv[] ) {
typedef hglib::DirectedHypergraph<hglib::DirectedVertex, hglib::NamedDirectedHyperedge> hypergraph;
hypergraph dhg;
// Add vertices with given name
dhg.addVertex("A"); // vertex id = 0
dhg.addVertex("B"); // vertex id = 1
dhg.addVertex("Foo"); // vertex id = 2
dhg.addVertex("Bar"); // vertex id = 3
dhg.addVertex(""); // vertex id = 4
dhg.addVertex("6"); // vertex id = 5
// Add vertices with default name
dhg.addVertex(); // vertex id = 6
dhg.addVertex(); // vertex id = 7
// add hyperarcs using the vertex names
dhg.addHyperarc(hglib::NAME, {{"A"}, {"Foo"}}, {"hyperarc1"});
dhg.addHyperarc(hglib::NAME, {{"A", "B"}, {"Bar", ""}}, {"hyperarc2"});
dhg.addHyperarc(hglib::NAME, {{"6"}, {""}}, {"hyperarc3"});
// add hyperarcs using the vertex ids
dhg.addHyperarc({{0, 1}, {2, 3}}, {"hyperarc4"});
dhg.addHyperarc({{3}, {6, 7}}, {"hyperarc5"});
// Iterating over the vertices of the hypergraph...
// ... with range based for loop
for (const auto& vertex : dhg.vertices()) {
std::cout << "Vertex: " << vertex->name() << '\n';
}
// ... with iterators I
for (auto it = dhg.verticesBegin(); it != dhg.verticesEnd(); ++it) {
std::cout << "Vertex: " << (*it)->name() << '\n';
}
// ... with iterators II
hypergraph::vertex_iterator itVertex, endVertices;
std::tie(itVertex, endVertices) = dhg.verticesBeginEnd();
for(; itVertex != endVertices; ++itVertex) {
std::cout << "Vertex: " << (*itVertex)->name() << '\n';
}
// Iterating over the hyperarcs of the hypergraph...
// ... with range based for loop
for (const auto& hyperarc : dhg.hyperarcs()) {
std::cout << "Hyperarc: " << hyperarc->name() << '\n';
}
// ... with iterators I
for (auto it = dhg.hyperarcsBegin(); it != dhg.hyperarcsEnd(); ++it) {
std::cout << "Hyperarc: " << (*it)->name() << '\n';
}
// ... with iterators II
hypergraph::hyperarc_iterator itHyperarc, endHyperarcs;
std::tie(itHyperarc, endHyperarcs) = dhg.hyperarcsBeginEnd();
for(; itHyperarc != endHyperarcs; ++itHyperarc) {
std::cout << "Hyperarc: " << (*itHyperarc)->name() << '\n';
}
// Iterating over the in-/out-arcs of a vertex...
for (const auto& vertex : dhg.vertices()) {
const auto& vertexId = vertex->id();
// Get in-degree
size_t inDegree = dhg.inDegree(vertexId);
// Iterate over in-hyperarcs
// ... with iterators I
for (auto it = dhg.inHyperarcsBegin(vertexId); it != dhg.inHyperarcsEnd(vertexId); ++it) {
std::cout << "In-arc: " << (*it)->name() << '\n';
}
// ... with iterators II
hypergraph::hyperarc_iterator it, end;
std::tie(it, end) = dhg.inHyperarcsBeginEnd(vertexId);
for (; it != end; ++it) {
std::cout << "In-arc: " << (*it)->name() << '\n';
}
/// ... with range based for loop
auto inHyperarcsPtr = dhg.inHyperarcs(vertexId);
for (const auto& arc : * inHyperarcsPtr) {
std::cout << "In-arc: " << arc->name() << '\n';
}
// Get out-degree
size_t outDegree = dhg.outDegree(vertexId);
// Iterate over out-hyperarcs
// ... with iterators I
for (auto it = dhg.outHyperarcsBegin(vertexId); it != dhg.outHyperarcsEnd(vertexId); ++it) {
std::cout << "Out-arc: " << (*it)->name() << '\n';
}
// ... with iterators II
std::tie(it, end) = dhg.outHyperarcsBeginEnd(vertexId);
for (; it != end; ++it) {
std::cout << "Out-arc: " << (*it)->name() << '\n';
}
/// ... with range based for loop
auto outHyperarcsPtr = dhg.outHyperarcs(vertexId);
for (const auto& arc : *outHyperarcsPtr) {
std::cout << "Out-arc: " << arc->name() << '\n';
}
}
// Iterate over tails/heads of a given hyperarc
for (const auto& hyperarc : dhg.hyperarcs()) {
const auto& arcId = hyperarc->id();
// Get number of tail vertices
size_t nbTails = dhg.nbTailVertices(arcId);
// Iterate over tails...
// ... with iterators I
for (auto it = dhg.tailsBegin(arcId); it != dhg.tailsEnd(arcId); ++it) {
std::cout << "Tail: " << (*it)->name() << '\n';
}
// ... with iterators II
hypergraph::vertex_iterator it, end;
std::tie(it, end) = dhg.tailsBeginEnd(arcId);
for (; it != end; ++it) {
std::cout << "Tail: " << (*it)->name() << '\n';
}
/// ... with range based for loop
auto tailsPtr = dhg.tails(arcId);
for (const auto& tail : *tailsPtr) {
std::cout << "Tail: " << tail->name() << '\n';
}
// Get number of head vertices
size_t nbHeads = dhg.nbHeadVertices(arcId);
// Iterate over heads...
// ... with iterators I
for (auto it = dhg.headsBegin(arcId); it != dhg.headsEnd(arcId); ++it) {
std::cout << "Head: " << (*it)->name() << '\n';
}
// ... with iterators II
std::tie(it, end) = dhg.headsBeginEnd(arcId);
for (; it != end; ++it) {
std::cout << "Head: " << (*it)->name() << '\n';
}
/// ... with range based for loop
auto headsPtr = dhg.heads(arcId);
for (const auto& head : *headsPtr) {
std::cout << "Head: " << head->name() << '\n';
}
}
return 0;
}
To assign properties to the vertices, hyperarcs, and the hypergraph, you can define a directed hypergraph as in the following code snippet where we create a directed hypergraph of six vertices and three hyperarcs (hyperarc1: A -> Foo, hyperarc2: A + B -> Bar + '', hyperarc3: 6 -> ''). To each vertex and hyperarc a property (struct with optional default values) is associated. The vertex property is composed of a name, and a colour. The hyperarc property contains a name, a weight, and a capacity. Furthermore, the properties called 'name', and 'colour' are associated to the hypergraph object (struct HypergraphProperty).
#include "path_to_hglib/hglib.h"
#include <iostream>
int main( int argc, const char* argv[] ) {
enum Colour {red, blue, green};
struct VertexProperty {
std::string name = "Default";
Colour colour = Colour::green;
};
struct HyperarcProperty {
std::string name = "Default";
double weight = 0.0;
double capacity = 0.0;
};
struct HypergraphProperty {
std::string name;
Colour colour = Colour::red;
};
// DirectedHypergraph is a class template with five parameters:
// 1. Vertex type (default DirectedVertex)
// 2. Hyperarc type (default Hyperarc)
// 3. Vertex property (optional)
// 4. Hyperarc property (optional)
// 5. Graph property (optional)
hglib::DirectedHypergraph<hglib::DirectedVertex, hglib::NamedDirectedHyperedge, VertexProperty, HyperarcProperty, HypergraphProperty> dhg;
// Add vertices
dhg.addVertex("A");
dhg.addVertex("B");
dhg.addVertex("Foo");
dhg.addVertex("Bar");
dhg.addVertex("");
dhg.addVertex("6");
// add hyperarcs
dhg.addHyperarc(hglib::NAME, {{"A"}, {"Foo"}}, {"hyperarc1"});
dhg.addHyperarc(hglib::NAME, {{"A", "B"}, {"Bar", ""}}, {"hyperarc2"});
dhg.addHyperarc(hglib::NAME, {{"6"}, {""}}, {"hyperarc3"});
// Access to vertex properties
for (const auto& vertex : dhg.vertices()) {
// Read access
const auto vProp = dhg.getVertexProperties(vertex->id());
std::cout << "Colour of vertex " << vertex->name() << ": " << vProp->colour << '\n';
// Write access to properties (Notice the '_' at the end of the function name)
auto vProp2 = dhg.getVertexProperties_(vertex->id());
vProp2->name = "Changed from default";
vProp2->colour = Colour::red;
}
// Access to hyperarc properties
for (const auto& hyperarc : dhg.hyperarcs()) {
// Read access
const auto aProp = dhg.getHyperarcProperties(hyperarc->id());
std::cout << "Capacity of hyperarc " << hyperarc->name() << ": " << aProp->capacity << '\n';
// Write access to properties (Notice the '_' at the end of the function name)
auto aProp2 = dhg.getHyperarcProperties_(hyperarc->id());
aProp2->weight = 1.0;
aProp2->capacity = 2.0;
}
// Read/Write access to hypergraph property
const auto hypergraphProp = dhg.getHypergraphProperties();
std::cout << "Colour of hypergraph: " << hypergraphProp->colour << '\n';
auto hypergraphProp2 = dhg.getHypergraphProperties_();
hypergraphProp2->colour = Colour::blue;
return 0;
}
A subgraph can be built providing a set of whitelisted vertices/hyperarcs:
#include "path_to_hglib/hglib.h"
int main( int argc, const char* argv[] ) {
hglib::DirectedHypergraph<> dhg;
for (auto vertexName : vertices) {
dhg.addVertex(vertexName);
}
// Add hyperarcs
for (auto hyperarc : hyperarcs) {
dhg.addHyperarc(hglib::NAME, hyperarc.first);
}
// The subgraph contains the vertices with the ids 1, 2, and 3.
// The subgraph contains the hyperarcs with the ids 1, and 2.
std::unordered_set<hglib::VertexIdType> whitelistedVertices = {1, 2, 3};
std::unordered_set<hglib::HyperedgeIdType> whitelistedHyperarcs = {1, 2};
// a unique_ptr is returned
auto subgraph = hglib::createDirectedSubHypergraph(&dhg, whitelistedVertices, whitelistedHyperarcs);
// Iterate over vertices
for (const auto& vertex : dhg.vertices()) {
std::cout << "Vertex " << vertex->id() << " is in subgraph: " << (subgraph->vertexById(vertex->id()) == nullptr ? "no" : "yes") << '\n';
}
// Iterate over hyperarcs
for (const auto& hyperarc : dhg.hyperarcs()) {
std::cout << "Hyperarc " << hyperarc->id() << " is in subgraph: " << (subgraph->hyperarcById(hyperarc->id()) == nullptr ? "no" : "yes") << '\n';
}
// The above statements should print
// Vertex 0 is in subgraph:no
// Vertex 1 is in subgraph:yes
// Vertex 2 is in subgraph:yes
// Vertex 3 is in subgraph:yes
// Vertex 4 is in subgraph:no
// Vertex 5 is in subgraph:no
// Hyperarc 0 is in subgraph: no
// Hyperarc 1 is in subgraph: yes
// Hyperarc 2 is in subgraph: yes
return 0;
}
The library can be used in a similar way for undirected hypergraphs:
#include "path_to_hglib/hglib.h"
int main( int argc, const char* argv[] ) {
hglib::UndirectedHypergraph<hglib::UndirectedVertex, hglib::NamedUndirectedHyperedge> uhg;
// Add vertices
uhg.addVertex("A");
uhg.addVertex("B");
uhg.addVertex("Foo");
uhg.addVertex("Bar");
uhg.addVertex("");
uhg.addVertex("6");
// add named undirected hyperedges
uhg.addHyperedge(hglib::NAME, {"A", "Foo"}, "hyperedge1");
uhg.addHyperedge(hglib::NAME, {"A", "B", "Bar", ""}, "hyperedge2");
uhg.addHyperedge(hglib::NAME, {"6", ""}, "hyperedge3");
// Iterate over vertices
for (const auto& vertex : uhg.vertices()) {
std::cout << "Vertex: " << vertex->name() << '\n';
// Iterate over implied hyperedges
auto it = uhg.hyperedgesBegin(vertex->id());
auto end = uhg.hyperedgesEnd(vertex->id());
for (; it != end; ++it) {
std::cout << "Is contained in hyperedge: " << (*it)->name() << '\n';
}
// with range based for loop
auto impliedHyperedgesPtr = uhg.hyperedges(vertex->id());
for (const auto& edge : *impliedHyperedgesPtr) {
std::cout << "Is contained in hyperedge: " << edge->name() << '\n';
}
}
// Iterate over hyperedges
for (const auto& hyperedge : uhg.hyperedges()) {
std::cout << "Hyperedge: " << hyperedge->name() << '\n';
// Iterate over implied vertices
auto it = uhg.impliedVerticesBegin(hyperedge->id());
auto end = uhg.impliedVerticesEnd(hyperedge->id());
for (; it != end; ++it) {
std::cout << "Contains vertex: " << (*it)->name() << '\n';
}
// with range based for loop
auto impliedVerticesPtr = uhg.impliedVertices(hyperedge->id());
for (const auto& vertex : *impliedVerticesPtr) {
std::cout << "Contains vertex: " << vertex->name() << '\n';
}
}
return 0;
}
1.8.14