From a646731204c808d7d2e24cd2dd4b4aec4752a516 Mon Sep 17 00:00:00 2001 From: dg314 Date: Thu, 21 Oct 2021 04:57:21 -0400 Subject: page rank --- src/client/views/search/SearchBox.tsx | 146 +++++++++++++++++++++++++++++----- 1 file changed, 125 insertions(+), 21 deletions(-) (limited to 'src') diff --git a/src/client/views/search/SearchBox.tsx b/src/client/views/search/SearchBox.tsx index 3612bd7c4..57c9a3d46 100644 --- a/src/client/views/search/SearchBox.tsx +++ b/src/client/views/search/SearchBox.tsx @@ -1,7 +1,7 @@ import { action, computed, observable } from 'mobx'; import { observer } from 'mobx-react'; import * as React from 'react'; -import { Doc, DocListCast, DocListCastAsync, Field } from '../../../fields/Doc'; +import { DirectLinksSym, Doc, DocListCast, DocListCastAsync, Field } from '../../../fields/Doc'; import { documentSchema } from "../../../fields/documentSchemas"; import { Id } from '../../../fields/FieldSymbols'; import { createSchema, makeInterface } from '../../../fields/Schema'; @@ -14,6 +14,8 @@ import "./SearchBox.scss"; import { DocumentManager } from '../../util/DocumentManager'; import { DocUtils } from '../../documents/Documents'; import { Tooltip } from "@material-ui/core"; +import { DictationOverlay } from '../DictationOverlay'; +import { CollectionSchemaBooleanCell } from '../collections/collectionSchema/CollectionSchemaCells'; export const searchSchema = createSchema({ Document: Doc @@ -22,6 +24,10 @@ export const searchSchema = createSchema({ type SearchBoxDocument = makeInterface<[typeof documentSchema, typeof searchSchema]>; const SearchBoxDocument = makeInterface(documentSchema, searchSchema); +const DAMPENING_FACTOR = 0.9; +const MAX_ITERATIONS = 25; +const ERROR = 0.03; + export interface SearchBoxProps extends FieldViewProps { linkSearch: boolean; linkFrom?: (() => Doc | undefined) | undefined; @@ -40,7 +46,10 @@ export class SearchBox extends ViewBoxBaseComponent = new Map(); + @observable _pageRanks: Map = new Map(); + @observable _linkedDocsOut: Map> = new Map>(); + @observable _linkedDocsIn: Map> = new Map>(); @observable _selectedResult: Doc | undefined = undefined; @observable _deletedDocsStatus: boolean = false; @observable _onlyAliases: boolean = true; @@ -110,11 +119,9 @@ export class SearchBox extends ViewBoxBaseComponent { - console.log(linkTo.title); if (this.props.linkFrom) { const linkFrom = this.props.linkFrom(); if (linkFrom) { - console.log(linkFrom.title); DocUtils.MakeLink({ doc: linkFrom }, { doc: linkTo }, "Link"); } } @@ -204,7 +211,7 @@ export class SearchBox extends ViewBoxBaseComponent(); SearchBox.documentKeys(doc).forEach(key => Field.toString(doc[key] as Field).toLowerCase().includes(query) && hlights.add(key)); blockedKeys.forEach(key => hlights.delete(key)); - Array.from(hlights.keys()).length > 0 && this._results.push([doc, Array.from(hlights.keys())]); + + if (Array.from(hlights.keys()).length > 0) { + this._results.set(doc, Array.from(hlights.keys())); + } } docIDs.push(doc[Id]); }); } + + this.computePageRanks(); } /** - * @param {Doc} doc - doc for which keys are returned - * - * This method returns a list of a document doc's keys. + * This method initializes the page rank of every document to the reciprocal + * of the number of documents in the collection. + */ + @action + initializePageRanks() { + this._pageRanks.clear(); + this._linkedDocsOut.clear(); + + this._results.forEach((_, doc) => { + this._linkedDocsIn.set(doc, new Set()); + }); + + this._results.forEach((_, doc) => { + this._pageRanks.set(doc, 1.0 / this._results.size); + + if (Doc.GetProto(doc)[DirectLinksSym].size == 0) { + this._linkedDocsOut.set(doc, new Set(this._results.keys())); + + this._results.forEach((_, linkedDoc) => { + this._linkedDocsIn.get(linkedDoc)?.add(doc); + }); + } + else { + let linkedDocSet: Set = new Set(); + + Doc.GetProto(doc)[DirectLinksSym].forEach((link) => { + let d1 = link?.anchor1 as Doc; + let d2 = link?.anchor2 as Doc; + if (doc == d1 && this._results.has(d2)) { + linkedDocSet.add(d2); + this._linkedDocsIn.get(d2)?.add(doc); + } + else if (doc == d2 && this._results.has(d1)) { + linkedDocSet.add(d1); + this._linkedDocsIn.get(d1)?.add(doc); + } + }) + + this._linkedDocsOut.set(doc, linkedDocSet); + } + }); + } + + /** + * This method runs one complete iteration of the page rank algorithm. It + * returns true iff all page ranks have converged (i.e. changed by less than + * the _error value), which means that the algorithm should terminate. + * + * @return true if page ranks have converged; false otherwise */ + @action + pageRankIteration(): boolean { + let converged = true; + const pageRankFromAll = (1 - DAMPENING_FACTOR) / this._results.size; + + let nextPageRanks: Map = new Map(); + + this._results.forEach((_, doc) => { + let nextPageRank = pageRankFromAll; + + this._linkedDocsIn.get(doc)?.forEach((linkedDoc) => { + nextPageRank += DAMPENING_FACTOR * (this._pageRanks.get(linkedDoc) ?? 0) / (this._linkedDocsOut.get(linkedDoc)?.size ?? 1); + }); + + nextPageRanks.set(doc, nextPageRank); + + if (Math.abs(nextPageRank - (this._pageRanks.get(doc) ?? 0)) > ERROR) { + converged = false; + } + }); + + this._pageRanks = nextPageRanks; + + return converged; + } + + /** + * This method performs the page rank algorithm on the graph of documents + * that match the search query. Vertices are documents and edges are links + * between documents. + */ + @action + computePageRanks() { + this.initializePageRanks(); + + for (let i = 0; i < MAX_ITERATIONS; i++) { + if (this.pageRankIteration()) { + break; + } + } + } + + /** + * @param {Doc} doc - doc for which keys are returned + * + * This method returns a list of a document doc's keys. + */ static documentKeys(doc: Doc) { const keys: { [key: string]: boolean } = {}; Doc.GetAllPrototypes(doc).map(proto => Object.keys(proto).forEach(key => keys[key] = false)); @@ -244,7 +349,7 @@ export class SearchBox extends ViewBoxBaseComponent { - this._results.forEach(result => { - Doc.UnBrushDoc(result[0]); - Doc.UnHighlightDoc(result[0]); + this._results.forEach((_, doc) => { + Doc.UnBrushDoc(doc); + Doc.UnHighlightDoc(doc); Doc.ClearSearchMatches(); }); }); /** * @param {Doc} doc - doc to be selected - * + * * This method selects a doc by either jumping to it (centering/zooming in on it) * or opening it in a new tab. */ @@ -292,8 +397,11 @@ export class SearchBox extends ViewBoxBaseComponent (this._pageRanks.get(b[0]) ?? 0) - (this._pageRanks.get(a[0]) ?? 0)) // sorted by page rank + + const resultsJSX = Array(); - const results = this._results.map(result => { + sortedResults.forEach((result) => { var className = "searchBox-results-scroll-view-result"; if (this._selectedResult === result[0]) { @@ -305,7 +413,7 @@ export class SearchBox extends ViewBoxBaseComponent
{title}
}>
this.makeLink(result[0]) : @@ -326,12 +434,8 @@ export class SearchBox extends ViewBoxBaseComponent ); } - - return null; }); - results.filter(result => result); - return (
@@ -345,7 +449,7 @@ export class SearchBox extends ViewBoxBaseComponent
- {results} + {resultsJSX}
-- cgit v1.2.3-70-g09d2 From 21119bf271f9291265bbbc6e2bd4ef26f3fc0762 Mon Sep 17 00:00:00 2001 From: dg314 Date: Tue, 26 Oct 2021 14:30:45 -0400 Subject: update --- src/client/views/search/SearchBox.tsx | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'src') diff --git a/src/client/views/search/SearchBox.tsx b/src/client/views/search/SearchBox.tsx index 57c9a3d46..fe297782c 100644 --- a/src/client/views/search/SearchBox.tsx +++ b/src/client/views/search/SearchBox.tsx @@ -330,9 +330,9 @@ export class SearchBox extends ViewBoxBaseComponent Object.keys(proto).forEach(key => keys[key] = false)); -- cgit v1.2.3-70-g09d2