This is a maintenance release with bugfix for #41, where the variable _edges
creates a key (which is default behaviour in collections.defaultdict
). This causes the graph to grow and can cause divergence when attempting to compare two otherwise identical graphs.
Published by root-11 8 months ago
Published by root-11 8 months ago
Bug fix release for error when detecting cycles with credit to Sappique.
the method g.has_cycle()
now uses topological sort instead of phaselines.
Changes:
Published by root-11 about 1 year ago
matplotlib is no longer a requirement.
no api changes other wise.
Published by root-11 about 1 year ago
Patches a speed improvement for TSP.
Published by root-11 about 1 year ago
This maintenance release contains a bug fix for shortest path with memorize (see #33 for details)
Otherwise no changes.
Published by root-11 over 1 year ago
This maintenance release refactors all of the modules, so they're easier to navigate.
None of the APIs (should) have changed, but should you be missing anything please raise a ticket.
Some may also find that the TSP solver is better and/or faster.
Published by root-11 over 1 year ago
This is a minor maintenance release.
The only changes are:
solve_tsp
for a rare case where the search runs into a infinite cycle.hash
to hash_methods
to avoid name-space collision with python's built-in hash
The version was updated to 2023.1.1 due to the breaking change of the name changes only.
Published by root-11 over 1 year ago
This maintenance release delivers a new algorithm for the detection of phaselines in graphs which reduces the runtime from O(V*E) to O(V+E).
From the docs string:
Detecting phaselines is useful for determining which tasks can be performed in parallel.
Each phase in the phaselines must be completed to assure that the tasks in the next phase can be performed with complete input.
This is in contrast to Topological sort that only generates a queue of tasks, may be fine for a single processor, but has no mechanism for coordination that all inputs for a task have been completed so that multiple processors can work on them.
Here is an example of a DAG with tasks:
u1 u4 u2 u3
\ \ \_______\
csg cs3 append
\ \ \
op1 \ op3
\ \ \
op2 \ cs2
\ \___________\
cs1 join
\ \
map1 map2
\___________\
save
The phaselines would be:
phaselines = {
"u1": 0, "u4": 0, "u2": 0, "u3": 0,
"csg": 1, "cs3": 1, "append": 1,
"op1": 2, "op3": 2,
"op2": 3, "cs2": 3,
"cs1": 4, "join": 4,
"map1": 5, "map2": 5,
"save": 6,
}
From this example it is visible that processing the 4 'uN' (uploads) is the highest degree of concurrency. This can be determined as follows:
d = defaultdict(int)
for _, pl in graph.phaselines():
d[pl] += 1
max_processors = max(d, key=d.get)
Published by root-11 almost 2 years ago
Import sped up by importing 3dplot in function call rather than at module top. Credit @fiendish
No API changes.
Published by root-11 almost 2 years ago
Fix for empty package.
Published by root-11 almost 2 years ago
There are no API changes.
Only added support for python 3.7-3.11
Published by root-11 almost 2 years ago
No changes. Only support for python 3.11
Published by root-11 almost 2 years ago
No significant changes.
Added support for python 3.11