4.1.8.2. dg/DG

class mod.DG

The derivation graph class. A derivation graph is a directed multi-hypergraph \(\mathcal{H} = (V, E)\). Each hyperedge \(e\in E\) is thus an ordered pair \((e^+, e^-)\) of multisets of vertices, the sources and the targets. Each vertex is annotated with a graph, and each hyperedge is annotated with list of transformation rules. A derivation graph is constructed incrementally using a DGBuilder obtained from the build() function. When the obtained builder is destructed the derivation graph becomes locked and can no longer be modified.

__init__(*, labelSettings=LabelSettings(LabelType.String, LabelRelation.Isomorphism), graphDatabase=[], graphPolicy=IsomorphismPolicy.Check)

Create an empty unlocked derivation graph object.

Parameters:
  • labelSettings (LabelSettings) – defines which category the derivation graph object works in. All morphism calculations (monomorphism and isomorphism) are thus defined by the LabelType, while the LabelRelation is used for for monomorphism enumeration.

  • graphDatabase (list[Graph]) – an initial graph database. Any subsequently added or constructed graph for this object will be checked for isomorphism against the graph database.

  • graphPolicy (IsomorphismPolicy) – the policy for how the graphs of graphDatabase are checked for isomorphism against each other initially. Only use IsomorphismPolicy.TrustMe if you are absolutely sure that the graphs are unique up to isomorphism.

Raises:

LogicError if graphPolicy == IsomorphismPolicy.Check and two graphs in graphDatabase are different objects but represents isomorphic graphs.

Raises:

LogicError if there is a None in graphDatabase.

id

The unique instance id among all DG objects.

Type:

int

labelSettings

(Read-only) The label settings for the derivation graph.

Type:

LabelSettings

hasActiveBuilder

(Read-only) Whether build() has been called and the returned DGBuilder is still active.

Type:

bool

locked

(Read-only) Whether the derivation graph is locked or not.

Type:

bool

numVertices

(Read-only) The number of vertices in the derivation graph.

Type:

int

Raises:

LogicError if neither hasActiveBuilder nor isLocked.

vertices

(Read-only) An iterable of all vertices in the derivation graph.

Type:

DGVertexRange

Raises:

LogicError if neither hasActiveBuilder nor isLocked.

numEdges

(Read-only) The number of hyperedges in the derivation graph.

Type:

int

Raises:

LogicError if neither hasActiveBuilder nor isLocked.

edges

(Read-only) An iterable of all hyperedges in the derivation graph.

Type:

DGEdgeRange

Raises:

LogicError if neither hasActiveBuilder nor isLocked.

findVertex(g)
Parameters:

g (Graph) – the graph to find a vertex which has it associated.

Returns:

a vertex descriptor for which the given graph is associated, or a null descriptor if no such vertex exists.

Return type:

DGVertex

Raises:

LogicError if neither hasActiveBuilder nor isLocked.

Raises:

LogicError if g is None.

findEdge(sources, targets)
findEdge(sourceGraphs, targetGraphs)
Parameters:
  • sources (list[DGVertex]) – the list of source vertices the resulting hyperedge must have.

  • targets (list[DGVertex]) – the list of targets vertices the resulting hyperedge must have.

  • sourceGraphs (list[Graph]) – the list of graphs that must be associated with the source vertices the resulting hyperedge must have.

  • targetGraphs (list[Graph]) – the list of graphs that must be associated with the targets vertices the resulting hyperedge must have.

Returns:

a hyperedge with the given sources and targets. If no such hyperedge exists in the derivation graph then a null edge is returned. In the second version, the graphs are put through findVertex() first.

Return type:

DGHyperEdge

Raises:

LogicError if a vertex descriptor is null, or does not belong to the derivation graph.

Raises:

LogicError if neither hasActiveBuilder nor isLocked.

build()
Returns:

an RAII-style object which can be used to construct the derivation graph. It can be used as a context manager in a with-statement (see the documentation of DGBuilder).

Return type:

DGBuilder

Raises:

LogicError if the DG already has an active builder (see hasActiveBuilder).

Raises:

LogicError if the DG is locked (see locked).

graphDatabase

All graphs known to the derivation graph.

Type:

list[Graph]

products

The subset of the vertex graphs which were discovered by the calculation.

Type:

list[Graph]

print(printer=DGPrinter(), data=None)

Print the derivation graph in style of a hypergraph. The appearance and structure of the visualisation can optionally be configured by giving a DG printer and/or data object.

Parameters:
  • printer (DGPrinter) – the printer to use governing the appearance.

  • data (DGPrintData) – the extra data to use encoding the structure of the graph.

Returns:

the name of the PDF-file that will be compiled in post-processing and the name of the coordinate tex-file used.

Return type:

tuple[str, str]

printNonHyper()

Print the derivation graph in style of a digraph, where each edge represents a hyperedge. Each vertex in the depiction then represents a multiset of vertices in the hypergraph.

Returns:

the name of the PDF-file that will be compiled in post-processing.

Return type:

str

dump()
dump(filename)

Exports the derivation graph to a file, including associated graphs and rules. Use load() or DGBuilder.load() to import the derivation graph again.

Parameters:

filename (str) –

the name of the file to save the dump to. If non is given an auto-generated name in the out/ folder is used. If an empty string is given, it is treated as if non is given.

Note

The filename is being used literally, i.e., it is not being prefixed according to the current script location as input filenames are.

Returns:

the filename of the exported derivation graph.

Return type:

str

Raises:

LogicError if the DG is not locked.

Raises:

LogicError if the target file can not be opened.

listStats()

Lists various statistics for the derivation graph.

Raises:

LogicError if the DG has not been calculated.

static load(graphDatabase, ruleDatabase, f, graphPolicy=IsomorphismPolicy.Check, verbosity=2)

Load a derivation graph dump as a locked object. Use DGBuilder.load() to load a dump into a derivation graph under construction.

This is done roughly by making a DG with the given graphDatabase and graphPolicy. The label settings are retrieved from the dump file. Vertices with graphs and hyperedges with rules are then added from the dump. Any graph in the dump which is isomorphic to a given graph is replaced by the given graph. The same procedure is done for the rules. If a graph/rule is not found in the given lists, a new object is instantiated and used. In the end the derivation graph is locked.

Note

If the dump to be loaded was made by version 0.10 or earlier, it does not contain the full rules but only the rule name. It is then crucial that the names of the given rules match with those used to create the dump in the first place.

See dg::DG::load() for an explanation of the verbosity levels.

Parameters:
Returns:

the loaded derivation graph.

Return type:

DG

Raises:

the same exceptions __init__() raises related to graphDatabase and graphPolicy.

Raises:

LogicError if there is a None in ruleDatabase.

Raises:

InputError if the file can not be opened or its content is bad.

mod.diffDGs(dg1, dg2)

Compare two derivation graphs and lists the difference. This is not a general isomorphism check; two vertices are equal if they have the same graph attached. Edges are equal if the head and tail sets are equal and if the attached rule is the same.

Parameters:
  • dg1 (DG) – the first derivation graph.

  • dg2 (DG) – the second derivation graph.