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.
1  n = graph.num_vertices()

1  auto 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:
1 2 3 4 5 6 7 8 9  import higra as hg
g = hg.UndirectedGraph()
g.add_vertex()
g.add_vertex()
g.add_vertices(3)
nv = g.num_vertices() # 5

1 2 3 4 5 6 7 8 9 10  #include "higra/graph.hpp"
using namespace hg;
ugraph g;
add_vertex(g);
add_vertex(g);
add_vertices(3, g);
auto 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 

1 2 3 4 5 6 7 8  g = hg.UndirectedGraph()
...
for v in g.vertices():
... # all vertices of g
for v in g.adjacent_vertices(1):
... # all vertices adjacent to vertex 1 in g

1 2 3 4 5 6 7 8 9 10  ugraph g;
...
for(auto v: vertex_iterator(g)){
... // all vertices of g
}
for(auto v: adjacent_vertex_iterator(1, g)){
... // all vertices adjacent to vertex 1 in g
}

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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  import higra as hg
# create a graph with 4 vertices and no edge
g = hg.UndirectedGraph(4)
# add an edge, between vertex 0 and 1
g.add_edge(0, 1)
# add an edge, between vertex 0 and 1
e = g.add_edge(1, 2)
s = g.source(e) # 1 or equivalently e[0]
t = g.target(e) # 2 or equivalently e[1]
ei = g.index(e) # 1 or equivalently e[2]
# add the two edges (3, 0) and (3, 1)
g.add_edges((3, 3), (0, 1));
ne = g.num_edges() # 4
sources, targets = g.edge_list() # sources = [0, 1, 0, 1], targets = [1, 2, 3, 3]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21  #include "higra/graph.hpp"
using namespace hg;
// create a graph with 4 vertices and no edge
ugraph g(4);
// add an edge, between vertex 0 and 1
add_edge(0, 1, g);
// add an edge, between vertex 0 and 1
auto e = add_edge(1, 2, g);
auto s = source(e, g); // 1
auto t = target(e, g); // 2
auto ei = index(e, g); // 1
// add the two edges (3, 0) and (3, 1)
add_edges({3, 3}, {0, 1}, g);
auto ne = num_edges(g); // 4
auto 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 

1 2 3 4 5 6 7 8 9 10 11  g = hg.UndirectedGraph()
...
for e in g.edges():
print(g.source(e), g.target(e))
for e in g.in_edges(1):
... # all edges e such that g.target(e) == 1
for e in g.out_edges(1):
... # all edges e such that g.source(e) == 1

1 2 3 4 5 6 7 8 9 10 11 12 13 14  ugraph g;
...
for(auto e: edge_iterator(g)){
std::cout << source(e, g) << " " << target(e, g) << std::endl;
}
for(auto e: in_edge_iterator(1, g)){
... // all edges e such that target(e, g) == 1
}
for(auto e: out_edge_iterator(1, g)){
... // all edges e such that source(e, g) == 1
}

Degrees¶
Currently, all the graphs are undirected, meaning that the degree, the outdegree and the indegree 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 

1 2 3 4 5 6 7 8 9 10 11  g = hg.UndirectedGraph()
...
# degree of vertex 1
d1 = g.degree(1)
# in degree of vertex 2
d2 = g.in_degree(2)
# out degree of vertex 3
d3 = g.out_degree(3)

1 2 3 4 5 6 7 8 9 10 11  ugraph g;
...
// degree of vertex 1
auto d1 = degree(1, g);
// in degree of vertex 2
auto d2 = in_degree(2, g);
// out degree of vertex 3
auto 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.
1 2 3 4 5  def sum_adjacent_vertices_weights(graph, vertex_weights, vertex):
result = 0
for v in g.adjacent_vertices(vertex);
result += vertex_weights[v]
return result

1 2 3 4 5 6 7 8 9 10  // compute the sum of vertex weights adjacent to given vertex
auto sum_adjacent_vertices_weights(const ugraph &g,
const array_1d<double> &vertex_weights,
index_t vertex){
double result = 0;
for(auto v: adjacent_vertex_iterator(vertex, g)){
result += vertex_weights[v];
}
return result
}
