Merge pull request #47 from brown-dash/search-david

Page rank

1 files changed, 123 insertions, 19 deletions

diff --git a/src/client/views/search/SearchBox.tsx b/src/client/views/search/SearchBox.tsx
index 3612bd7c4..fe297782c 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<SearchBoxProps, SearchBoxDoc
 
     @observable _searchString = "";
     @observable _docTypeString = "all";
-    @observable _results: [Doc, string[]][] = [];
+    @observable _results: Map<Doc, string[]> = new Map<Doc, string[]>();
+    @observable _pageRanks: Map<Doc, number> = new Map<Doc, number>();
+    @observable _linkedDocsOut: Map<Doc, Set<Doc>> = new Map<Doc, Set<Doc>>();
+    @observable _linkedDocsIn: Map<Doc, Set<Doc>> = new Map<Doc, Set<Doc>>();
     @observable _selectedResult: Doc | undefined = undefined;
     @observable _deletedDocsStatus: boolean = false;
     @observable _onlyAliases: boolean = true;
@@ -110,11 +119,9 @@ export class SearchBox extends ViewBoxBaseComponent<SearchBoxProps, SearchBoxDoc
     });
 
     makeLink = action((linkTo: Doc) => {
-        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<SearchBoxProps, SearchBoxDoc
         const collection = CollectionDockingView.Instance;
         query = query.toLowerCase();
 
-        this._results = [];
+        this._results.clear();
         this._selectedResult = undefined;
 
         if (collection !== undefined) {
@@ -216,16 +223,114 @@ export class SearchBox extends ViewBoxBaseComponent<SearchBoxProps, SearchBoxDoc
                     const hlights = new Set<string>();
                     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();
+    }
+
+    /**
+     * 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<Doc> = 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<Doc, number> = new Map<Doc, number>();
+
+        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) {
@@ -244,7 +349,7 @@ export class SearchBox extends ViewBoxBaseComponent<SearchBoxProps, SearchBoxDoc
 
         const query = StrCast(this._searchString);
         Doc.SetSearchQuery(query);
-        this._results = [];
+        this._results.clear();
 
         if (query) {
             this.searchCollection(query);
@@ -256,16 +361,16 @@ export class SearchBox extends ViewBoxBaseComponent<SearchBoxProps, SearchBoxDoc
      * brushes and highlights. All search matches are cleared as well.
      */
     resetSearch = action(() => {
-        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<SearchBoxProps, SearchBoxDoc
 
         const isLinkSearch: boolean = this.props.linkSearch;
 
+        const sortedResults = Array.from(this._results.entries()).sort((a, b) => (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<SearchBoxProps, SearchBoxDoc
 
             if (this._docTypeString === "all" || this._docTypeString === result[0].type) {
                 validResults++;
-                return (
+                resultsJSX.push(
                     <Tooltip key={result[0][Id]} placement={"right"} title={<><div className="dash-tooltip">{title}</div></>}>
                         <div onClick={isLinkSearch ?
                             () => this.makeLink(result[0]) :
@@ -326,12 +434,8 @@ export class SearchBox extends ViewBoxBaseComponent<SearchBoxProps, SearchBoxDoc
                     </Tooltip>
                 );
             }
-
-            return null;
         });
 
-        results.filter(result => result);
-
         return (
             <div style={{ pointerEvents: "all" }} className="searchBox-container">
                 <div className="searchBox-bar" >
@@ -345,7 +449,7 @@ export class SearchBox extends ViewBoxBaseComponent<SearchBoxProps, SearchBoxDoc
                         {`${validResults}` + " result" + (validResults === 1 ? "" : "s")}
                     </div>
                     <div className="searchBox-results-scroll-view">
-                        {results}
+                        {resultsJSX}
                     </div>
                 </div>
             </div >