While text variant graphs are increasingly frequently used for the visualization of a text transmitted in multiple versions, the graph is also a very appropriate model for the querying and transformation of such a text in the course of producing a critical edition. This article describes the algorithms used in the StemmaREST repository for variant text traditions. The variant graph has, in various forms, seen a steady uptake in use within the textual criticism community since its initial proposal by Schmidt and Colom1b7.][ It presents a compact yet expressive way to take in the variation across divergent copies of the same text, where (in most implementations since the 昀椀rst) the readings, or text tokens, form the nodes of the graph and the witness pathways are indicated along the edges. Such a data structure can, moreover, easily be expressed in a TEI-conformant form when divergent witness pathways are encoded using the double endpoint attachment method of critical apparatus expressio1n8].[ While variant graphs has o昀琀en been used simply as a means of representation and visualization, there has been some interest in the last ten years in using the graph as a site of user interaction with the text, both within the Stemmaweb project6][ and also as a feature of the TRAViz library 1[4]. These interactions can include the manual correction of a machineproduced collation, annotation of the text within that collation, or even the establishment of a canonical text and recording of emendations that an editor would make. When variant graphs are used to interact with and even edit a text tradition, however, it is all too easy for logical mistakes to be introduced into the data structure. The problem of so昀琀ware support to ensure the correctness and consistency of an encoded critical text has been discussed by Burghardt in the TEI context8[]; a similar problem can easily arise in the context of the variant graph. The most damaging sort of mistake is that which alters the 'ground truth': that is, it causes the construction of versions of individual witness texts from the collation data
that are not the same as the versions that went into its making. We might refer to this as a corrupted collation.
The purpose of this paper is to give a formal de昀椀nition of one variant graph model, describe its logical and mathematical properties, and provide some well-de昀椀ned algorithms for how this graph may be interacted with and modi昀椀ed, in order to provide the functionality that scholarly editors would expect to have while avoiding the production of corrupted collations. The model described in this paper is implemented in the StemmaREST reposito1riyn, use via the Stemmaweb tools for a variety of critical edition projects since 2021; many of the concepts and algorithms discussed have their roots in the Perl librTaerxyt::Tradition,2 which was the predecessor to StemmaREST.
Most models for variant graphs are broadly similar. A昀琀er their initial description by Schmidt
and Colomb, the most signi昀椀cant change in their conception and use came around 2010 with
the adoption of the variant graph in the CollateX tool: unlike in the prior model, where all
information was carried along the edges of the graph, the CollateX graph moved the reading
text to the vertices and le昀琀 only the witness labels on the edges1.[
Let us 昀椀rst brie昀氀y outline the StemmaREST data model.3 A Tradition may possess two or moreWitnesses, which record information about di昀erent manuscript versions of a given text. The Tradition also possesses distincStections; these sections have a canonical order and, taken together, comprise the text. EachSection contains a single text collation composed of Readings, the sequences in which they occur, and information on how they arreelated to each other. Areading is a piece of text that is found in one or more of thWeitnesses. It is frequently a single word, but can be a sequence of words or even a fragment of a word, depending on the needs of the editor. AReading object, then, is a transcription of its text as well as the metadata that is needed to situate it (e.g. a normalized or canonical form, the language it is in, whether it is the form that will be adopted in the edited text, and so on.) The Reading objects occur in somesequence in each witness, and may be related to each other insofar as they are variants of each other.
It is the structure and properties of the variant graph — that is, the subgraph whose vertices are Reading nodes and whose edges aresequence edges, and how this interacts with reading relations — that interests us here. In all versions of the variant graph to date, it is modelled as 1https://github.com/DHUniWien/tradition_repo 2https://github.com/tla/stemmatology 3An OWL-based version of this model was also recently presented at DH 2023; se2e].[ a connected, rooted, directed acyclic graph (CRDAG). That is: • Connected — the graph contains no disjoint subgroups. • Rooted — there is exactly one vertex with an in-degree of zero; this is the origin, or root. • Directed — all edges have an explicit direction. Paths through the graph must respect this direction.
• Acyclic — there is no path in the graph in which a node is visited twice.
In the StemmaREST variant graph, we refer to the root as thsetart reading; this is a special case of Reading. In addition to the CRDAG constraints, we add a constraint, which is that the variant graph has a single terminal vertex for all possible paths. This is another special case of Reading known as the end reading.
When we model variant text into a graph, we must also deal with the issue of witness layers. It quite frequently occurs in textual scholarship that a single witness can carry multiple versions, or layers, of the text in places; this is most easily seen when the scribe has made a correction to his or her own text. Since these corrections can o昀琀en have some signi昀椀cance when it comes to understanding the transmission history of the text, we must account for the fact that a single witness might give rise to multiple paths through the graph. In order to conceptualize this, we posit that every witness has abase layer which is a single complete version of the text; the witness also has zero or more additional layers that represent alternative versions of speci昀椀c subsets of that text. Formally, we may state the following: 1. Let be a variant graph consisting ofReading nodes as vertices andsequence edges connecting them. Let and , respectively, denote the initial vertex and terminal vertex (start and end reading) of all paths i n. As described above, is a connected, rooted, directed acyclic graph.
= . two ∈ ings ∈ (), 2. Let
be a manuscript witness; le t be a single ordered set of readin g∈s () represents the text carried in the base layer of . A single non-cyclical pat h must exist from the start readin g to the end reading whose set of inner vertices which = ... whose inner set of vertice s
= . 4. is the set of all path s and for a given set of witnesses. 3. For every additional lay erin , there exists one or more disjoint ordered sets of read ∉ ; moreover, a single non-cyclical pat h must exist between some
This de昀椀nition has some overlap with the ‘multi-version document’ (MVD) of Schmidt and Colomb, especially the construction of start and end readings and the constraint that a witness text must comprise a single unbroken path from start to end. The MVD model, however, did not speci昀椀cally describe ways to account for separate layers in individual witnesses. Of note for the StemmaREST model is that witness layers are not necessarily regarded as full and separate versions of the text. Consider, for example, a manuscript that has multiple scribal corrections in the original hand; typically, where the pre-corrected state of the text can be deciphered, it will be represented in a critical apparatus with the notation ‘a.acn.’t(e correctionem). It would be possible (and has been done from time to time) to imagine a witness layer that runs from the beginning to the end of the text, taking none of the corrections into account, and refer to this as ‘the a.c. layer’. The epistemological problem here, however, is that there is no evidence that the text ever existed in a fully uncorrected state; it is much more likely that at least some of the corrections were made immediately during the composition or copying process. For this reason, the StemmaREST variant graph model only stores non-base witness layers where they are recorded to exist.
In StemmaREST’s Neo4J implementation, individual witness layer paths are represented using edge properties, where the property key denotes the name of a layer and the property value is an array of sigla whose witness texts follow that edge. The name of the base layerwiistnesses; typical names for other layers might be ‘a.c.’ or ‘s.ls.u’p(ra lineam). The property key witnesses must be present and non-empty for every edge; property keys for other layers may be present and must be non-empty.
In this model, the traversal is a simple matter of following the correctly labeled sequence paths from the start node to the end node. We do this by providing a custoEmvaluator algorithm to a Neo4J traversal description, as given in AppendAi x.1. The validity of a given variant graph may be checked at any point by ensuring that every de昀椀ned layer of every witness, substituted by the witness’s base layer where the given layer is not present at all, produces a single unbroken sequence of readings from start to end.
One of the advantages of a graph model for text collation, as described in 2012, is the ability
to indicate relations between variant readings as a separate category of edge in the graph —
that is, to classify variants. This is a feature that is usually indispensable to scholarly editors,
who must work through the variants and make determinations about how an edited version of
the text should be constituted, or understand how the di昀erent versions of the text came to be.
Variant classi昀椀cation is an essential 昀椀rst step, for example, for the construction of astemma
codicum in most accepted methods.[
The StemmaREST model allows for the following properties orfelaated edge between two readings: • type — indicates the classi昀椀cation being made (see below). • scope — indicates whether the relation applies only to this variant location, or to all variant locations for this text where the related readings occur. Possible valuelsoacrael and document. • is_significant — indicates whether, according to the judgment of the editor, the variation is stemmatically signi昀椀cant. The three values ‘yes’, ‘maybe’, and ‘no’ are accepted. • alters_meaning — boolean to indicate whether the variation alters the semantic interpretation of the text. • non_independent — boolean to indicates whether, according to the judgment of the editor, the variation was unlikely to occur in two unrelated manuscripts. This corresponds to the concept of aBindefehler. • a_derivable_from_b, b_derivable_from_a — booleans to indicate whether, in the judgment of the editor, one of the readings would have been correctable to the other by a typical scribe. This corresponds to the concept ofTarennfehler.
Of particular interest here is the typology of relations. The set of relation types that apply to any given text tradition is de昀椀ned by the user; each relation type is given a name and description and is de昀椀ned according to a set of properties. With the properties given, it is possible to create a limited hierarchy of relation types.
• is_colocation — a boolean to indicate whether this relation is de昀椀ned within a single variant location. A transposition, for example, is not a colocation. One of the features of the StemmaREST model is to ensure that, if a colocation relation is set between two readings, those readings remain topologically at the same location in the text. • is_transitive — a boolean to indicate whether this relation typetirsansitive. • is_generalizable — a boolean to indicate whether this relation type may be applied at document scope. • bindlevel — an integer to indicate how closely related readings of this type are. Lower values indicate closer relations. This value is used to deduimceplication for transitive relations.
The logic of transitivity and implication in the graph is crucial to the robust representation of text variation. To illustrate this, let us de昀椀ne two relation typsepselling and grammatical; as their names imply, readings that are linked through relations of these types are, respectively, spelling variations and grammatical variations of each other. Both these relation types will have true values for all three booleans (the relation implies colocation of the respective readings; the relations are logically transitive; the relations may be applied to identical colocated pairs of readings throughout the text). Since spelling variants are much more o昀琀en treated as ‘the same reading’ than grammatical variants are, we set a lowberindlevel value (e.g. 1) for the spelling relation type than the value we would set (e.g. 2) for thgerammatical relation type.
An example of transitivity can be seen in Figure1. Here, the editor has set relations of type grammatical between the two reading pairs (‘croit’, ‘croient’) and (‘croit’, ‘crois’); since all three readings are conjugations of the verbe ‘croire’, they all have the same relationship to each other as variants and the third relation has been inferred by the model.
Transitivity alone, however, is not su昀케cient for correct automatic deduction of relations between readings. Consider the situation in Figur2e; if the editor were to set agrammatical relation between ‘suggestiones’ and ‘suggestionem’, and between ‘suggestiones’ and ‘sug(a) A mixed pair of variant relations. Two rela-(b) ...the third is inferred based on transitivity and tions are set by the editor... implication rules. gescionem’, the logic of transitivity would give usgarammatical relation between ‘suggestionem’ and ‘suggescionem’, when an editor would rather seesapelling relation. Here the concept of implication, represented by ourbindlevel setting, comes into play: wherever a transitive relation (e.g.grammatical) is set between two readings, and one of these readings has a more closely-bound (e.g.spelling) relation to a third reading, a more loosely-bound relation between the as-yet unconnected readings will be inferred. This holds true no matter the order in which the di昀erently-typed relations are set; our experience, however, is that for variant locations with very many variants, the best results are achieved by ‘working outwards‘ from the most closely bound readings to the least.
The system of transitivity and implication, simplistic though it is, handles the logical consequences of di昀erent levels of normalization and serves thereby as both a practical help and a sanity check for users of the StemmaREST model. A more comprehensive typology of variant readings would be a useful future direction; one possibility would be to construct a graph hierarchy of possible relation types, and use the hierarchy to determine implication rather than the bindlevel value.4 4At least one proposal for a di昀erent typology, in the form of an ontology, has been mad11e][; implementation of this particular typology in StemmaREST would additionally require the direction of relation edges to be taken into account, as they currently are not.
(a) The original graph; spelling relations are marked in green
(b) The projected graph of spelling normalization; cluster representatives are majority
readings
4. Relation-based normalization of a variant graph
Text normalization is a frequent desideratum of scholarly editors, who are usually faced with
the con昀氀icting desires to represent the text versions as faithfully as possible on the one hand,
and to avoid burdening their readers on the other hand with variation that would be
considered trivial1.[
A StemmaREST variant graph can be normalized by means of its reading relations. A common task, for example, is to omit variations in spelling and punctuation. In order to produce a collation normalized in this way, we 昀椀rst identify the clusters of multiple readings that should be treated as a single reading — that is, the readings that are related to each other with either the ‘spelling’ type or the ‘punctuation’ type. Readings that are part of no such relation then become one-member clusters.
The next step is to create agraph projection in which each cluster is represented by one of its members. The choice of representative may be made in any number of ways, e.g. a reading selected at random, the reading present in a majority or plurality of witnesses, or the reading that has been selected as a lemma (i.e. canonical) by the editor.
Each edge in the projection corresponds to an edge in the original graph, replacing the original source and target vertices with their respective cluster representatives. Its properties are calculated as a union of the properties of all edges in the original graph that it represents. An example of normalization is given in Figur3e. 5. Self-consistency of the variant graph: reading rank and reading location It is not di昀케cult to 昀椀nd examples in printed critical editions of apparatus entries that are mistaken or confusing. Even when a tool such as Classical Text Editor is used, the intention of the editor does not always translate correctly to the underlying data model, as is frequently discovered when the editor attempts to export a TEI XML-encoded version of their editi4o]n. [ The logical notion of variant location is not only key to the clear and error-free construction of an apparatus, but is also a necessary precondition for any sort of computer-assisted stemmatic analysis of the manuscript tradition.
It is clear that, if a normalized projection is made of a variant graph, that projection is subject to the same rules provided in sectio2n: it must itself be a CRDAG whose base witness paths run unbroken from the start reading to the end reading, and the sequence of readings produced for any given witness path must correspond correctly to the editor’s view of how the text of the respective manuscript reads. This restriction in turn informs what relations may be created within the graph: a reading relation may only be set if one of the following two conditions holds: 1. The relation type is de昀椀ned as a colocation, and a graph projection using this relation together with all other colocated relations de昀椀ned in the graph would result in a valid graph according to our de昀椀nition. 2. The relation type is NOT de昀椀ned as a colocation, and a graph projection using this relation together with all other colocated relations de昀椀ned in the graph would NOT result in a valid graph according to our de昀椀nition.
We improve the e昀케ciency of our consistency check by de昀椀ning colocations in terms of reading rank. One can speak of ranking the vertices of a DAG according to their sequence in the paths de昀椀ned for that graph. A typical algorithm for this is
= 1 + max ( ) , where is the rank of vertex and is the rank of the source vertex of an incoming edge to .
In our variant graph, we understand reading rank to be synonymous with variant location. That is, all readings with the same rank can be understood to be at the same location in the text, and thus variants of each other. Colocation in the sense of reading relations, then, is strictly equivalent to identical node rank of the related readings. For this we slightly modify our formula for calculating rank:
= max (max ( ), 1 + max ( )) where is the rank of a vertex connected by a colocation relation t.oAn implementation of our ranking algorithm is given in AppendAix.2.
Once the reading rank is calculated for all readings in a variant graph, it may be used to set constraints on other graph operations. Perhaps the most crucial of these, from the point of view of avoiding a corrupted collation, is as a constraint for setting relations between readings. For any proposed reading relation between readingsand , we 昀椀rst check whether the relation is a colocation and = ; if so, the relation may be allowed without further calculation. If this condition does not hold, then a full projection (that is, a projection that takes into account all colocated relations) must be made for all readings wh ere≤ ≤ and the graph must be searched for the existence of a path between the representative vertices ofand .
The other primary use of reading rank as a constraint arises when the editor is ready to establish the text. One of the primary purposes of almost any critical edition of a text is to present a single version that the editor considers the best representative of the text. This version is o昀琀en known as the lemma text. In terms of the variant graph, then, the lemma text is modelled as a single path which obeys the same rules as a witness base path: that is, it runs without interruption through some set of readings from start to end. An additional constraint for the lemma text path is that its creation may not alter the rank of any of its readings. When the editor comes to set a lemma text through StemmaREST, this constraint will be enforced to ensure that there is never more than one lemma reading at any given rank in the variant graph, and that the lemma text respects the order of the existing ranks. In this way the consistency of the eventual edition and its critical apparatus is ensured.
The idea of a variant graph is now around 昀椀琀een years old. Its properties and its use has been described more or less formally by those who have adopted it, but the implications have o昀琀en been le昀琀 to the reader’s intuition. Over the course of developing the StemmaREST repository, we have encountered many more consequences, pitfalls, implications, and inadvertent production of corrupted collations than we have yet seen described in any of the existing literature; all of these situations have led to a much more thorough and explicit de昀椀nition of what a variant graph is. We present that de昀椀nition here with the hope that it will be of service to digital textual scholarship.
The StemmaREST code was begun in the spring semester of 2015 by a team of students in the class ‘So昀琀ware Engineering’ under the supervision of Prof. Thomas Studer of the University of Bern; its further development was made possible in the framework of the SNSF-funded project ‘TheChronicle of Matthew of Edessa Online’ (#159433) and through support from the University of Vienna. Further contributors to the source code have included Julia Damerow, Sascha Kaufmann, and Tamim Ziai.
A. Java implementations for selected algorithms
Let sigil be a string whose value is the sigil forWaitness node; letlayer be a string whose value is a named witness layer; ledtb be the GraphDatabaseService object for querying the database. public class WitnessPath { /* ... */ public Evaluator getEvalForWitness () { return path -> { if (path.length() == 0) {
return Evaluation.EXCLUDE_AND_CONTINUE; } // Find all relevant alternative paths out from last node; // there should be zero or one.
Relationship correct = null; for (String layer : alternative) {
Node priorNode = path.lastRelationship().getStartNode(); for (Relationship r : ↪ priorNode.getRelationships(Direction.OUTGOING, seqType))
if (r.hasProperty(layer) && ↪ witnessIn(r.getProperty(layer))) if (correct != null)
// There is more than one relevant path; cut the ↪ tree off.
return Evaluation.EXCLUDE_AND_PRUNE; else
correct = r; } // There is one relevant path; return depending on whether // that path is us. if (correct != null) return correct.equals(path.lastRelationship())
? Evaluation.INCLUDE_AND_CONTINUE : ↪ Evaluation.EXCLUDE_AND_PRUNE; // Follow the main path in the absence of an alternative if (path.lastRelationship().hasProperty("witnesses")
&& ↪ witnessIn(path.lastRelationship().getProperty("witnesses"))) return Evaluation.INCLUDE_AND_CONTINUE; return Evaluation.EXCLUDE_AND_PRUNE; }; } private Boolean witnessIn (Object property) {
String[] arr = (String []) property; for (String str : arr) { if (str.equals(sigil)) {
return true; } }
} } return false; /* ... */ Evaluator e = new WitnessPath(sigil, layer).getEvalForWitness(); db.traversalDescription().depthFirst() .relationships(ERelations.SEQUENCE, Direction.OUTGOING)
private static class RankEvaluate implements Evaluator { private final Long rank; RankEvaluate(Long stoprank) {
rank = stoprank; } }
} } @Override public Evaluation evaluate(Path path) { if (path.endNode().equals(path.startNode()))
return Evaluation.INCLUDE_AND_CONTINUE; Node testNode = path.lastRelationship().getStartNode(); if (testNode.hasProperty("rank")
&& (Long) testNode.getProperty("rank") >= rank) { return Evaluation.INCLUDE_AND_PRUNE; } else {
return Evaluation.INCLUDE_AND_CONTINUE; } public static class AlignmentTraverse implements PathExpander { private final HashSet<String> includeRelationTypes = new HashSet<>(); // Walk the graph of sequences and colocated relations public AlignmentTraverse(Node referenceNode) throws Exception { // Get the colocated types for this node's tradition
List<RelationTypeModel> rtms = ↪ RelationService.ourRelationTypes(referenceNode); for (RelationTypeModel rtm : rtms) if (rtm.getIs_colocation()) includeRelationTypes.add(rtm.getName()); public Iterable<Relationship> expand(Path path, BranchState state) { return expansion(path, Direction.OUTGOING); private Iterable<Relationship> expansion(Path path, Direction dir) { ArrayList<Relationship> relevantRelations = new ArrayList<>(); // Get the sequence relationships for (Relationship relationship : path.endNode()
.getRelationships(dir, ERelations.SEQUENCE, ↪ ERelations.LEMMA_TEXT, ERelations.EMENDED))
relevantRelations.add(relationship); // Get the alignment relationships and filter them for (Relationship r : path.endNode().getRelationships(Direction.BOTH, ↪ ERelations.RELATED)) {
if ↪ (includeRelationTypes.contains(r.getProperty("type").toString())) relevantRelations.add(r); } return relevantRelations; }
} public static Set<Node> recalculateRank (Node startNode, boolean ↪ recalculateAll) throws Exception {
RankCalcEvaluate e = new RankCalcEvaluate(startNode, recalculateAll); AlignmentTraverse a = new AlignmentTraverse(startNode); GraphDatabaseService db = startNode.getGraphDatabase(); ResourceIterable<Node> touched = db.traversalDescription().depthFirst() .expand(a) .evaluator(e) .uniqueness(Uniqueness.RELATIONSHIP_GLOBAL) .traverse(startNode).nodes(); // Run the traverser and commit the updated ranks Set<Node> changed = new HashSet<>(); for (Node n : touched.stream().collect(Collectors.toSet())) { if (!n.hasProperty("newrank"))
throw new Exception (String.format("Node %d (%s) traversed but ↪ not re-ranked!",
n.getId(), n.getProperty("text"))); Long nr = (Long) n.removeProperty("newrank"); if (!n.hasProperty("rank") || !n.getProperty("rank").equals(nr)) { changed.add(n); } } n.setProperty("rank", nr); return changed; 591