Digraph {rdecision}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.

Super class

rdecision::Graph -> Digraph

Methods

Public methods

Inherited methods

Method new()

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

Usage
Digraph$new(V, A)
Arguments
V

A list of Nodes.

A

A 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
boolean

If 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
v

The 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
v

The 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
a

An 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
a

An 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
s

Source node.

t

Target 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
P

A list of Nodes

what

One 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
rankdir

One of "LR" (default), "TB", "RL" or "BT".

width

of the drawing, in inches

height

of 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). If all nodes have labels, these are used in the graph, otherwise the labels are the node indices.

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
Digraph$clone(deep = FALSE)
Arguments
deep

Whether 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, 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.

Kahn AB, Topological Sorting of Large Networks, Communications of the ACM, 1962;5:558-562, doi:10.1145/368996.369025.

[Package rdecision version 1.2.1 Index]