graphkit icon indicating copy to clipboard operation
graphkit copied to clipboard

ENH: ignore unsatified operations with partial inputs

Open ankostis opened this issue 6 years ago • 3 comments

Reason:

The purpose is not to require a "perfect" input model for the dag to run, but the algorithm to find the minimum viable subgraph that can compute.

Useful also when 2 (or more) operations provide the same output, and provided inputs fully satisfy only one of operation.

Changes

For instance, the graph below with this PR can go ahead and compute

  • ab_plus_c=21 when given just a=10 & b1=2, and
  • ab_plus_c=6 when given just a=10 & b2=2:

t

Before this PR, the above graph would fail on execution time while trying to evaluate needlesly the un-satisfied operations.

NOTE that it is an invasive change and have repercussions to many decision of this library.


I confirm that this contribution is made under the terms of the license found in the root directory of this repository's source tree and that I have the authority necessary to make this contribution on behalf of its copyright owner.

ankostis avatar Sep 29 '19 17:09 ankostis

Codecov Report

Merging #18 into master will increase coverage by 1.14%. The diff coverage is 88.37%.

Impacted file tree graph

@@            Coverage Diff             @@
##           master      #18      +/-   ##
==========================================
+ Coverage   77.87%   79.01%   +1.14%     
==========================================
  Files           5        5              
  Lines         348      367      +19     
==========================================
+ Hits          271      290      +19     
  Misses         77       77
Impacted Files Coverage Δ
graphkit/functional.py 93.82% <100%> (+0.07%) :arrow_up:
graphkit/network.py 72.68% <86.48%> (+2.48%) :arrow_up:

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update e70718b...7b99b16. Read the comment docs.

codecov-io avatar Sep 29 '19 20:09 codecov-io

Merged with #23 bc ordered-set is needed to rewrite unsatisfied traversal with topo-sort (without visited nodes).

ankostis avatar Oct 01 '19 13:10 ankostis

$ date
Tue 08 Oct 2019 06:55:39 PM EEST
$ cloc --by-file-by-lang  graphkit 
       5 text files.
       5 unique files.                              
       0 files ignored.

github.com/AlDanial/cloc v 1.82  T=0.01 s (539.2 files/s, 106761.0 lines/s)
------------------------------------------------------------------------------------
File                                  blank        comment           code
------------------------------------------------------------------------------------
graphkit/network.py                     116            190            237
graphkit/functional.py                   51             77             89
graphkit/base.py                         34             78             68
graphkit/__init__.py                      3              3              5
graphkit/modifiers.py                     8             29              2
------------------------------------------------------------------------------------
SUM:                                    212            377            401
------------------------------------------------------------------------------------

-------------------------------------------------------------------------------
Language                     files          blank        comment           code
-------------------------------------------------------------------------------
Python                           5            212            377            401
-------------------------------------------------------------------------------
SUM:                             5            212            377            401
-------------------------------------------------------------------------------

ankostis avatar Oct 08 '19 15:10 ankostis