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

A 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 outgoing edges, and has an optional value.

Edges are represented by indices to two vertices (a source and a target), a double precision floating-point weight, and an index to the sibling edge (the one that connects the same vertices in the other direction). Not all edges are actually used; use dip::DirectedGraph::Edge::IsValid to test this.

Constructors, destructors, assignment and conversion operators

DirectedGraph(dip::uint nVertices, dip::uint nEdges = 0) explicit
Construct a directed 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.
DirectedGraph(dip::Image const& image, dip::uint connectivity = 1, dip::String const& weights = "difference", dip::String const& extraEdges = "none")
Construct a directed graph for the given image. more...
DirectedGraph(dip::Graph const& graph)
Constructs a directed graph from an undirected graph.

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::DirectedGraph::Edge::IsValid to test.
auto SourceVertex(dip::DirectedGraph::EdgeIndex edge) const -> dip::DirectedGraph::VertexIndex
Finds the index to the vertex that is the source (origin) of the given edge.
auto TargetVertex(dip::DirectedGraph::EdgeIndex edge) const -> dip::DirectedGraph::VertexIndex
Finds the index to the vertex that is the target (destination) of the given edge.
auto SiblingEdge(dip::DirectedGraph::EdgeIndex edge) const -> dip::DirectedGraph::EdgeIndex
Finds the index to the edge that is the sibling (connects the same vertices in the other direction) of the given edge. If it returns edge, there is no sibling.
auto EdgeWeight(dip::DirectedGraph::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::DirectedGraph::EdgeIndex edge) const -> bool
Returns true if the edge is a valid edge.
auto EdgeIndices(dip::DirectedGraph::VertexIndex vertex) const -> dip::DirectedGraph::EdgeList const&
Get the indices to the edges that start at vertex vertex.
auto VertexValue(dip::DirectedGraph::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::DirectedGraph::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::DirectedGraph::VertexIndex source, dip::DirectedGraph::VertexIndex target, dip::dfloat weight)
Add an edge from vertex source to target, with weight weight. If the edge already exists, update its weight to be weight.
void AddEdgeSumWeight(dip::DirectedGraph::VertexIndex source, dip::DirectedGraph::VertexIndex target, dip::dfloat weight)
Add an edge from vertex source to target, with weight weight. If the edge already exists, update its weight by adding weight to the existing weight.
void AddEdgePair(dip::DirectedGraph::VertexIndex vertex1, dip::DirectedGraph::VertexIndex vertex2, dip::dfloat weight)
Add an edge pair between vertices vertex1 and vertex2, both with weight weight. If the edges already exist, update their weights to be weight.
void AddEdgePair(dip::DirectedGraph::VertexIndex vertex1, dip::DirectedGraph::VertexIndex vertex2, dip::dfloat weight1, dip::dfloat weight2)
Add an edge pair between vertices vertex1 and vertex2, with weight weight1 and weight2 respectively. If the edges already exist, update their weights to be weight.
void AddEdgePairSumWeight(dip::DirectedGraph::VertexIndex vertex1, dip::DirectedGraph::VertexIndex vertex2, dip::dfloat weight)
Add an edge pair between vertices vertex1 and vertex2, both with weight weight. If the edges already exist, update their weight by adding the new weight to the existing weight.
void AddEdgePairSumWeight(dip::DirectedGraph::VertexIndex vertex1, dip::DirectedGraph::VertexIndex vertex2, dip::dfloat weight1, dip::dfloat weight2)
Add an edge pair between vertices vertex1 and vertex2, with weight weight1 and weight2 respectively. If the edges already exist, update their weight by adding the new weight to the existing weight.
void DeleteEdge(dip::DirectedGraph::VertexIndex source, dip::DirectedGraph::VertexIndex target)
Delete the edge from vertex source to target.
void DeleteEdgePair(dip::DirectedGraph::VertexIndex vertex1, dip::DirectedGraph::VertexIndex vertex2)
Delete both edges between vertex vertex1 and vertex2.
void DeleteEdge(dip::DirectedGraph::EdgeIndex edge)
Delete the edge edge.
void DeleteEdgePair(dip::DirectedGraph::EdgeIndex edge)
Delete the edge edge and its sibling.
auto Neighbors(dip::DirectedGraph::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 source, dfloat target), where the two inputs to func are the value of the two vertices. The sibling edge, if it exists, gets the same value, it is computed only once. So func has to be symmetric.
void UpdateEdgeWeights() const
Re-computes edge weights as the absolute difference between vertex values.
void IsConnectedTo(dip::DirectedGraph::VertexIndex root)
Sets the vertex weight to 1 if the vertex is connected to vertex root, to 0 otherwise.

Class documentation

struct Edge

An edge in the graph

If both vertices are equal, the edge is not valid (never used or deleted).

If Edge::sibling is *this, there is no sibling.

Variables
dip::DirectedGraph::VertexIndex source The vertex that the edge starts at
dip::DirectedGraph::VertexIndex target The vertex that the edge goes to
mutable dip::dfloat weight The weight of this edge
dip::DirectedGraph::EdgeIndex sibling The index to the sibling edge (the one that connects target to source)

Function documentation

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

Construct a directed 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. Each edge is guaranteed to have a sibling.

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::DirectedGraph::UpdateEdgeWeights to compute weights in some other way, or manually set the weights.

If extraEdges is "graphcut", then space will be reserved for the additional 2 vertices and all the edges and that the graph cut segmentation algorithm adds to the graph that this function makes. By default, extraEdges is "none", and the memory allocated is just enough to contain the edges and vertices created by this function. It is always possible to add additional edges or vertices, but this incurs a reallocation cost.