From: Jean Privat Date: Fri, 16 Oct 2015 12:19:49 +0000 (-0400) Subject: Merge: metrics: not a number fix X-Git-Tag: v0.7.9~33 X-Git-Url: http://nitlanguage.org?hp=3c5f2c4a2dc845573a5d8c6459368e6707e08edf Merge: metrics: not a number fix 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 --- diff --git a/lib/core/collection/hash_collection.nit b/lib/core/collection/hash_collection.nit index 1c9c17c..8ee3491 100644 --- a/lib/core/collection/hash_collection.nit +++ b/lib/core/collection/hash_collection.nit @@ -376,7 +376,7 @@ private class HashMapNode[K, V] 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 @@ -405,10 +405,10 @@ class HashMapIterator[K, V] 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 diff --git a/lib/core/text/abstract_text.nit b/lib/core/text/abstract_text.nit index 01d0eab..baf8ae7 100644 --- a/lib/core/text/abstract_text.nit +++ b/lib/core/text/abstract_text.nit @@ -966,14 +966,14 @@ abstract class Text 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` # @@ -990,7 +990,7 @@ abstract class FlatText # # 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 diff --git a/lib/core/text/flat.nit b/lib/core/text/flat.nit index 5bc76fc..6cf1584 100644 --- a/lib/core/text/flat.nit +++ b/lib/core/text/flat.nit @@ -36,18 +36,18 @@ end 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 @@ -90,7 +90,7 @@ redef class FlatText # 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 @@ -1148,8 +1148,9 @@ redef class Array[E] 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 diff --git a/lib/graphs/digraph.nit b/lib/graphs/digraph.nit index 8f45495..bc9a8af 100644 --- a/lib/graphs/digraph.nit +++ b/lib/graphs/digraph.nit @@ -117,7 +117,7 @@ # 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] # ~~~ @@ -291,7 +291,7 @@ interface Digraph[V: Object] # 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) @@ -317,7 +317,7 @@ interface Digraph[V: Object] # 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]] @@ -340,7 +340,7 @@ interface Digraph[V: Object] # 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]] @@ -383,6 +383,15 @@ interface Digraph[V: Object] 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 ## ## ------------ ## diff --git a/lib/graphs/pagerank.nit b/lib/graphs/pagerank.nit new file mode 100644 index 0000000..5177e5a --- /dev/null +++ b/lib/graphs/pagerank.nit @@ -0,0 +1,88 @@ +# 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