{"owner":"fetsorn","repo":"pijul-spec","channel":"main","channels":["main"],"can_delete":true,"inode":{"File":{"path":[{"basename":"resources","pos":"4NBQFWD6E7ZJM.OVHAA","meta":576},{"basename":"20131113_categorical_theory_of_patches.md","pos":"4NBQFWD6E7ZJM.KUQRS","meta":0}],"file":"# Document Title\n\narXiv:1311.3903v1 [cs.LO] 13 Nov 2013\nA Categorical Theory of Patches\nSamuel Mimram Cinzia Di Giusto\nCEA, LIST∗\nAbstract\nWhen working with distant collaborators on the same documents, one\noften uses a version control system, which is a program tracking the history\nof files and helping importing modifications brought by others as patches.\nThe implementation of such a system requires to handle lots of situations\ndepending on the operations performed by users on files, and it is thus\ndifficult to ensure that all the corner cases have been correctly addressed.\nHere, instead of verifying the implementation of such a system, we adopt\na complementary approach: we introduce a theoretical model, which is\ndefined abstractly by the universal property that it should satisfy, and\nwork out a concrete description of it. We begin by defining a category of\nfiles and patches, where the operation of merging the effect of two coinitial\npatches is defined by pushout. Since two patches can be incompatible,\nsuch a pushout does not necessarily exist in the category, which raises\nthe question of which is the correct category to represent and manipulate\nfiles in conflicting state. We provide an answer by investigating the free\ncompletion of the category of files under finite colimits, and give an explicit\ndescription of this category: its objects are finite sets labeled by lines\nequipped with a transitive relation and morphisms are partial functions\nrespecting labeling and relations.\n1 Introduction\nIt is common nowadays, when working with distant collaborators on the same\nfiles (multiple authors writing an article together for instance), to use a program\nwhich will track the history of files and handle the operation of importing mod-\nifications of other participants. These software called version control systems\n(vcs for short), like git or Darcs, implement two main operations. When a user\nis happy with the changes it has brought to the files it can record those changes\nin a patch (a file coding the differences between the current version and the last\nrecorded version) and commit them to a server, called a repository. The user\ncan also update its current version of the file by importing new patches added\nby other users to the repository and applying the corresponding modifications\nto the files. One of the main difficulties to address here is that there is no global\nnotion of “time”: patches are only partially ordered. For instance consider a\nrepository with one file A and two users u1 and u2. Suppose that u1 modifies\nfile A into B by committing a patch f , which is then imported by u2, and\n∗This work was partially supported by the French project ANR-11-INSE-0007 REVER.\n1\nthen u1 and u2 concurrently modify the file B into C (resp. D) by committing\na patch g (resp. h). The evolution of the file is depicted on the left and the\npartial ordering of patches in the middle:\nC D\nB\ng\n`\n`\n❆❆❆ h\n>\n>\n⑥⑥⑥\nA\nf O O\ng h\nf\n]\n]\n✿✿✿ A A ✄✄✄\nE\nC\nh/g > > ⑥⑥⑥ D\ng/h``❆❆❆\nB\ng\n`\n`\n❆❆❆ h\n>\n>\n⑥⑥⑥\nA\nf O O\nNow, suppose that u2 imports the patch g or that u1 imports the patch h.\nClearly, this file resulting from the merging of the two patches should be the\nsame in both cases, call it E. One way to compute this file, is to say that there\nshould be a patch h/g, the residual of h after g, which transforms C into E and\nhas the “same effect” as h once g has been applied, and similarly there should be\na patch g/h transforming D into E. Thus, after each user has imported changes\nfrom the other, the evolution of the file is as pictured on the right above. In\nthis article, we introduce a category L whose objects are files and morphisms\nare patches. Since residuals should be computed in the most general way, we\nformally define them as the arrows of pushout cocones, i.e. the square in the\nfigure on the right should be a pushout.\nHowever, as expected, not every pair of coinitial morphisms have a pushout\nin the category L: this reflects the fact that two patches can be conflicting (for\ninstance if two users modify the same line of a file). Representing and handling\nsuch conflicts in a coherent way is one of the most difficult part of implementing\na vcs (as witnessed for instance by the various proposals for Darcs: mergers,\nconflictors, graphictors, etc. [10]). In order to be able to have a representation\nfor all conflicting files, we investigate the free completion of the category L\nunder all pushouts, this category being denoted P, which corresponds to adding\nall conflicting files to the category, in the most general way as possible. This\ncategory can easily be shown to exist for general abstract reasons, and one\nof the main contributions of this work is to provide an explicit description by\napplying the theory of presheaves. This approach paves the way towards the\nimplementation of a vcs whose correctness is deduced from universal categorical\nproperties.\nRelated work. The Darcs community has investigated a formalization of pat-\nches based on commutation properties [10]. Operational transformations tackle\nessentially the same issues by axiomatizing the notion of residual patches [9].\nIn both cases, the fact that residual should form a pushout cocone is never\nexplicitly stated, excepting in informal sentences saying that “g/f should have\nthe same effect as g once f has been applied”. We should also mention another\ninteresting approach to the problem using inverse semigroups in [4]. Finally,\nHouston has proposed a category with pushouts, similar to ours, in order to\nmodel conflicting files [3], see Section 6.\nPlan of the paper. We begin by defining a category L of files and patches in\nSection 2. Then, in Section 3, we abstractly define the category P of conflicting\nfiles obtained by free finite cocompletion. Section 4 provides a concrete descrip-\ntion of the construction in the simpler case where patches can only insert lines.\n2\nWe give some concrete examples in Section 5 and adapt the framework to the\ngeneral case in Section 6. We conclude in Section 7.\n2 Categories of files and patches\nIn this section, we investigate a model for a simplified vcs: it handles only one\nfile and the only allowed operations are insertion and deletion of lines (modi-\nfication of a line can be encoded by a deletion followed by an insertion). We\nsuppose fixed a set L = {a, b, . . .} of lines (typically words over an alphabet of\ncharacters). A file A is a finite sequence of lines, which will be seen as a function\nA : [n] → L for some number of lines n ∈ N, where the set [n] = {0, 1, . . . , n − 1}\nindexes the lines of the files. For instance, a file A with three lines such that\nA(0) = a, A(1) = b and A(2) = c models the file abc. Given a ∈ L, we some-\ntimes simply write a for the file A : [1] → L such that A(0) = a. A morphism\nbetween two files A : [m] → L and B : [n] → L is an injective increasing partial\nfunction f : [m] → [n] such that ∀i ∈ [m], B ◦ f (i) = A(i) whenever f (i) is\ndefined. Such a morphism is called a patch.\nDefinition 1. The category L has files as objects and patches as morphisms.\nNotice that the category L is strictly monoidal with [m] ⊗ [n] = [m + n] and\nfor every file A : [m] → L and B : [n] → L, (A ⊗ B)(i) = A(i) if i < m and\n(A ⊗ B)(i) = B(i − m) otherwise, the unit being the empty file I : [0] → L, and\ntensor being defined on morphisms in the obvious way. The following proposition\nshows that patches are generated by the operations of inserting and deleting a\nline:\nProposition 2. The category L is the free monoidal category containing L as\nobjects and containing, for every line a ∈ L, morphisms ηa : I → a (insertion\nof a line a) and εa : a → I (deletion of a line a) such that εa ◦ ηa = idI (deleting\nan inserted line amounts to do nothing).\nExample 3. The patch corresponding to transforming the file abc into dadeb,\nby deleting the line c and inserting the lines labeled by d and e, is modeled by\nthe partial function f : [3] → [5] such that f (0) = 1 and f (1) = 4 and f (2) is\nundefined. Graphically,\na\nb\nc\nd\na\nd\ne\nb\nThe deleted line is the one on which f is not defined and the inserted lines are\nthose which are not in the image of f . In other words, f keeps track of the\nunchanged lines.\nIn order to increase readability, we shall consider the particular case where L\nis reduced to a single element. In this unlabeled case, the objects of L can be\nidentified with integers (the labeling function is trivial), and Proposition 2 can\nbe adapted to achieve the following description of the category, see also [6].\nProposition 4. If L is reduced to a singleton, the category L is the free category\nwhose objects are integers and morphisms are generated by sn\ni : n → n + 1 and\n3\ndn\ni : n + 1 → n for every n ∈ N and i ∈ [n + 1] (respectively corresponding to\ninsertion and deletion of a line at i-th position), subject to the relations\nsn+1\ni sn\nj = sn+1\nj+1 sn\ni dn\ni sn\ni = idn dn\ni dn+1\nj = dn\nj dn+1\ni+1 (1)\nwhenever 0 ≤ i ≤ j < n.\nWe will also consider the subcategory L+ of L, with same objects, and to-\ntal injective increasing functions as morphisms. This category models patches\nwhere the only possible operation is the insertion of lines: Proposition 2 can be\nadapted to show that L+ is the free monoidal category containing morphisms\nηa : I → a and, in the unlabeled case, Proposition 4 can be similarly adapted\nto show that it is the free category generated by morphisms sn\ni : n → n + 1\nsatisfying sn+1\ni sn\nj = sn+1\nj+1 sn\ni with 0 ≤ i ≤ j < n.\n3 Towards a category of conflicting files\nSuppose that A is a file which is edited by two users, respectively applying\npatches f1 : A → A1 and f2 : A → A2 to the file. For instance,\na c c b f1\n←− a b f2\n−→ a b c d (2)\nNow, each of the two users imports the modification from the other one. The\nresulting file, after the import, should be the smallest file containing both mod-\nifications on the original file: accbcd. It is thus natural to state that it should\nbe a pushout of the diagram (2). Now, it can be noticed that not every diagram\nin L has a pushout. For instance, the diagram\na c b f1\n←− a b f2\n−→ a d b (3)\ndoes not admit a pushout in L. In this case, the two patches f1 and f2 are said\nto be conflicting.\nIn order to represent the state of files after applying two conflicting patches,\nwe investigate the definition of a category P which is obtained by completing\nthe category L under all pushouts. Since, this completion should also contain\nan initial object (i.e. the empty file), we are actually defining the category P as\nthe free completion of L under finite colimits: recall that a category is finitely\ncocomplete (has all finite colimits) if and only if it has an initial object and is\nclosed under pushouts [6]. Intuitively, this category is obtained by adding files\nwhose lines are not linearly ordered, but only partially ordered, such as on the\nleft of a\n\n\n \u001f \u001f ❃❃❃\nc\n\u001d\n\u001d ❁❁❁ d\n\n\n✂✂✂\nb\na\n<<<<<<< HEAD\nc\n=======\nd\n>>>>>>> 5c55...\nb\n(4)\nwhich would intuitively model the pushout of the diagram (3) if it existed,\nindicating that the user has to choose between c and d for the second line.\nNotice the similarities with the corresponding textual notation in git on the\nright. The name of the category L reflects the facts that its objects are files\nwhose lines are linearly ordered, whereas the objects of P can be thought as files\nwhose lines are only partially ordered. More formally, the category is defined\nas follows.\n4\nDefinition 5. The category P is the free finite conservative cocompletion of L:\nit is (up to equivalence of categories) the unique finitely cocomplete category\ntogether with an embedding functor y : L → P preserving finite colimits, such\nthat for every finitely cocomplete category C and functor F : L → C preserv-\ning finite colimits, there exists, up to unique isomorphism, a unique functor\n˜F : P → C preserving finite colimits and satisfying ˜F ◦ y = F :\nL\ny \u000f \u000f\nF / / C\nP ˜F\n?\n?\nAbove, the term conservative refers to the fact that we preserve colimits which\nalready exist in L (we will only consider such completions here). The “standard”\nway to characterize the category P, which always exists, is to use the following\nfolklore theorem, often attributed to Kelly [5, 1]:\nTheorem 6. The conservative cocompletion of the category L is equivalent to\nthe full subcategory of ˆL whose objects are presheaves which preserve finite limits,\ni.e. the image of a limit in Lop (or equivalently a colimit in L) is a limit in Set\n(and limiting cones are transported to limiting cones). The finite conservative\ncocompletion P can be obtained by further restricting to presheaves which are\nfinite colimits of representables.\nExample 7. The category FinSet of finite sets and functions is the conservative\ncocompletion of the terminal category 1.\nWe recall that the category ˆL of presheaves over L, is the category of functors\nLop → Set and natural transformations between them. The Yoneda functor\ny : L → ˆL defined on objects n ∈ L by yn = L(−, n), and on morphisms\nby postcomposition, provides a full and faithful embedding of L into the cor-\nresponding presheaf category, and can be shown to corestrict into a functor\ny : L → P [1]. A presheaf of the form yn for some n ∈ L is called representable.\nExtracting a concrete description of the category P from the above propo-\nsition is a challenging task, because we a priori need to characterize firstly all\ndiagrams admitting a colimit in L, and secondly all presheaves in ˆL which pre-\nserve those diagrams. This paper introduces a general methodology to build\nsuch a category. In particular, perhaps a bit surprisingly, it turns out that\nwe have to “allow cycles” in the objects of the category P, which will be de-\nscribed as the category whose objects are finite sets labeled by lines together with\na transitive relation and morphisms are partial functions respecting labels and\nrelations.\n4 A cocompletion of files and insertions of lines\nIn order to make our presentation clearer, we shall begin our investigation of the\ncategory P in a simpler case, which will be generalized in Section 6: we compute\nthe free finite cocompletion of the category L+ (patches can only insert lines)\nin the case where the set of labels is a singleton. To further lighten notations,\nin this section, we simply write L for this category.\nWe sometimes characterize the objects in L as finite colimits of objects in a\nsubcategory G of L. This category G is the full subcategory of L whose objects\n5\nare 1 and 2: it is the free category on the graph 1 / / / / 2 , the two arrows\nbeing s1\n0 and s1\n1. The category ˆG of presheaves over G is the category of graphs:\na presheaf P ∈ ˆG is a graph with P (1) as vertices, P (2) as edges, the functions\nP (s1\n1) and P (s1\n0) associate to a vertex its source and target respectively, and\nmorphisms correspond to usual morphisms of graphs. We denote by x ։ y a\npath going from a vertex x to a vertex y in such a graph. The inclusion functor\nI : G → L induces, by precomposition, a functor I∗ : ˆL → ˆG. The image\nof a presheaf in ˆL under this functor is called its underlying graph. By well\nknown results about presheaves categories, this functor admits a right adjoint\nI∗ : ˆG → ˆL: given a graph G ∈ ˆG, its image under the right adjoint is the\npresheaf G∗ ∈ ˆL such that for every n ∈ N, G∗(n + 1) is the set of paths of\nlength n in the graph G, with the expected source maps, and G∗(0) is reduced\nto one element.\nRecall that every functor F : C → D induces a nerve functor NF : D → ˆC\ndefined on an object A ∈ C by NF (A) = D(F −, A) [7]. Here, we will consider\nthe nerve NI : L → ˆG associated to the inclusion functor I : G → L. An easy\ncomputation shows that the image NI (n) of n ∈ L is a graph with n vertices,\nso that its objects are isomorphic to [n], and there is an arrow i → j for every\ni, j ∈ [n] such that i < j. For instance,\nNI (3) = 0 / / 6 6 1 / / 2 NI (4) = 0 / / ( ( 4 4 1 / / ( ( 2 / / 3\nIt is, therefore, easy to check that this embedding is full and faithful, i.e. mor-\nphisms in L correspond to natural transformations in ˆG. Moreover, since NI (1)\nis the graph reduced to a vertex and NI (2) is the graph reduced to two vertices\nand one arrow between them, every graph can be obtained as a finite colimit of\nthe graphs NI (1) and NI (2) by “gluing arrows along vertices”. For instance, the\ninitial graph NI (0) is the colimit of the empty diagram, and the graph NI (3) is\nthe colimit of the diagram\nNI (2) NI (2)\nNI (1)\nNI (s1 ) , , ❳❳❳❳❳❳❳❳❳❳❳❳❳❳\nNI (s1 ) 6 6❧❧❧❧ NI (1)\nNI (s0 )hh❘❘❘❘ NI (s1) 6 6❧❧❧❧ NI (1)\nNI (s0 )hh❘❘❘❘\nNI (s0 )rr❢❢❢❢❢❢❢❢❢❢❢❢❢❢\nNI (2)\nwhich may also be drawn as on the left of\n*\n*\n❯❯❯❯❯❯❯❯❯\n:\n: ✈✈✈✈ f f ◆◆◆◆ 8 8 ♣♣♣♣ d d ❍❍❍❍\nt\nt\n✐✐✐✐✐✐✐✐✐\n2 2\n1\n&\n&\n◆◆◆◆◆◆◆\n@\n@\n✁✁✁ 1\n^\n^\n❂❂❂ @ @ ✁✁✁ 1\n^\n^\n❂❂❂\nx\nx\n♣♣♣♣♣♣♣\n2\nby drawing the graphs NI (0) and NI (1). Notice, that the object 3 is the col-\nimit of the corresponding diagram in L (on the right), and this is generally\ntrue for all objects of L, moreover this diagram is described by the functor\nEl(NI (3)) π\n−→ L. The notation El(P ) refers to the category of elements of a\npresheaf P ∈ ˆC, whose objects are pairs (A, p) with A ∈ C and p ∈ P (A)\nand morphisms f : (A, p) → (B, q) are morphisms f : A → B in C such that\nP (f )(q) = p, and π is the first projection functor. The functor I : G → L is\nthus a dense functor in the sense of Definition 9 below, see [7] for details.\n6\nProposition 8. Given a functor F : C → D, with D cocomplete, the associated\nnerve NF : D → ˆC admits a left adjoint RF : ˆC → D called the realization\nalong F . This functor is defined on objects P ∈ ˆC by\nRF (P ) = colim(El(P ) π\n−→ C F\n−→ D)\nProof. Given a presheaf P ∈ ˆC and an object D, it can be checked directly that\nmorphisms P → NF D in ˆC with cocones from El(P ) D\n−→ to D, which in turn\nare in bijection with morphisms RF (P ) → D in D, see [7].\nDefinition 9. A functor F : C → D is dense if it satisfies one of the two\nequivalent conditions:\n(i) the associated nerve functor NF : D → ˆC is full and faithful,\n(ii) every object of D is canonically a colimit of objects in C: for every D ∈ D,\nD ∼= colim(El(NF D) π\n−→ C F\n−→ D) (5)\nSince the functor I is dense, every object of L is a finite colimit of objects\nin G, and G does not have any non-trivial colimit. One could expect the free\nconservative finite cocompletion of L to be the free finite cocompletion P of G.\nWe will see that this is not the case because the image in L of a non-trivial\ndiagram in G might still have a colimit. By Theorem 6, the category P is the\nfull subcategory of ˆL of presheaves preserving limits, which we now describe\nexplicitly. This category will turn out to be equivalent to a full subcategory\nof ˆG (Theorem 15). We should first remark that those presheaves satisfy the\nfollowing properties:\nProposition 10. Given a presheaf P ∈ ˆL which is an object of P,\n1. the underlying graph of P is finite,\n2. for each non-empty path x ։ y there exists exactly one edge x → y (in\nparticular there is at most one edge between two vertices),\n3. P (n + 1) is the set of paths of length n in the underlying graph of P ,\nand P (0) is reduced to one element.\nProof. We suppose given a presheaf P ∈ P, it preserves limits by Theorem 6.\nThe diagram on the left\n3\n2\ns2\n2 = = ③③③ 2\ns2\n0aa❉❉❉\n1s1\n0\na\na\n❉❉❉ s1\n1\n=\n=\n③③③\nP (3)\nP (2)\nx\nx\nP (s2\n2)\nqq\nP (2)\n&\n&\nP (s2\n0 )▼▼\nP (1)\n&\n&P (s1\n0)\n▼▼ x x P (s1\n1 )\nqq\nis a pushout in L, or equivalently the dual diagram is a pullback in Lop. There-\nfore, writing D for the diagram 2 1\ns1\n0\noo s1\n1 / / 2 in L, a presheaf P ∈ P should satisfy\nP ((colim D)op) ∼= lim P (Dop), i.e. the above pushout diagram in L should be\ntransported by P into the pullback diagram in Set depicted on the right of the\nabove figure. This condition can be summarized by saying that P should satisfy\n7\nthe isomorphism P (3) ∼= P (2) ×P (1) P (2) (and this isomorphism should respect\nobvious source and target maps given by the fact that the functor P should\nsend a limiting cone to a limiting cone). From this fact, one can deduce that\nthe elements α of P (3) are in bijection with the paths x → y → z of length 2\nin the underlying graph of P going from x = P (s2\n2s1\n1)(α) to z = P (s2\n0s1\n0)(α). In\nparticular, this implies that for any path α = x → y → z of length 2 in the\nunderlying graph of P , there exists an edge x → z, which is P (s2\n1)(α). More\ngenerally, given any integer n > 1, the object n + 1 is the colimit in L of the\ndiagram\n2 2 2 2\n1\ns1\n1 ; ; ①①① 1\ns1\n0cc❋❋❋ s1\n1 ; ; ①①① s1\n0aa❈❈❈❈ . . .\ns1\n1 = = ④④④④ 1\ns1\n0cc❋❋❋ s1\n1 ; ; ①①① 1\ns1\n0cc❋❋❋ (6)\nwith n + 1 occurrences of the object 1, and n occurrences of the object 2.\nTherefore, for every n ∈ N, P (n+ 1) is isomorphic to the set of paths of length n\nin the underlying graph. Moreover, since the diagram\n2 2 2 2\n1\ns1\n1 , , ❩❩❩❩❩❩❩❩❩❩❩❩❩❩❩❩❩❩❩\ns1\n1 < < ②②② 1\ns1\n0bb❊❊❊ s1\n1 < < ②②② s1\n0``❇❇❇ . . .\ns1\n1 > > ⑤⑤⑤ 1\ns1\n0bb❊❊❊ s1\n1 < < ②②② 1\ns1\n0bb❊❊❊\ns1\n0\nrr❞❞❞❞❞❞❞❞❞❞❞❞❞❞❞❞❞❞❞\n2\n(7)\nwith n + 1 occurrences of the object 1 also admits the object n + 1 as colimit,\nwe should have P (n + 1) ∼= P (n + 1) × P (2) between any two vertices x and y,\ni.e. for every non-empty path x ։ y there exists exactly one edge x → y. Also,\nsince the object 0 is initial in L, it is the colimit of the empty diagram. The\nset P (0) should thus be the terminal set, i.e. reduced to one element. Finally,\nsince I is dense, P should be a finite colimit of the representables NI (1) and\nNI (2), the set P (1) is necessarily finite, as well as the set P (2) since there is at\nmost one edge between two vertices.\nConversely, we wish to show that the conditions mentioned in the above\nproposition exactly characterize the presheaves in P among those in ˆL. In order\nto prove so, by Theorem 6, we have to show that presheaves P satisfying these\nconditions preserve finite limits in L, i.e. that for every finite diagram D : J → L\nadmitting a colimit we have P (colim D) ∼= lim(P ◦ Dop). It seems quite difficult\nto characterize the diagrams admitting a colimit in L, however the following\nlemma shows that it is enough to check diagrams “generated” by a graph which\nadmits a colimit.\nLemma 11. A presheaf P ∈ ˆL preserves finite limits if and only if it sends the\ncolimits of diagrams of the form\nEl(G) πG\n−−→ G I\n−→ L (8)\nto limits in Set, where G ∈ ˆG is a finite graph such that the above diagram\nadmits a colimit. Such a diagram in L is said to be generated by the graph G.\nProof. In order to check that a presheaf P ∈ ˆL preserves finite limits, we have\nto check that it sends colimits of finite diagrams in L which admit a colimit\nto limits in Set, and therefore we have to characterize diagrams which admit\ncolimits in L. Suppose given a diagram K : J → L. Since I is dense, every\nobject of linear is a colimit of a diagram involving only the objects 1 and 2 (see\n8\nDefinition 9). We can therefore suppose that this is the case in the diagram K.\nFinally, it can be shown that diagram K admits the same colimits as a diagram\ncontaining only s1\n0 and s1\n1 as arrows (these are the only non-trivial arrows in L\nwhose source and target are 1 or 2), in which every object 2 is the target of\nexactly one arrow s1\n0 and one arrow s1\n1. For instance, the diagram in L below\non the left admits the same colimits as the diagram in the middle.\n2 3\n1s1\n0\n^\n^\n❂❂❂\ns1\n1\n\u001e \u001e ❂❂❂\ns2\n2 s1\n1 @ @ ✁✁✁ 1\ns1\n0\n\n\n✁✁✁\ns2\n0s1\n0\n^^❂❂❂\n1\ns1\n0jj2\n2 2 2\n1\ns1\n1 @ @ ✁✁✁ 1\ns1\n0\n^^❂❂❂\ns1\n1 @ @ ✁✁✁\ns1\n1 & & ◆◆◆◆◆◆◆ 1\ns1\n0\n^^❂❂❂\ns1\n1 @ @ ✁✁✁ 1\ns1\n0\nxx♣♣♣♣♣♣♣\ns1\n0\n^^❂❂❂\n2\n0 / / 1 / / 6 6 2 / / 3\nAny such diagram K is obtained by gluing a finite number of diagrams of the\nform 1 s1\n1 / / 2 1\ns1\n0\noo along objects 1, and is therefore of the form El(G) π\n−→ G I\n−→ L\nfor some finite graph G ∈ ˆG: the objects of G are the objects 1 in K, the edges of\nG are the objects 2 in K and the source and target of an edge 2 are respectively\ngiven by the sources of the corresponding arrows s1\n1 and s1\n0 admitting it as target.\nFor instance, the diagram in the middle above is generated by the graph on the\nright. The fact that every diagram is generated by a presheaf (is a discrete\nfibration) also follows more abstractly and generally from the construction of\nthe comprehensive factorization system on Cat [8, 11].\nAmong diagrams generated by graphs, those admitting a colimit can be\ncharacterized using the following proposition:\nLemma 12. Given a graph G ∈ ˆG, the associated diagram (8) admits a colimit\nin L if and only if there exists n ∈ L and a morphism f : G → NI n in ˆL\nsuch that every morphism g : G → NI m in ˆL, with m ∈ L, factorizes uniquely\nthrough NI n: G f/ /\ng\n2 2\nNI n / / NI m\nProof. Follows from the existence of a partially defined left adjoint to NI , in\nthe sense of [8], given by the fact that I is dense (see Definition 9).\nWe finally arrive at the following concrete characterization of diagrams admit-\nting colimits:\nLemma 13. A finite graph G ∈ ˆG induces a diagram (8) in L which admits a\ncolimit if and only if it is “tree-shaped”, i.e. it is\n1. acyclic: for any vertex x, the only path x ։ x is the empty path,\n2. connected: for any pair of vertices x and y there exists a path x ։ y or a\npath y ։ x.\nProof. Given an object n ∈ L, recall that NI n is the graph whose objects are\nelements of [n] and there is an arrow i → j if and only if i < j. Given a finite\ngraph G, morphisms f : G → NI n are therefore in bijection with functions\nf : VG → [n], where VG denotes the set of vertices of G, such that f (x) < f (y)\nwhenever there exists an edge x → y (or equivalently, there exists a non-empty\npath x ։ y).\n9\nConsider a finite graph G ∈ ˆG, by Lemma 12, it induces a diagram (8)\nadmitting a colimit if there is a universal arrow f : G → NI n with n ∈ L. From\nthis it follows that the graph is acyclic: otherwise, we would have a non-empty\npath x ։ x for some vertex x, which would imply f (x) < f (x). Similarly,\nsuppose that G is a graph with vertices x and y such that there is no path\nx ։ y or y ։ x, and there is an universal morphism f : G → NI n for some\nn ∈ L. Suppose that f (x) ≤ f (y) (the case where f (y) ≤ f (x) is similar). We\ncan define a morphism g : G → NI (n + 1) by g(z) = f (z) + 1 if there is a path\nx ։ z, g(y) = f (x) and g(z) = f (z) otherwise. This morphism is easily checked\nto be well-defined. Since we always have f (x) ≤ f (y) and g(x) > g(y), there is\nno morphism h : NI n → NI (n + 1) such that h ◦ f = g.\nConversely, given a finite acyclic connected graph G, the relation ≤ defined\non morphisms by x ≤ y whenever there exists a path x ։ y is a total order.\nWriting n for the number of vertices in G, the function f : G → NI n, which to\na vertex associates the number of vertices strictly below it wrt ≤, is universal\nin the sense of Lemma 12.\nProposition 14. The free conservative finite cocompletion P of L is equiva-\nlent to the full subcategory of ˆL whose objects are presheaves P satisfying the\nconditions of Proposition 10.\nProof. By Lemma 11, the category P is equivalent to the full subcategory of ˆL\nwhose objects are presheaves preserving limits of diagrams of the form (8) gen-\nerated by some graph G ∈ ˆG which admits a colimit, i.e. by Lemma 13 the finite\ngraphs which are acyclic and connected. We write Gn for the graph with [n]\nas vertices and edges i → (i + 1) for 0 ≤ i < n − 1. It can be shown that any\nacyclic and connected finite graph can be obtained from the graph Gn, for some\nn ∈ N, by iteratively adding an edge x → y for some vertices x and y such\nthat there exists a non-empty path x ։ y. Namely, suppose given an acyclic\nand connected finite graph G. The relation ≤ on its vertices, defined by x ≤ y\nwhenever there exists a path x ։ y, is a total order, and therefore the graph G\ncontains Gn, where n is the number of edges of G. An edge in G which is not\nin Gn is necessarily of the form x → y with x ≤ y, otherwise it would not be\nacyclic. Since by Proposition 10, see (7), the diagram generated by a graph of\nthe form . . .\nis preserved by presheaves in P (which corresponds to adding an edge between\nvertices at the source and target of a non-empty path), it is enough to show\nthat presheaves in P preserve diagrams generated by graphs Gn. This follows\nagain by Proposition 10, see (6).\nOne can notice that a presheaf P ∈ P is characterized by its underlying\ngraph since P (0) is reduced to one element and P (n) with n > 2 is the set of\npaths of length n in this underlying graph: P ∼= I∗(I∗P ). We can therefore\nsimplify the description of the cocompletion of L as follows:\nTheorem 15. The free conservative finite cocompletion P of L is equivalent to\nthe full subcategory of the category ˆG of graphs, whose objects are finite graphs\nsuch that for every non-empty path x ։ y there exists exactly one edge x → y.\nEquivalently, it can be described as the category whose objects are finite sets\nequipped with a transitive relation <, and functions respecting relations.\n10\nIn this category, pushouts can be explicitly described as follows:\nProposition 16. With the last above description, the pushout of a diagram in\nP (B,