Graph {rdecision}

An undirected graph

Description

An R6 class to represent a graph (from discrete mathematics).

Details

Encapsulates and provides methods for computation and checking of undirected graphs. Graphs are systems of vertices connected in pairs by edges. A base class.

Methods

Public methods

• Graph$new()

• Graph$order()

• Graph$size()

• Graph$vertexes()

• Graph$vertex_along()

• Graph$vertex_index()

• Graph$vertex_at()

• Graph$has_vertex()

• Graph$vertex_label()

• Graph$edges()

• Graph$edge_along()

• Graph$edge_index()

• Graph$edge_at()

• Graph$has_edge()

• Graph$edge_label()

• Graph$graph_adjacency_matrix()

• Graph$is_simple()

• Graph$is_connected()

• Graph$is_acyclic()

• Graph$is_tree()

• Graph$degree()

• Graph$neighbours()

• Graph$as_DOT()

• Graph$clone()

Method new()

Create a new Graph object from sets of nodes and edges.

Usage

Graph$new(V, E)

Arguments

V

An unordered set of Nodes, as a list.

E

An unordered set of Edges, as a list.

Returns

A Graph object.

Method order()

Return the order of the graph (number of vertices).

Usage

Graph$order()

Returns

Order of the graph (integer).

Method size()

Return the size of the graph (number of edges).

Usage

Graph$size()

Returns

Size of the graph (integer).

Method vertexes()

A list of all the Node objects in the graph.

Usage

Graph$vertexes()

Details

The list of Node objects is returned in the same order as their indexes understood by vertex_index, vertex_at and vertex_along, which is not necessarily the same order in which they were supplied in the V argument to new.

Method vertex_along()

Sequence of vertex indices.

Usage

Graph$vertex_along()

Details

Similar to base::seq_along, this function provides the indices of the vertices in the graph. It is intended for use by graph algorithms which iterate vertices.

Returns

A numeric vector of indices from 1 to the order of the graph. The vertex at index i is not guaranteed to be the same vertex at V[[i]] of the argument V to new (i.e., the order in which the vertices are stored internally within the class may differ from the order in which they were supplied).

Method vertex_index()

Find the index of a vertex in the graph.

Usage

Graph$vertex_index(v)

Arguments

v

A vertex, or list of vertexes.

Returns

Index of v. The index of vertex v is the one used internally to the class object, which is not necessarily the same as the order of vertices in the V argument of new. NA if v is not a vertex, or is a vertex that is not in the graph.

Method vertex_at()

Find the vertex at a given index.

Usage

Graph$vertex_at(index, as_list = FALSE)

Arguments

index

Index of vertex in the graph, as an integer, or vector of integers.

as_list

Boolean. If TRUE the method returns list of Nodes, even if the length of index is 1.

Details

The inverse of function vertex_index. The function will raise an abort signal if all the supplied indexes are not vertexes. The function is vectorized, but for historical compatibility the return object is a single Node if index is a scalar. The return object can be guaranteed to be a list if as_list is set.

Returns

Node at index if index is a scalar, a list of Nodes at the values of index if index is a vector, or an empty list if index is an empty array.

Method has_vertex()

Test whether a vertex is an element of the graph.

Usage

Graph$has_vertex(v)

Arguments

v

Subject vertex.

Returns

TRUE if v is an element of V(G).

Method vertex_label()

Find label of vertexes at index i.

Usage

Graph$vertex_label(iv)

Arguments

iv

Index of vertex, or vector of indexes.

Returns

Label(s) of vertex at index i

Method edges()

A list of all the Edge objects in the graph.

Usage

Graph$edges()

Details

The list of Edge objects is returned in the same order as their indexes understood by edge_index, edge_at and edge_along, which is not necessarily the same order in which they were supplied in the E argument to new.

Method edge_along()

Sequence of edge indices.

Usage

Graph$edge_along()

Details

Similar to base::seq_along, this function provides the indices of the edges in the graph. It is intended for use by graph algorithms which iterate edges. It is equivalent to seq_along(g$edges()), where g is a graph.

Returns

A numeric vector of indices from 1 to the size of the graph. The edge at index i is not guaranteed to be the same edge at E[[i]] of the argument E to new (i.e., the order in which the edges are stored internally within the class may differ from the order in which they were supplied).

Method edge_index()

