Digraph: A directed graph
In rdecision: Decision Analytic Modelling in Health Economics
Digraph R Documentation
A directed graph
Description
An R6 class representing a digraph (a directed graph).
Details
Encapsulates and provides methods for computation and checking of
directed graphs (digraphs). Inherits from class Graph.
Value
A GML stream as a character vector.
Super class
rdecision::Graph -> Digraph
Methods
Public methods
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
Inherited methods
rdecision::Graph$degree()rdecision::Graph$edge_along()rdecision::Graph$edge_at()rdecision::Graph$edge_index()rdecision::Graph$edge_label()rdecision::Graph$edges()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()rdecision::Graph$vertex_label()rdecision::Graph$vertexes()
Method new()
Create a new Digraph object from sets of nodes and
edges.
Usage
Digraph$new(V, A)
Arguments
VA list of Nodes.
AA list of Arrows.
Returns
A Digraph object.
Method digraph_adjacency_matrix()
Compute the adjacency matrix for the digraph.
Usage
Digraph$digraph_adjacency_matrix(boolean = FALSE)
Arguments
booleanIf TRUE, the adjacency matrix is logical, each
cell is {FALSE,TRUE}.
Details
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).
Returns
A square integer 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.
Method digraph_incidence_matrix()
Compute the incidence matrix for the digraph.
Usage
Digraph$digraph_incidence_matrix()
Details
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.
Returns
The incidence matrix of integers.
Method topological_sort()
Topologically sort the vertexes in the digraph.
Usage
Digraph$topological_sort()
Details
Uses Kahn's algorithm (Kahn, 1962).
Returns
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.
Method is_connected()
Test whether the graph is connected.
Usage
Digraph$is_connected()
Details
For digraphs this will always return FALSE because
connected is not defined. Function weakly_connected
calculates whether the underlying graph is connected.
Returns
TRUE if connected, FALSE if not.
Method is_weakly_connected()
Test whether the digraph is weakly connected, i.e. if the
underlying graph is connected.
Usage
Digraph$is_weakly_connected()
Returns
TRUE if connected, FALSE if not.
Method is_acyclic()
Checks for the presence of a cycle in the graph.
Usage
Digraph$is_acyclic()
Details
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.
Returns
TRUE if no cycles detected.
Method is_tree()
Is the digraph's underlying graph a tree?
Usage
Digraph$is_tree()
Details
It is a tree if it is connected and acyclic.
Returns
TRUE if the underlying graph is a tree; FALSE
if not.
Method is_polytree()
Is the digraph's underlying graph a polytree?
Usage
Digraph$is_polytree()
Details
It is a polytree if it is directed, connected and acyclic.
Because the object is a digraph (directed), this is synonymous with
tree.
Returns
TRUE if the underlying graph is a tree; FALSE
if not.
Method is_arborescence()
Is the digraph an arborescence?
Usage
Digraph$is_arborescence()
Details
An arborescence is a tree with a single root and unique
paths from the root.
Returns
TRUE if the digraph is an arborescence; FALSE
if not.
Method direct_successors()
Find the direct successors of a node.
Usage
Digraph$direct_successors(v)
Arguments
vThe index vertex (a scalar; does not accept a vector of nodes).
Returns
A list of Nodes or an empty list if the specified
node has no successors.
Method direct_predecessors()
Find the direct predecessors of a node.
Usage
Digraph$direct_predecessors(v)
Arguments
vThe index vertex (a scalar; does not accept an index of nodes).
Returns
A list of Nodes or an empty list if the specified
node has no predecessors.
Method arrow_source()
Find the node that is the source of the given arrow.
Usage
Digraph$arrow_source(a)
Arguments
aAn arrow (directed edge), which must be in the digraph.
Details
The source node is a property of the arrow, not the digraph of
which it is part, hence the canonical method for establishing the source
node of an arrow is via method $source of an Arrow object.
This function is provided for convenience when iterating the arrows of a
digraph. It raises an error if the arrow is not in the graph. It
returns the index of the source node, which is a property of the graph;
the node object itself may be retrieved using the $vertex_at
method of the graph.
Returns
Index of the source node of the specified edge.
Method arrow_target()
Find the node that is the target of the given arrow.
Usage
Digraph$arrow_target(a)
Arguments
aAn arrow (directed edge), which must be in the digraph.
Details
The target node is a property of the arrow, not the digraph of
which it is part, hence the canonical method for establishing the target
node of an arrow is via method $target of an $Arrow object.
This function is provided for convenience when iterating the arrows of a
digraph. It raises an error if the arrow is not in the graph. It
returns the index of the target node, which is a property of the graph;
the node itself may be retrieved using the $vertex_at method
of the graph.
Returns
Index of the target node of the specified edge.
Method paths()
Find all directed simple paths from source to target.
Usage
Digraph$paths(s, t)
Arguments
sSource node.
tTarget node.
Details
In simple paths all vertexes are unique. Uses a recursive
depth-first search algorithm.
Returns
A list of ordered node lists.
Method walk()
Sequence of edges which join the specified path.
Usage
Digraph$walk(P, what = "edge")
Arguments
PA list of Nodes
whatOne of "edge" or "index".
Returns
A list of Edges for what = "edge" or a list of Edge
indices for what = "index".
Method as_DOT()
Exports the digraph in DOT notation.
Usage
Digraph$as_DOT(rankdir = "LR", width = 7, height = 7)
Arguments
rankdirOne of "LR" (default), "TB", "RL" or "BT".
widthof the drawing, in inches
heightof the drawing, in inches
Details
Writes a representation of the digraph in the
graphviz DOT language
(https://graphviz.org/doc/info/lang.html) for drawing with one
of the graphviz tools, including dot (Gansner, 1993).
This option is recommended if it is desired to rapidly plot a graph;
however it gives limited control over details of the appearance. In
addition, the appearance may vary between calls if the node order changes
(specifically, if there is no Hamiltonian path). For greater control over
the appearance of a graph, use the as_gml function and manipulate
the graph using igraph or DiagrammeR; please refer to the vignettes for
examples.
Returns
A character vector. Intended for passing to writeLines
for saving as a text file.
Method as_gml()
Exports the digraph as a Graph Modelling Language (GML)
stream.
Usage
Digraph$as_gml()
Details
Intended to work with the igraph or DiagrammeR packages, which
are able to import GML files.
Method clone()
The objects of this class are cloneable with this method.
Usage
Digraph$clone(deep = FALSE)
Arguments
deepWhether to make a deep clone.
Author(s)
Andrew Sims andrew.sims@newcastle.ac.uk
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, \Sexpr[results=rd]{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, \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1201/b16132")}.
Kahn AB, Topological Sorting of Large Networks,
Communications of the ACM,
1962;5:558-562, \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1145/368996.369025")}.
rdecision documentation built on April 3, 2025, 6:09 p.m.
R Package Documentation
Browse R Packages
We want your feedback!
Note that we can't provide technical support on individual packages. You should contact the package authors for that.
| Digraph | R Documentation |
A directed graph
Description
An R6 class representing a digraph (a directed graph).
Details
Encapsulates and provides methods for computation and checking of
directed graphs (digraphs). Inherits from class Graph.
Value
A GML stream as a character vector.
Super class
rdecision::Graph -> Digraph
Methods
Public methods
Inherited methods
rdecision::Graph$degree()rdecision::Graph$edge_along()rdecision::Graph$edge_at()rdecision::Graph$edge_index()rdecision::Graph$edge_label()rdecision::Graph$edges()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()rdecision::Graph$vertex_label()rdecision::Graph$vertexes()
Method new()
Create a new Digraph object from sets of nodes and
edges.
Usage
Digraph$new(V, A)
Arguments
VA list of Nodes.
AA list of Arrows.
Returns
A Digraph object.
Method digraph_adjacency_matrix()
Compute the adjacency matrix for the digraph.
Usage
Digraph$digraph_adjacency_matrix(boolean = FALSE)
Arguments
booleanIf
TRUE, the adjacency matrix is logical, each cell is{FALSE,TRUE}.
Details
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).
Returns
A square integer 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.
Method digraph_incidence_matrix()
Compute the incidence matrix for the digraph.
Usage
Digraph$digraph_incidence_matrix()
Details
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.
Returns
The incidence matrix of integers.
Method topological_sort()
Topologically sort the vertexes in the digraph.
Usage
Digraph$topological_sort()
Details
Uses Kahn's algorithm (Kahn, 1962).
Returns
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.
Method is_connected()
Test whether the graph is connected.
Usage
Digraph$is_connected()
Details
For digraphs this will always return FALSE because
connected is not defined. Function weakly_connected
calculates whether the underlying graph is connected.
Returns
TRUE if connected, FALSE if not.
Method is_weakly_connected()
Test whether the digraph is weakly connected, i.e. if the underlying graph is connected.
Usage
Digraph$is_weakly_connected()
Returns
TRUE if connected, FALSE if not.
Method is_acyclic()
Checks for the presence of a cycle in the graph.
Usage
Digraph$is_acyclic()
Details
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.
Returns
TRUE if no cycles detected.
Method is_tree()
Is the digraph's underlying graph a tree?
Usage
Digraph$is_tree()
Details
It is a tree if it is connected and acyclic.
Returns
TRUE if the underlying graph is a tree; FALSE
if not.
Method is_polytree()
Is the digraph's underlying graph a polytree?
Usage
Digraph$is_polytree()
Details
It is a polytree if it is directed, connected and acyclic.
Because the object is a digraph (directed), this is synonymous with
tree.
Returns
TRUE if the underlying graph is a tree; FALSE
if not.
Method is_arborescence()
Is the digraph an arborescence?
Usage
Digraph$is_arborescence()
Details
An arborescence is a tree with a single root and unique paths from the root.
Returns
TRUE if the digraph is an arborescence; FALSE
if not.
Method direct_successors()
Find the direct successors of a node.
Usage
Digraph$direct_successors(v)
Arguments
vThe index vertex (a scalar; does not accept a vector of nodes).
Returns
A list of Nodes or an empty list if the specified node has no successors.
Method direct_predecessors()
Find the direct predecessors of a node.
Usage
Digraph$direct_predecessors(v)
Arguments
vThe index vertex (a scalar; does not accept an index of nodes).
Returns
A list of Nodes or an empty list if the specified node has no predecessors.
Method arrow_source()
Find the node that is the source of the given arrow.
Usage
Digraph$arrow_source(a)
Arguments
aAn arrow (directed edge), which must be in the digraph.
Details
The source node is a property of the arrow, not the digraph of
which it is part, hence the canonical method for establishing the source
node of an arrow is via method $source of an Arrow object.
This function is provided for convenience when iterating the arrows of a
digraph. It raises an error if the arrow is not in the graph. It
returns the index of the source node, which is a property of the graph;
the node object itself may be retrieved using the $vertex_at
method of the graph.
Returns
Index of the source node of the specified edge.
Method arrow_target()
Find the node that is the target of the given arrow.
Usage
Digraph$arrow_target(a)
Arguments
aAn arrow (directed edge), which must be in the digraph.
Details
The target node is a property of the arrow, not the digraph of
which it is part, hence the canonical method for establishing the target
node of an arrow is via method $target of an $Arrow object.
This function is provided for convenience when iterating the arrows of a
digraph. It raises an error if the arrow is not in the graph. It
returns the index of the target node, which is a property of the graph;
the node itself may be retrieved using the $vertex_at method
of the graph.
Returns
Index of the target node of the specified edge.
Method paths()
Find all directed simple paths from source to target.
Usage
Digraph$paths(s, t)
Arguments
sSource node.
tTarget node.
Details
In simple paths all vertexes are unique. Uses a recursive depth-first search algorithm.
Returns
A list of ordered node lists.
Method walk()
Sequence of edges which join the specified path.
Usage
Digraph$walk(P, what = "edge")
Arguments
PA list of Nodes
whatOne of "edge" or "index".
Returns
A list of Edges for what = "edge" or a list of Edge
indices for what = "index".
Method as_DOT()
Exports the digraph in DOT notation.
Usage
Digraph$as_DOT(rankdir = "LR", width = 7, height = 7)
Arguments
rankdirOne of "LR" (default), "TB", "RL" or "BT".
widthof the drawing, in inches
heightof the drawing, in inches
Details
Writes a representation of the digraph in the
graphviz DOT language
(https://graphviz.org/doc/info/lang.html) for drawing with one
of the graphviz tools, including dot (Gansner, 1993).
This option is recommended if it is desired to rapidly plot a graph;
however it gives limited control over details of the appearance. In
addition, the appearance may vary between calls if the node order changes
(specifically, if there is no Hamiltonian path). For greater control over
the appearance of a graph, use the as_gml function and manipulate
the graph using igraph or DiagrammeR; please refer to the vignettes for
examples.
Returns
A character vector. Intended for passing to writeLines
for saving as a text file.
Method as_gml()
Exports the digraph as a Graph Modelling Language (GML) stream.
Usage
Digraph$as_gml()
Details
Intended to work with the igraph or DiagrammeR packages, which are able to import GML files.
Method clone()
The objects of this class are cloneable with this method.
Usage
Digraph$clone(deep = FALSE)
Arguments
deepWhether to make a deep clone.
Author(s)
Andrew Sims andrew.sims@newcastle.ac.uk
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, \Sexpr[results=rd]{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, \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1201/b16132")}.
Kahn AB, Topological Sorting of Large Networks, Communications of the ACM, 1962;5:558-562, \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1145/368996.369025")}.
R Package Documentation
Browse R Packages
We want your feedback!
Note that we can't provide technical support on individual packages. You should contact the package authors for that.
Embedding an R snippet on your website
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.