The library infrastructure module
#include "diplib/graph.h"
dip::Graph class

A non-directed, edge-weighted graph.

Contents

Vertices are identified by an index, these indices are expected to be consecutive. Each vertex contains a list of indices to edges, and has an optional value. Edges are represented by indices to two vertices, and a double precision floating-point weight. If the two vertex indices for an edge are the same, the edge is not valid; this situation arises when an edge is deleted.

If converting an image to a graph, each pixel is converted to a vertex. The pixel’s linear index (see On pixel coordinates, indices, offsets and data pointers) is the vertex index.

Constructors, destructors, assignment and conversion operators

Graph(dip::uint nVertices, dip::uint nEdges = 0) explicit
Construct a graph with nVertices vertices. Vertices are identified by their index, which is in the range [0,nVertices]. nEdges is the expected number of edges for each vertex, and is used to reserve space for them.
Graph(dip::Image const& image, dip::uint connectivity = 1, dip::String const& weights = "difference")
Construct a graph for the given image.

Classes

struct Vertex
A vertex in the graph
struct Edge
An edge in the graph

Aliases

using VertexIndex = dip::uint
Type for indices to vertices
using EdgeIndex = dip::uint
Type for indices to edges
using EdgeList = std::vector<EdgeIndex>
Type for list of edge indices

Functions

auto NumberOfVertices() const -> dip::uint
Returns the number of vertices in the graph.
auto NumberOfEdges() const -> dip::uint
Returns the number of edges in the graph, including invalid edges.
auto CountEdges() const -> dip::uint
Counts the number of valid edges in the graph.
auto Edges() const -> std::vector<Edge> const&
Gets the set of edges in the graph. The weights of the edges are mutable, they can be directly modified.
auto OtherVertex(dip::Graph::EdgeIndex edge, dip::Graph::VertexIndex vertex) const -> dip::Graph::VertexIndex
Finds the index to the vertex that is joined to the vertex with index vertex through the edge with index edge.
auto EdgeWeight(dip::Graph::EdgeIndex edge) const -> dip::dfloat&
Returns a reference to the weight of the edge with index edge. This value is mutable even if the graph is const.
auto EdgeIndices(dip::Graph::VertexIndex v) const -> dip::Graph::EdgeList const&
Get the indices to the edges that join vertex v.
auto VertexValue(dip::Graph::VertexIndex v) const -> dip::dfloat&
Returns a reference to the value of the vertex v. This value is mutable even if the graph is const.
void AddEdge(dip::Graph::VertexIndex v1, dip::Graph::VertexIndex v2, dip::dfloat weight)
Add an edge between vertices v1 and v2, with weight weight. If the edge already exists, update the weight of the edge to be weight.
void AddEdgeSumWeight(dip::Graph::VertexIndex v1, dip::Graph::VertexIndex v2, dip::dfloat weight)
Add an edge between vertices v1 and v2, with weight weight. If the edge already exists, update the weight of the edge by adding weight to the existing weight.
void DeleteEdge(dip::Graph::VertexIndex v1, dip::Graph::VertexIndex v2)
Delete the edge between vertices v1 and v2.
void DeleteEdge(dip::Graph::EdgeIndex edge)
Delete the edge edge.
auto Neighbors(dip::Graph::VertexIndex v) -> std::vector<VertexIndex>
Returns a list of indices to neighboring vertices. The list is created. EdgeIndices is a more efficient, but less convenient, function.
void UpdateEdgeWeights() const
Re-computes edge weights as the absolute difference between vertex values.
auto MinimumSpanningForest(std::vector<VertexIndex> const& roots = {}) const -> dip::Graph
Computes the minimum spanning forest (MSF) using Prim’s algorithm.
void RemoveLargestEdges(dip::uint number)
Removes number edges with the largest weights from the graph.

Class documentation

struct Edge

An edge in the graph

If both vertices are 0, the edge is not valid (never used or deleted). Otherwise, vertices[1] > vertices[0].

Variables
std::array<VertexIndex, 2> vertices The two vertices joined by this edge
mutable dip::dfloat weight The weight of this edge

Function documentation

Graph(dip::Image const& image, dip::uint connectivity = 1, dip::String const& weights = "difference")

Construct a graph for the given image.

connectivity indicates which pixels are considered neighbors. Currently, only a connectivity of 1 is allowed. This makes neighbors the pixels at a city-block distance of 1 (in 2D, there are 4 such neighbors, in 3D there are 6).

By default, the edge weights are given by the absolute difference between the two pixel values. If weights is "average", the edge weights are given by the average of the two pixel values.

Vertex values are set to the corresponding pixel value.

dip::Graph MinimumSpanningForest(std::vector<VertexIndex> const& roots = {}) const

Computes the minimum spanning forest (MSF) using Prim’s algorithm.

If roots is an empty set, the vertex with index 0 is used as the root, and the resulting graph will be a minimum spanning tree (MST). If multiple roots are given, each one will spawn a tree.

The output graph only contains edges reachable from the given roots. Any components not connected to the roots will not remain in the graph (the vertices will be copied over, but not connected).

void RemoveLargestEdges(dip::uint number)

Removes number edges with the largest weights from the graph.

If the graph is a minimum spanning tree, it will be converted to a minimum spanning forest with number + 1 trees. This is a segmentation of the tree into the number + 1 regions with smallest trees.