Specyfikacja grafu

{
"graph":{
"directed":false,
"name":"Przykładowy graf G",
"vertices":[
{"index":0,"label":"A"},
{"index":1,"label":"B"},
{"index":2,"label":"C"},
{"index":3,"label":"D"}
],

"edges":[
{"u":0,"v":1},
{"u":0,"v":2},
{"u":1,"v":2},
{"u":2,"v":3,"weight":4.5,"label":"most"}
]
}
}

Format, w którym obie strony produkcji są grafami w powyższym formacie. Do tego dochodzą dwie rzeczy, bez których sama para grafów nie wystarcza:

• odwzorowanie (mapping): które wierzchołki lewej strony przechodzą na prawą, czyli zostają zachowane;
• reguły osadzania (embedding): co zrobić z krawędziami, które łączyły usuwane wierzchołki z resztą grafu, do którego stosujemy produkcję.

{
  "production": {
    "name": "P1",
    "directed": false,

    "left": {
      "vertices": [
        { "index": 0, "label": "A" },
        { "index": 1, "label": "X" }
      ],
      "edges": [
        { "u": 0, "v": 1 }
      ]
    },

    "right": {
      "vertices": [
        { "index": 0, "label": "A" },
        { "index": 1, "label": "Y" },
        { "index": 2, "label": "Z" }
      ],
      "edges": [
        { "u": 0, "v": 1 },
        { "u": 1, "v": 2 }
      ]
    },

    "mapping": [
      { "left": 0, "right": 0 }
    ],

    "embedding": [
      { "leftVertex": 1, "neighborLabel": "*", "connectTo": [2] }
    ]
  }
}

Co robi ta produkcja: szuka w grafie wierzchołka X połączonego z A. Wierzchołek A zostaje (jest w mapping). X jest usuwany, a w jego miejsce powstaje ścieżka A – Y – Z. Wszystkie inne krawędzie, które X miał w grafie (poza krawędzią do A), zostają przepięte do Z.

Znaczenie pól:

• left to lewa strona (G): wzorzec, który szukamy w grafie.
• right to prawa strona (H): co wstawiamy w miejsce wzorca. Indeksy w left i right są niezależne, łączy je tylko mapping.
• mapping to pary left → right dla wierzchołków zachowanych. Z niego wynika:
  • wierzchołek z left bez pary jest usuwany;
  • wierzchołek z right bez pary jest tworzony;
  • wierzchołek z parą zostaje, razem ze wszystkimi swoimi krawędziami do reszty grafu. Jego etykieta może się zmienić, jeśli w right ma inną.
• embedding mówi, co zrobić z krawędziami usuwanych wierzchołków:
  • leftVertex to usuwany wierzchołek z left;
  • neighborLabel to etykieta sąsiada spoza wzorca, którego dotyczy reguła ("*" oznacza dowolną etykietę);
  • connectTo to lista wierzchołków z right, do których te krawędzie są przepinane (może być kilka albo żaden).

Zasady poprawności:

1. Oba grafy spełniają warunki z poprzedniego formatu: indeksy unikalne, krawędzie wskazują istniejące wierzchołki.
2. mapping jest różnowartościowe: każdy indeks z left i z right występuje w nim najwyżej raz.
3. leftVertex w embedding musi być wierzchołkiem usuwanym (bez pary w mapping), a connectTo musi wskazywać istniejące wierzchołki right.
4. Jeśli usuwany wierzchołek ma w grafie krawędź do sąsiada, którego nie obejmuje żadna reguła embedding, trzeba z góry wybrać, co się dzieje:
   • produkcji nie wolno zastosować, albo
   • krawędź jest po prostu usuwana.

   Ten wybór warto zapisać jawnie, np. jako pole "danglingEdges": "forbid" lub "delete".

Rozszerzenia, jeśli będą potrzebne:

• Całą gramatykę zapiszesz jako { "startGraph": {...}, "productions": [ ... ] }.
• Warunki stosowalności, np. „wierzchołek X nie może mieć sąsiada o etykiecie B”, można dodać jako pole "negativeConditions" z dodatkowymi grafami.
• Etykiety krawędzi (label przy krawędzi) działają po obu stronach tak samo jak w poprzednim formacie.

 Przykładowy graf: http://galaxy.agh.edu.pl/~sedziwy/wordpress/wp-content/uploads/graph_json-1.txt graph_json

