cifasis / sb-graph Goto Github PK

Currently, the SBG library doesn't count with a parser, which leads to a huge test suit (GraphTest).

It would be nice to define DSL for intervals, multi-intervals, etc. Then, define its parser. A big bonus would be a graphic interface to draw graphs.

Develop an SCC algorithm for SBG, using minReach function.

The current implementation makes use of the boost graph library to represent SBG. In the implementation of algorithms we use the defined maps (ignoring the boost module) or else we have to make two calls (one to boost and another to the SBG functions).
Also many modules of structures such as intervals, multi_intervals, etc. were in an experimental stage, and as such their implementation is pretty messy.
A complete refactor of these modules is proposed, adding the optimizations described in iss-18.

The current implementation of maps uses double to represent real numbers. This can be a problem when working with big numbers (main application of ModelicaCC), where the distribution of floating point numbers is sparse. With such numbers, the application of a map to a domain leads to an incorrect result.

Suggestion: use fractional numbers. Check if BOOST supports them.

Just to be able to separately compile sbg-graph library as a third party lib.

Currently disable pw_map and map eval system tests because they are failing consistently. Either fix or update them so we can add them back to the test-suite.

Currently the minimum reachable operation composes many times different maps. By profiling some examples, this last operation proved to be one of the most costly in regards to execution time. A very brief sketch of the proposed new implementation to be testes is as follows:

1. Keep track of MRV (minimum reachable vertex) with a representative's map Rmap, and the distance to each of them with a distance map Dmap. Also, a successor map Smap will indicate the path used to reach each MRV.
2. Calculate a new Rmap with adjacent vertices using minAdj.
3. Between all the possible successors that lead to the MRV, choose the one with minimum distance to the MRV according to Dmap. The distance is necessary for the case in which the graph contains cycles.

Currently, sets are implemented without order. We think that canonizing them through order can be an improvement to the cost of the operations.