This code was written as an assignment during course on Warsaw University.

The code is bundled using PHP so it should be available from terminal as well as swipl utility. To build the project run make all. The bundled Prolog file will be present in build/ folder.

To run tests with swipl command line please call make test command from your shell.

EF-Graph is a triplet <V, E, F> where:

• V is a vertex set
• E ⊆ V^2 is a set of directed edges
• F ⊆ {{v1, v2} | v1, v2 ∈ V } is a set of undirected edges

The ordered sequence of vertices v1, . . . , vn is a valid E-route iff for each i = 1, . . . , n − 1 the condition <vi, vi+1> ∈ E is met.

The ordered sequence of vertices v1, . . . , vn is a valid F-route iff for each i = 1, . . . , n − 1 the condition {vi, vi+1} ∈ F is met.

The EF-graph G is well-layouted iff the following conditions are met:

• There is exactly one pair of vertices Vs, Ve such that there is no (v, Vs) E-edges and no (Ve, v') E-edges.
• There exists a Hamiltonian path from Vs to Ve using only E-edges.
• For each vertex v ∈ V there is at most 3 F-edges that have endings in that vertex.

For a given EF-Graph the Vs will be called graph source and Ve graph drain.

The EF-graph G is well-permuting iff the following conditions are met:

• For each vertex v if there exist vertices v1, w1 such that (v, v1) ∈ E and v1 is not equal to Ve and {v, w1} ∈ F, then there also exists a vertex u such that (w1, u) ∈ E and {v1, u} ∈ F.
• For each vertex v if there exist vertices v1, w1 such that (v1, v) ∈ E and w1 is not equal to Vs and {v, w1} ∈ F, then there also exists a vertex u such that (u, w1) ∈ E and {v1, u} ∈ F.

Let v1, . . . , vn and w1, . . . , wm be F-routes. We say that v1, . . . , vn is an succesor of w1, . . . , wm iff the following conditions are met:

• m ≤ n
• for each i ∈ {1, . . . , m}, (wi, vi) ∈ E.

The EF-Graphs are represented inside the program as incidention lists, where each node is a tuple consiting of node's label, its E-neighbours and F-neighbours.

For example, for EF-Graph:

• V = {v0, v1, v2, v3}
• E = {(v0, v1),(v1, v2),(v2, v3)}
• F = {{v0, v2}, {v1, v3}}

We represent node v0 as term node(v0, [v1], [v2]) and the entire graph is represented using the following list:

  [
    node(v0, [v1], [v2]),
    node(v1, [v2], [v3]),
    node(v2, [v3], [v0]),
    node(v3, [], [v1])
  ]

This gaph is well-layouted and well-permuting.

The program defines its main predicates:

• jestEFGrafem(+Term) - checks if the term is a well-specified EF-Graph
• jestDobrzeUlozony(+EFgraf) - checks if the given EF-Graph is well-layouted
• jestDobrzePermutujacy(+EFGraf) - checks if the given EF-Graph is well-permuting
• jestSucc(+EFgraf, -Lista1, -Lista2) - checks if F-route represented by the list of node labels Lista2 represents a successor of the F-route represented by the list of node labels Lista1 in the EF-Graph EFgraf