Segmentation » Graphs module

#include "diplib/graph.h"

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

Computes the minimum spanning forest (MSF) of a graph 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 dip::GraphCut(dip::DirectedGraph& graph, dip::DirectedGraph::VertexIndex sourceIndex, dip::DirectedGraph::VertexIndex sinkIndex)

Computes the minimum cut of the graph, separating the source node from the sink node.

graph is a directed graph where each edge has a reverse sibling. That is, each pair of connected vertices must be connected by two edges in opposite direction. The edge weights represent the maximum flow that can run through it in its natural direction, and will determine where the cut happens.

sourceIndex and sinkIndex are indices pointing at the source and sink nodes (vertices). These are the two marker nodes that will be separated by the cut. If there is more than one marker node for either source or sink, create a new node that is strongly connected (very large edge weight) to all these marker nodes, and use this new node as the source or sink.

graph is expected to have a path from sourceIndex to sinkIndex. If no such path exists, there’s nothing to cut.

The function will find the maximum flow through the graph from source to sink. This will naturally saturate a set of edges. This set of edges is the minimum cut that will separate the source from the sink. The algorithm used to compute the maximum flow is the one proposed by Boykov and Kolmogorov. This algorithm was shown to be faster than older algorithms when applied to a 2D image converted to a graph using a 4-connected neighborhood.

The input graph will be modified as follows: The edge weights will reflect the residual of the maximum flow from the source node to the sink node (i.e. how much more capacity each edge has). The edges with a zero residual (and their sibling) will be removed; these edges compose the minimum cut, and removing them separates the source from the sink in separate connected components. dip::Label can identify the two components created by this cut.

dip::LabelMap dip::Label(dip::Graph const& graph)

Connected component analysis of a graph.

The output can be used to relabel the image that the graph was constructed from. It maps the graph’s vertex indices to labels, where each connected component in the graph represents a label.

See also dip::Relabel.

dip::LabelMap dip::Label(dip::DirectedGraph const& graph)

Connected component analysis of a graph.

The output can be used to relabel the image that the graph was constructed from. It maps the graph’s vertex indices to labels, where each connected component in the graph represents a label.

See also dip::Relabel.