Pre-order set graph.

This class models an incremental pre-order graph where new nodes and edges can be added (but not removed). Pre-order graph has two characteristics:

  • reflexivity: an element is in relation with itself (ie self.has(e) implies self.has_edge(e,e))
  • transitivity: (self.has_edge(e,f) and self.has_edge(f,g)) implies self.has_edge(e,g)

Nodes and edges are added to the POSet.

var pos = new POSet[String]
pos.add_edge("A", "B") # add A->B
pos.add_edge("B", "C") # add B->C
pos.add_node("D") # add unconnected node "D"

# A -> B -> C    D

assert pos.has_edge("A", "B") == true

Since a poset is transitive, direct and indirect edges are considered by default. Direct edges (transitive-reduction) can also be considered independently.

assert pos.has_edge("A", "C") == true  # indirect
assert pos.has_edge("A", "D") == false # no edge
assert pos.has_edge("B", "A") == false # edges are directed

assert pos.has_direct_edge("A", "B") == true  # direct
assert pos.has_direct_edge("A", "C") == false

POSet are dynamic. It means that the transitivity is updated while new nodes and edges are added. The transitive-reduction (direct edges)) is also updated, so adding new edges can make some direct edge to disappear.

pos.add_edge("A","D")
pos.add_edge("D","B")
pos.add_edge("A","E")
pos.add_edge("E","C")

# A -> D -> B
# |         |
# v         v
# E ------> C

assert pos.has_edge("D", "C") == true # new indirect edge
assert pos.has_edge("A", "B") == true # still an edge
assert pos.has_direct_edge("A", "B") == false

Thanks to the [] method, elements can be considered relatively to the poset. SEE POSetElement

Introduced properties

fun [](e: E): POSetElement[E]

poset :: POSet :: []

Return a view of e in the poset.
fun add_chain(es: SequenceRead[E])

poset :: POSet :: add_chain

Add an edge between all elements of es in order.
fun add_edge(f: E, t: E)

poset :: POSet :: add_edge

Add an edge from f to t.
fun add_node(e: E): POSetElement[E]

poset :: POSet :: add_node

Add a node (an element) to the posed
fun has_direct_edge(f: E, t: E): Bool

poset :: POSet :: has_direct_edge

Is there a direct edge from f to t?
fun has_edge(f: E, t: E): Bool

poset :: POSet :: has_edge

Is there an edge (transitive or not) from f to t?
fun linearize(elements: Collection[E]): Array[E]

poset :: POSet :: linearize

Sort a sorted array of poset elements using linearization order
fun print_metrics

poset :: POSet :: print_metrics

Display exhaustive metrics about the poset
fun select_greatest(elements: Collection[E]): Array[E]

poset :: POSet :: select_greatest

Filter elements to return only the greatest ones
fun select_smallest(elements: Collection[E]): Array[E]

poset :: POSet :: select_smallest

Filter elements to return only the smallest ones
fun show_dot

poset :: POSet :: show_dot

Display the POSet in a graphical windows.
fun sub(elements: Collection[E]): POSet[E]

poset :: POSet :: sub

Return an induced sub-poset
fun write_dot(f: Writer)

poset :: POSet :: write_dot

Write the POSet as a graphviz digraph.

Redefined properties

redef fun ==(other: nullable Object): Bool

poset $ POSet :: ==

Two posets are equal if they contain the same elements and edges.
redef type COMPARED: E

poset $ POSet :: COMPARED

What to compare to
redef type SELF: POSet[E]

poset $ POSet :: SELF

Type of this instance, automatically specialized in every class
redef fun clone: SELF

poset $ POSet :: clone

Duplicate self
redef fun compare(a: COMPARED, b: COMPARED): Int

poset $ POSet :: compare

Compare two elements in an arbitrary total order.
redef fun core_serialize_to(serializer: Serializer)

poset $ POSet :: core_serialize_to

Actual serialization of self to serializer
redef init from_deserializer(deserializer: Deserializer)

poset $ POSet :: from_deserializer

Create an instance of this class from the deserializer
redef fun has(e: nullable Object): Bool

poset $ POSet :: has

Is item in the collection ?
redef fun hash: Int

poset $ POSet :: hash

The hash code of the object.
redef fun iterator: Iterator[E]

poset $ POSet :: iterator

