Type used to store the information needed to solve AMT-separation on the SCCs of a dgraph. More...

#include <sep_group.h>

Public Attributes
uint	size_graph
	Number of vertices in the dgraph.

uint	size_alpha
	Number of labels in the dgraph.

uint	nb_trees
	Maximal number of trees in the spanning forest (at most the number of SCCs in the dgraph).

int **	span_forest
	The spanning forest. For each state q and each letter a, span_forest[q][a] is the number of occurrences of a on the path from the root of the tree to q in the spanning tree associated to the SCC of q.

uint *	numtree
	Array indexed by the states of the dgraph. For each state q, num_tree[q] is the index of the tree of q in the spanning forest.

uint *	root
	Array index by the trees of the spanning forest. For each tree i, root[i] is the root of the tree.

dequeue **	dropped
	Indexed by the trees of the spanning forest. For each tree i dropped[i] is the list of all edges within the corresponding scc which are not used in the spanning tree.

Detailed Description

Type used to store the information needed to solve AMT-separation on the SCCs of a dgraph.

Stores a spanning forest. It contains at most one tree by SCC of the dgraph (this tree is a spanning tree of the SCC). Some SCCs can be skipped.

Remarks: Only partial information is stored for each spanning tree: span_forest[s][a] is the number of occurrences of the letter a on the path from the root of the tree to s.; For each tree i, the root of the tree is stored in root[i]. The dequeue dropped[i] contains the edges of the dgraph which are not used in the spanning tree. An edge (r,a,s) is represented by the integer r * size_alpha + a (this is a code since the graph is deterministic).

The documentation for this struct was generated from the following file:

Public Attributes