# 2.2.4. DG.h¶

## 2.2.4.1. Class DG¶

class DG

The main derivation graph class. A derivation graph is a directed hypergraph $$\mathcal{H} = (V, E)$$. Each vertex is annotated with a graph, and each hyperedge is annotated with a transformation rule. A derivation graph can either be calculated from a strategy or loaded from external data.

### 2.2.4.1.1. Synopsis¶

struct DG {
DG(const DG&) = delete;
DG &operator=(const DG&) = delete;
public:
class Vertex;
class HyperEdge;
class VertexIterator;
class VertexRange;
class EdgeIterator;
class EdgeRange;
class InEdgeIterator;
class InEdgeRange;
class OutEdgeIterator;
class OutEdgeRange;
class SourceIterator;
class SourceRange;
class TargetIterator;
class TargetRange;
class RuleIterator;
class RuleRange;
private:
DG(std::unique_ptr<lib::DG::NonHyper> dg);
public:
~DG();
std::size_t getId() const;
friend std::ostream &operator<<(std::ostream &s, const DG &dg);
const lib::DG::NonHyper &getNonHyper() const;
const lib::DG::Hyper &getHyper() const;
public: // hypergraph interface
std::size_t numVertices() const;
VertexRange vertices() const;
std::size_t numEdges() const;
EdgeRange edges() const;
public: // searching for vertices and hyperedges
Vertex findVertex(std::shared_ptr<Graph> g) const;
HyperEdge findEdge(const std::vector<Vertex> &sources, const std::vector<Vertex> &targets) const;
HyperEdge findEdge(const std::vector<std::shared_ptr<Graph> > &sources, const std::vector<std::shared_ptr<Graph> > &targets) const;
public:
void calc();
const std::set<std::shared_ptr<Graph>, GraphLess> &getGraphDatabase() const;
const std::vector<std::shared_ptr<Graph> > &getProducts() const;
void print(const DGPrintData &data, const DGPrinter &printer) const;
std::string dump() const;
void list() const;
void listStats() const;
// :throws: :class:LogicError if the DG has not been calculated or if the DG is not created from strategies.
std::vector<std::shared_ptr<Graph> > getStratOutputSubset() const;
private:
struct Pimpl;
std::unique_ptr<Pimpl> p;
public:
static std::shared_ptr<DG> derivations(const std::vector<Derivation> &derivations);
static std::shared_ptr<DG> abstract(const std::string &specification);
static std::shared_ptr<DG> ruleComp(const std::vector<std::shared_ptr<Graph> > &graphs,
std::shared_ptr<DGStrat> strategy);
static std::shared_ptr<DG> dumpImport(const std::vector<std::shared_ptr<Graph> > &graphs, const std::vector<std::shared_ptr<Rule> > &rules, const std::string &file);
static void diff(std::shared_ptr<DG> dg1, std::shared_ptr<DG> dg2);
};

### 2.2.4.1.2. Details¶

std::size_t getId() const
Returns: the instance identifier for the object.
const lib::DG::NonHyper &getNonHyper() const
const lib::DG::Hyper &getHyper() const
Returns: the internal data structures of the derivation graph.
std::size_t numVertices() const
Returns: the number of vertices in the derivation graph.
VertexRange vertices() const
Returns: a range of all vertices in the derivation graph.
std::size_t numEdges() const
Returns: the number of edges in the derivation graph.
EdgeRange edges() const
Returns: a range of all edges in the derivation graph.
Vertex findVertex(std::shared_ptr<Graph> g) const
Returns: a vertex descriptor for which the given graph is associated, or a null descriptor if no such vertex exists.
HyperEdge findEdge(const std::vector<Vertex> &sources, const std::vector<Vertex> &targets) const
HyperEdge findEdge(const std::vector<std::shared_ptr<Graph>> &sources, const std::vector<std::shared_ptr<Graph>> &targets) const
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. LogicError if a vertex descriptor is null, or does not belong to the derivation graph.
void calc()

Compute the derivation graph.

const std::set<std::shared_ptr<Graph>, GraphLess> &getGraphDatabase() const
Returns: the set of all graphs created by the derivation graph, and all graphs given when constructed.
const std::vector<std::shared_ptr<Graph>> &getProducts() const
Returns: the list of new graphs discovered by the derivation graph.
void print(const DGPrintData &data, const DGPrinter &printer) const

Print the derivation graph in style of a hypergraph.

Throws: LogicError if the print data is not for this DG.
std::string dump() const

Exports the derivation graph to a text file, which can be importetet.

Returns: the name of the file with the exported data. LogicError if the DG has not been calculated.
void list() const

Output information on the calculation of the derivation graph. For strategy-based calculations, this outputs the expression tree.

void listStats() const

Output various stats of the derivation graph.

Throws: LogicError if the DG has not been calculated.
static std::shared_ptr<DG> derivations(const std::vector<Derivation> &derivations)

Create a derivation graph from a list of Derivation.

static std::shared_ptr<DG> abstract(const std::string &specification)

Create a derivation graph from an abstract description according to the following grammar.

description ::=  derivation { derivation }
derivation  ::=  side ("->" | "<=>") side
side        ::=  term { "+" term }
term        ::=  [ unsignedInt ] identifier
static std::shared_ptr<DG> ruleComp(const std::vector<std::shared_ptr<Graph>> &graphs, std::shared_ptr<DGStrat> strategy)

Initialize a derivation graph with a DGStrat and an initial graph database. Any derived graph isomorphic to a given graph is replaced by the given graph.

static std::shared_ptr<DG> dumpImport(const std::vector<std::shared_ptr<Graph>> &graphs, const std::vector<std::shared_ptr<Rule>> &rules, const std::string &file)

Load a derivation graph 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, however only using the name of the rule for comparison.

static void diff(std::shared_ptr<DG> dg1, std::shared_ptr<DG> 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.

## 2.2.4.2. Class DerivationRef¶

class DerivationRef

The class represents a reference to a derivation in a derivation graph. A reference may be invalid.

### 2.2.4.2.1. Synopsis¶

class DerivationRef {
friend class lib::DG::Hyper;
DerivationRef(unsigned int id, std::shared_ptr<DG> dg);
public:
DerivationRef();
DerivationRef(DG::HyperEdge e);
operator DG::HyperEdge() const;
friend std::ostream &operator<<(std::ostream &s, const DerivationRef &d);
unsigned int getId() const;
std::shared_ptr<DG> getDG() const;
bool isValid() const;
Derivation operator*() const;
void print(const GraphPrinter &printer, const std::string &matchColour) const;
bool operator<(const DerivationRef &other) const;
friend bool operator==(const DerivationRef &a, const DerivationRef &b) {
return a.id == b.id && a.dg == b.dg;
}
private:
unsigned int id;
std::shared_ptr<DG> dg;
};

### 2.2.4.2.2. Details¶

DerivationRef()

Constructor for an invalid reference.

unsigned int getId() const
Returns: the id of the derivation.
std::shared_ptr<DG> getDG() const
Returns: the derivation graph the reference is pointing into.
bool isValid() const
Returns: true iff the reference is valid.
Derivation operator*() const
Returns: the derivation represented by the reference.
void print(const GraphPrinter &printer, const std::string &matchColour) const

Print the derivation pointed to by the derivation reference. All possible Double-Pushout diagrams for the derivation are printed. The matchColour must be a valid colour for TikZ, which is applied to the rule and its image in the bottom span.