# 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

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