graph-theory

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.

Bug fix release for __eq__ with credit to @sappique (bug #40).

Changes:

• new tests
• code changes

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:

• new test 1
• change: 2

matplotlib is no longer a requirement.
no api changes other wise.

Patches a speed improvement for TSP.

This maintenance release contains a bug fix for shortest path with memorize (see #33 for details)
Otherwise no changes.

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.

This is a minor maintenance release.

The only changes are:

• bug fix for solve_tsp for a rare case where the search runs into a infinite cycle.
• change of name of module 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.

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)

Import sped up by importing 3dplot in function call rather than at module top. Credit @fiendish
No API changes.

Fix for empty package.

There are no API changes.
Only added support for python 3.7-3.11

No changes. Only support for python 3.11

No significant changes.
Added support for python 3.11