f
to t
.Because a POSet is transitive, all transitive edges are also added to the graph. If the edge already exists, the this function does nothing.
var pos = new POSet[String]
pos.add_edge("A", "B") # add A->B
assert pos.has_edge("A", "C") == false
pos.add_edge("B", "C") # add B->C
assert pos.has_edge("A", "C") == true
If a reverse edge (from t
to f
) already exists, a loop is created.
FIXME: Do something clever to manage loops.
# Add an edge from `f` to `t`.
# Because a POSet is transitive, all transitive edges are also added to the graph.
# If the edge already exists, the this function does nothing.
#
# ~~~
# var pos = new POSet[String]
# pos.add_edge("A", "B") # add A->B
# assert pos.has_edge("A", "C") == false
# pos.add_edge("B", "C") # add B->C
# assert pos.has_edge("A", "C") == true
# ~~~
#
# If a reverse edge (from `t` to `f`) already exists, a loop is created.
#
# FIXME: Do something clever to manage loops.
fun add_edge(f, t: E)
do
var fe = add_node(f)
var te = add_node(t)
# Skip if edge already present
if fe.tos.has(t) then return
# Add the edge and close the transitivity
for ff in fe.froms do
var ffe = self.elements[ff]
for tt in te.tos do
var tte = self.elements[tt]
tte.froms.add ff
ffe.tos.add tt
end
end
# Update the transitive reduction
if te.tos.has(f) then return # Skip the reduction if there is a loop
# Remove transitive edges.
# Because the sets of direct is iterated, the list of edges to remove
# is stored and is applied after the iteration.
# The usual case is that no direct edges need to be removed,
# so start with a `null` list of edges.
var to_remove: nullable Array[E] = null
for x in te.dfroms do
var xe = self.elements[x]
if xe.tos.has(f) then
if to_remove == null then to_remove = new Array[E]
to_remove.add x
xe.dtos.remove(t)
end
end
if to_remove != null then
for x in to_remove do te.dfroms.remove(x)
to_remove.clear
end
for x in fe.dtos do
var xe = self.elements[x]
if xe.froms.has(t) then
xe.dfroms.remove(f)
if to_remove == null then to_remove = new Array[E]
to_remove.add x
end
end
if to_remove != null then
for x in to_remove do fe.dtos.remove(x)
end
fe.dtos.add t
te.dfroms.add f
end
lib/poset/poset.nit:123,2--189,4