Gramatyka grafowa

Gramatyka składa się z grafu startowego, zbiorów etykiet i listy produkcji w formacie zaproponowanym wcześniej. Poniżej przykład, który generuje ścieżki typu a – a – … – a – b:

{
  "grammar": {
    "name": "Gramatyka ścieżek",
    "directed": false,
    "danglingEdges": "forbid",

    "labels": {
      "nonterminals": ["S", "A"],
      "terminals": ["a", "b"]
    },

    "startGraph": {
      "vertices": [
        { "index": 0, "label": "S" }
      ],
      "edges": []
    },

    "productions": [
      {
        "name": "P1",
        "description": "S → A – S (wydłużenie ścieżki)",
        "left": {
          "vertices": [ { "index": 0, "label": "S" } ],
          "edges": []
        },
        "right": {
          "vertices": [
            { "index": 0, "label": "A" },
            { "index": 1, "label": "S" }
          ],
          "edges": [ { "u": 0, "v": 1 } ]
        },
        "mapping": [],
        "embedding": [
          { "leftVertex": 0, "neighborLabel": "*", "connectTo": [0] }
        ]
      },
      {
        "name": "P2",
        "description": "A → a",
        "left": {
          "vertices": [ { "index": 0, "label": "A" } ],
          "edges": []
        },
        "right": {
          "vertices": [ { "index": 0, "label": "a" } ],
          "edges": []
        },
        "mapping": [ { "left": 0, "right": 0 } ],
        "embedding": []
      },
      {
        "name": "P3",
        "description": "S → b (zakończenie)",
        "left": {
          "vertices": [ { "index": 0, "label": "S" } ],
          "edges": []
        },
        "right": {
          "vertices": [ { "index": 0, "label": "b" } ],
          "edges": []
        },
        "mapping": [ { "left": 0, "right": 0 } ],
        "embedding": []
      }
    ]
  }
}

Nowe pola (poza samymi produkcjami)

• name, directed: nazwa gramatyki i typ grafów. Wszystkie produkcje i graf startowy muszą mieć ten sam typ, więc directed jest tu raz zamiast w każdej produkcji.
• danglingEdges: wspólna zasada dla wszystkich produkcji. Mówi, co zrobić z krawędzią usuwanego wierzchołka, której nie obejmuje żadna reguła embedding:
  • "forbid": produkcji nie wolno zastosować;
  • "delete": krawędź jest usuwana.

  Pojedyncza produkcja może ją nadpisać własnym polem danglingEdges.

• labels: etykiety nieterminalne (do dalszego przepisywania) i terminalne (końcowe). Graf należy do języka gramatyki, gdy wszystkie jego wierzchołki mają etykiety terminalne.
• startGraph: graf startowy w formacie grafu z wcześniejszej propozycji.
• productions: lista produkcji w formacie z wcześniejszej propozycji. Pole description jest opcjonalne i służy tylko do czytania przez człowieka.

Jak działa przykład

Wyprowadzenie, w którym stosujemy kolejno P1, P1, P3, P2, P2:

S  ⇒P1  A – S  ⇒P1  A – A – S  ⇒P3  A – A – b  ⇒P2  a – A – b  ⇒P2  a – a – b

• P1 usuwa S i wstawia A – S. Za drugim razem S ma już sąsiada (A z poprzedniego kroku). Reguła embedding przepina tę krawędź do nowego A (indeks 0 po prawej stronie), więc ścieżka się nie rozpada.
• P2 i P3 tylko zmieniają etykietę. Wierzchołek jest w mapping, czyli zachowany, więc zachowuje wszystkie swoje krawędzie i embedding nie jest potrzebny.

Zasady poprawności całej gramatyki

1. Zbiory nonterminals i terminals są rozłączne.
2. Każda etykieta użyta w startGraph i w produkcjach należy do jednego z tych zbiorów.
3. Lewa strona każdej produkcji zawiera co najmniej jeden nieterminal, bo inaczej produkcja przepisywałaby gotowy fragment wyniku.
4. Nazwy produkcji (name) są unikalne.
5. Każda produkcja spełnia warunki z wcześniejszej propozycji: poprawne grafy, różnowartościowe mapping, poprawne odwołania w embedding.