Get a new iterator on the collection.

All properties

fun !=(other: nullable Object): Bool

core :: Object :: !=

Have self and other different values?
fun ==(other: nullable Object): Bool

core :: Object :: ==

Have self and other the same value?
type CLASS: Class[SELF]

core :: Object :: CLASS

The type of the class of self.
type COMPARED: nullable Object

core :: Comparator :: COMPARED

What to compare to
type CONCURRENT: ConcurrentCollection[E]

core :: Collection :: CONCURRENT

Type of the concurrent variant of this collection
type SELF: Object

core :: Object :: SELF

Type of this instance, automatically specialized in every class
fun [](e: E): POSetElement[E]

poset :: POSet :: []

Return a view of e in the poset.
protected fun accept_json_serializer(v: JsonSerializer)

serialization :: Serializable :: accept_json_serializer

Refinable service to customize the serialization of this class to JSON
protected fun accept_msgpack_attribute_counter(v: AttributeCounter)

serialization :: Serializable :: accept_msgpack_attribute_counter

Hook to customize the behavior of the AttributeCounter
protected fun accept_msgpack_serializer(v: MsgPackSerializer)

serialization :: Serializable :: accept_msgpack_serializer

Hook to customize the serialization of this class to MessagePack
fun add_chain(es: SequenceRead[E])

poset :: POSet :: add_chain

Add an edge between all elements of es in order.
fun add_edge(f: E, t: E)

poset :: POSet :: add_edge

Add an edge from f to t.
fun add_node(e: E): POSetElement[E]

poset :: POSet :: add_node

Add a node (an element) to the posed
protected fun add_to_bundle(bundle: NativeBundle, key: JavaString)

serialization :: Serializable :: add_to_bundle

Called by []= to dynamically choose the appropriate method according
fun bubble_sort(array: Array[COMPARED], from: Int, to: Int)

core :: Comparator :: bubble_sort

Bubble-sort array between from and to indices
protected fun class_factory(name: String): CLASS

core :: Object :: class_factory

Implementation used by get_class to create the specific class.
fun class_name: String

core :: Object :: class_name

The class name of the object.
abstract fun clone: SELF

core :: Cloneable :: clone

Duplicate self
fun combinations(r: Int): Collection[SequenceRead[E]]

core :: Collection :: combinations

All r-length combinations on self (in same order) without repeated elements.
fun combinations_with_replacement(r: Int): Collection[SequenceRead[E]]

core :: Collection :: combinations_with_replacement

All r-length combination on self (in same order) with repeated elements.
abstract fun compare(a: COMPARED, b: COMPARED): Int

core :: Comparator :: compare

Compare a and b.
fun core_serialize_to(serializer: Serializer)

serialization :: Serializable :: core_serialize_to

Actual serialization of self to serializer
fun count(item: nullable Object): Int

core :: Collection :: count

How many occurrences of item are in the collection?
fun first: E

core :: Collection :: first

Return the first item of the collection
init from_deserializer(deserializer: Deserializer)

serialization :: Serializable :: from_deserializer

Create an instance of this class from the deserializer
fun get_class: CLASS

core :: Object :: get_class

The meta-object representing the dynamic type of self.
fun has(item: nullable Object): Bool

core :: Collection :: has

Is item in the collection ?
fun has_all(other: Collection[nullable Object]): Bool

core :: Collection :: has_all

Does the collection contain at least each element of other?
fun has_any(other: Collection[nullable Object]): Bool

core :: Collection :: has_any

Does the collection contain at least one element of other?
fun has_direct_edge(f: E, t: E): Bool

poset :: POSet :: has_direct_edge

Is there a direct edge from f to t?
fun has_edge(f: E, t: E): Bool

poset :: POSet :: has_edge

Is there an edge (transitive or not) from f to t?
fun has_exactly(other: Collection[nullable Object]): Bool

core :: Collection :: has_exactly

Does the collection contain exactly all the elements of other?
fun has_only(item: nullable Object): Bool

core :: Collection :: has_only

Is the collection contain only item?
fun hash: Int

core :: Object :: hash

The hash code of the object.
fun heap_sort(array: Array[COMPARED], from: Int, to: Int)

core :: Comparator :: heap_sort

Heap-sort array between from and to indices
init init

core :: Object :: init

