#include "BaseGraph/directed_graph.hpp"

Labeled directed graph

LabeledDirectedGraph is a class which is able to store edge information (i.e. a label).

Usage

Edge-labeled directed graphs are created and manipulated very similarly to a DirectedGraph. Suppose edges represent flights between cities

struct Flight {
    std::string company;
    double distance;
};

A directed graph of these flights is created using

BaseGraph::LabeledDirectedGraph<Flight> graph(5);

To add a flight in this graph, use the method addEdge with the appropriate label

graph.addEdge(0, 1, {"Company A", 10.});
graph.addEdge(4, 3, {"Company B", 2.2});

The information about each flight is retrieved using getEdgeLabel

Flight flightB = graph.getEdgeLabel(4, 3);
Flight flightA = graph.getEdgeLabel(0, 1);

It’s also possible to change the value of a label with setEdgeLabel

graph.setEdgeLabel(0, 1, {"Company B", 10.});

Detailed documentation

template<typename EdgeLabel> class LabeledDirectedGraph

Directed graph with edge labels, self-loops and without multiedges. When no EdgeLabel is specified, it acts as an unlabeled graph.

Vertices are identified an integer index between 0 and size -1. Vertices can be added using resize. Vertices cannot be removed because it requires reindexing. However, a vertex can be effectively removed by erasing all of its edges with removeVertexFromEdgeList.

Template Parameters:: EdgeLabel – Container of edge information. Requires a default constructor.

Subclassed by BaseGraph::LabeledUndirectedGraph< EdgeLabel >

Public Functions

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

template<template<class...> class Container, class ...Args, typename U = EdgeLabel> inline explicit LabeledDirectedGraph(const Container<Edge, Args...> &edgeSequence, typename std::enable_if<std::is_same<U, NoLabel>::value, long long int>::type* = 0)

Constructs a graph containing each edge in edgeSequence. The graph size is adjusted to the largest index in edgeSequence. This method is available only for a unlabeled graph (BaseGraph::DirectedGraph).

For example:

std::list<BaseGraph::Edge> edges = {{0, 2}, {0, 1}, {0, 0}, {5, 10}};
BaseGraph::DirectedGraph graph(edges);

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

template<template<class...> class Container, class ...Args> inline explicit LabeledDirectedGraph(const Container<LabeledEdge<EdgeLabel>, Args...> &edgeSequence)

Constructs graph containing every vertex in edgeSequence. Graph size is adjusted to the largest index in edgeSequence. This method is available to any labeled graph.

For example:

std::list<BaseGraph::LabeledEdge<std::string>> labeledEdges =
        {{0, 2, "a"}, {0, 1, "b"}, {0, 0, "c"}, {5, 10, "d"}};
BaseGraph::LabeledDirectedGraph graph(labeledEdges);

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

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.

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

bool operator==(const LabeledDirectedGraph<EdgeLabel> &other) const: Returns if graph instance and other have the same size, edges and edge labels.

inline bool operator!=(const LabeledDirectedGraph<EdgeLabel> &other) const: Returns not operator==.

void addEdge(VertexIndex source, VertexIndex destination, const EdgeLabel &label, bool force = false)

Adds labeled directed edge 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.
label – Label of the edge created.
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 addEdge(VertexIndex source, VertexIndex destination, bool force = false): Adds edge from vertex source to destination with the default label constructor. This is the suggested method to add edges in a BaseGraph::DirectedGraph. See the other overload.

inline void addReciprocalEdge(VertexIndex vertex1, VertexIndex vertex2, const EdgeLabel &label, bool force = false): Calls addEdge for both edge orientations.

inline void addReciprocalEdge(VertexIndex vertex1, VertexIndex vertex2, bool force = false): Calls addReciprocalEdge using the label EdgeLabel().

bool hasEdge(VertexIndex source, VertexIndex destination) const: Returns if a directed edge of any label connects source to destination.

inline bool hasEdge(VertexIndex source, VertexIndex destination, const EdgeLabel &label) const: Returns if a directed edge of label label connects source to destination.

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

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

inline EdgeLabel getEdgeLabel(VertexIndex source, VertexIndex destination, bool throwIfInexistent = true) const

Returns label of directed edge connecting source to destination.

Parameters:

source, destination – Index of the source and destination vertices.
throwIfInexistent – If true, the method throws std::invalid_argument if the directed edge doesn’t exist. If false, the method returns EdgeLabel() when the edge isn’t found.

Returns:

Label of the edge.

void setEdgeLabel(VertexIndex source, VertexIndex destination, const EdgeLabel &label, bool force = false)

Changes the label of directed edge connecting source to destination.

Parameters:

source, destination – Index of the source and destination vertices.
label – New edge label.
force – If true, the method will not check if the edge exists. This may create a label for an inexistent edge. If false, the method throws std::invalid_argument if the directed edge doesn’t exist.

inline LabeledDirectedGraph<EdgeLabel> getReversedGraph() const: Constructs a graph where each edge orientation is reversed.

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.

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 size_t getInDegree(VertexIndex vertex) const: Counts the number of in edges of vertex. 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.

inline size_t getOutDegree(VertexIndex vertex) const: Counts the number of edges coming from vertex.

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

inline AdjacencyMatrix getAdjacencyMatrix() const: Constructs the adjacency matrix.

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

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

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

inline void assertVertexInRange(VertexIndex vertex) const: Throws std::out_of_range if vertex is not contained in the graph.

Friends

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

struct Edges

Structure that iterates on the graph’s edges.

struct constEdgeIterator