#include "BaseGraph/undirected_multigraph.hpp"

Undirected multigraphs

UndirectedMultigraph is a undirected graph that allows parallel edges. The number of parallel edges connecting a pair of vertices is called its multiplicity.

Usage

UndirectedMultigraph is used very similarly to UndirectedGraph, the main difference being that parallel edges are accounted for when adding and removing edges. For example, we can add an edge \((i,j)\) even if it already exists once. In that case, the multiplicty will be increased to 2

BaseGraph::UndirectedMultigraph graph(5);

graph.addEdge(0, 1);
graph.addEdge(0, 1); // Edge (0, 1) now has multiplicity 2.

The same principle applies when removing an edge: if the multiplicity is 2, then removing an edge reduces it to 1

graph.removeEdge(0, 1); // Edge (0, 1) now has multiplicity 1.

Additionally, we can add and remove multiple edges at the same time

graph.addMultiedge(0, 2, 3); // Edge (0, 2) has multiplicity 3
graph.removeMultiedge(0, 2, 2); // Edge (0, 2) has multiplicity 1

The multiplicity of an edge is obtained with getEdgeMultiplicity

std::cout << "Multiplicity of edge (0, 2) is: "
    << graph.getEdgeMultiplicity(0, 2) << std::endl;

Detailed documentation

class UndirectedMultigraph : private BaseGraph::LabeledUndirectedGraph<EdgeMultiplicity>

Undirected graphs with self-loops and multiedges.

Behaves nearly identically to BaseGraph::UndirectedGraph. The main difference is that addEdge and removeEdge count parallel edges (multiedges). The number of parallel edges is stored in a BaseGraph::EdgeMultiplicity.

Public Functions

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

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

Constructs graph containing every vertex in multiedgeList. Graph size is adjusted to the largest index in edgeSequence.

For example:

std::list<BaseGraph::LabeledEdge<BaseGraph::EdgeMultiplicity>> multiedges
=
        {{0, 2, 1}, {0, 1, 4}, {0, 0, 1}, {5, 10, 2}};
BaseGraph::UndirectedMultigraph graph(multiedges);

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

inline size_t getTotalEdgeNumber() const: Returns the edge number including parallel edges.

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

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

inline void addEdge(VertexIndex vertex1, VertexIndex vertex2, bool force = false): Adds a single edge with addMultiedge.

inline void addMultiedge(VertexIndex vertex1, VertexIndex vertex2, EdgeMultiplicity multiplicity, bool force = false)

Add multiple directed edges connecting vertex1 to vertex2. If the edge already exists, the current multiplicity is increased (unless force is true).

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. Note that removeDuplicateEdges does not merge duplicate edges, it only removes them. Duplicate edges are not multiedges.

Parameters:

vertex1, vertex2 – Index of the vertices to connect.
multiplicity – Edge multiplicity.
force – If false and the edge exists, the multiplicity is increased. If true, a new edge (potentially duplicate) is added without checking its existence (quicker).

inline void removeEdge(VertexIndex vertex1, VertexIndex vertex2): Removes one directed edge from source to destination with removeMultiedge.

inline void removeMultiedge(VertexIndex vertex1, VertexIndex vertex2, EdgeMultiplicity multiplicity)

Remove multiple edges connecting vertex1 and vertex2. If multiplicity is greater or equal to the current multiplicity, the multiplicity is set to 0.

Parameters:

vertex1, vertex2 – Index of the vertices to remove.
multiplicity – Number of edges to remove.

inline bool hasEdge(VertexIndex vertex1, VertexIndex vertex2) const: Returns if there is at least one directed edge that connects vertex1 to vertex2.

inline EdgeMultiplicity getEdgeMultiplicity(VertexIndex vertex1, VertexIndex vertex2) const: Returns the multiplicity of the edge connecting vertex1 to vertex2.

inline void setEdgeMultiplicity(VertexIndex vertex1, VertexIndex vertex2, EdgeMultiplicity multiplicity)

Change the multiplicity of the edge connecting vertex1 and vertex2. If multiplicity is 0, the multiedge is removed. If the edge doesn’t exist, it’s created.

Parameters:

vertex1, vertex2 – Index of the vertices.
multiplicity – New edge multiplicity.

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

Warning

The duplicate edges are not merged, meaning that the edge multiplicities are not changed by this method.

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

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 multigraph to a labeled graph, thus ignoring edge multiplicities.

inline AdjacencyMatrix getAdjacencyMatrix(bool countSelfLoopsTwice = true) const: Constructs the adjacency matrix. The element \(a_{ij}\) of the matrix is the multiplicity of edge \((i,j)\).

inline size_t getDegree(VertexIndex vertex, bool countSelfLoopsTwice = true) const: Counts the number of edges connected to vertex, including parallel edges.

inline std::vector<size_t> getDegrees(bool countSelfLoopsTwice = true) const: Counts the number of edges connected to each vertex, including parallel edges.

Friends

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