#include "BaseGraph/directed_weighted_graph.hpp"

Directed weighted graph

DirectedWeightedGraph is a directed graph in which each edge has a weight.

Usage

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

BaseGraph::DirectedWeightedGraph graph(5);

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

We can modify a existing weight

graph.setEdgeWeight(1, 0, 5);

get the weight of any edge

graph.getEdgeWeight(3, 0); // 1.5

and get the sum of the weights in the graph

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

Detailed documentation

class DirectedWeightedGraph : private BaseGraph::LabeledDirectedGraph<EdgeWeight>

Directed graphs with self-loops and weighted edges.

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

Public Functions

inline explicit DirectedWeightedGraph(size_t size = 0): Constructs an empty graph with size vertices.

template<template<class...> class Container, class ...Args> inline explicit DirectedWeightedGraph(const Container<LabeledEdge<EdgeWeight>, Args...> &weightedEdgeList)

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::DirectedWeightedGraph graph(edges);

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

inline long double 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 DirectedWeightedGraph &other) const: Returns if graph instance and other have the same size, edges and edge weights.

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

inline void addEdge(VertexIndex source, VertexIndex destination, EdgeWeight weight, bool force = false)

Adds directed edge of weight weight from vertex source to destination.

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:

source, destination – Index of the source and destination vertices.
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 addReciprocalEdge(VertexIndex source, VertexIndex destination, bool force = false): Calls addEdge for both edge orientations.

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

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

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

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

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

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 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 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 DirectedWeightedGraph &graph): Outputs graph’s size and edges in text to a given std::stream object.