{ "cells": [ { "cell_type": "markdown", "source": [ "# Meets in Preorders\n", "\n", "\n", "Our first example of a concept defined by a universal mapping property is a meet respectively meet." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "The first step is our Catlab imports" ], "metadata": {} }, { "outputs": [], "cell_type": "code", "source": [ "using Core: GeneratedFunctionStub\n", "using Test\n", "\n", "using Catlab.Theories, Catlab.CategoricalAlgebra, Catlab.Graphics\n", "import Catlab.Theories: compose\n", "\n", "using DataStructures" ], "metadata": {}, "execution_count": 1 }, { "cell_type": "markdown", "source": [ "# Defining some basic preorders" ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "Presentation{Catlab.Theories.ThSchema.Meta.T, Symbol}(Catlab.Theories.FreeSchema, (Ob = Catlab.Theories.FreeSchema.Ob{:generator}[a₁, a₂, a₃, a₄], Hom = Catlab.Theories.FreeSchema.Hom{:generator}[f, g, h, k], AttrType = Catlab.Theories.FreeSchema.AttrType{:generator}[], Attr = Catlab.Theories.FreeSchema.Attr{:generator}[]), Dict(:a₃ => (:Ob => 3), :f => (:Hom => 1), :k => (:Hom => 4), :a₄ => (:Ob => 4), :a₁ => (:Ob => 1), :a₂ => (:Ob => 2), :g => (:Hom => 2), :h => (:Hom => 3)), Pair[])" }, "metadata": {}, "execution_count": 2 } ], "cell_type": "code", "source": [ "@present P(FreeSchema) begin\n", " (a₁,a₂,a₃,a₄)::Ob\n", " f::Hom(a₁, a₂)\n", " g::Hom(a₁, a₃)\n", " h::Hom(a₂, a₄)\n", " k::Hom(a₃, a₄)\n", "end" ], "metadata": {}, "execution_count": 2 }, { "cell_type": "markdown", "source": [ "We can draw a picture of our preorder as a Hasse Diagram." ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "Catlab.Graphics.Graphviz.Graph(\"G\", true, \"neato\", Catlab.Graphics.Graphviz.Statement[Catlab.Graphics.Graphviz.Node(\"n1\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"a₁\")), Catlab.Graphics.Graphviz.Node(\"n2\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"a₂\")), Catlab.Graphics.Graphviz.Node(\"n3\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"a₃\")), Catlab.Graphics.Graphviz.Node(\"n4\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"a₄\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"f\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"g\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"h\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"k\"))], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:margin => \"0\", :shape => \"ellipse\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}())", "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "G\n", "\n", "\n", "\n", "n1\n", "\n", "a₁\n", "\n", "\n", "\n", "n2\n", "\n", "a₂\n", "\n", "\n", "\n", "n1->n2\n", "\n", "\n", "f\n", "\n", "\n", "\n", "n3\n", "\n", "a₃\n", "\n", "\n", "\n", "n1->n3\n", "\n", "\n", "g\n", "\n", "\n", "\n", "n4\n", "\n", "a₄\n", "\n", "\n", "\n", "n2->n4\n", "\n", "\n", "h\n", "\n", "\n", "\n", "n3->n4\n", "\n", "\n", "k\n", "\n", "\n", "\n" ] }, "metadata": {}, "execution_count": 3 } ], "cell_type": "code", "source": [ "to_graphviz(P)" ], "metadata": {}, "execution_count": 3 }, { "cell_type": "markdown", "source": [ "It will be convenient to program with our preorders based on the Hasse Diagram\n", "represent as a labeled graph so we convert the Presentation{Schema, Symbol} into a FreeDigram.\n", "FreeDiagrams are implemented as an ACSet which you can think of as an in-memory database.\n", "ACSets are a key feature of Catlab that allow you to represent many data structures in a\n", "common framework." ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "FreeDiagram{Catlab.Theories.FreeSchema.Ob, Catlab.Theories.FreeSchema.Hom} {V:4, E:4, Ob:0, Hom:0}\n┌───┬────┐\n│\u001b[1m V │\u001b[1m ob │\n├───┼────┤\n│\u001b[1m 1 │ a₁ │\n│\u001b[1m 2 │ a₂ │\n│\u001b[1m 3 │ a₃ │\n│\u001b[1m 4 │ a₄ │\n└───┴────┘\n┌───┬─────┬─────┬─────┐\n│\u001b[1m E │\u001b[1m src │\u001b[1m tgt │\u001b[1m hom │\n├───┼─────┼─────┼─────┤\n│\u001b[1m 1 │ 1 │ 2 │ f │\n│\u001b[1m 2 │ 1 │ 3 │ g │\n│\u001b[1m 3 │ 2 │ 4 │ h │\n│\u001b[1m 4 │ 3 │ 4 │ k │\n└───┴─────┴─────┴─────┘\n", "text/html": [ "
\n", "FreeDiagram{Catlab.Theories.FreeSchema.Ob, Catlab.Theories.FreeSchema.Hom} {V:4, E:4, Ob:0, Hom:0}\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
Vob
1a₁
2a₂
3a₃
4a₄
\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
Esrctgthom
112f
213g
324h
434k
\n", "
\n" ] }, "metadata": {}, "execution_count": 4 } ], "cell_type": "code", "source": [ "g = FreeDiagram(P)" ], "metadata": {}, "execution_count": 4 }, { "cell_type": "markdown", "source": [ "To give ourselves a graph-like API for Hasse Diagrams, we define parents and children." ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "children (generic function with 1 method)" }, "metadata": {}, "execution_count": 5 } ], "cell_type": "code", "source": [ "parents(g, y::Int) = subpart(g, incident(g, y, :tgt), :src)\n", "children(g, x::Int) = subpart(g, incident(g, x, :src), :tgt)" ], "metadata": {}, "execution_count": 5 }, { "cell_type": "markdown", "source": [ "We can compute upsets/downsets with breadth first search." ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "bfs (generic function with 2 methods)" }, "metadata": {}, "execution_count": 6 } ], "cell_type": "code", "source": [ "function bfs(g, x::Int, f=children)\n", " explored = falses(nparts(g, :V))\n", " explored[x] = 1\n", " q = Queue{Int}()\n", " enqueue!(q, x)\n", " while !isempty(q)\n", " v = dequeue!(q)\n", " S = f(g,v)\n", " map(filter(s -> !explored[s], S)) do s\n", " enqueue!(q, s)\n", " end\n", " explored[S] .= true\n", " end\n", " return findall(explored)\n", "end" ], "metadata": {}, "execution_count": 6 }, { "cell_type": "markdown", "source": [ "The upset of a preorder element is all the elements that come after it in the preorder." ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "upset (generic function with 1 method)" }, "metadata": {}, "execution_count": 7 } ], "cell_type": "code", "source": [ "upset(g,x) = bfs(g,x,children)" ], "metadata": {}, "execution_count": 7 }, { "cell_type": "markdown", "source": [ "The downset is the dual notion, which we compute by reversing the role of children and parents." ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "4-element Vector{Int64}:\n 1\n 2\n 3\n 4" }, "metadata": {}, "execution_count": 8 } ], "cell_type": "code", "source": [ "downset(g,x) = bfs(g,x,parents)\n", "\n", "upset(g, 1)" ], "metadata": {}, "execution_count": 8 }, { "cell_type": "markdown", "source": [ "We can use upsets to define the less than or equal two relation implied by any Hasse Diagram" ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "leq (generic function with 1 method)" }, "metadata": {}, "execution_count": 9 } ], "cell_type": "code", "source": [ "function leq(g::FreeDiagram, x::Int, y::Int)\n", " return y in upset(g, x)\n", "end" ], "metadata": {}, "execution_count": 9 }, { "cell_type": "markdown", "source": [ "### Exercise 1\n", "Define a more efficient algorithm for checking whether two elements satisfy the leq relation." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Multiple dispatch allows us to overload the leq function with another method for symbols." ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "leq (generic function with 2 methods)" }, "metadata": {}, "execution_count": 10 } ], "cell_type": "code", "source": [ "function leq(g::FreeDiagram, x::Symbol, y::Symbol)\n", " leq(g, incident(g, x, :ob), incident(g, y, :ob))\n", "end" ], "metadata": {}, "execution_count": 10 }, { "cell_type": "markdown", "source": [ "the meet of two elements is the largest element in the intersection of their downsets." ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "meet (generic function with 2 methods)" }, "metadata": {}, "execution_count": 11 } ], "cell_type": "code", "source": [ "function meet(g::FreeDiagram, x::Int, y::Int)\n", " U = downset(g, x) ∩ downset(g,y)\n", " maxima(g, U)\n", " return maximum(g, U)\n", "end\n", "\n", "function meet(g::FreeDiagram, x, y)\n", " meet(g, incident(g, x, :ob)[1], incident(g, y, :ob)[1])\n", "end" ], "metadata": {}, "execution_count": 11 }, { "cell_type": "markdown", "source": [ "assuming that D is a downset, the maxima are those elements whose children are disjoint from D." ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "maximum (generic function with 1 method)" }, "metadata": {}, "execution_count": 12 } ], "cell_type": "code", "source": [ "function maxima(g::FreeDiagram, D::Vector{Int})\n", " X = Set(D)\n", " M = filter(D) do x\n", " Pₓ = children(g, x) ∩ X\n", " length(Pₓ) == 0\n", " end\n", " return M\n", "end\n", "\n", "function hastop(g::FreeDiagram, xs::Vector{Int})\n", " length(maxima(g, xs)) == 1\n", "end\n", "\n", "function maximum(g::FreeDiagram, xs::Vector{Int})\n", " m = maxima(g, xs::Vector{Int})\n", " if length(m) == 1\n", " return m[1]\n", " end\n", " if length(m) > 1\n", " all_iso = all(m) do a\n", " Uₐ = downset(g, a)\n", " a_le_allb = all(m) do b\n", " b in Uₐ\n", " end\n", " return a_le_allb\n", " end\n", " if all_iso\n", " return m[1]\n", " end\n", " end\n", " return nothing\n", "end" ], "metadata": {}, "execution_count": 12 }, { "cell_type": "markdown", "source": [ "From the definition of minimum, you can see that when you want to do many leq queries\n", "in sequence, you can reuse the upsets that you compute with bfs. This is a place where\n", "mathematical abstractions don't work well with the operational needs of computer programming.\n", "In a mathematical definition you can define x ≤ y as y ∈ upset(x), but in programming, that is\n", "inefficient when you want to check a property like for all y in Y, x ≤ y. Programming requires\n", "you to reason about not only the correctness of the code, but also the performance. Much of the\n", "complexity of software engineering comes from the fact that computational performance requires\n", "the programmers to break down their clean abstractions to optimize the code." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### Exercise 2\n", "If you wanted to perform many x ≤ y queries in a loop, you might want to\n", "precompute the matrix L where L[i,j] = 1 if and only if i ≤ j in the preorder P.\n", "Implement an algorithm that performs this computation in O(V⋅E) time where V is the number of\n", "elements in P and E is the number of edges in the corresponding FreeDiagram." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "## Testing it out" ], "metadata": {} }, { "cell_type": "markdown", "source": [ "Let's make sure we get the answers that we expect." ], "metadata": {} }, { "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Test Summary: | Pass Total Time\n", "Upsets | 4 4 0.2s\n", "Test Summary: | Pass Total Time\n", "Downsets | 4 4 0.0s\n", "Test Summary: | Pass Total Time\n", "Meets | 6 6 0.1s\n" ] }, { "output_type": "execute_result", "data": { "text/plain": "Test.DefaultTestSet(\"Meets\", Any[], 6, false, false, true, 1.71392832995066e9, 1.713928330052379e9, false, \"/home/runner/work/Catlab.jl/Catlab.jl/docs/src/generated/sketches/meets.ipynb\")" }, "metadata": {}, "execution_count": 13 } ], "cell_type": "code", "source": [ "using Test\n", "@testset \"Upsets\" begin\n", " @test upset(g, 3) == [3,4]\n", " @test upset(g, 2) == [2,4]\n", " @test upset(g, 1) == [1,2,3,4]\n", " @test upset(g, 4) == [4]\n", "end\n", "@testset \"Downsets\" begin\n", " @test downset(g, 3) == [1,3]\n", " @test downset(g, 2) == [1,2]\n", " @test downset(g, 4) == [1,2,3,4]\n", " @test downset(g, 1) == [1]\n", "end\n", "\n", "@testset \"Meets\" begin\n", " @test meet(g, 2,3) == 1\n", " @test meet(g, 1,2) == 1\n", " @test meet(g, 3,4) == 3\n", " @test meet(g, 1, 4) == 1\n", " @test meet(g, 1, 1) == 1\n", " @test meet(g, 2, 2) == 2\n", "end" ], "metadata": {}, "execution_count": 13 }, { "cell_type": "markdown", "source": [ "## Another Example:" ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "Presentation{Catlab.Theories.ThSchema.Meta.T, Symbol}(Catlab.Theories.FreeSchema, (Ob = Catlab.Theories.FreeSchema.Ob{:generator}[a₁, a₂, a₃, a₄, a₅], Hom = Catlab.Theories.FreeSchema.Hom{:generator}[f, g, h, k, l], AttrType = Catlab.Theories.FreeSchema.AttrType{:generator}[], Attr = Catlab.Theories.FreeSchema.Attr{:generator}[]), Dict(:a₃ => (:Ob => 3), :f => (:Hom => 1), :l => (:Hom => 5), :k => (:Hom => 4), :a₄ => (:Ob => 4), :a₁ => (:Ob => 1), :a₂ => (:Ob => 2), :g => (:Hom => 2), :h => (:Hom => 3), :a₅ => (:Ob => 5)…), Pair[])" }, "metadata": {}, "execution_count": 14 } ], "cell_type": "code", "source": [ "@present P(FreeSchema) begin\n", " (a₁,a₂,a₃,a₄, a₅)::Ob\n", " f::Hom(a₁, a₂)\n", " g::Hom(a₁, a₃)\n", " h::Hom(a₂, a₄)\n", " k::Hom(a₃, a₄)\n", " l::Hom(a₅, a₂)\n", "end" ], "metadata": {}, "execution_count": 14 }, { "cell_type": "markdown", "source": [ "Which can be viewed as a picture:" ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "Catlab.Graphics.Graphviz.Graph(\"G\", true, \"neato\", Catlab.Graphics.Graphviz.Statement[Catlab.Graphics.Graphviz.Node(\"n1\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"a₁\")), Catlab.Graphics.Graphviz.Node(\"n2\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"a₂\")), Catlab.Graphics.Graphviz.Node(\"n3\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"a₃\")), Catlab.Graphics.Graphviz.Node(\"n4\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"a₄\")), Catlab.Graphics.Graphviz.Node(\"n5\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"a₅\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"f\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"g\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"h\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"k\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n5\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"l\"))], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:margin => \"0\", :shape => \"ellipse\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}())", "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "G\n", "\n", "\n", "\n", "n1\n", "\n", "a₁\n", "\n", "\n", "\n", "n2\n", "\n", "a₂\n", "\n", "\n", "\n", "n1->n2\n", "\n", "\n", "f\n", "\n", "\n", "\n", "n3\n", "\n", "a₃\n", "\n", "\n", "\n", "n1->n3\n", "\n", "\n", "g\n", "\n", "\n", "\n", "n4\n", "\n", "a₄\n", "\n", "\n", "\n", "n2->n4\n", "\n", "\n", "h\n", "\n", "\n", "\n", "n3->n4\n", "\n", "\n", "k\n", "\n", "\n", "\n", "n5\n", "\n", "a₅\n", "\n", "\n", "\n", "n5->n2\n", "\n", "\n", "l\n", "\n", "\n", "\n" ] }, "metadata": {}, "execution_count": 15 } ], "cell_type": "code", "source": [ "to_graphviz(P)" ], "metadata": {}, "execution_count": 15 }, { "cell_type": "markdown", "source": [ "Or, as tables:" ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "FreeDiagram{Catlab.Theories.FreeSchema.Ob, Catlab.Theories.FreeSchema.Hom} {V:5, E:5, Ob:0, Hom:0}\n┌───┬────┐\n│\u001b[1m V │\u001b[1m ob │\n├───┼────┤\n│\u001b[1m 1 │ a₁ │\n│\u001b[1m 2 │ a₂ │\n│\u001b[1m 3 │ a₃ │\n│\u001b[1m 4 │ a₄ │\n│\u001b[1m 5 │ a₅ │\n└───┴────┘\n┌───┬─────┬─────┬─────┐\n│\u001b[1m E │\u001b[1m src │\u001b[1m tgt │\u001b[1m hom │\n├───┼─────┼─────┼─────┤\n│\u001b[1m 1 │ 1 │ 2 │ f │\n│\u001b[1m 2 │ 1 │ 3 │ g │\n│\u001b[1m 3 │ 2 │ 4 │ h │\n│\u001b[1m 4 │ 3 │ 4 │ k │\n│\u001b[1m 5 │ 5 │ 2 │ l │\n└───┴─────┴─────┴─────┘\n", "text/html": [ "
\n", "FreeDiagram{Catlab.Theories.FreeSchema.Ob, Catlab.Theories.FreeSchema.Hom} {V:5, E:5, Ob:0, Hom:0}\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
Vob
1a₁
2a₂
3a₃
4a₄
5a₅
\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
Esrctgthom
112f
213g
324h
434k
552l
\n", "
\n" ] }, "metadata": {}, "execution_count": 16 } ], "cell_type": "code", "source": [ "g = FreeDiagram(P)" ], "metadata": {}, "execution_count": 16 }, { "cell_type": "markdown", "source": [ "### Test suite" ], "metadata": {} }, { "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Test Summary: | Pass Total Time\n", "meets2 | 8 8 0.0s\n" ] }, { "output_type": "execute_result", "data": { "text/plain": "Test.DefaultTestSet(\"meets2\", Any[], 8, false, false, true, 1.713928330104718e9, 1.713928330104883e9, false, \"/home/runner/work/Catlab.jl/Catlab.jl/docs/src/generated/sketches/meets.ipynb\")" }, "metadata": {}, "execution_count": 17 } ], "cell_type": "code", "source": [ "@testset \"meets2\" begin\n", " @test meet(g, 2,3) == 1\n", " @test meet(g, 1,2) == 1\n", " @test meet(g, 3,4) == 3\n", " @test meet(g, 1, 4) == 1\n", " @test meet(g, 1, 1) == 1\n", " @test meet(g, 2, 2) == 2\n", " @test meet(g, 3, 5) == nothing\n", " @test meet(g, 2, 5) == 5\n", "end" ], "metadata": {}, "execution_count": 17 }, { "cell_type": "markdown", "source": [ "### Exercise 3\n", "Make bigger preorders to test corner cases in the above code.\n", "If you find an example that breaks these implementations, please report it." ], "metadata": {} }, { "cell_type": "markdown", "source": [ "### Exercise 4\n", "Implement the dual constructions for joins." ], "metadata": {} } ], "nbformat_minor": 3, "metadata": { "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.10.2" }, "kernelspec": { "name": "julia-1.10", "display_name": "Julia 1.10.2", "language": "julia" } }, "nbformat": 4 }