#include "BaseGraph/directed_multigraph.hpp"

Directed multigraphs

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

Usage

DirectedMultigraph is used very similarly to DirectedGraph, 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. In that case, the multiplicty is increased to 2

BaseGraph::DirectedMultigraph 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.

In addition, multiple edges can be added or removed 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 DirectedMultigraph : private BaseGraph::LabeledDirectedGraph<EdgeMultiplicity>

Directed graphs with self-loops and multiedges.

Behaves nearly identically to BaseGraph::DirectedGraph. 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 DirectedMultigraph(size_t size = 0): Constructs an empty graph with size vertices.

template<template<class...> class Container, class ...Args> inline explicit DirectedMultigraph(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::DirectedMultigraph 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 DirectedMultigraph &other) const: Returns if graph instance and other have the same size, edges and edge multiplicities.

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

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

inline void addReciprocalEdge(VertexIndex source, VertexIndex destination, bool force = false): Adds reciprocal edge. Calls addEdge for both edge orientations.

inline void addMultiedge(VertexIndex source, VertexIndex destination, EdgeMultiplicity multiplicity, bool force = false)

Adds multiple directed edges from vertex source to destination. 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:

source, destination – Index of the source and destination vertices.
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 addReciprocalMultiedge(VertexIndex source, VertexIndex destination, EdgeMultiplicity multiplicity, bool force = false): Adds reciprocal edges. Calls addMultiedge for both edge orientations.

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

inline void removeMultiedge(VertexIndex source, VertexIndex destination, EdgeMultiplicity multiplicity)

Removes multiple directed edges from source to destination. If multiplicity is greater or equal to the current multiplicity, the multiplicity is set to 0.

Parameters:

source, destination – Index of the source and destination vertices.
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 source to destination.

inline EdgeMultiplicity getEdgeMultiplicity(VertexIndex source, VertexIndex destination) const: Return the multiplicity of the edge connecting source to destination.

inline void setEdgeMultiplicity(VertexIndex source, VertexIndex destination, EdgeMultiplicity multiplicity)

Change the multiplicity of the edge connecting source to destination. If multiplicity is 0, the multiedge is removed. If the edge doesn’t exist, it’s created.

Parameters:

source, destination – 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() const: Constructs the adjacency matrix. The element \(a_{ij}\) of the matrix is the multiplicity of edge \((i,j)\).

inline size_t getOutDegree(VertexIndex vertex) const: Counts the number of out edges of vertex, including parallel edges.

inline std::vector<size_t> getOutDegrees() const: Counts the number of out edges of each vertex, including parallel edges.

inline size_t getInDegree(VertexIndex vertex) const: Counts the number of in edges of vertex, including parallel edges. getInDegrees is more efficient when more than one in degree is needed.

inline std::vector<size_t> getInDegrees() const: Counts the number of in edges of each vertex, including parallel edges.

Friends

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