Graphs module
#include "diplib/graph.h"
dip::Graph class

A non-directed, edge-weighted graph.

Reference

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 Edge: An edge in the graph more...
struct Vertex: A vertex in the graph more...

Aliases

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

Functions

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.
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.
auto CountEdges() const -> dip::uint: Counts the number of valid edges in the graph.
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 EdgeIndices(dip::Graph::VertexIndex vertex) const -> dip::Graph::EdgeList const&: Get the indices to the edges that join vertex vertex.
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 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 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.
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.
auto NumberOfEdges() const -> dip::uint: Returns the number of edges in the graph, including invalid edges.
auto NumberOfVertices() const -> dip::uint: Returns the number of vertices in the graph.
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.
void RemoveLargestEdges(dip::uint number): Removes number edges with the largest weights from the graph. more...
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 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.

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

Alias documentation

using EdgeList = std::vector<EdgeIndex>

Type for list of edge indices

Function documentation

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.

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.

dip::uint NumberOfVertices( ) const

Returns the number of vertices in the graph.

dip::uint NumberOfEdges( ) const

Returns the number of edges in the graph, including invalid edges.

dip::uint CountEdges( ) const

Counts the number of valid edges in the graph.

std::vector<Edge> const& Edges( ) 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.

dip::Graph::VertexIndex EdgeVertex( dip::Graph::EdgeIndex edge, bool which) const

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.

dip::Graph::VertexIndex OtherVertex( dip::Graph::EdgeIndex edge, dip::Graph::VertexIndex vertex) const

Finds the index to the vertex that is joined to the vertex with index vertex through the edge with index edge.

dip::dfloat& EdgeWeight( dip::Graph::EdgeIndex edge) const

Returns a reference to the weight of the edge with index edge. This value is mutable even if the graph is const.

bool IsValidEdge( dip::Graph::EdgeIndex edge) const

Returns true if the edge is a valid edge.

dip::Graph::EdgeList const& EdgeIndices( dip::Graph::VertexIndex vertex) const

Get the indices to the edges that join vertex vertex.

dip::dfloat& VertexValue( dip::Graph::VertexIndex vertex) const

Returns a reference to the value of the vertex vertex. This value is mutable even if the graph is const.

dip::Graph::VertexIndex AddVertex( dip::uint nEdges = 0, dip::dfloat weight = 0.0)

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.

std::vector<VertexIndex> Neighbors( dip::Graph::VertexIndex vertex)

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.

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

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.

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.

Graphs module#include "diplib/graph.h" dip::Graph class

Contents