Release notes from graph-theory

Bug fix

2025-02-02T21:41:21Z

Bug fix for shortest path.

In #42 @joshinils discovered that a call to shortest path with 0 as starting node, would result a call to graph.edges(from_node=0) which python interprets as False in the function selection in if from_node: ...

This bug is now solved with commit: #21e9d376.

There are no other changes.

Bug fix

2024-04-29T21:41:32Z

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.

Maintenance release

2024-03-13T20:03:03Z

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

Changes:

Maintenance release

2024-02-27T11:21:32Z

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

Maintenance release

2023-10-14T21:38:45Z

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

Maintenance release

2023-09-26T11:15:50Z

Patches a speed improvement for TSP.

bugfix release

2023-08-18T19:56:00Z

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

Maintenance release

2023-07-03T18:11:10Z

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.

Maintenance release

2023-06-26T22:25:14Z

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.

Maintenance release

2023-05-23T14:52:51Z

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)