#include "BaseGraph/undirected_graph.hpp"

Labeled undirected graph

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

Usage

Edge-labeled undirected graphs are created and manipulated very similarly to UndirectedGraph. Suppose edges represent relationships

struct Relationship {
    enum Status {
        MARRIED, DIVORCED
    } status;
    unsigned int marriageDuration;
};

An undirected graph of these relationships is created using

BaseGraph::LabeledUndirectedGraph<Relationship> graph(5);

To add a relationship in this graph, use addEdge with the desired label

graph.addEdge(0, 1, {Relationship::Status::MARRIED, 10});
graph.addEdge(4, 3, {Relationship::Status::DIVORCED, 5});

The information about each relationship is retrieved using getEdgeLabel

Relationship relationshipA = graph.getEdgeLabel(0, 1);
Relationship relationshipB = graph.getEdgeLabel(4, 3);

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

graph.setEdgeLabel(0, 1, {Relationship::Status::DIVORCED, 10});

Detailed documentation

template<typename EdgeLabel>
class LabeledUndirectedGraph : protected BaseGraph::LabeledDirectedGraph<EdgeLabel>

Undirected graph with edge labels, self-loops and without multiedges. When no

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.

Public Functions

inline explicit LabeledUndirectedGraph(size_t size = 0)

Constructs an empty graph with size vertices.

Parameters:

size – Number of vertices.

template<template<class...> class Container, class ...Args, typename U = EdgeLabel>
inline explicit LabeledUndirectedGraph(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 in edgeSequence. The graph size is adjusted to the largest index in edgeSequence. This method is available only for an unlabeled graph (BaseGraph::UndirectedGraph).

For example: 

std::list<BaseGraph::Edge> edges = {{0, 2}, {0, 1}, {0, 0}, {5, 10}};
BaseGraph::UndirectedGraph 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 LabeledUndirectedGraph(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::LabeledUndirectedGraph graph(labeledEdges);

Template Parameters:

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

inline explicit LabeledUndirectedGraph(const Directed &directedGraph)

Constructs a undirected graph containing each edge of directedGraph.

inline bool operator==(const LabeledUndirectedGraph<EdgeLabel> &other) const

Returns if graph instance and other have the same size, edges and edge labels.

inline bool operator!=(const LabeledUndirectedGraph<EdgeLabel> &other) const

Returns not operator==.

void addEdge(VertexIndex vertex1, VertexIndex vertex2, const EdgeLabel &label, bool force = false)

Adds labeled edge between 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 be connected.

  • 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 vertex1, VertexIndex vertex2, bool force = false)

Adds edge connecting vertex1 and vertex2 with the default label constructor. This is the suggested method to add edges in a BaseGraph::UndirectedGraph. See the other addEdge(VertexIndex,VertexIndex,const EdgeLabel&, bool) “overload”.

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.

void removeEdge(VertexIndex vertex1, VertexIndex vertex2)

Removes edges (including duplicates) between vertex1 and vertex2.

inline const Successors &getNeighbours(VertexIndex vertex) const

Same as getOutNeighbours.

inline EdgeLabel getEdgeLabel(VertexIndex vertex1, VertexIndex vertex2, bool throwIfInexistent = true) const

Returns label of edge connecting vertex1 and vertex2.

Parameters:

  • vertex1, vertex2 – Index of the vertices of the edge.

  • throwIfInexistent – If true, the method throws std::invalid_argument if the edge doesn’t exist. If false, the method returns EdgeLabel() when the edge isn’t found.

Returns:

Label of the edge.

inline void setEdgeLabel(VertexIndex vertex1, VertexIndex vertex2, const EdgeLabel &label, bool force = false)

Changes the label of edge connecting vertex1 and vertex2.

Parameters:

  • vertex1, vertex2 – Index of the vertices of the edge.

  • label – New label value for the edge.

  • 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.

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.

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

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

Return the degree of every vertex. See getDegree.

AdjacencyMatrix getAdjacencyMatrix(bool countSelfLoopsTwice = true) const

Constructs the adjacency matrix.

Directed getDirectedGraph() const

Constructs a LabeledDirectedGraph containing each reciprocal edge of the LabeledUndirectedGraph instance.

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 Edges edges() const

Creates LabeledUndirectedGraph::Edges object that supports range-based for loop.

inline size_t getEdgeNumber() const

Returns the number of edges.

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 const Successors &getOutNeighbours(VertexIndex vertex) const

Returns vertices to which vertex is connected.

inline void assertVertexInRange(VertexIndex vertex) const

Throws std::out_of_range if vertex is not contained in the graph.

inline VertexIterator begin() const

Returns VertexIterator of first vertex. Allows ranged-based loop on the graph’s vertices.

inline void clearEdges()

Removes all the edges from the graph.

inline VertexIterator end() const

Returns VertexIterator of last vertex. Allows ranged-based loop on the graph’s vertices.

Friends

inline friend std::ostream &operator<<(std::ostream &stream, const LabeledUndirectedGraph<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