An R6 class to represent a graph (from discrete mathematics).
Andrew Sims andrew.sims@newcastle.ac.uk
new()Create a new Graph object from sets of nodes
and edges.
Graph$new(V, E)VA list of Nodes.
EA list of Edges.
A Graph object.
Order of the graph (integer).
size()Return the size of the graph (number of edges).
Graph$size()Size of the graph (integer).
vertex_along()Sequence of vertex indices.
Graph$vertex_along()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.
A numeric vector.
vertex_index()Find the index of a vertex in the graph.
Graph$vertex_index(v)vA vertex.
Index of v. The vertices are normally stored in the same
order they are specified in new, but this cannot be guaranteed.
This function returns the same index as used in the adjacency matrix and
NA if v is not a vertex, or is a vertex that is not in
the graph.
vertex_at()Find the vertex at a given index.
Graph$vertex_at(index)indexIndex of a vertex in the graph, as an integer. The indices
of the vertices normally run from 1 to the order of the graph, and are
normally in the same sequence as the list of vertices, V, supplied
when the graph was created. However, these assumptions are not
guaranteed to hold for future versions of the package, and it is
recommended to supply an index value that has been provided by another
class function such as vertex_index, vertex_along and
graph_adjacency_matrix.
The inverse of function vertex_index. The function will
raise an abort signal if the supplied index is not a vertex.
the node (vertex) with the specified index.
has_vertex()Test whether a vertex is an element of the graph.
Graph$has_vertex(v)vSubject vertex.
TRUE if v is an element of V(G).
edge_along()Sequence of edge indices.
Graph$edge_along()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.
A numeric vector.
edge_index()Find the index of an edge in a graph.
Graph$edge_index(e)eSubject edge.
Index of e. The edges are normally stored in the same
order they are specified in new, but this cannot be guaranteed.
This function returns the same index returned in other functions and
NA if the edge is not in the graph.
edge_at()Find the edge at a given index.
Graph$edge_at(index)indexIndex of a edge in the graph, as an integer. The indices
of the edges normally run from 1 to the size of the graph, and are
normally in the same sequence as the list of edges, E, supplied
when the graph was created. However, these assumptions are not
guaranteed to hold for future versions of the package, and it is
recommended to supply an index value that has been provided by another
class function such as edge_index and edge_along.
The inverse of function dge_index. The function will
raise an abort signal if the supplied index is not an edge.
the edge with the specified index.
has_edge()Test whether an edge is element of the graph.
Graph$has_edge(e)eSubject edge.
TRUE if e is an element of \(E(G)\).
graph_adjacency_matrix()Compute the adjacency matrix for the graph.
Graph$graph_adjacency_matrix(boolean = FALSE)booleanIf TRUE, the adjacency matrix is logical, each
cell is FALSE, TRUE.
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).
A square numeric 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 labels, or the node indices if not.
is_simple()Is this a simple graph?
Graph$is_simple()A simple graph has no self loops or multi-edges.
TRUE if simple, FALSE if not.
is_connected()Test whether the graph is connected.
Graph$is_connected()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.
TRUE if connected, FALSE if not.
is_acyclic()Checks for the presence of a cycle in the graph.
Graph$is_acyclic()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.
TRUE if no cycles detected.
is_tree()Compute whether the graph is connected and acyclic.
Graph$is_tree()TRUE if the graph is a tree; FALSE if not.
degree()The degree of a vertex in the graph.
Graph$degree(v)vThe subject node.
The number of incident edges.
Degree of the vertex, integer.
neighbours()Find the neighbours of a node.
Graph$neighbours(v)vThe subject node.
A property of the graph, not the node. Does not include self, even in the case of a loop to self.
A list of nodes which are joined to the subject.
as_DOT()Export a representation of the graph in DOT format.
Graph$as_DOT()Writes the representation in the graphviz DOT language
(http://graphviz.org/doc/info/lang.html) for drawing with one
of the graphviz tools including dot (Gansner, 1993).
A character vector. Intended for passing to writeLines
for saving as a text file.
clone()The objects of this class are cloneable with this method.
Graph$clone(deep = FALSE)deepWhether to make a deep clone.
Encapsulates and provides methods for computation and checking of undirected graphs. Graphs are systems of vertices connected in pairs by edges. A base class.
Gansner ER, Koutsofios E, North SC, Vo K-P. A technique for drawing directed graphs. IEEE Transactions on Software Engineering, 1993;19:214–30, tools:::Rd_expr_doi("10.1109/32.221135"). Gross JL, Yellen J, Zhang P. Handbook of Graph Theory. Second edition, Chapman and Hall/CRC.; 2013, tools:::Rd_expr_doi("10.1201/b16132")