fun insertion_sort(array: Array[COMPARED], from: Int, to: Int)

core :: Comparator :: insertion_sort

Insertion-sort array between from and to indices
fun inspect: String

core :: Object :: inspect

Developer readable representation of self.
protected fun inspect_head: String

core :: Object :: inspect_head

Return "CLASSNAME:#OBJECTID".
fun is_empty: Bool

core :: Collection :: is_empty

Is there no item in the collection?
intern fun is_same_instance(other: nullable Object): Bool

core :: Object :: is_same_instance

Return true if self and other are the same instance (i.e. same identity).
fun is_same_serialized(other: nullable Object): Bool

core :: Object :: is_same_serialized

Is self the same as other in a serialization context?
intern fun is_same_type(other: Object): Bool

core :: Object :: is_same_type

Return true if self and other have the same dynamic type.
fun is_sorted(seq: SequenceRead[COMPARED]): Bool

core :: Comparator :: is_sorted

Is seq sorted?
abstract fun iterator: Iterator[E]

core :: Collection :: iterator

Get a new iterator on the collection.
fun join(separator: nullable Text, last_separator: nullable Text): String

core :: Collection :: join

Concatenate and separate each elements with separator.
fun length: Int

core :: Collection :: length

Number of items in the collection.
fun linearize(elements: Collection[E]): Array[E]

poset :: POSet :: linearize

Sort a sorted array of poset elements using linearization order
fun max(a: COMPARED, b: COMPARED): COMPARED

core :: Comparator :: max

Returns the maximum between a and b.
fun merge_sort(array: Array[COMPARED], from: Int, to: Int)

core :: Comparator :: merge_sort

Merge-sort array between from and to indices
fun min(a: COMPARED, b: COMPARED): COMPARED

core :: Comparator :: min

Returns the minimum between a and b.
protected fun msgpack_extra_array_items: Int

serialization :: Serializable :: msgpack_extra_array_items

Hook to request a larger than usual metadata array
fun not_empty: Bool

core :: Collection :: not_empty

Alias for not is_empty.
intern fun object_id: Int

core :: Object :: object_id

An internal hash code for the object based on its identity.
fun output

core :: Object :: output

Display self on stdout (debug only).
intern fun output_class_name

core :: Object :: output_class_name

Display class name on stdout (debug only).
fun permutations(r: Int): Collection[SequenceRead[E]]

core :: Collection :: permutations

All r-length permutations on self (all possible ordering) without repeated elements.
fun plain_to_s: String

core :: Collection :: plain_to_s

Concatenate elements without separators
fun print_metrics

poset :: POSet :: print_metrics

Display exhaustive metrics about the poset
fun product(r: Int): Collection[SequenceRead[E]]

core :: Collection :: product

Cartesian product, over r times self.
fun quick_sort(array: Array[COMPARED], from: Int, to: Int)

core :: Comparator :: quick_sort

Quick-sort array between from and to indices
fun rand: E

core :: Collection :: rand

Return a random element form the collection
fun sample(length: Int): Array[E]

core :: Collection :: sample

Return a new array made of (at most) length elements randomly chosen.
fun select_greatest(elements: Collection[E]): Array[E]

poset :: POSet :: select_greatest

Filter elements to return only the greatest ones
fun select_smallest(elements: Collection[E]): Array[E]

poset :: POSet :: select_smallest

Filter elements to return only the smallest ones
fun serialization_hash: Int

core :: Object :: serialization_hash

Hash value use for serialization
fun serialize_msgpack(plain: nullable Bool): Bytes

serialization :: Serializable :: serialize_msgpack

Serialize self to MessagePack bytes
fun serialize_to(serializer: Serializer)

serialization :: Serializable :: serialize_to

Serialize self to serializer
fun serialize_to_json(plain: nullable Bool, pretty: nullable Bool): String

serialization :: Serializable :: serialize_to_json

Serialize self to JSON
fun show_dot

poset :: POSet :: show_dot

Display the POSet in a graphical windows.
fun sort(array: Array[COMPARED])

core :: Comparator :: sort

Sort array using the compare function.
fun sub(elements: Collection[E]): POSet[E]

poset :: POSet :: sub

Return an induced sub-poset
intern fun sys: Sys

core :: Object :: sys

Return the global sys object, the only instance of the Sys class.
fun to_a: Array[E]

