Comments (3)
Can you give me an example of a problem that benefits from this?
One potential concern is if any weights are numbers from 0 to 1, the shortest-path algorithm wouldn't find the shortest path.
from ubergraph.
Hello @Engelberg. Thanks for the quick response
The use case
I have a graph where each edge has a "probability" and I want to find the path with the highest probability. Where the probabilities are numbers between 0.0-1.0 and the probability of 0.5 with another 0.5 is 0.25.
Current solution
I end up fixing it with math: cost-fn
returns (- (Math/log probability))
.
So the probability of 0.5 is 0.3. Composing -log(0.5) with -log(0.5) results is 0.6 by sum
I'm not sure if this solution is totally right, but it is working for our use-case.
Final solution
If we decide to use compose-cost-fn
, we will need to use it on initial state too. possibly follow the clojure convention where the operator with no parameters returns the identity
value (+) => 0
(*) => 1
https://github.com/Engelberg/ubergraph/blob/v0.8.1/src/ubergraph/alg.clj#L297-L299
from ubergraph.
Your probability use-case is interesting, and your solution of doing the additive inverse of the log is a clever way to transform a "find the greatest product" problem into "find the smallest sum" problem.
If you had compose-cost-fn of *
, I don't think it would help here, at least not directly.
First, the shortest-path algorithm would be trying to find the smallest product, not the greatest. Second, the algorithm wouldn't even succeed at finding the smallest product because each successive edge in the graph is lowering the cost, and this algorithm assumes the total cost of the path stays the same or increases with each edge. (So, for example, with additive costs, negative numbers won't work and currently the library catches that and notifies the user they should be using Bellman-Ford instead, which can handle negative weights).
So, even if *
were available to you, you'd still have to do some sort of transformation, like taking 1/cost
for each edge, so that the numbers are all above 1 and you're minimizing the cost. And if you have to do a transformation anyway, why not do the transformation you've chosen?
The negative log solution also has another advantage: multiplying lots of probabilities will quickly tend towards 0, making it difficult to compare two long paths accurately due to limitations of floating point numbers, whereas the logs should put them into a range where addition is more stable.
I think your current solution may well be the best solution.
from ubergraph.
Related Issues (20)
- Perhaps more escaping help for ubergraph users? HOT 1
- Should removing a node from a graph also remove its attributes? HOT 5
- Questions for possible mention in ubergraph docs somewhere HOT 9
- Add full support for namespaced keywords HOT 5
- find-edges returns edges with no metadata HOT 4
- Odd behavior for `(add-attr g e k v)` when `e` is edge object from different graph HOT 4
- Possible warning for documentation on attribute functions HOT 1
- Clojurescript pathfinding HOT 5
- Allow arbitrary additional keys in a graph? HOT 4
- Several implementations of graph algorithms that could be added to ubergraph.alg namespace HOT 2
- Does the implementation of other-direction need to call edge-description->edge ? HOT 1
- `topsort` doesn't work with multigraphs HOT 5
- Adding metadata produces wrong graph HOT 4
- Inits vs Manual Graph Creation Differences and find-nodes? HOT 2
- In Dorothy 0.0.7, save! moved to dorothy.jvm HOT 2
- Heuristics function that takes 2 arguments HOT 2
- Expose loom.graph/subgraph function through ubergraph.core HOT 5
- Functions taking edge descriptions can't deal with multigraphs and multi-digraphs HOT 1
- Function ubergraph.core/weight doesn't return the correct weight for parallel edge specified with edge objects in multigraph/multi-digraph HOT 4
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from ubergraph.