Graphs#
Utopia makes use of the Boost Graph Library as well as some custom methods to implement graph-related features. The following will help you create and use graphs in your model.
Creating Graph Objects#
Utopia provides the create_graph functionality to easily construct a graph. Assuming we are inside a Utopia model class, such that we have access to a model configuration (this->_cfg) and a random number generator (*this->_rng), here is an example of how you could construct an undirected graph:
#include <utopia/core/graph.hh>
// ...
/// The vertex container type
using VertexContainer = boost::vecS;
/// The edge container type
using EdgeContainer = boost::vecS;
/// The graph type (here: undirected)
using Graph = boost::adjacency_list<
EdgeContainer,
VertexContainer,
boost::undirectedS>;
// ..
/// Inside the model class: initialize its graph member
Graph g = create_graph<Graph>(this->_cfg["my_graph"], *this->_rng);
Here cfg["my_graph"] points to the relevant configuration entry from the model configuration file. It could look like this:
my_graph:
# graph model
model: ErdosRenyi # (a random graph)
num_vertices: 200
mean_degree: 4
ErdosRenyi:
parallel: False
self_edges: False
The Model key tells Utopia which graph generation algorithm you wish to use, for which there are several currently available options. Each model key requires its own parameters for the graph generation algorithm – see below for more details.
Note
Depending on your needs, you will need to use either boost::undirectedS or boost::directedS/boost::bidirectionalS in the adjacency matrix of your graph.
Hint
Boost allows you to use different container types for vertices and edges, e.g. boost::vecS or boost::listS, each optimised for different purposes. See the boost graph documentation entry for more details.
Graph generation algorithms in Utopia#
Utopia contains a selection of graph creation algorithms. The
Utopia::Graph::create_graph() function lets you easily switch between
different graph creation models.
Regular graphs#
Utopia provides a regular graph generator to create \(k\)-regular graphs (meaning each vertex has \(k\) neighbors).
Vertices are located on a circle and connected to their nearest neighbors until the desired degree is reached.
Depending on the graph type, there are the following requirements:
For undirected graphs, the degree must be even, as neighbors are connected symmetrically.
For directed regular graphs, you can choose between an oriented and an unoriented regular graph.
In the oriented case, each vertex is connected to its upper \(k\) neighbors, meaning vertex \(i\) is connected to vertices \(i+1, i+2, ..., i+k\).
In the unoriented case, a vertex is connected to its \(k/2\) upper and \(k/2\) lower neighbors, i.e. \(i\) is connected to \(i+1, ..., i+k/2\) and \(i-1, ..., i-k/2\).
If the graph is unoriented, the mean degree must therefore also be even.
Warning
For undirected graphs and directed graphs with oriented: false, the mean_degree must be even. See below for an example configuration.
Hint
Special case: simple cycle graph: You can generate a simple cycle of length \(N\) by using a directed graph type, setting num_vertices: N, mean_degree: 1 and oriented: true.
Complete graphs#
Using the complete graph generator, you can generate a complete (fully-connected) graph. If the underlying graph type is directed, this means that all possible in- and out-edges are added.
Erdős-Rényi random graphs#
The random model creates a random graph using the Erdös-Rényi model, in which all links have an equal probability of occuring. If you set the parallel key to false, no multi-edges are added. Utopia uses the boost::generate_random_graph algorithm.
Small-world Watts-Strogatz graphs#
The WattsStrogatz model creates a small-world network, and is controlled via a rewiring probability p_rewire. The algorithm begins with a regular graph, and then rewires random edges with probability p_rewire, thereby reducing the average path length.
As with the regular graph, a choice must be made regarding the type of underlying regular graph in the directed case (see above).
To this end, the algorithm requires the oriented argument.
Note
No parallel edges or self-loops are created.
This implementation does not use the boost::SWGen, but a custom implementation which is more controllable than the BGL algorithm.
Klemm-Eguíluz graphs#
The Klemm-Eguíluz algorithm produces a highly clustered, small-world, scale-free network. The network is generated by adding new edges to a group of ‘active’ nodes, and activating/deactivating nodes with a probability proportional to their degree. The parameter mu is a probability, and controls whether new edges are added to one of the active nodes (more likely for lower mu), or to a non-active node chosen with a probability proportional to its degree. For mu=1, we obtain a Barabási-Albert scale-free graph. As mu increases, the degree distribution becomes more scale-free, and the average path length drops. The clustering, on the other hand, is higher for low mu. Multi-edges and self-loops are not created.
Note
For directed graphs, selection of random nodes occurs on the basis of their absolute degree, that is \(\text{degree} := \text{in-degree} + \text{out-degree}\). Deactivation, however, occurs on the basis only of the in-degree.
Warning
The Klemm-Eguíluz produces graphs with a mean degree that will deviate by a small amount (less than 1) from the mean_degree specified in the config. When generating the network, the core logger will inform about the actual mean degree of the network. If you are not seeing such a log message, you may have to adjust the corresponding log level (see utopya_base_cfg for appropriate keys).
Scale-free graphs#
Scale-free graphs are graphs with a power-law degree distribution. Utopia provides the BarabasiAlbert and BollobasRiordan algorithms to generate such networks. Both algorithms use the preferential attachment model. The BarabasiAlbert is particularly suited for undirected networks, whereas the Bollobás-Riordan algorithm only works for directed graphs, and does not produce parallel edges or self-loops. The Barabási-Albert model allows controlling whether or not parallel edges are created, using the parallel key. If parallel: true, the graph type must be undirected. For parallel: false, a Klemm-Eguíluz network is returned with mu=1 (see above).
Load your own custom graph#
Utopia allows you to load your own graph from a file; see below for more.
Graph configuration#
Let’s assume that we have defined a graph type as done in the previous section.
Let’s again further assume that we are inside a Utopia model class, such that we
have access to a model configuration (this->_cfg) and a random number
generator (*this->_rng). (Of course, you would need to adapt these two
options if you use the function in another situation.)
In this case, we can just write:
Graph g = create_graph<Graph>(
this->_cfg["my_graph"], // Your model configuration file
// requires a "my_graph"
// entry.
*this->_rng
);
This function is configured through a configuration node. The corresponding YAML file looks like this:
create_graph:
# The model to use for generating the graph. Valid options are:
# "regular", "complete", "ErdosRenyi", "WattsStrogatz", "KlemmEguiluz",
# "BarabasiAlbert" (if parallel=true: undirected only),
# "BollobasRiordan" (directed only), or "load_from_file"
model: "ErdosRenyi"
# The number of vertices
num_vertices: 1000
# The mean degree (equals degree in regular model;
# not relevant in BollobasRiordan model)
mean_degree: 4
# Model-specific parameters
regular:
# Whether or not the graph is oriented (relevant to directed only)
oriented: false
ErdosRenyi:
# Allow parallel edges
parallel: false
# Allow self edges
self_edges: false
WattsStrogatz:
# Rewiring probability
p_rewire: 0.2
# Whether or not the underlying lattice is oriented (relevant to directed only)
oriented: false
KlemmEguiluz:
# Probability of connecting to an active rather than a non-active node
mu: 0.5
BarabasiAlbert:
# Allow parallel edges
parallel: false
BollobasRiordan:
# Graph generating parameters
alpha: 0.2
beta: 0.8
gamma: 0.
del_in: 0.
del_out: 0.5
load_from_file:
base_dir: "~/Utopia/network-files"
filename: "my_airlines_network.xml"
format:"graphml" # or "graphviz"/"dot" (the same)
This of course is the fully documented configuration. You only need to specify configuration options if the creation algorithm you set requires them, otherwise they will be just ignored.
Attaching custom objects to graph vertices and edges#
Oftentimes it is desirable to attach custom objects to vertices and edges of your graph (or, more precisely: the boost::adjacency_list), e.g. to store a custom vertex state. In the following example, the structs Vertex and Edge are applied to an adjacency_list. If you access e.g. a vertex with a vertex_descriptor vd such as g[vd], an object of type Vertex is returned, which holds the properties id and state. Introducing properties like this provides an easy way to set up and access internal properties. For further information, see the bundled property documentation .
/// The vertex struct
struct Vertex {
std::size_t id;
int state;
};
/// The edge struct
struct Edge {
double weight;
};
/// The containter types
using EdgeCont = boost::vecS;
using VertexCont = boost::vecS;
/// The graph type
using Graph = boost::adjacency_list<EdgeCont,
VertexCont,
boost::undirectedS,
Vertex,
Edge>;
// Construct a graph
Graph g;
If you want to use Utopia’s full graph functionality, we strongly recommend that you define your graph as described in the section on applying rules on graph entities.
Warning
When constructing the adjacency_list, take care that the order of the
template arguments specifying the vertex/edge container type and their
struct is correct! For the container types, you first need to specify the
edge container type and then the vertex container type, whereas for the structs you first need to specify the vertex struct and then the edge struct.
If you’re wondering why this is — we are, too!
Apply Rule Interface#
Utopia provides an interface to easily apply a rule to entities of
a graph. The user just needs to define a lambda function that takes one
graph entity descriptor as input and call the apply_rule function.
This is best described through examples:
// -- Simple Examples -----------------------------------------------------
// NOTE: The full possibilities are described in the detailed example below
// Sequentially iterate over all vertices (without shuffling) and set the
// vertices' v_prop to 42.
apply_rule<IterateOver::vertices, Update::async, Shuffle::off>(
[](const auto vertex_desc, auto& g){
auto& state = g[vertex_desc].state;
state.v_prop = 42;
},
g
);
// Set all neighbors' v_prop synchronously to the sum of all their
// neighbors' v_prop accumulated to the former v_prop.
apply_rule<IterateOver::neighbors, Update::sync>(
[](const auto neighbor_desc, auto& g){
auto state = g[neighbor_desc].state;
for (const auto next_neighbor
: range<IterateOver::neighbors>(neighbor_desc, g))
{
state.v_prop += g[next_neighbor].state.v_prop;
}
return state;
},
boost::vertex(0, g), // Neighbors of vertex '0'
g
);
// -- Example with detailed explanation -----------------------------------
apply_rule< // Apply a rule to graph entities
IterateOver::vertices, // Choose the entities that the rule
// should be applied to. Here: vertices.
// All available options are:
// * IterateOver::vertices
// * IterateOver::edges
//
// * IterateOver::neighbors
// * IterateOver::inv_neighbors (inverse)
// * IterateOver::out_edges
// * IterateOver::in_edges
//
// The last options require the
// parent_vertex that works as a reference.
Update::async, // Apply the rule asynchronously, i.e.
// sequentially.
// With Update::sync, the state change is
// first buffered and applied to all
// entities at once.
Shuffle::off // Whether to randomize the order. This
// argument is only available for the
// Update::async mode. For Shuffle::on, it
// requires to pass an RNG to apply_rule.
>(
[]
(const auto vertex_desc, // In this example, iteration happens
// over vertices; thus, the first argument
// is the vertex descriptor.
// The vertex descriptor is normally just a
// literal type, so copying is actually
// faster than taking it by const reference
// NOTE: The cell- or agent-based
// apply_rule expect the state as a const
// reference.
auto& g) // The rule function expects the graph
// as second argument.
// NOTE: It's IMPORTANT to pass this as
// (non-const) reference, otherwise the
// whole graph is copied!
{
// Get the state (by reference)
auto& state = g[vertex_desc].state;
// WARNING: If Update::sync was selected, you should work on a COPY
// of the state. To achieve that, leave away the '&' and
// return the state at the end of the rule function.
// Set a vertex property
state.v_prop = 42;
// ... can do more stuff here ...
// For Update::sync, return the state. Optional for Update::async.
// return state;
},
// boost::vertex(0, g), // This is the parent_vertex argument.
// The parent vertex that needs to be
// given when IterateOver requires a
// reference vertex.
// As an example, vertex 0 is given here.
g // Specify the graph that contains the
// objects to iterate over.
// It is passed as the second argument to
// the rule function.
// rng // For Update::async and when you would
// like to shuffle the order of the rule
// application, pass the random number
// generator as last argument here.
// In such a scenario, the Shuffle template
// argument is optional.
);
Note
You can find the whole working and tested example, including all the references,
in the file utopia/test/core/apply_rule_graph_doc_test.cc.
Prerequisits on Graph, Vertex, and Edge Type#
Note that this functionality can only be used if the vertices and edges of the graph are derived from a Utopia::Entity. Your definition of the graph needs to look like this:
// -- Vertex --------------------------------------------------------------
/// The vertex state
struct VertexState {
/// A vertex property
unsigned v_prop = 0;
// Add your vertex parameters here.
// ...
};
/// The traits of a vertex are just the traits of a graph entity
using VertexTraits = Utopia::GraphEntityTraits<VertexState>;
/// A vertex is a graph entity with vertex traits
using Vertex = GraphEntity<VertexTraits>;
// -- Edge ----------------------------------------------------------------
/// The edge state
struct EdgeState {
/// An edge property
unsigned e_prop = 0;
// Add your edge parameters here.
// ...
};
/// The traits of an edge are just the traits of a graph entity
using EdgeTraits = Utopia::GraphEntityTraits<EdgeState>;
/// An edge is a graph entity with edge traits
using Edge = GraphEntity<EdgeTraits>;
// -- Graph ---------------------------------------------------------------
/// Declare a graph type with the formerly defined Vertex and Edge types
using Graph = boost::adjacency_list<
boost::vecS, // edge container
boost::vecS, // vertex container
boost::undirectedS,
Vertex,
Edge>;
This graph structure is similar to, though slighly more sophisticated than, the one described above in the section on Graph Creation. In this graph definition, the vertex and edge property access works as follows:
// Get the vertex property v_prop
g[vertex].state.v_prop;
// Get the edge property e_prop
g[edge].state.e_prop;
Modifying the graph structure while looping over a graph entity#
When looping over a graph and simultaneously modifying its structure, you need to be really careful, because the iterators you use to loop over the graph can easily be invalidated. Have a look at the boost graph documentation for further information.
As a rule of thumb: If you want to change the graph structure …
use
boost::listSas the appropriate list and edge containers anddo not use the
apply_rulefunctions because they can easily result in buggy behavior.
Saving Graph Data#
Utopia provides an interface to save boost::adjacency_list s or custom properties attached to it. In a first step, it is highly recommended to set up a separate HDFGroup for the graph data using the create_graph_group function. It automatically adds some metadata as group attributes that allows to conveniently load the data as a GraphGroup on the frontent side.
Saving a static graph#
If you want to save only the topology of a graph, you can use the save_graph functionality to write the vertices and edges to HDF5:
using Utopia::DataIO::create_graph_group;
using Utopia::DataIO::save_graph;
// Open a graph group and save the graph
const auto ggrp = create_graph_group(g, grp, "graph_grp");
save_graph(g, ggrp);
// This will result in the following data structure
// (assuming the graph has 10 vertices and 20 edges):
//
// └┬ graph_grp
// └┬ _vertices < ... shape(10,)
// └ _edges < ... shape(2, 20)
Hint
The save_graph function as used in the example above uses boost::vertex_index_t to retreive the vertex indices. However, custom vertex ids can be used by additionaly passing a PropertyMap of vertex ids. This would be needed, for example, when using a boost::listS VertexContainer.
Note
If using a VertexContainer (EdgeContainer) type that does not provide a fixed internal ordering and if additionaly saving vertex (edge) properties, then the vertices and edges should be stored alongside the latter dynamically. For more details see below
Saving vertex and edge properties dynamically#
With the save_vertex_properties and save_edge_properties functions Utopia provides an interface for dynamic saving of graph data accessible via the vertex descriptors and edge descriptors, respectively.
When should you use this interface?
* Not all VertexContainer and EdgeContainer types provide a fixed internal ordering. For example boost::vecS does, whereas boost::listS does not. In case a fixed ordering is not given: If you want to save multiple properties or if you want to save property data alongside the graph topology, all of that data should be written using this dynamic interface. Correct alignment of the data is guaranteed since all data is written in a single loop over the graph.
* If in your model the number of vertices and edges changes over time it is difficult to initialize appropriate datasets as the size is not known. Thus, for dynamic graphs the dynamic interface should be used which circumvents this problem by creating a new dataset for each time step.
Let’s look at an example: Let’s assume we have a graph where each vertex holds a some_prop property and we want to save the graph topology and property data. For that we need to provide tuples of tuples, each of the latter containing a property name and the respective adaptor. The adaptor is a lambda function returning the property data given a vertex or edge descriptor and a reference to the graph. In order to write 2D data (here: for the edge data), multiple such adaptors must be passed (one for each coordinate) as well as the name of the second dimension.
const auto vertex_adaptors = std::make_tuple(
// 1D case: Pass a (name, adaptor) tuple
std::make_tuple("_vertices",
[](auto vd, auto& g){
return boost::get(boost::vertex_index_t(), g, vd);
}
),
std::make_tuple("some_prop",
[](auto vd, auto& g){ return g[vd].state.some_prop; }
)
);
const auto edge_adaptors = std::make_tuple(
// 2D case: Pass a (name, dim0_name,
// (coord1, adaptor1),
// (coord2, adaptor2), ...) tuple
std::make_tuple("_edges", "label",
std::make_tuple("source",
[](auto ed, auto& g){
return boost::get(
boost::vertex_index_t(), g, boost::source(ed, g)
);
}
),
std::make_tuple("target",
[](auto ed, auto& g){
return boost::get(
boost::vertex_index_t(), g, boost::target(ed, g)
);
}
)
)
);
Note that while here we simply extract the properties from the vertices (edges), in general the adaptors can contain any calculation on vd (ed).
These tuples can then be passed to the functions save_vertex_properties and save_edge_properties together with an adjacency_list, a parent HDFGroup, and a label. The label will be used to distinguish the saved data and should be unique.
For example, if you write a graph at every time step the label should encode the time at which the graph was written.
using Utopia::DataIO::create_graph_group;
using Utopia::DataIO::save_vertex_properties;
using Utopia::DataIO::save_edge_properties;
const auto ggrp = create_graph_group(g, grp, "graph_grp");
// Common usage within a Utopia model: Replace "0" by
// std::to_string(this->get_time()) to set the current time as dset name.
save_vertex_properties(g, ggrp, "0", vertex_adaptors);
save_edge_properties(g, ggrp, "0", edge_adaptors);
// ... the first model update step, assuming one vertex and one edge
// are added to the graph ...
// Write the data for the next time step
save_vertex_properties(g, ggrp, "1", vertex_adaptors);
save_edge_properties(g, ggrp, "1", edge_adaptors);
// This would result in the following data structure
// (assuming the graph initially has 10 vertices and 20 edges):
//
// └┬ graph_grp
// └┬ _vertices
// ┬─ 0 < ... shape(10,)
// └─ 1 < ... shape(11,)
// ├ some_prop
// ┬─ 0 < ... shape(10,)
// └─ 1 < ... shape(11,)
// ├ _edges
// ┬─ 0 < ... shape(2, 20)
// └─ 1 < ... shape(2, 21)
Note
In order to guarantee correct alignment of the data, which is needed if you want to be able to associate properties with one another, the save_vertex_properties and save_edge_properties functions must only be called once per model update step.
Loading a Graph from a File#
Using real-world networks as a basis for the graph#
Using the create_graph config interface you can access the graph loading mechanism and do your simulations on airline networks, social networks, and anything that you are able to find out there. The usage is as simple as the following example:
create_graph:
model: "load_from_file"
load_from_file:
base_dir: "~/Utopia/network-files"
filename: "my_airlines_network.xml"
format: "graphml" # or "graphviz"/"gv"/"dot"
Warning
The loader only supports loading to boost’s adjacency_list, not to an adjacency_matrix, as this is a bit more difficult.
A workaround could be to copy the graph via boosts copy graph functionality .
The data that you load may need some curation before it works, though. As we are only loading the graph’s topology, without node/edge/graph attributes, you might have to get rid of some data attributes, that can cause the loader to crash.
As far as we experienced it, attributes of the type vector_float or vector_string will cause the loader to break down. To avoid that, delete the declaration and every occurrence of the malicious attribute in your GraphML file. To make it illustrative, in the following GraphML file, you could use the regex ^ <data key="key2.*\n to do a find and replace (by nothing) to remove the entire lines of the problematic key2:
<?xml version="1.0" encoding="UTF-8"?>
<graphml>
<key id="key1" for="node" attr.name="user_name" attr.type="string" />
<key id="key2" for="node" attr.name="full_name" attr.type="vector_string" />
<graph id="G" edgedefault="undirected" parse.nodeids="canonical" parse.edgeids="canonical" parse.order="nodesfirst">
<node id="n1">
<data key="key1">pia</data>
<data key="key2">Iuto, Pia</data>
</node>
<node id="n2">
<data key="key1">tro</data>
<data key="key2">Dan, Tro</data>
</node>
...
</graph>
</graphml>
Note
If you encounter a format other than GraphML or Graphviz/DOT, be aware that there are a number of command line converters that might work right away: Try typing mm2gv, gxl2gv, or gml2gv, to convert from the MatrixMarket, GrapheXchangeLanguage, and the Graph Modeling Language, respectively. If that doesn’t help, check if the Gephi Graph Exploration software can maybe read the format, or otherwise pass it to python’s networkx possibly by writing your own script. Both Gephi and networkx should be able to export to one of the accepted formats.
Hint
One large database of real-world networks, that are available for download in the GraphML format, is Netzschleuder, another database, that uses the MatrixMarket .mtx format is Network Repository.
Loading edge weights (or some other property) into utopia#
If you want to load edge weights, or some other edge property which is stored in GraphViz via
digraph "Directed Weighted Test GraphViz Graph" {
1 -> 0 [weight=1, some_int=5];
0 -> 2 [weight=1.5, some_int=5];
1 -> 3 [weight=.5, some_int=4];
1 -> 3 [weight=2.5];
4;
}
or in GraphML via
...
<graphml>
<key id="key1" for="edge" attr.name="weight" attr.type="double" />
<key id="key2" for="node" attr.name="some_int" attr.type="int" />
<graph id="G" edgedefault="undirected">
<node id="n1"> </node>
<node id="n2"> </node>
<edge id="e0" source="n1" target="n0">
<data key="key1">2.</data>
<data key="key2">5</data>
</edge>
</graph>
</graphml>
then you need to pass a dynamic property map to the create graph algorithm. This can be done in two ways: either to boost’s built-in boost:edge_weight, or to a bundled property, for example a struct EdgeState:
#include <boost/property_map/dynamic_property_map.hpp>
#include <boost/graph/adjacency_list.hpp>
#include "utopia/core/graph.hh"
#include "utopia/data_io/graph_load.hh"
struct EdgeState {
double weight = 2.;
int some_int = 1;
};
using GraphType = boost::adjacency_list<
boost::vecS, // edge container
boost::vecS, // vertex container
boost::directedS,
boost::no_property, // no vertex properties
boost::property<boost::edge_weight_t,
double, EdgeState>
>;
GraphType g(0);
// Now you need to define dynamic property maps
boost::dynamic_properties pmaps(boost::ignore_other_properties);
// Like this, it would simply ignore all properties in the file.
// So now add a reference to the built-in or bundled weight as a source
// for the weight pmap. To load to the bundle's ``weight``, use:
pmaps.property("weight", boost::get(&EdgeState::weight, g));
// To load to boost's built_in ``edge_weight``, use:
// pmaps.property("weight", boost::get(boost::edge_weight, g));
// You can also, if you want, load more edge properties, like:
pmaps.property("some_int", boost::get(&EdgeState::some_int, g));
// Now load the graph, either via ``create_graph``, or ``load_graph``
g = Graph::create_graph<GraphType>(_cfg["create_graph"], *_rng, pmaps)
// g = GraphLoad::load_graph<GraphType>(_cfg_cg["load_from_file"], pmaps);
// where you need to pass the corresponding config nodes.
Now your graph should be loaded with the edge properties of your desire. If you find out how to read vertex properties, from the file, please let us know.
Note
Make sure you load undirected graphs into undirected boost graphs and directed ones into directed ones. Conversions can be made both on the side of the file, and on boost’s side, but for the reading process it must be coherent.
Note
Whenever you use more than just one vertex/edge property, or more than just the bundle, the properties need to be nested, as in boost::property<boost::edge_weight_t, double, EdgeState>. See the documentation page on bundled properties for more examples.
Warning
The loading into bundled edge properties does not work with the typical utopia graph entity specifications as yet, so using EdgeTraits = Utopia::GraphEntityTraits<EdgeState>; using Edge = GraphEntity<EdgeTraits>;, limits you to boost’s built-in properties, which are quite a few actually.