core :: Collection :: to_a

Build a new array from a collection
abstract fun to_concurrent: CONCURRENT

core :: Collection :: to_concurrent

Wraps self in a thread-safe collection
fun to_counter: Counter[E]

core :: Collection :: to_counter

Create and fill up a counter with the elements of `self.
fun to_curlslist: CURLSList

core :: Collection :: to_curlslist

Convert Collection[String] to CURLSList
fun to_json: String

serialization :: Serializable :: to_json

Serialize self to plain JSON
abstract fun to_jvalue(env: JniEnv): JValue

core :: Object :: to_jvalue

fun to_pretty_json: String

serialization :: Serializable :: to_pretty_json

Serialize self to plain pretty JSON
fun to_s: String

core :: Object :: to_s

User readable representation of self.
fun to_shuffle: Array[E]

core :: Collection :: to_shuffle

Return a new array made of elements in a random order.
fun write_dot(f: Writer)

poset :: POSet :: write_dot

Write the POSet as a graphviz digraph.
package_diagram poset::POSet POSet core::Collection Collection poset::POSet->core::Collection core::Comparator Comparator poset::POSet->core::Comparator core::Cloneable Cloneable poset::POSet->core::Cloneable serialization::Serializable Serializable poset::POSet->serialization::Serializable core::Object Object core::Collection->core::Object core::Comparator->core::Object core::Cloneable->core::Object serialization::Serializable->core::Object ...core::Object ... ...core::Object->core::Object fca::ConceptLattice ConceptLattice fca::ConceptLattice->poset::POSet

Ancestors

interface Object

core :: Object

The root of the class hierarchy.

Parents

interface Cloneable

core :: Cloneable

Something that can be cloned
interface Collection[E: nullable Object]

core :: Collection

The root of the collection hierarchy.
interface Comparator

core :: Comparator

This abstract class generalizes ways to sort an array
interface Serializable

serialization :: Serializable

Instances of this class can be passed to Serializer::serialize

Children

class ConceptLattice[O: Object, A: Object]

fca :: ConceptLattice

Concept Lattice

Class definitions

poset $ POSet
# Pre-order set graph.
# This class models an incremental pre-order graph where new nodes and edges can be added (but not removed).
# Pre-order graph has two characteristics:
#  * reflexivity: an element is in relation with itself (ie `self.has(e) implies self.has_edge(e,e)`)
#  * transitivity: `(self.has_edge(e,f) and self.has_edge(f,g)) implies self.has_edge(e,g)`
#
# Nodes and edges are added to the POSet.
#
# ~~~
# var pos = new POSet[String]
# pos.add_edge("A", "B") # add A->B
# pos.add_edge("B", "C") # add B->C
# pos.add_node("D") # add unconnected node "D"
#
# # A -> B -> C    D
#
# assert pos.has_edge("A", "B") == true  # direct
# ~~~
#
# Since a poset is transitive, direct and indirect edges are considered by default.
# Direct edges (transitive-reduction) can also be considered independently.
#
# ~~~
# assert pos.has_edge("A", "C") == true  # indirect
# assert pos.has_edge("A", "D") == false # no edge
# assert pos.has_edge("B", "A") == false # edges are directed
#
# assert pos.has_direct_edge("A", "B") == true  # direct
# assert pos.has_direct_edge("A", "C") == false # indirect
# ~~~
#
# POSet are dynamic.
# It means that the transitivity is updated while new nodes and edges are added.
# The transitive-reduction (*direct edges*)) is also updated,
# so adding new edges can make some direct edge to disappear.
#
# ~~~
# pos.add_edge("A","D")
# pos.add_edge("D","B")
# pos.add_edge("A","E")
# pos.add_edge("E","C")
#
# # A -> D -> B
# # |         |
# # v         v
# # E ------> C
#
# assert pos.has_edge("D", "C") == true # new indirect edge
# assert pos.has_edge("A", "B") == true # still an edge
# assert pos.has_direct_edge("A", "B") == false  # but no-more a direct one
# ~~~
#
# Thanks to the `[]` method, elements can be considered relatively to the poset.
# SEE `POSetElement`
class POSet[E]
	super Collection[E]
	super Comparator
	super Cloneable
	super Serializable

	redef type COMPARED: E is fixed

	redef fun iterator do return elements.keys.iterator

	# All the nodes
	private var elements = new HashMap[E, POSetElement[E]]

	redef fun has(e) do return self.elements.keys.has(e)

	# Add a node (an element) to the posed
	# The new element is added unconnected to any other nodes (it is both a new root and a new leaf).
	# Return the POSetElement associated to `e`.
	# If `e` is already present in the POSet then just return the POSetElement (usually you will prefer []) is this case.
	fun add_node(e: E): POSetElement[E]
	do
		if elements.keys.has(e) then return self.elements[e]
		var poe = new POSetElement[E](self, e, elements.length)
		poe.tos.add(e)
		poe.froms.add(e)
		self.elements[e] = poe
		return poe
	end

	# Return a view of `e` in the poset.
	# This allows to view the elements in their relation with others elements.
	#
	#     var poset = new POSet[String]
	#     poset.add_chain(["A", "B", "D"])
	#     poset.add_chain(["A", "C", "D"])
	#     var a = poset["A"]
	#     assert a.direct_greaters.has_exactly(["B", "C"])
	#     assert a.greaters.has_exactly(["A", "B", "C", "D"])
	#     assert a.direct_smallers.is_empty
	#
	# REQUIRE: has(e)
	fun [](e: E): POSetElement[E]
	do
		assert elements.keys.has(e)
		return self.elements[e]
	end

	# 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

	# Add an edge between all elements of `es` in order.
	#
	# ~~~~
	# var pos = new POSet[String]
	# pos.add_chain(["A", "B", "C", "D"])
	# assert pos.has_direct_edge("A", "B")
	# assert pos.has_direct_edge("B", "C")
	# assert pos.has_direct_edge("C", "D")
	# ~~~~
	fun add_chain(es: SequenceRead[E])
	do
		if es.is_empty then return
		var i = es.iterator
		var e = i.item
		i.next
		for f in i do
			add_edge(e, f)
			e = f
		end
	end

	# Is there an edge (transitive or not) from `f` to `t`?
	#
	# SEE: `add_edge`
	#
	# Since the POSet is reflexive, true is returned if `f == t`.
	#
	# ~~~
	# var pos = new POSet[String]
	# pos.add_node("A")
	# assert pos.has_edge("A", "A") == true
	# ~~~
	fun has_edge(f,t: E): Bool
	do
		if not elements.keys.has(f) then return false
		var fe = self.elements[f]
		return fe.tos.has(t)
	end

	# Is there a direct edge from `f` to `t`?
	#
	# ~~~
	# var pos = new POSet[String]
	# pos.add_chain(["A", "B", "C"]) # add A->B->C
	# assert pos.has_direct_edge("A", "B") == true
	# assert pos.has_direct_edge("A", "C") == false
	# assert pos.has_edge("A", "C")        == true
	# ~~~
	#
	# Note that because of loops, the result may not be the expected one.
	fun has_direct_edge(f,t: E): Bool
	do
		if not elements.keys.has(f) then return false
		var fe = self.elements[f]
		return fe.dtos.has(t)
	end

	# Write the POSet as a graphviz digraph.
	#
	# Nodes are labeled with their `to_s` so homonymous nodes may appear.
	# Edges are unlabeled.
	fun write_dot(f: Writer)
	do
		f.write "digraph \{\n"
		var ids = new HashMap[E, Int]
		for x in elements.keys do
			ids[x] = ids.length
		end
		for x in elements.keys do
			var xstr = (x or else "null").to_s.escape_to_dot
			var nx = "n{ids[x]}"
			f.write "{nx}[label=\"{xstr}\"];\n"
			var xe = self.elements[x]
			for y in xe.dtos do
				var ny = "n{ids[y]}"
				if self.has_edge(y,x) then
					f.write "{nx} -> {ny}[dir=both];\n"
				else
					f.write "{nx} -> {ny};\n"
				end
			end
		end
		f.write "\}\n"
	end

	# Display the POSet in a graphical windows.
	# Graphviz with a working -Txlib is expected.
	#
	# See `write_dot` for details.
	fun show_dot
	do
		var f = new ProcessWriter("dot", "-Txlib")
		write_dot(f)
		f.close
		f.wait
	end

	# Compare two elements in an arbitrary total order.
	#
	# This function is mainly used to sort elements of the set in an coherent way.
	#
	# ~~~~
	# var pos = new POSet[String]
	# pos.add_chain(["A", "B", "C", "D", "E"])
	# pos.add_chain(["A", "X", "C", "Y", "E"])
	# var a = ["X", "C", "E", "A", "D"]
	# pos.sort(a)
	# assert a == ["E", "D", "C", "X", "A"]
	# ~~~~
	#
	# POSet are not necessarily total orders because some distinct elements may be incomparable (neither greater or smaller).
	# Therefore this method relies on arbitrary linear extension.
	# This linear extension is a lawful total order (transitive, anti-symmetric, reflexive, and total), so can be used to compare the elements.
	#
	# The abstract behavior of the method is thus the following:
	#
	# ~~~~nitish
	# if a == b then return 0
	# if has_edge(b, a) then return -1
	# if has_edge(a, b) then return 1
	# return -1 or 1 # according to the linear extension.
	# ~~~~
	#
	# Note that the linear extension is stable, unless a new node or a new edge is added.
	redef fun compare(a, b)
	do
		var ae = self.elements[a]
		var be = self.elements[b]
		var res = ae.tos.length <=> be.tos.length
		if res != 0 then return res
		return elements[a].count <=> elements[b].count
	end

	# Filter elements to return only the smallest ones
	#
	# ~~~
	# var s = new POSet[String]
	# s.add_edge("B", "A")
	# s.add_edge("C", "A")
	# s.add_edge("D", "B")
	# s.add_edge("D", "C")
	# assert s.select_smallest(["A", "B"]) == ["B"]
	# assert s.select_smallest(["A", "B", "C"]) == ["B", "C"]
	# assert s.select_smallest(["B", "C", "D"]) == ["D"]
	# ~~~
	fun select_smallest(elements: Collection[E]): Array[E]
	do
		var res = new Array[E]
		for e in elements do
			for f in elements do
				if e == f then continue
				if has_edge(f, e) then continue label
			end
			res.add(e)
		end label
		return res
	end

	# Filter elements to return only the greatest ones
	#
	# ~~~
	# var s = new POSet[String]
	# s.add_edge("B", "A")
	# s.add_edge("C", "A")
	# s.add_edge("D", "B")
	# s.add_edge("D", "C")
	# assert s.select_greatest(["A", "B"]) == ["A"]
	# assert s.select_greatest(["A", "B", "C"]) == ["A"]
	# assert s.select_greatest(["B", "C", "D"]) == ["B", "C"]
	# ~~~
	fun select_greatest(elements: Collection[E]): Array[E]
	do
		var res = new Array[E]
		for e in elements do
			for f in elements do
				if e == f then continue
				if has_edge(e, f) then continue label
			end
			res.add(e)
		end label
		return res
	end

	# Sort a sorted array of poset elements using linearization order
	# ~~~~
	# var pos = new POSet[String]
	# pos.add_chain(["A", "B", "C", "D", "E"])
	# pos.add_chain(["A", "X", "C", "Y", "E"])
	# var a = pos.linearize(["X", "C", "E", "A", "D"])
	# assert a == ["E", "D", "C", "X", "A"]
	# ~~~~
	fun linearize(elements: Collection[E]): Array[E] do
		var lin = elements.to_a
		sort(lin)
		return lin
	end

	redef fun clone do return sub(self)

	# Return an induced sub-poset
	#
	# The elements of the result are those given in argument.
	#
	# ~~~
	# var pos = new POSet[String]
	# pos.add_chain(["A", "B", "C", "D", "E"])
	# pos.add_chain(["A", "X", "C", "Y", "E"])
	#
	# var pos2 = pos.sub(["A", "B", "D", "Y", "E"])
	# assert pos2.has_exactly(["A", "B", "D", "Y", "E"])
	# ~~~
	#
	# The full relationship is preserved between the provided elements.
	#
	# ~~~
	# for e1 in pos2 do for e2 in pos2 do
	#    assert pos2.has_edge(e1, e2) == pos.has_edge(e1, e2)
	# end
	# ~~~
	#
	# Not that by definition, the direct relationship is the transitive
	# reduction of the full reduction. Thus, the direct relationship of the
	# sub-poset may not be included in the direct relationship of self because an
	# indirect edge becomes a direct one if all the intermediates elements
	# are absent in the sub-poset.
	#
	# ~~~
	# assert pos.has_direct_edge("B", "D")  == false
	# assert pos2.has_direct_edge("B", "D") == true
	#
	# assert pos2["B"].direct_greaters.has_exactly(["D", "Y"])
	# ~~~
	#
	# If the `elements` contains all then the result is a clone of self.
	#
	# ~~~
	# var pos3 = pos.sub(pos)
	# assert pos3 == pos
	# assert pos3 == pos.clone
	# ~~~
	fun sub(elements: Collection[E]): POSet[E]
	do
		var res = new POSet[E]
		for e in self do
			if not elements.has(e) then continue
			res.add_node(e)
		end
		for e in res do
			for f in self[e].greaters do
				if not elements.has(f) then continue
				res.add_edge(e, f)
			end
		end
		return res
	end

	# Two posets are equal if they contain the same elements and edges.
	#
	# ~~~
	# var pos1 = new POSet[String]
	# pos1.add_chain(["A", "B", "C", "D", "E"])
	# pos1.add_chain(["A", "X", "C", "Y", "E"])
	#
	# var pos2 = new POSet[Object]
	# pos2.add_edge("Y", "E")
	# pos2.add_chain(["A", "X", "C", "D", "E"])
	# pos2.add_chain(["A", "B", "C", "Y"])
	#
	# assert pos1 == pos2
	#
	# pos1.add_edge("D", "Y")
	# assert pos1 != pos2
	#
	# pos2.add_edge("D", "Y")
	# assert pos1 == pos2
	#
	# pos1.add_node("Z")
	# assert pos1 != pos2
	# ~~~
	redef fun ==(other) do
		if not other isa POSet[nullable Object] then return false
		if not self.elements.keys.has_exactly(other.elements.keys) then return false
		for e, ee in elements do
			if ee.direct_greaters != other[e].direct_greaters then return false
		end
		assert hash == other.hash
		return true
	end

	redef fun hash
	do
		var res = 0
		for e, ee in elements do
			if e == null then continue
			res += e.hash
			res += ee.direct_greaters.length
		end
		return res
	end

	redef fun core_serialize_to(serializer)
	do
		# Optimize written data because this structure has duplicated data
		# For example, serializing the class hierarchy of a simple program where E is String
		# result is before: 200k, after: 56k.
		serializer.serialize_attribute("elements", elements)
	end

	redef init from_deserializer(deserializer)
	do
		deserializer.notify_of_creation self
		var elements = deserializer.deserialize_attribute("elements")
		if elements isa HashMap[E, POSetElement[E]] then
			self.elements = elements
		end
	end
end
lib/poset/poset.nit:22,1--507,3

counter :: counter $ POSet
redef class POSet[E]
	private fun show_counter(c: Counter[Int])
	do
		var list = c.sort
		default_comparator.sort(list)
		for e in list do
			print " {e} -> {c[e]} times ({div(c[e]*100, c.sum)}%)"
		end
	end

	# Display exhaustive metrics about the poset
	fun print_metrics
	do
		var nb_greaters = new Counter[E]
		var nb_direct_greaters = new Counter[E]
		var nb_smallers = new Counter[E]
		var nb_direct_smallers = new Counter[E]
		var nb_direct_edges = 0
		var nb_edges = 0
		for n in self do
			var ne = self[n]
			nb_edges += ne.greaters.length
			nb_direct_edges += ne.direct_greaters.length
			nb_greaters[n] = ne.greaters.length
			nb_direct_greaters[n] = ne.direct_greaters.length
			nb_smallers[n] = ne.smallers.length
			nb_direct_smallers[n] = ne.direct_smallers.length
		end
		print "Number of nodes: {self.length}"
		print "Number of edges: {nb_edges} ({div(nb_edges,self.length)} per node)"
		print "Number of direct edges: {nb_direct_edges} ({div(nb_direct_edges,self.length)} per node)"
		print "Distribution of greaters"
		nb_greaters.print_summary
		print "Distribution of direct greaters"
		nb_direct_greaters.print_summary
		print "Distribution of smallers"
		nb_smallers.print_summary
		print "Distribution of direct smallers"
		nb_direct_smallers.print_summary
	end
end
lib/counter/counter.nit:348,1--388,3