An R6 class representing a digraph (a directed graph).
Andrew Sims andrew.sims@newcastle.ac.uk
rdecision::Graph -> Digraph
Inherited methods
rdecision::Graph$degree()rdecision::Graph$edge_along()rdecision::Graph$edge_at()rdecision::Graph$edge_index()rdecision::Graph$graph_adjacency_matrix()rdecision::Graph$has_edge()rdecision::Graph$has_vertex()rdecision::Graph$is_simple()rdecision::Graph$neighbours()rdecision::Graph$order()rdecision::Graph$size()rdecision::Graph$vertex_along()rdecision::Graph$vertex_at()rdecision::Graph$vertex_index()
new()Create a new Digraph object from sets of nodes and edges.
Digraph$new(V, A)VA list of Nodes.
AA list of Arrows.
A Digraph object.
digraph_adjacency_matrix()Compute the adjacency matrix for the digraph.
Digraph$digraph_adjacency_matrix(boolean = FALSE)booleanIf TRUE, the adjacency matrix is logical, each
cell is {FALSE,TRUE}.
Each cell contains the number of edges from the row vertex to
the column vertex, with the convention of self loops being counted once,
unless boolean is TRUE when cells are either FALSE
(not adjacent) or TRUE (adjacent).
A square numeric matrix with the number of rows and columns
equal to the order of the graph. The rows and columns are in the
same order as V. If the nodes have defined and unique labels the
dimnames of the matrix are the labels of the nodes.
digraph_incidence_matrix()Compute the incidence matrix for the digraph.
Digraph$digraph_incidence_matrix()Each row is a vertex and each column is an edge. Edges leaving a vertex have value -1 and edges entering have value +1. By convention self loops have value 0 (1-1). If all vertexes have defined and unique labels and all edges have defined and unique labels, the dimnames of the matrix are the labels of the vertexes and edges.
The incidence matrix.
topological_sort()Topologically sort the vertexes in the digraph.
Digraph$topological_sort()Uses Kahn's algorithm (Kahn, 1962).
A list of vertexes, topologically sorted. If the digraph has cycles, the returned ordered list will not contain all the vertexes in the graph, but no error will be raised.
is_connected()Test whether the graph is connected.
Digraph$is_connected()For digraphs this will always return FALSE because
connected is not defined. Function weakly_connected
calculates whether the underlying graph is connected.
TRUE if connected, FALSE if not.
is_weakly_connected()Test whether the digraph is weakly connected, i.e. if the underlying graph is connected.
Digraph$is_weakly_connected()TRUE if connected, FALSE if not.
is_acyclic()Checks for the presence of a cycle in the graph.
Digraph$is_acyclic()Attempts to do a topological sort. If the sort does not contain
all vertexes, the digraph contains at least one cycle. This method
overrides is_acyclic in Graph.
TRUE if no cycles detected.
is_tree()Is the digraph's underlying graph a tree?
Digraph$is_tree()It is a tree if it is connected and acyclic.
TRUE if the underlying graph is a tree; FALSE
if not.
is_polytree()Is the digraph's underlying graph a polytree?
Digraph$is_polytree()It is a polytree if it is directed, connected and acyclic.
Because the object is a digraph (directed), this is synonymous with
tree.
TRUE if the underlying graph is a tree; FALSE
if not.
is_arborescence()Is the digraph an arborescence?
Digraph$is_arborescence()An arborescence is a tree with a single root and unique paths from the root.
TRUE if the digraph is an arborescence; FALSE
if not.
direct_successors()Find the direct successors of a node.
Digraph$direct_successors(v)vThe index vertex.
A list of nodes or an empty list if the specified node has no successors.
direct_predecessors()Find the direct predecessors of a node.
Digraph$direct_predecessors(v)vThe index vertex.
A list of nodes or an empty list if the specified node has no predecessors.
paths()Find all directed simple paths from source to target.
Digraph$paths(s, t)sSource node.
tTarget node.
In simple paths all vertexes are unique. Uses a recursive depth-first search algorithm.
A list of ordered node lists.
walk()Sequence of edges which join the specified path.
Digraph$walk(P, what = "edge")PA list of Nodes
whatOne of "edge" or "index".
A list of Edges for what = "edge" or a list of Edge
indices for what = "index".
as_DOT()Exports the digraph in DOT notation.
Digraph$as_DOT()Writes a representation of the digraph 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.
Digraph$clone(deep = FALSE)deepWhether to make a deep clone.
Encapsulates and provides methods for computation and checking of
directed graphs (digraphs). Inherits from class Graph.
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"). Kahn AB, Topological Sorting of Large Networks, Communications of the ACM, 1962;5:558-562, tools:::Rd_expr_doi("10.1145/368996.369025").