Crate unobtanium_graph_algorithms

Expand description

§Unobtanium Graph Algorithms

This rust crate implements graph ranking algorithms for the unobtanium search engine.

Currently implemented Algorithms are:

PageRank (needs fixes, only works for undirected graphs right now)
TextRank

§Overview

At the core of this crate is the Graph data structure, which can be populated with arbitrary data (Must implement Hash, Eq and Clone) that represents nodes.

On top of this Graph functions like populate_for_textrank() and run_pagerank() can prepare the graph and run different algorithms on it.

Custom graph configurations can be realized by populating the graph inside a callback to its modify method. The callback is to make sure that node ids inside the graph stay opaque and can’t be confused with the ids of another graph structure. (This is called Data Branding)

§License

The Unobtanium Graph Algorithms crate is licensed as LGPL-3.0-only.

The project aims to be compliant with version 3.3 of the reuse specification.

§Where to start

Construct a Graph, run one of the populate_*() methods and follow its recommendations on a run_*() method.

Example: TextRank keyword extraction

use unobtanium_graph_algorithms::Graph;
 
let mut graph = Graph::new();
graph.populate_for_textrank(&["This", "text", "is", "about", "cats", "and", "dogs", "but", "mostly", "dogs"], 2);
let result = graph.run_pagerank(&Default::default());

// The top word is "dogs"
let top_word = result.sorted_iter().next().unwrap();
assert_eq!(*top_word.0, "dogs");
assert!(top_word.1 > 1.3, "Expected: score (={0}) > 1.3", top_word.1);

// The total value in the pagerank graph is equal to the result length 
let total_score_sum = result.unsorted_iter().fold(0.0, |a, i| a+i.1);
assert_eq!(result.len() as f32, total_score_sum);

Structs§

BrandedNodeId: A Node identifier that is strongly coupled to the MutableGraph it belongs into.
Graph: Datastructure to run graph algorithms on.
MutableGraph: Mutable version of Graph which you can use inside the callback given to Graph::modify.
PageRankConfiguration: Parameters for the pagerank algorithm
RankedNodes: Holds the result of a ranking algorithm that was run on a Graph.
SortedRankedNodesIter: Iterator sorted by best score first over the elements in a RankedNodes structure.
UnsortedRankedNodesIter: Unsorted iterator over the RankedNodes structure.