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

inline VertexIterator begin() const: Returns VertexIterator of first vertex. Allows ranged-based loop on the graph’s vertices.

inline Edges edges() const: Creates LabeledUndirectedGraph::Edges object that supports range-based for loop.

inline VertexIterator end() const: Returns VertexIterator of last vertex. Allows ranged-based loop on the graph’s vertices.

AdjacencyMatrix getAdjacencyMatrix(bool countSelfLoopsTwice = true) const: Constructs the adjacency matrix.

inline size_t getEdgeNumber() const: Returns the number of edges.

inline const Successors &getOutNeighbours(VertexIndex vertex) const: Returns vertices to which vertex is connected.

inline size_t getSize() const: Returns the number of vertices.

void resize(size_t newSize)

Sets the number of vertices to newSize.

Parameters:: newSize – Number of vertices. Must be larger than the current number of vertices.

size_t getDegree(VertexIndex vertex, bool countSelfLoopsTwice = true) const

Returns the number of vertices connected to vertex.

Parameters:

vertex – Index of a vertex.
countSelfLoopsTwice – If true, self-loops are counted twice. If false, self-loops are counted once. If there are no self-loops, set to false for better performance, i.e. constant instead of linear complexity.

Returns:

Degree of vertex vertex Doesn’t consider the edge weights.

inline std::vector<size_t> getDegrees(bool countSelfLoopsTwice = true) const

Return the degree of every vertex. See getDegree.

Doesn’t consider the edge weights.

inline bool hasEdge(VertexIndex vertex1, VertexIndex vertex2) const: Returns if an edge of any label connects vertex1 to vertex2.

inline bool hasEdge(VertexIndex vertex1, VertexIndex vertex2, const EdgeLabel &label) const: Returns if an edge of label label connects vertex1 to vertex2.

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.