Towards the Automated Generation of Consistent, Diverse, Scalable, and Realistic Graph Models

Publication Reference

Title: Towards the Automated Generation of Consistent, Diverse, Scalable, and Realistic Graph Models
Authors: Dániel Varró, Oszkár Semeráth, Gábor Szárnyas, Ákos Horváth
Publication: Graph Transformation, Specifications, and Nets - In Memory of Hartmut Ehrig
Publisher: Springer
Series: Lecture Notes in Computer Science, vol 10800
Year: 2018
Pages: 285-312
DOI: https://doi.org/10.1007/978-3-319-75396-6_16

Abstract

This chapter presents a long-term research challenge on how to generate graph models specific to a domain which are consistent, diverse, scalable and realistic at the same time. The work provides foundations for a class of model generators along a refinement relation which operates over partial models with 3-valued representation and ensures that subsequently derived partial models preserve the truth evaluation of well-formedness constraints in the domain. The approach aims to address the need for automated model generation in various application scenarios including software tool certification, validation of cyber-physical systems, and benchmarking graph databases.

Contact

For more details, contact the authors:

• [email protected]
• [email protected]
• [email protected]
• [email protected]

Yakindu Metamodel

We have extraced a simplified (pruned) metamodel from the Yakindu Statechart tool, which only contains elements relevant to the state hierarchy and transitions (excluding namespace management and action language). The simplified metamodel is illustrated below:

The .ecore metamodel is downloadable from here.

Well-Formedness Constraints

We have implemented several well-formedness constraint as graph patterns from the actual validation rules of the Yakindu developement environment. Patterns annoted by @Constraint indicate an error pattern.

package hu.bme.mit.inf.dslreasoner.partialsnapshot_mavo.yakindu

import "hu.bme.mit.inf.yakindumm"

/////////
// Entry
/////////

pattern entryInRegion(r1 : Region, e1 : Entry) {
	Region.vertices(r1, e1);
}

@Constraint(severity="error", message="error", key = {r1})
pattern noEntryInRegion(r1 : Region) {
	neg find entryInRegion(r1, _);
}

@Constraint(severity="error", message="error", key = {r})
pattern multipleEntryInRegion(r : Region) {
	find entryInRegion(r, e1);
	find entryInRegion(r, e2);
	e1 != e2;
}

pattern transition(t : Transition, src : Vertex, trg : Vertex) {
	Transition.source(t, src);
	Transition.target(t, trg);
}

@Constraint(severity="error", message="error", key = {e})
pattern incomingToEntry(t : Transition, e : Entry) {
	find transition(t, _, e);
}

@Constraint(severity="error", message="error", key = {e})
pattern noOutgoingTransitionFromEntry(e : Entry) {
	neg find transition(_, e, _);
}

@Constraint(severity="error", message="error", key = {e})
pattern multipleTransitionFromEntry(e : Entry, t1 : Transition, t2: Transition) {
	Entry.outgoingTransitions(e,t1);
	Entry.outgoingTransitions(e,t2);
	t1!=t2;
}

/////////
// Exit
/////////

@Constraint(severity="error", message="error", key = {e})
pattern outgoingFromExit(t : Transition, e : Exit) {
	Exit.outgoingTransitions(e,t);
}

/////////
// Final
/////////

@Constraint(severity="error", message="error", key = {f})
pattern outgoingFromFinal(t : Transition, f : FinalState) {
	FinalState.outgoingTransitions(f,t);
}

/////////
// State vs Region
/////////

@Constraint(severity="error", message="error", key = {region})
pattern noStateInRegion(region: Region) {
	neg find StateInRegion(region,_);
}
pattern StateInRegion(region: Region, state: State) {
	Region.vertices(region,state);
}

/////////
// Choice
/////////

@Constraint(severity="error", message="error", key = {c})
pattern choiceHasNoOutgoing(c : Choice) {
	neg find transition(_, c, _);
}

@Constraint(severity="error", message="error", key = {c})
pattern choiceHasNoIncoming(c: Choice) {
	neg find transition(_, _, c);
}

Instance Models

We have generated several instance models using Alloy and VIATRA-Solver. The models are available here: https://github.com/FTSRG/publication-pages/tree/master/FMHE-Models

---

Tags: graph-models, model-generation, metamodel, viatra-solver, alloy, consistency, diversity, scalability, realistic-models, partial-models, well-formedness-constraints, yakindu, state-charts, publication