Graphs 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. Not all edges are actually used; use dip::Graph::Edge::IsValid to test this.

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. more...

Classes

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

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. Not all edges connect vertices, use dip::Graph::Edge::IsValid to test.
auto EdgeVertex(dip::Graph::EdgeIndex edge, bool which) const -> dip::Graph::VertexIndex
Gets the index to one of the two vertices that are joined by an edge. which is 0 or 1 to specify which of the two vertices to return.
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 IsValidEdge(dip::Graph::EdgeIndex edge) const -> bool
Returns true if the edge is a valid edge.
auto EdgeIndices(dip::Graph::VertexIndex vertex) const -> dip::Graph::EdgeList const&
Get the indices to the edges that join vertex vertex.
auto VertexValue(dip::Graph::VertexIndex vertex) const -> dip::dfloat&
Returns a reference to the value of the vertex vertex. This value is mutable even if the graph is const.
auto AddVertex(dip::uint nEdges = 0, dip::dfloat weight = 0.0) -> dip::Graph::VertexIndex
Adds a vertex to the graph with the given weight and space reserved for the given number of edges. Returns the index to the new vertex.
void AddEdge(dip::Graph::VertexIndex vertex1, dip::Graph::VertexIndex vertex2, dip::dfloat weight)
Add an edge between vertices vertex1 and vertex2, with weight weight. If the edge already exists, update the weight of the edge to be weight.
void AddEdgeSumWeight(dip::Graph::VertexIndex vertex1, dip::Graph::VertexIndex vertex2, dip::dfloat weight)
Add an edge between vertices vertex1 and vertex2, 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 vertex1, dip::Graph::VertexIndex vertex2)
Delete the edge between vertices vertex1 and vertex2.
void DeleteEdge(dip::Graph::EdgeIndex edge)
Delete the edge edge.
auto Neighbors(dip::Graph::VertexIndex vertex) -> std::vector<VertexIndex>
Returns a list of indices to neighboring vertices. The list is created. EdgeIndices is a more efficient, but less convenient, function.
template<typename F>
void UpdateEdgeWeights(F func) const
Re-computes edge weights using the function func, called as dfloat func(dfloat val1, dfloat val2), where the two inputs to func are the value of the two vertices.
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. See dip::MinimumSpanningForest for details. Does not modify `this.
void RemoveLargestEdges(dip::uint number)
Removes number edges with the largest weights from the graph. more...

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[0] < vertices[1].

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.

Each pixel becomes a vertex in the graph, the vertex’s index is equal to the linear index (see On pixel coordinates, indices, offsets and data pointers) of the pixel in the image (that is, vertices are stored in the same order as the pixels in the image with normal strides). Vertex values are set to the corresponding pixel value.

An edge will connect each pixel to each of its neighbors.

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).

The value of weights is: - "difference" (default): the edge weights are given by the absolute difference between the two pixel values. - "average": the edge weights are given by the average of the two pixel values. - "zero": the edge weights are all set to 0, use dip::Graph::UpdateEdgeWeights to compute weights in some other way, or manually set the weights.

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.