Graph¶

class Graph¶

A Graph class to perform automatic differentiation with weighted finite-state acceptors (WFSAs) and transducers (WFSTs).

Example:

Graph graph;
graph.addNode(true); // Add a start node
graph.addNode(); // Add an internal node
graph.addNode(false, true); // Add an accept node

// Add an arc from node 0 to 1 with ilabel 0, olabel 1 and weight 2.0
graph.addArc(0, 1, 0, 1, 2.0);

// Add an arc from node 1 to 2 with ilabel 1, olabel 2 and weight 1.0
graph.addArc(1, 2, 1, 2, 1.0);

// Compute the Viterbi score of the graph
auto score = viterbiScore(graph);

print(score); // Print the score graph to std out

backward(score); // Compute the gradient
graph.grad(); // Access the gradient
graph.zeroGrad(); // Clear the gradient

All operations are in the log or tropical semirings. The default score for an arc is 0 (e.g. the multiplicative identity) and the additive identity is -infinity. Path scores are accumulated with log-sum-exp or max operations and the score for a path is accumulated with addition.

Graph-level Methods¶

Graph(bool calcGrad = true)¶

Construct a Graph.

Parameters: calcGrad – Whether or not to compute gradients with respect to this graph when calling gtn::backward.

int addNode(bool start = false, bool accept = false)¶

Adds a node to the graph.

Parameters

start – Indicates if the node is a starting node.
accept – Indicates if the node is an accepting node.

Returns

The id of the node (used for e.g. adding arcs).

size_t addArc(size_t srcNode, size_t dstNode, int label)¶

Add a arc between two nodes.

This assumes the graph is an acceptor, the input label on the arc is the same as the output label.

Parameters

srcNode – The id of the source node.
dstNode – The id of the destination node.
label – The arc label.

Returns

The id of the added arc.

size_t addArc(size_t srcNode, size_t dstNode, int ilabel, int olabel, float weight = 0.0)¶

Add a arc between two nodes.

Parameters

srcNode – The id of the source node.
dstNode – The id of the destination node.
ilabel – The arc input label.
olabel – The arc output label.
weight – The arc weight.

Returns

The id of the added arc.

inline size_t numArcs() const¶: The number of arcs in the graph.

inline size_t numNodes() const¶: The number of nodes in the graph.

inline size_t numStart() const¶: The number of starting nodes in the graph.

inline size_t numAccept() const¶: The number of accepting nodes in the graph.

float item() const¶: Get the weight on a single arc graph.

static Graph deepCopy(const Graph &src)¶

A deep copy of a graph src which is not recorded in the autograd tape.

For a version which is recorded in the autograd tape see gtn::clone.

void arcSort(bool olabel = false)¶

Sort the arcs entering and exiting a node in increasing order by arc in label or out label if olabel == true.

This function is intended to be used prior to calls to intersect and compose to improve the efficiency of the algorithm.

inline void markArcSorted(bool olabel = false)¶

Mark a graph’s arcs as sorted.

If olabel == false then the graph will be marked as sorted by arc input labels, otherwise it will be marked as sorted by the arc output labels.

inline bool ilabelSorted() const¶: Check if the arcs entering and exiting every node are sorted by input label.

inline bool olabelSorted() const¶: Check if the arcs entering and exiting every node are sorted by output label.

inline float *weights()¶

Returns an array of weights from a graph.

The array will contain Graph::numArcs() elements.

inline const float *weights() const¶: A const version of Graph::weights.

void setWeights(const float *weights)¶

Set the arc weights on a graph.

The weights array must have Graph::numArcs() elements.

void labelsToArray(int *out, bool ilabel = true)¶

Extract an array of labels from a graph.

The array should have space for Graph::numArcs() elements.

Parameters

out – [out] A pointer to the buffer to populate with labels.
ilabel – [in] Retreive ilabels if true, otherwise gets olabels.

std::vector<int> labelsToVector(bool ilabel = true)¶

Extract a std::vector of labels from the graph.

See Graph::labelsToArray.

Autograd Methods¶

void addGrad(std::vector<float> &&other)¶

Add a std::vector of gradients to the gradient graph weights without making a copy of other.

The Graph::addGrad methods are intended for use by the autograd. This overload is used with an rvalue or std::move to avoid an extra copy:

graph.addGrad(std::move(graphGrad));

void addGrad(const std::vector<float> &other)¶

Add a std::vector of gradients to the gradient graph weights.

The Graph::addGrad methods are intended for use by the autograd.

void addGrad(const Graph &other)¶

Add a Graph of gradients to the gradient graph.

The Graph::addGrad methods are intended for use by the autograd.

inline bool calcGrad() const¶: Check if a graph requires a gradient.

inline bool isGradAvailable() const¶: Check if a graph’s gradient is computed.

Graph &grad()¶: Get the gradient graph.

const Graph &grad() const¶: A const version of Graph::grad.

void setCalcGrad(bool calcGrad)¶: Specify if the gradient for this graph should be computed.

void zeroGrad()¶: Clear the graph’s gradients.

std::uintptr_t id()¶

A unique identifier for a graph.