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 setE ⊆ V^2
is a set of directed edgesF ⊆ {{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
toVe
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 verticesv1
,w1
such that(v, v1) ∈ E
andv1
is not equal toVe
and{v, w1} ∈ F
, then there also exists a vertexu
such that(w1, u) ∈ E
and{v1, u} ∈ F
. - For each vertex
v
if there exist verticesv1
,w1
such that(v1, v) ∈ E
andw1
is not equal toVs
and{v, w1} ∈ F
, then there also exists a vertexu
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-GraphjestDobrzeUlozony(+EFgraf)
- checks if the given EF-Graph is well-layoutedjestDobrzePermutujacy(+EFGraf)
- checks if the given EF-Graph is well-permutingjestSucc(+EFgraf, -Lista1, -Lista2)
- checks if F-route represented by the list of node labelsLista2
represents a successor of the F-route represented by the list of node labelsLista1
in the EF-GraphEFgraf