SystemOrganization addCategory: #'PageRank-Core'!

Object subclass: #PageRanker
	instanceVariableNames: 'damping iterations outlinks'
	classVariableNames: ''
	poolDictionaries: ''
	category: 'PageRank-Core'!

!PageRanker methodsFor: 'accessing' stamp: 'lr 7/9/2010 11:03'!
damping: aNumber
	"The damping factor represents the probability the flow will continue at any step. The deafult value is 0.85."

	damping := aNumber asFloat! !

!PageRanker methodsFor: 'initialization' stamp: 'lr 7/9/2010 11:14'!
initialize
	self iterations: 100; damping: 0.85.
	self outlinks: [ :node | #() ]! !

!PageRanker methodsFor: 'accessing' stamp: 'lr 7/9/2010 11:07'!
iterations: anInteger
	"The number of iterations defines how many times the calculation is repeated, more iterations give more accurate results. The default value is 100."
	
	iterations := anInteger! !

!PageRanker methodsFor: 'accessing' stamp: 'lr 7/9/2010 11:09'!
outlinks: aBlock
	"Defines how the children of a given element are retrieved."

	outlinks := aBlock! !

!PageRanker methodsFor: 'actions' stamp: 'lr 7/9/2010 11:37'!
runOn: aNodeCollection
	| previous |
	previous := IdentityDictionary new: aNodeCollection size.
	aNodeCollection
		do: [ :each | previous at: each put: 1.0 / aNodeCollection size ].
	iterations timesRepeat: [
		| current |
		current := IdentityDictionary new: aNodeCollection size.
		previous keysAndValuesDo: [ :node :rank |
			| children |
			current
				at: node
				ifAbsentPut: [ 1.0 - damping ].
			(children := (outlinks value: node) reject: [ :each | each == node ]) do: [ :child |
				current
					at: child
					put: (current
						at: child
						ifAbsent: [ 1.0 - damping ]) + (damping * rank / children size) ] ].
		previous := current ].
	^ previous! !

Object subclass: #PageRankerExample
	instanceVariableNames: ''
	classVariableNames: ''
	poolDictionaries: ''
	category: 'PageRank-Core'!

!PageRankerExample methodsFor: 'examples' stamp: 'lr 7/9/2010 15:37'!
importantClassesIn: aBrowserEnvironment
	"self new importantClassesIn: (BrowserEnvironment new)"
	"self new importantClassesIn: (BrowserEnvironment new forPackageNames: #('TextLint-Model'))"
	
	| graph ranks result |
	graph := IdentityDictionary new.
	aBrowserEnvironment classesAndSelectorsDo: [ :class :selector |
		| collection |
		collection := graph 
			at: class theNonMetaClass name
			ifAbsentPut: [ 
				class superclass isNil 
					ifTrue: [ OrderedCollection new ] 
					ifFalse: [ OrderedCollection with: class superclass name ]].
		(class compiledMethodAt: selector) literalsDo: [ :each |
			(each isVariableBinding and: [ graph includesKey: each key ])
				ifTrue: [ collection addLast: each key ] ] ].
	ranks := PageRanker new 
		outlinks: [ :each | graph at: each ifAbsent: [ #() ] ];
		runOn: graph keys.
	result := graph keys 
		asSortedCollection: [ :a :b | (ranks at: a) >= (ranks at: b) ].
	^ result first: 25! !

!PageRankerExample methodsFor: 'examples' stamp: 'lr 7/9/2010 15:37'!
importantSelectorsIn: aBrowserEnvironment
	"self new importantSelectorsIn: (BrowserEnvironment new)"
	"self new importantSelectorsIn: (BrowserEnvironment new forPackageNames: #('TextLint-Model'))"
	
	| graph ranks result |
	graph := IdentityDictionary new.
	aBrowserEnvironment classesAndSelectorsDo: [ :class :selector |
		| collection |
		collection := graph at: selector ifAbsentPut: [ OrderedCollection new ].
		(class compiledMethodAt: selector) messagesDo: [ :each |
			each isSymbol
				ifTrue: [ collection addLast: each ] ] ].
	ranks := PageRanker new 
		outlinks: [ :each | graph at: each ifAbsent: [ #() ] ];
		runOn: graph keys.
	result := graph keys 
		asSortedCollection: [ :a :b | (ranks at: a) >= (ranks at: b) ].
	^ result first: 25! !

TestCase subclass: #PageRankerTest
	instanceVariableNames: 'graph ranks ranker'
	classVariableNames: ''
	poolDictionaries: ''
	category: 'PageRank-Core'!

!PageRankerTest methodsFor: 'as yet unclassified' stamp: 'lr 7/9/2010 11:16'!
setUp
	super setUp.
	graph := Dictionary new.
	graph at: #a put: #(c).
	graph at: #b put: #(a).
	graph at: #c put: #(a).
	graph at: #d put: #(c b).
	ranker := PageRanker new.
	ranker outlinks: [ :node | graph at: node ]! !

!PageRankerTest methodsFor: 'as yet unclassified' stamp: 'lr 7/9/2010 11:21'!
testFirstStep
	ranker iterations: 1; damping: 1.
	ranks := ranker runOn: graph keys.
	self assert: (ranks at: #a) = 0.5.
	self assert: (ranks at: #b) = 0.125.
	self assert: (ranks at: #c) = 0.375.
	self assert: (ranks at: #d) = 0.0.! !

!PageRankerTest methodsFor: 'as yet unclassified' stamp: 'lr 7/9/2010 11:21'!
testInitialStep
	ranker iterations: 0; damping: 1.
	ranks := ranker runOn: graph keys.
	self assert: (ranks at: #a) = 0.25.
	self assert: (ranks at: #b) = 0.25.
	self assert: (ranks at: #c) = 0.25.
	self assert: (ranks at: #d) = 0.25.! !

!PageRankerTest methodsFor: 'as yet unclassified' stamp: 'lr 7/9/2010 11:22'!
testSecondStep
	ranker iterations: 2; damping: 1.
	ranks := ranker runOn: graph keys.
	self assert: (ranks at: #a) = 0.5.
	self assert: (ranks at: #b) = 0.0.
	self assert: (ranks at: #c) = 0.5.
	self assert: (ranks at: #d) = 0.0.! !