Skip `nan` values in metrics so the sum and std_div still have sense.
Also change `Metric::collect` to accept any kind of `Collection`.
Pull-Request: #1755
Reviewed-by: Jean Privat <jean@pryen.org>
end
# A `MapIterator` over a `HashMap`.
-class HashMapIterator[K, V]
+private class HashMapIterator[K, V]
super MapIterator[K, V]
redef fun is_ok do return _node != null
end
# The map to iterate on
- private var map: HashMap[K, V]
+ var map: HashMap[K, V]
# The current node
- private var node: nullable HashMapNode[K, V] = null
+ var node: nullable HashMapNode[K, V] = null
init
do
end
# All kinds of array-based text representations.
-abstract class FlatText
+private abstract class FlatText
super Text
# Underlying C-String (`char*`)
#
# Warning : Might be void in some subclasses, be sure to check
# if set before using it.
- private var items: NativeString is noinit
+ var items: NativeString is noinit
# Returns a char* starting at position `first_byte`
#
#
# As always, do not modify the content of the String in C code, if this is what you want
# copy locally the char* as Nit Strings are immutable.
- private fun fast_cstring: NativeString is abstract
+ fun fast_cstring: NativeString is abstract
redef var length = 0
redef class FlatText
- private fun first_byte: Int do return 0
+ fun first_byte: Int do return 0
- private fun last_byte: Int do return _bytelen - 1
+ fun last_byte: Int do return _bytelen - 1
# Cache of the latest position (char) explored in the string
- private var position: Int = 0
+ var position: Int = 0
# Cached position (bytes) in the NativeString underlying the String
- private var bytepos: Int = 0
+ var bytepos: Int = 0
# Index of the character `index` in `_items`
- private fun char_to_byte_index(index: Int): Int do
+ fun char_to_byte_index(index: Int): Int do
var ln = length
assert index >= 0
assert index < ln
# This enables a double-optimization in `escape_to_c` since if this
# method returns 0, then `self` does not need escaping and can be
# returned as-is
- protected fun chars_to_escape_to_c: Int do
+ fun chars_to_escape_to_c: Int do
var its = _items
var max = last_byte
var pos = first_byte
do
var l = length
if l == 0 then return ""
- if l == 1 then if self[0] == null then return "" else return self[0].to_s
- var its = _items
+ var its = _items.as(not null)
+ var first = its[0]
+ if l == 1 then if first == null then return "" else return first.to_s
var na = new NativeArray[String](l)
var i = 0
var sl = 0
# g.add_arcs([[1,2],[2,1],[2,3],[3,4],[4,5],[5,3]])
# for component in g.strongly_connected_components.to_partitions
# do
-# print component
+# print component
# end
# # Prints [1,2] and [3,4,5]
# ~~~
# g.add_arc(0, 2)
# g.add_arc(1, 2)
# for arc in g.arcs_iterator do
- # assert g.has_arc(arc[0], arc[1])
+ # assert g.has_arc(arc[0], arc[1])
# end
# ~~~
fun arcs_iterator: Iterator[Array[V]] do return new ArcsIterator[V](self)
# g.add_arc(1, 3)
# g.add_arc(2, 3)
# for arc in g.incoming_arcs(3) do
- # assert g.is_predecessor(arc[0], arc[1])
+ # assert g.is_predecessor(arc[0], arc[1])
# end
# ~~~
fun incoming_arcs(u: V): Collection[Array[V]]
# g.add_arc(2, 3)
# g.add_arc(1, 2)
# for arc in g.outgoing_arcs(1) do
- # assert g.is_successor(arc[1], arc[0])
+ # assert g.is_successor(arc[1], arc[0])
# end
# ~~~
fun outgoing_arcs(u: V): Collection[Array[V]]
return s
end
+ # Open Graphviz with `self.to_dot`.
+ #
+ # Mainly used for debugging.
+ fun show_dot do
+ var f = new ProcessWriter("dot", "-Txlib")
+ f.write to_dot
+ f.close
+ end
+
## ------------ ##
## Neighborhood ##
## ------------ ##
--- /dev/null
+# This file is part of NIT (http://www.nitlanguage.org).
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+# http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# Add PageRank computation for vertices in Digraph.
+module pagerank
+
+import graphs::digraph
+
+redef class Digraph[V]
+
+ # Compute PageRank for each vertex
+ #
+ # Details of the algorithm can be found in:
+ # > L. Page, S. Brin, R. Motwani, and T.Winograd.
+ # > **The pagerank citation ranking: Bringing order to the web.**
+ # > *Technical report, Stanford Digital Library Technologies Project, 1998*
+ #
+ # Example:
+ # ~~~
+ # var g = new HashDigraph[String]
+ # g.add_arc("A", "B")
+ # g.add_arc("A", "C")
+ # g.add_arc("B", "C")
+ # g.add_arc("C", "A")
+ # g.add_arc("D", "C")
+ #
+ # assert g.pagerank.join(", ", ":") == "A:1.488, B:0.782, C:1.575, D:0.15"
+ # ~~~
+ fun pagerank: PRMap[V] do
+ # `d` constant such as `initial_pagerank(node) == (1 - d) != 0`
+ var d = 0.85 # commonly-choosen value
+ # Init each node page rank with an initial_value
+ var values = new PRMap[V]
+ var vertices = self.vertices
+ for v in vertices do values[v] = 1.0 - d
+ # Compute page rank until convergence
+ var prev = new PRMap[V]
+ while not values.is_approx(prev, 0.001) do
+ prev = new PRMap[V].from(values)
+ for v in vertices do
+ var in_pr = 0.0
+ for o in predecessors(v) do
+ in_pr += values[o] / out_degree(o).to_f
+ end
+ values[v] = (1.0 - d) + d * in_pr
+ end
+ end
+ return values
+ end
+end
+
+# Map each Vertice of a Digraph to it's PageRank.
+#
+# See: `Digraph::pagerank`.
+class PRMap[V]
+ super HashMap[V, Float]
+
+ # Init `self` by copying `other` values.
+ init from(other: PRMap[V]) do
+ init
+ for k, v in other do self[k] = v
+ end
+
+ # Is `self` approximately equal to another PRMap?
+ #
+ # `self` is approximately equal to `o` if `o` contains all the key from `self`
+ # with the same values.
+ #
+ # Values equality is based on `Float::is_approx` with `precision`.
+ fun is_approx(o: SELF, precision: Float): Bool do
+ for k1, v1 in self do
+ if not o.has_key(k1) then return false
+ if not v1.is_approx(o[k1], precision) then return false
+ end
+ return true
+ end
+end
nitlanguage / nit.git / commitdiff