Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

fix up and build up on top paths finder algorithm - for better unit tests of compiler plugin #5

Open
matanox opened this issue Nov 15, 2015 · 0 comments
Labels

Comments

@matanox
Copy link
Member

matanox commented Nov 15, 2015

The algorithm for finding acceptable paths between two nodes and its usage in the compiler plugin's unit test code need to be stepped up into better shape:

  • there should be a finer set of tests for the pure algorithm, in simple-graph's test code.
  • Algorithm (!) the algorithm can avoid storing so much in the caches -- by creating a list of lists of all paths as another run after all edges have been marked with their final "leads to target" status. It should reduce memory consumption at the cost of another pass (O(E)) on the graph, or on a subset of it that only contains nodes/edges that are "leads to target" = true.
    Consider the list creating approach e.g. described here and demonstrated here as an alternative for avoiding excessive storage at each node/vertex, or for a way to create the list of paths - however note a list including edges is needed in our domain here as we look at the edges types not just sterile edges.
  • Algorithm (!) the algorithm should memoize (cache status for) edges not vertices
  • there should be more graph-laden negative testing, in the compiler plugin's unit tests, in addition to the "positive" ones, for the simple cases. Then there can be added more tests as part of related tasks exploring correct capture from code examples.

Also explore tail recursion to justify the recursive implementation...

@matanox matanox changed the title Fix up and build up on top paths finder algorithm - for better unit tests of compiler plugin fix up and build up on top paths finder algorithm - for better unit tests of compiler plugin Nov 15, 2015
@matanox matanox added the core label Dec 2, 2015
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

No branches or pull requests

1 participant