The project is divided in the five namespaces below:
- Adapter
Functions that intermediate input and output with the logic functions.
- Data
Functions related to insert and manage data.
- Logic
Functions that compose the main logic of reward system.
- Handler
Routes of endpoint to receive input and/or show output.
- Utility
Utility functions that are needed and used in others namespaces.
The main function is bfs that is a recursive function that explore nodes by theirs levels. Is an implementation of the breadth-first search (BFS) algorithm for traversing the graph. Produces a lazy-seq of points for each node visited, it means that only calculate the necessary like (take 2 (bfs args)) only returns the seq of the first two points of nodes visiteds.
Detailed flow of input:
1 2
1 3
3 4
2 4
4 5
4 6
The graph below represents the data structured used in the solution. Note that inviteds and confirmed-inviteds are defined before by using sets in insertion (people that invited someone are confirmed-inviteds).
The states used are:
-
Levels: A hash-map of levels of each node.
-
Visited: Nodes that are already been visiteds in the tranversing algorithm.
-
Adjacent: Nodes to be visited in a queue.
-
Vertice: Current node.
-
Inviteds: Nodes directly connected to vertice.
-
Confirmed-inviteds: Quantity of inviteds that are confirmed-inviteds.
-
Level: Level of vertice.
-
Points: Intermediate points of vertice calculated by (1/2)^level * number of confirmed inviteds.
Points of 1 = 2 + 0.5 + 0.0 + 0.0 + 0.0 + 0.0 = 2.5
To calcute rewards points of other nodes is necessary to call bfs with the target node being the start-point.
The run function in reward-system.adapter use future to parallelize the count of node reward points. And use deref to wait until all futures are done to show result. Since ranking is an atom (thread safe and retriable), the use of future has no damage to the result consistency.
The old-run function in reward-system.adapter count the node reward points sequentially.
Therefore, the parallelism technique has more performance gain with larger inputs.
$ lein ring server
$ curl http://localhost:3000/
$ curl http://localhost:3000/ranking
$ curl -H "Content-Type: application/json" -X POST -d '{"path": "path/to/file"}' http://localhost:3000/insert/file
$ curl -H "Content-Type: application/json" -X POST -d '{"path": "resources/sample-in"}' http://localhost:3000/insert/file
THe inviter and invited value must be strings representing numbes like "1".
$ curl -H "Content-Type: application/json" -X POST -d '{"inviter": "inviter", "invited": "invited"}' http://localhost:3000/insert
$ curl -H "Content-Type: application/json" -X POST -d '{"inviter": "1", "invited": "2"}' http://localhost:3000/insert
$ lein midje