Comments (2)
I will also add my greedy algorithm for approximating a minimum NFVS. This algorithm uses FVS_python3 to compute an FVS first. Then, it iteratively removes nodes from the FVS until there is no negative cycles. We will compare the two algorithms.
In my experience, exact methods using ILP, SAT, or ASP do not scale well for very large models in most cases. In addition, the time spent for computing a minimum NFVS may be much larger than the time spent for Preprocessing SSF on the extra states. Hence, I do not recommend using exact methods here.
from biobalm.
I have a greedy algorithm in AEON that does this. Sadly it's not exported in AEON.py yet, but it shouldn't be a problem to reimplement it on a generic DiGraph. So the algorithm is not optimal (the NFVS is not necessarily minimal), but works quite all right on most networks.
Later, I can try to add some method based on SAT to compute the actual minimal NFVS, but that might not be particularly fast for very large networks, so I'm not sure if we want that anyway... Maybe eventually, we can also compare the size of the greedy NFVS and the number of independent negative cycles in the graph and if the discrepancy is too big, we can run the SAT based detection to get the optimal result :)
from biobalm.
Related Issues (20)
- AEON FVS parity option seems to have no effect HOT 7
- Add License HOT 2
- Our package name is scooped! HOT 9
- SCC Expansion Bug HOT 1
- Tracking issue for control HOT 5
- Storing Succession Diagrams HOT 2
- Investigate using constant nodes as drivers
- Succession diagram size bigger than expected HOT 1
- Source SCC based expansion HOT 15
- Control optimization HOT 2
- User friendliness improvements HOT 5
- Remaining tasks to run HOT 2
- Percolation is very slow HOT 12
- AEON stubs outdated? HOT 5
- Clean up repository
- Unused code HOT 2
- Standardize documentation HOT 6
- Move analysis to separate repository HOT 6
- Simplify `SuccessionDiagram` API HOT 2
- mole site down HOT 3
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 biobalm.