Find the index of an edge in a graph.

Usage

Graph$edge_index(e)

Arguments

e

An edge object, or list of edge objects.

Details

The index of edge e is the one used internally to the class object, which is not necessarily the same as the order of edges in the E argument of new.

Returns

Index of e. NA if e is not an edge, or is an edge that is not in the graph.

Method edge_at()

Find the edge at a given index.

Usage

Graph$edge_at(index, as_list = FALSE)

Arguments

index

Index of edge in the graph, as an integer, vector of integers, or list of integers.

as_list

Boolean. If TRUE the method returns list of Edges, even if the length of index is 1.

Details

The inverse of function edge_index. The function will raise an abort signal if the supplied index is not an edge. The function is vectorized, but for historical compatibility the return object is a single Edge if index is a scalar. The return object can be guaranteed to be a list if as_list is set.

Returns

The edge, or list of edges, with the specified index.

Method has_edge()

Test whether an edge is an element of the graph.

Usage

Graph$has_edge(e)

Arguments

e

Edge or list of edges.

Returns

Logical vector with each element TRUE if the corresponding element of e is an element of E(G).

Method edge_label()

Find label of edge at index i

Usage

Graph$edge_label(ie)

Arguments

ie

Index of edge, or vector of indexes.

Returns

Label of edge at index i, or character vector with the labels at indexes ie.

Method graph_adjacency_matrix()

Compute the adjacency matrix for the graph.

Usage

Graph$graph_adjacency_matrix(boolean = FALSE)

Arguments

boolean

If TRUE, the adjacency matrix is logical, each cell is {FALSE, TRUE}.

Details

Each cell contains the number of edges joining the two vertexes, with the convention of self loops being counted twice, unless binary is TRUE when cells are either 0 (not adjacent) or 1 (adjacent).

Returns

A square integer matrix with the number of rows and columns equal to the order of the graph. The rows and columns are labelled with the node labels, if all the nodes in the graph have unique labels, or the node indices if not.

Method is_simple()

Is this a simple graph?

Usage

Graph$is_simple()

Details

A simple graph has no self loops or multi-edges.

Returns

TRUE if simple, FALSE if not.

Method is_connected()

Test whether the graph is connected.

Usage

Graph$is_connected()

Details

Graphs with no vertices are considered unconnected; graphs with 1 vertex are considered connected. Otherwise a graph is connected if all nodes can be reached from an arbitrary starting point. Uses a depth first search.

Returns

TRUE if connected, FALSE if not.

Method is_acyclic()

Checks for the presence of a cycle in the graph.

Usage

Graph$is_acyclic()

Details

Uses a depth-first search from each node to detect the presence of back edges. A back edge is an edge from the current node joining a previously detected (visited) node, that is not the parent node of the current one.

Returns

TRUE if no cycles detected.

Method is_tree()

Compute whether the graph is connected and acyclic.

Usage

Graph$is_tree()

Returns

TRUE if the graph is a tree; FALSE if not.

Method degree()

The degree of a vertex in the graph.

Usage

Graph$degree(v)

Arguments

v

The subject node.

Details

The number of incident edges.

Returns

Degree of the vertex, integer.

Method neighbours()

Find the neighbours of a node.

Usage

Graph$neighbours(v)

Arguments

v

The subject node (scalar, not a list).

Details

A property of the graph, not the node. Does not include self, even in the case of a loop to self.

Returns

A list of nodes which are joined to the subject.

Method as_DOT()

Export a representation of the graph in DOT format.

Usage

Graph$as_DOT()

Details

Writes the representation in the graphviz DOT language (https://graphviz.org/doc/info/lang.html) for drawing with one of the graphviz tools including dot (Gansner, 1993).

Returns

A character vector. Intended for passing to writeLines for saving as a text file.

Method clone()

The objects of this class are cloneable with this method.

Usage

Graph$clone(deep = FALSE)

Arguments

deep

Whether to make a deep clone.

Author(s)

Andrew Sims [e-mail]

References

Gansner ER, Koutsofios E, North SC, Vo K-P. A technique for drawing directed graphs. IEEE Transactions on Software Engineering, 1993;19:214–30, doi:10.1109/32.221135.

Gross JL, Yellen J, Zhang P. Handbook of Graph Theory. Second edition, Chapman and Hall/CRC.; 2013, doi:10.1201/b16132