Graphs
Important
#include "higra/graph.hpp
Graphs come in three flavours in Higra:
ugraph
represents general undirected graphs (adjacency list).tree
represents undirected connected acyclic rooted graphs (parent array).regular_graph
represents implicit graphs: in such graphs edges are computed on the fly (not stored). For example, they can be used to represent pixel adjacencies in images.
This page presents common functions for the manipulation of graphs.
A dedicated page for the tree
structure, see Trees.
All functions acting on graphs have the same name in C++ and in Python, except for iterators to avoid name collisions with the Boost Graph Library (BGL).
In c++, graph related methods are free functions (as in BGL), while in Python they are member functions.
For example, the function num_vertices
that returns the number of vertices in a graph, will be called:
Important
In c++, one must call the function compute_children
on a tree before using it as a graph.
1n = graph.num_vertices()
1auto n = num_vertices(graph);
Vertices
Graph vertices are represented by positive integers (index_t
in c++), suitable for array indexing.
Note that the constructor of the ugraph class accepts a single parameter: the initial number of vertices in the graph.
Function |
Returns |
Description |
Available |
---|---|---|---|
|
new vertex |
add a new vertex to the graph |
|
|
void |
add a given number of new vertices to the graph |
|
|
positive integer |
Number of vertices in the graph |
|
Example:
1import higra as hg
2
3g = hg.UndirectedGraph()
4g.add_vertex()
5g.add_vertex()
6
7g.add_vertices(3)
8
9nv = g.num_vertices() # 5
1#include "higra/graph.hpp"
2using namespace hg;
3
4ugraph g;
5add_vertex(g);
6add_vertex(g);
7
8add_vertices(3, g);
9
10auto nv = num_vertices(g); // 5
Iterating on vertices
Function |
Returns |
Description |
Available |
---|---|---|---|
|
a range of iterators |
iterator on all graph vertices |
|
|
a range of iterators |
iterator on all vertices adjacent to the given vertex |
|
1g = hg.UndirectedGraph()
2...
3
4for v in g.vertices():
5 ... # all vertices of g
6
7for v in g.adjacent_vertices(1):
8 ... # all vertices adjacent to vertex 1 in g
1ugraph g;
2...
3
4for(auto v: vertex_iterator(g)){
5 ... // all vertices of g
6}
7
8for(auto v: adjacent_vertex_iterator(1, g)){
9 ... // all vertices adjacent to vertex 1 in g
10}
Edges
Graph edges are composed of a source vertex, a target vertex, and, optionally, an index.
Graphs which have indexed edges provide the following guaranties:
edge indices of a graph
g
are integers (typeindex_t
) comprised between 0 (included) andnum_edges(g)
(excluded);the index of a given edge will never change during the object lifetime.
However, note that in an undirected graph, the edges (x, y)
and (y, x)
have the same index.
All operations are done in constant time.
Function |
Returns |
Description |
Available |
---|---|---|---|
|
void |
add a new edge to the graph |
|
|
void |
add all edges given as a pair of arrays (sources, targets) to the graph |
|
|
positive integer |
number of edges in the graph |
|
|
vertex index |
source vertex of an edge |
|
|
vertex index |
target vertex of an edge |
|
|
edge index |
the index of the given edge in the current graph |
|
|
edge |
the edge with given index (in an undirected graph, always returns the edge whose source vertex is smaller than the target vertex) |
|
|
a pair of arrays (sources, targets) defining all the edges of the graph |
void |
|
Note that python’s edges are simply tuples whose first value is the source vertex, second value is the target vertex, and third (optional) value is the index.
Example:
1import higra as hg
2
3# create a graph with 4 vertices and no edge
4g = hg.UndirectedGraph(4)
5
6# add an edge, between vertex 0 and 1
7g.add_edge(0, 1)
8# add an edge, between vertex 0 and 1
9e = g.add_edge(1, 2)
10
11s = g.source(e) # 1 or equivalently e[0]
12t = g.target(e) # 2 or equivalently e[1]
13ei = g.index(e) # 1 or equivalently e[2]
14
15# add the two edges (3, 0) and (3, 1)
16g.add_edges((3, 3), (0, 1));
17
18ne = g.num_edges() # 4
19
20sources, targets = g.edge_list() # sources = [0, 1, 0, 1], targets = [1, 2, 3, 3]
1#include "higra/graph.hpp"
2using namespace hg;
3
4// create a graph with 4 vertices and no edge
5ugraph g(4);
6
7// add an edge, between vertex 0 and 1
8add_edge(0, 1, g);
9// add an edge, between vertex 0 and 1
10auto e = add_edge(1, 2, g);
11
12auto s = source(e, g); // 1
13auto t = target(e, g); // 2
14auto ei = index(e, g); // 1
15
16// add the two edges (3, 0) and (3, 1)
17add_edges({3, 3}, {0, 1}, g);
18
19auto ne = num_edges(g); // 4
20
21auto edges = edge_list(g); // edges.first = {0, 1, 0, 1}, edges.second = {1, 2, 3, 3}
Iterating on edges
Function |
Returns |
Description |
Available |
---|---|---|---|
|
a range of iterators |
iterator on graph edges |
|
|
a range of iterators |
iterators on all edges whose target is the given vertex |
|
|
a range of iterators |
iterators on all edges whose source is the given vertex |
|
1g = hg.UndirectedGraph()
2...
3
4for e in g.edges():
5 print(g.source(e), g.target(e))
6
7for e in g.in_edges(1):
8 ... # all edges e such that g.target(e) == 1
9
10for e in g.out_edges(1):
11 ... # all edges e such that g.source(e) == 1
1ugraph g;
2...
3
4for(auto e: edge_iterator(g)){
5 std::cout << source(e, g) << " " << target(e, g) << std::endl;
6}
7
8for(auto e: in_edge_iterator(1, g)){
9 ... // all edges e such that target(e, g) == 1
10}
11
12for(auto e: out_edge_iterator(1, g)){
13 ... // all edges e such that source(e, g) == 1
14}
Degrees
Currently, all the graphs are undirected, meaning that the degree, the out-degree and the in-degree of a vertex are all equal.
Operations are done in constant time in ugraph
, tree
. Operations are done in time proportional to \(|E|/|V|\) in regular_graph
.
Function |
Returns |
Description |
Available |
---|---|---|---|
|
a positive integer |
number of edges containing the given vertex as either the source or the target |
|
|
a positive integer |
number of edges containing the given vertex as the target |
|
|
a positive integer |
number of edges containing the given vertex as either the source or the target |
|
1g = hg.UndirectedGraph()
2...
3
4# degree of vertex 1
5d1 = g.degree(1)
6
7# in degree of vertex 2
8d2 = g.in_degree(2)
9
10# out degree of vertex 3
11d3 = g.out_degree(3)
1ugraph g;
2...
3
4// degree of vertex 1
5auto d1 = degree(1, g);
6
7// in degree of vertex 2
8auto d2 = in_degree(2, g);
9
10// out degree of vertex 3
11auto d3 = out_degree(3, g);
Weighted graph
Higra enforces a strong separation between graphs and weights (on vertices or edges): a graph never stores weights.
Vertex indices and edge indices (except for regular_graph
) enables to have an immediate mapping between vertices
or edges and values stored in an array. The preferred storage for weights are xtensor
containers in c++ and numpy
arrays in python.
1def sum_adjacent_vertices_weights(graph, vertex_weights, vertex):
2 result = 0
3 for v in g.adjacent_vertices(vertex);
4 result += vertex_weights[v]
5 return result
1// compute the sum of vertex weights adjacent to given vertex
2auto sum_adjacent_vertices_weights(const ugraph &g,
3 const array_1d<double> &vertex_weights,
4 index_t vertex){
5 double result = 0;
6 for(auto v: adjacent_vertex_iterator(vertex, g)){
7 result += vertex_weights[v];
8 }
9 return result
10}