#include "BaseGraph/undirected_weighted_graph.hpp"

Undirected weighted graph

UndirectedWeightedGraph is an undirected graph in which each edge has a weight.

Usage

UndirectedWeightedGraph is a LabeledUndirectedGraph where the edge labels are weights. For that reason, both are almost identical. For example, we add a few weighted edges

BaseGraph::UndirectedWeightedGraph graph(5);

graph.addEdge(0, 1, -10);
graph.addEdge(1, 1, 0);
graph.addEdge(2, 4, 1.5);

We can modify a existing weight

graph.setEdgeWeight(1, 1, 5);

get the weight of any edge

graph.getEdgeWeight(2, 4); // 1.5

and get the sum of the weights in the graph

graph.getTotalWeight(); // -10 + 5 + 1.5 = 3.5

Detailed documentation

class UndirectedWeightedGraph : private BaseGraph::LabeledUndirectedGraph<EdgeWeight>

Undirected graphs with self-loops and weighted edges.

Behaves nearly identically to BaseGraph::LabeledUndirectedGraph. The difference is that each edge must have a weight stored in a EdgeMultiplicity.

Public Functions

template<template<class...> class Container, class ...Args> inline explicit UndirectedWeightedGraph(const Container<LabeledEdge<EdgeMultiplicity>, Args...> &multiedgeList)

Constructs a graph containing each edge in edgeSequence. The graph size is adjusted to the largest index in edgeSequence.

For example:

std::list<BaseGraph::LabeledEdge<BaseGraph::EdgeWeight>> edges =
{{0, 2, 0.5}, {0, 1, -2}, {0, 10, 10.1}, {5, 0, 0}};
BaseGraph::UndirectedWeightedGraph graph(edges);

Template Parameters:: Container – Any container of LabeledEdge<EdgeWeight>> that supports range-based loops. Most STL containers are usable.

inline EdgeWeight getTotalWeight() const: Returns the sum of the edge weights in the graph.

Warning

As any floating point operation, the result will seldom be exact. The error may increase when edges are added and/or removed frequently.

inline bool operator==(const UndirectedWeightedGraph &other) const: Returns if graph instance and other have the same size, edges and edge weights.

inline bool operator!=(const UndirectedWeightedGraph &other) const: Returns not operator==.

inline void addEdge(VertexIndex vertex1, VertexIndex vertex2, EdgeWeight weight, bool force = false)

Adds edge of weight weight connecting vertex vertex1 and vertex2.

Warning

Use force=true with caution as it may create duplicate edges. Since this class isn’t designed to handle them, it might behave unexpectedly in some algorithms. Remove duplicate edges with removeDuplicateEdges.

Parameters:

vertex1, vertex2 – Index of the vertices to connect.
weight – Edge weight.
force – If false, the edge is not added if it already exists. If true, the edge is added without checking its existence (quicker).

inline void removeEdge(VertexIndex vertex1, VertexIndex vertex2): Removes directed edges (including duplicates) from source to destination.

inline EdgeWeight getEdgeWeight(VertexIndex vertex1, VertexIndex vertex2, bool throwIfInexistent = true) const: Returns the weight of an edge connnecting vertex1 to vertex2. See LabeledDirectedGraph::getEdgeLabel for more details.

inline void setEdgeWeight(VertexIndex vertex1, VertexIndex vertex2, EdgeWeight newWeight): Changes the weight of the edge connecting vertex1 and vertex2 to newWeight. If the edge doesn’t exist, it is created.

inline void removeSelfLoops(): Removes each edge which connects a vertex to itself.

inline void removeDuplicateEdges(): Removes duplicate edges that have been created using the flag force=true in addEdge.

inline void removeVertexFromEdgeList(VertexIndex vertex): Removes all edges that connect vertex to another vertex. This is nearly equivalent to removing a vertex from the graph.

inline void clearEdges(): Removes all the edges from the graph.

inline const BaseClass &asLabeledGraph() const: Casts the weighted graph to a labeled graph, thus ignoring edge weights.

inline WeightMatrix getWeightMatrix() const: Constructs a matrix in which the element \(w_{ij}\) is the weight of the edge \((i,j)\).

Friends

inline friend std::ostream &operator<<(std::ostream &stream, const UndirectedWeightedGraph &graph): Outputs graph’s size and edges in text to a given std::stream object.