{"id":3400,"date":"2026-10-08T13:49:20","date_gmt":"2026-10-08T11:49:20","guid":{"rendered":"https:\/\/galaxy.agh.edu.pl\/~sedziwy\/wordpress\/?page_id=3400"},"modified":"2026-10-15T15:35:29","modified_gmt":"2026-10-15T13:35:29","slug":"wptg-2026-2027","status":"publish","type":"page","link":"https:\/\/galaxy.agh.edu.pl\/~sedziwy\/wordpress\/?page_id=3400","title":{"rendered":"WPTG 2026-2027"},"content":{"rendered":"<p><strong>Specyfikacja grafu<\/strong><\/p>\n<pre data-line=\"1\" data-line-type=\"context\" data-line-index=\"0\"><span style=\"color: #800080;\">{<\/span>\r\n<span style=\"color: #800080;\">\"graph\":{<\/span>\r\n<span style=\"color: #800080;\">\"directed\":false,<\/span>\r\n<span style=\"color: #800080;\">\"name\":\"Przyk\u0142adowy graf G\",<\/span>\r\n<span style=\"color: #800080;\">\"vertices\":[<\/span>\r\n<span style=\"color: #800080;\">{\"index\":0,\"label\":\"A\"},<\/span>\r\n<span style=\"color: #800080;\">{\"index\":1,\"label\":\"B\"},<\/span>\r\n<span style=\"color: #800080;\">{\"index\":2,\"label\":\"C\"},<\/span>\r\n<span style=\"color: #800080;\">{\"index\":3,\"label\":\"D\"}<\/span>\r\n<span style=\"color: #800080;\">],<\/span>\r\n\r\n<span style=\"color: #800080;\">\"edges\":[<\/span>\r\n<span style=\"color: #800080;\">{\"u\":0,\"v\":1},<\/span>\r\n<span style=\"color: #800080;\">{\"u\":0,\"v\":2},<\/span>\r\n<span style=\"color: #800080;\">{\"u\":1,\"v\":2},<\/span>\r\n<span style=\"color: #800080;\">{\"u\":2,\"v\":3,\"weight\":4.5,\"label\":\"most\"}<\/span>\r\n<span style=\"color: #800080;\">]<\/span>\r\n<span style=\"color: #800080;\">}<\/span>\r\n<span style=\"color: #800080;\">}\r\n\r\n<\/span><\/pre>\n<p dir=\"ltr\">Format, w kt\u00f3rym obie strony produkcji s\u0105 grafami w powy\u017cszym formacie. Do tego dochodz\u0105 dwie rzeczy, bez kt\u00f3rych sama para graf\u00f3w nie wystarcza:<\/p>\n<ul dir=\"ltr\">\n<li><strong>odwzorowanie<\/strong> (<code>mapping<\/code>): kt\u00f3re wierzcho\u0142ki lewej strony przechodz\u0105 na praw\u0105, czyli zostaj\u0105 zachowane;<\/li>\n<li><strong>regu\u0142y osadzania<\/strong> (<code>embedding<\/code>): co zrobi\u0107 z kraw\u0119dziami, kt\u00f3re \u0142\u0105czy\u0142y usuwane wierzcho\u0142ki z reszt\u0105 grafu, do kt\u00f3rego stosujemy produkcj\u0119.<\/li>\n<\/ul>\n<div>\n<div>\n<div>\n<div>\n<pre>{\r\n  \"production\": {\r\n    \"name\": \"P1\",\r\n    \"directed\": false,\r\n\r\n    \"left\": {\r\n      \"vertices\": [\r\n        { \"index\": 0, \"label\": \"A\" },\r\n        { \"index\": 1, \"label\": \"X\" }\r\n      ],\r\n      \"edges\": [\r\n        { \"u\": 0, \"v\": 1 }\r\n      ]\r\n    },\r\n\r\n    \"right\": {\r\n      \"vertices\": [\r\n        { \"index\": 0, \"label\": \"A\" },\r\n        { \"index\": 1, \"label\": \"Y\" },\r\n        { \"index\": 2, \"label\": \"Z\" }\r\n      ],\r\n      \"edges\": [\r\n        { \"u\": 0, \"v\": 1 },\r\n        { \"u\": 1, \"v\": 2 }\r\n      ]\r\n    },\r\n\r\n    \"mapping\": [\r\n      { \"left\": 0, \"right\": 0 }\r\n    ],\r\n\r\n    \"embedding\": [\r\n      { \"leftVertex\": 1, \"neighborLabel\": \"*\", \"connectTo\": [2] }\r\n    ]\r\n  }\r\n}<\/pre>\n<\/div>\n<div>\n<div><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<p dir=\"ltr\"><strong>Co robi ta produkcja:<\/strong> szuka w grafie wierzcho\u0142ka <code>X<\/code> po\u0142\u0105czonego z <code>A<\/code>. Wierzcho\u0142ek <code>A<\/code> zostaje (jest w <code>mapping<\/code>). <code>X<\/code> jest usuwany, a w jego miejsce powstaje \u015bcie\u017cka <code>A \u2013 Y \u2013 Z<\/code>. Wszystkie inne kraw\u0119dzie, kt\u00f3re <code>X<\/code> mia\u0142 w grafie (poza kraw\u0119dzi\u0105 do <code>A<\/code>), zostaj\u0105 przepi\u0119te do <code>Z<\/code>.<\/p>\n<p dir=\"ltr\"><strong>Znaczenie p\u00f3l:<\/strong><\/p>\n<ul dir=\"ltr\">\n<li><code>left<\/code> to lewa strona (G): wzorzec, kt\u00f3ry szukamy w grafie.<\/li>\n<li><code>right<\/code> to prawa strona (H): co wstawiamy w miejsce wzorca. Indeksy w <code>left<\/code> i <code>right<\/code> s\u0105 niezale\u017cne, \u0142\u0105czy je tylko <code>mapping<\/code>.<\/li>\n<li><code>mapping<\/code> to pary <code>left \u2192 right<\/code> dla wierzcho\u0142k\u00f3w zachowanych. Z niego wynika:\n<ul dir=\"ltr\">\n<li>wierzcho\u0142ek z <code>left<\/code> bez pary jest <strong>usuwany<\/strong>;<\/li>\n<li>wierzcho\u0142ek z <code>right<\/code> bez pary jest <strong>tworzony<\/strong>;<\/li>\n<li>wierzcho\u0142ek z par\u0105 <strong>zostaje<\/strong>, razem ze wszystkimi swoimi kraw\u0119dziami do reszty grafu. Jego etykieta mo\u017ce si\u0119 zmieni\u0107, je\u015bli w <code>right<\/code> ma inn\u0105.<\/li>\n<\/ul>\n<\/li>\n<li><code>embedding<\/code> m\u00f3wi, co zrobi\u0107 z kraw\u0119dziami usuwanych wierzcho\u0142k\u00f3w:\n<ul dir=\"ltr\">\n<li><code>leftVertex<\/code> to usuwany wierzcho\u0142ek z <code>left<\/code>;<\/li>\n<li><code>neighborLabel<\/code> to etykieta s\u0105siada spoza wzorca, kt\u00f3rego dotyczy regu\u0142a (<code>\"*\"<\/code> oznacza dowoln\u0105 etykiet\u0119);<\/li>\n<li><code>connectTo<\/code> to lista wierzcho\u0142k\u00f3w z <code>right<\/code>, do kt\u00f3rych te kraw\u0119dzie s\u0105 przepinane (mo\u017ce by\u0107 kilka albo \u017caden).<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p dir=\"ltr\"><strong>Zasady poprawno\u015bci:<\/strong><\/p>\n<ol dir=\"ltr\" start=\"1\">\n<li>Oba grafy spe\u0142niaj\u0105 warunki z poprzedniego formatu: indeksy unikalne, kraw\u0119dzie wskazuj\u0105 istniej\u0105ce wierzcho\u0142ki.<\/li>\n<li><code>mapping<\/code> jest r\u00f3\u017cnowarto\u015bciowe: ka\u017cdy indeks z <code>left<\/code> i z <code>right<\/code> wyst\u0119puje w nim najwy\u017cej raz.<\/li>\n<li><code>leftVertex<\/code> w <code>embedding<\/code> musi by\u0107 wierzcho\u0142kiem usuwanym (bez pary w <code>mapping<\/code>), a <code>connectTo<\/code> musi wskazywa\u0107 istniej\u0105ce wierzcho\u0142ki <code>right<\/code>.<\/li>\n<li>Je\u015bli usuwany wierzcho\u0142ek ma w grafie kraw\u0119d\u017a do s\u0105siada, kt\u00f3rego nie obejmuje \u017cadna regu\u0142a <code>embedding<\/code>, trzeba z g\u00f3ry wybra\u0107, co si\u0119 dzieje:\n<ul dir=\"ltr\">\n<li>produkcji nie wolno zastosowa\u0107, albo<\/li>\n<li>kraw\u0119d\u017a jest po prostu usuwana.<\/li>\n<\/ul>\n<p dir=\"ltr\">Ten wyb\u00f3r warto zapisa\u0107 jawnie, np. jako pole <code>\"danglingEdges\": \"forbid\"<\/code> lub <code>\"delete\"<\/code>.<\/p>\n<\/li>\n<\/ol>\n<p dir=\"ltr\"><strong>Rozszerzenia, je\u015bli b\u0119d\u0105 potrzebne:<\/strong><\/p>\n<ul dir=\"ltr\">\n<li>Ca\u0142\u0105 gramatyk\u0119 zapiszesz jako <code>{ \"startGraph\": {...}, \"productions\": [ ... ] }<\/code>.<\/li>\n<li>Warunki stosowalno\u015bci, np. \u201ewierzcho\u0142ek X nie mo\u017ce mie\u0107 s\u0105siada o etykiecie B\u201d, mo\u017cna doda\u0107 jako pole <code>\"negativeConditions\"<\/code> z dodatkowymi grafami.<\/li>\n<li>Etykiety kraw\u0119dzi (<code>label<\/code> przy kraw\u0119dzi) dzia\u0142aj\u0105 po obu stronach tak samo jak w poprzednim formacie.<\/li>\n<\/ul>\n<pre data-line=\"1\" data-line-type=\"context\" data-line-index=\"0\"><span style=\"color: #800080;\"> Przyk\u0142adowy graf: http:\/\/galaxy.agh.edu.pl\/~sedziwy\/wordpress\/wp-content\/uploads\/graph_json-1.txt <a href=\"http:\/\/galaxy.agh.edu.pl\/~sedziwy\/wordpress\/wp-content\/uploads\/graph_json-1.txt\">graph_json<\/a>\r\n<\/span><\/pre>\n<p><strong>Gramatyka grafowa<\/strong><\/p>\n<p dir=\"ltr\">Gramatyka sk\u0142ada si\u0119 z grafu startowego, zbior\u00f3w etykiet i listy produkcji w formacie zaproponowanym wcze\u015bniej. Poni\u017cej przyk\u0142ad, kt\u00f3ry generuje \u015bcie\u017cki typu <code>a \u2013 a \u2013 \u2026 \u2013 a \u2013 b<\/code>:<\/p>\n<div>\n<div>\n<div>\n<div>\n<pre>{\r\n  \"grammar\": {\r\n    \"name\": \"Gramatyka \u015bcie\u017cek\",\r\n    \"directed\": false,\r\n    \"danglingEdges\": \"forbid\",\r\n\r\n    \"labels\": {\r\n      \"nonterminals\": [\"S\", \"A\"],\r\n      \"terminals\": [\"a\", \"b\"]\r\n    },\r\n\r\n    \"startGraph\": {\r\n      \"vertices\": [\r\n        { \"index\": 0, \"label\": \"S\" }\r\n      ],\r\n      \"edges\": []\r\n    },\r\n\r\n    \"productions\": [\r\n      {\r\n        \"name\": \"P1\",\r\n        \"description\": \"S \u2192 A \u2013 S (wyd\u0142u\u017cenie \u015bcie\u017cki)\",\r\n        \"left\": {\r\n          \"vertices\": [ { \"index\": 0, \"label\": \"S\" } ],\r\n          \"edges\": []\r\n        },\r\n        \"right\": {\r\n          \"vertices\": [\r\n            { \"index\": 0, \"label\": \"A\" },\r\n            { \"index\": 1, \"label\": \"S\" }\r\n          ],\r\n          \"edges\": [ { \"u\": 0, \"v\": 1 } ]\r\n        },\r\n        \"mapping\": [],\r\n        \"embedding\": [\r\n          { \"leftVertex\": 0, \"neighborLabel\": \"*\", \"connectTo\": [0] }\r\n        ]\r\n      },\r\n      {\r\n        \"name\": \"P2\",\r\n        \"description\": \"A \u2192 a\",\r\n        \"left\": {\r\n          \"vertices\": [ { \"index\": 0, \"label\": \"A\" } ],\r\n          \"edges\": []\r\n        },\r\n        \"right\": {\r\n          \"vertices\": [ { \"index\": 0, \"label\": \"a\" } ],\r\n          \"edges\": []\r\n        },\r\n        \"mapping\": [ { \"left\": 0, \"right\": 0 } ],\r\n        \"embedding\": []\r\n      },\r\n      {\r\n        \"name\": \"P3\",\r\n        \"description\": \"S \u2192 b (zako\u0144czenie)\",\r\n        \"left\": {\r\n          \"vertices\": [ { \"index\": 0, \"label\": \"S\" } ],\r\n          \"edges\": []\r\n        },\r\n        \"right\": {\r\n          \"vertices\": [ { \"index\": 0, \"label\": \"b\" } ],\r\n          \"edges\": []\r\n        },\r\n        \"mapping\": [ { \"left\": 0, \"right\": 0 } ],\r\n        \"embedding\": []\r\n      }\r\n    ]\r\n  }\r\n}<\/pre>\n<\/div>\n<div>\n<div><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<h3 dir=\"ltr\">Nowe pola (poza samymi produkcjami)<\/h3>\n<ul dir=\"ltr\">\n<li><code>name<\/code>, <code>directed<\/code>: nazwa gramatyki i typ graf\u00f3w. Wszystkie produkcje i graf startowy musz\u0105 mie\u0107 ten sam typ, wi\u0119c <code>directed<\/code> jest tu raz zamiast w ka\u017cdej produkcji.<\/li>\n<li><code>danglingEdges<\/code>: wsp\u00f3lna zasada dla wszystkich produkcji. M\u00f3wi, co zrobi\u0107 z kraw\u0119dzi\u0105 usuwanego wierzcho\u0142ka, kt\u00f3rej nie obejmuje \u017cadna regu\u0142a <code>embedding<\/code>:\n<ul dir=\"ltr\">\n<li><code>\"forbid\"<\/code>: produkcji nie wolno zastosowa\u0107;<\/li>\n<li><code>\"delete\"<\/code>: kraw\u0119d\u017a jest usuwana.<\/li>\n<\/ul>\n<p dir=\"ltr\">Pojedyncza produkcja mo\u017ce j\u0105 nadpisa\u0107 w\u0142asnym polem <code>danglingEdges<\/code>.<\/p>\n<\/li>\n<li><code>labels<\/code>: etykiety nieterminalne (do dalszego przepisywania) i terminalne (ko\u0144cowe). Graf nale\u017cy do j\u0119zyka gramatyki, gdy wszystkie jego wierzcho\u0142ki maj\u0105 etykiety terminalne.<\/li>\n<li><code>startGraph<\/code>: graf startowy w formacie grafu z wcze\u015bniejszej propozycji.<\/li>\n<li><code>productions<\/code>: lista produkcji w formacie z wcze\u015bniejszej propozycji. Pole <code>description<\/code> jest opcjonalne i s\u0142u\u017cy tylko do czytania przez cz\u0142owieka.<\/li>\n<\/ul>\n<h3 dir=\"ltr\">Jak dzia\u0142a przyk\u0142ad<\/h3>\n<p dir=\"ltr\">Wyprowadzenie, w kt\u00f3rym stosujemy kolejno P1, P1, P3, P2, P2:<\/p>\n<div>\n<div>\n<div>\n<div>\n<pre>S  \u21d2P1  A \u2013 S  \u21d2P1  A \u2013 A \u2013 S  \u21d2P3  A \u2013 A \u2013 b  \u21d2P2  a \u2013 A \u2013 b  \u21d2P2  a \u2013 a \u2013 b<\/pre>\n<\/div>\n<div>\n<div><\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<ul dir=\"ltr\">\n<li><strong>P1<\/strong> usuwa <code>S<\/code> i wstawia <code>A \u2013 S<\/code>. Za drugim razem <code>S<\/code> ma ju\u017c s\u0105siada (<code>A<\/code> z poprzedniego kroku). Regu\u0142a <code>embedding<\/code> przepina t\u0119 kraw\u0119d\u017a do nowego <code>A<\/code> (indeks 0 po prawej stronie), wi\u0119c \u015bcie\u017cka si\u0119 nie rozpada.<\/li>\n<li><strong>P2<\/strong> i <strong>P3<\/strong> tylko zmieniaj\u0105 etykiet\u0119. Wierzcho\u0142ek jest w <code>mapping<\/code>, czyli zachowany, wi\u0119c zachowuje wszystkie swoje kraw\u0119dzie i <code>embedding<\/code> nie jest potrzebny.<\/li>\n<\/ul>\n<h3 dir=\"ltr\">Zasady poprawno\u015bci ca\u0142ej gramatyki<\/h3>\n<ol dir=\"ltr\" start=\"1\">\n<li>Zbiory <code>nonterminals<\/code> i <code>terminals<\/code> s\u0105 roz\u0142\u0105czne.<\/li>\n<li>Ka\u017cda etykieta u\u017cyta w <code>startGraph<\/code> i w produkcjach nale\u017cy do jednego z tych zbior\u00f3w.<\/li>\n<li>Lewa strona ka\u017cdej produkcji zawiera co najmniej jeden nieterminal, bo inaczej produkcja przepisywa\u0142aby gotowy fragment wyniku.<\/li>\n<li>Nazwy produkcji (<code>name<\/code>) s\u0105 unikalne.<\/li>\n<li>Ka\u017cda produkcja spe\u0142nia warunki z wcze\u015bniejszej propozycji: poprawne grafy, r\u00f3\u017cnowarto\u015bciowe <code>mapping<\/code>, poprawne odwo\u0142ania w <code>embedding<\/code>.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Specyfikacja grafu { &#8222;graph&#8221;:{ &#8222;directed&#8221;:false, &#8222;name&#8221;:&#8221;Przyk\u0142adowy graf G&#8221;, &#8222;vertices&#8221;:[ {&#8222;index&#8221;:0,&#8221;label&#8221;:&#8221;A&#8221;}, {&#8222;index&#8221;:1,&#8221;label&#8221;:&#8221;B&#8221;}, {&#8222;index&#8221;:2,&#8221;label&#8221;:&#8221;C&#8221;}, {&#8222;index&#8221;:3,&#8221;label&#8221;:&#8221;D&#8221;} ], &#8222;edges&#8221;:[ {&#8222;u&#8221;:0,&#8221;v&#8221;:1}, {&#8222;u&#8221;:0,&#8221;v&#8221;:2}, {&#8222;u&#8221;:1,&#8221;v&#8221;:2}, {&#8222;u&#8221;:2,&#8221;v&#8221;:3,&#8221;weight&#8221;:4.5,&#8221;label&#8221;:&#8221;most&#8221;} ] } } Format, w kt\u00f3rym obie strony produkcji s\u0105 grafami w powy\u017cszym formacie. Do tego dochodz\u0105 dwie rzeczy, bez kt\u00f3rych sama para graf\u00f3w nie wystarcza: odwzorowanie (mapping): kt\u00f3re wierzcho\u0142ki lewej strony przechodz\u0105 na praw\u0105, czyli &hellip; <a href=\"https:\/\/galaxy.agh.edu.pl\/~sedziwy\/wordpress\/?page_id=3400\" class=\"more-link\">Czytaj dalej <span class=\"screen-reader-text\">WPTG 2026-2027<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-3400","page","type-page","status-publish","hentry"],"jetpack_shortlink":"https:\/\/wp.me\/P5r0Nf-SQ","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/galaxy.agh.edu.pl\/~sedziwy\/wordpress\/index.php?rest_route=\/wp\/v2\/pages\/3400","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/galaxy.agh.edu.pl\/~sedziwy\/wordpress\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/galaxy.agh.edu.pl\/~sedziwy\/wordpress\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/galaxy.agh.edu.pl\/~sedziwy\/wordpress\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/galaxy.agh.edu.pl\/~sedziwy\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3400"}],"version-history":[{"count":7,"href":"https:\/\/galaxy.agh.edu.pl\/~sedziwy\/wordpress\/index.php?rest_route=\/wp\/v2\/pages\/3400\/revisions"}],"predecessor-version":[{"id":3418,"href":"https:\/\/galaxy.agh.edu.pl\/~sedziwy\/wordpress\/index.php?rest_route=\/wp\/v2\/pages\/3400\/revisions\/3418"}],"wp:attachment":[{"href":"https:\/\/galaxy.agh.edu.pl\/~sedziwy\/wordpress\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3400"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}