feat: graph module and priority queue Dijkstra implementation

[joao-conde]

This relates to the RIPE Tech issue of multiple state transitions.

For RIPE Tech, we will need to find the shortest path between two states and make all the in-between transitions. Instead of a bespoke solution for order states only, I thought it was better to generalize the issue at hand: finding the shortest path in the graph. Hence I decided to implement a simple Dijkstra. This will allow us to abstract that logic here and simply apply the transitions in RIPE Core. It will also work for future entities with their own states and state graphs (while a bespoke solution for Order statuses only would not).

I think this source makes sense to be added to the Appier codebase because a graph module and graph utilities by themselves are useful in many domains (maybe in the future in networking to find the shortest path between nodes).

The proposed and implemented API is:

import appier

# a list of edges which is a list of tuples
# where the first element is the source node
# the second element is the destination node
# the third element is the cost of the edge (defaults to 1)
# the fourth element indicates whether the edge is bidirectional or not (defaults to unidirectional)
edges = [
    ("A", "B"),
    ("A", "C", 6, True),
    ("B", "D"),
    ("C", "D"),
    ("D", "E", 10),
    ("D", "F", 15),
    ("E", "F", 6),
    ("E", "G", 2),
    ("F", "G", 6)
]
graph = appier.Graph()
graph.add_edges(edges)

path, cost = graph.dijkstra("A", "F")
assert(path == ['A', 'B', 'D', 'F'])
assert(cost == 17)

Initializing the graph can also be done by passing the edges as an argument:

graph = appier.Graph([
    ("A", "B"),
    ("A", "C", 6, True),
    ("B", "D"),
    ("C", "D"),
    ("D", "E", 10),
    ("D", "F", 15),
    ("E", "F", 6),
    ("E", "G", 2),
    ("F", "G", 6)
])

[joao-conde]

@joamag manual tagging

[coveralls]

Coverage increased (+0.4%) to 64.341% when pulling b82b92920677a05c876aeef11df0accc1bea5913 on joao-conde:master into 97c854dcb86d840a53675486717e5009a374be48 on hivesolutions:master.

[coveralls]

Coverage decreased (-0.04%) to 63.935% when pulling 5a4438161369d98993b06346f6c9d5bcb420a72e on joao-conde:master into 97c854dcb86d840a53675486717e5009a374be48 on hivesolutions:master.