Working np Algorithm

Algorithm seems to work. More testing and overthinking the structure necessary.

evrouting/charge/T.py

-from copy import copy
-from collections import namedtuple
+from typing import Callable, NamedTuple
 from math import inf
 
-import networkx as nx
-
 from evrouting.T import SoC, Wh, ChargingCoefficient, Time, Node
-from evrouting.graph_tools import charging_cofficient, consumption
 
-Label = namedtuple('Label', ['t_trip', 'beta_u', 'u', 'SoCProfile_u_v'])
 
+class SoCProfile:
+    """
+    The SoC Profile maps an initial SoC to the SoC after
+    traversing a path.
 
-class ChargingFunction:
+    SoC profile of a path is fully described with two parameters:
+        - cost: Cost of going from u to v.
+        - out: Maximal SoC after passing the path from u to v.
+    """
 
-    def __init__(self, G: nx.Graph, l: Label):
-        self.t_trip: Time = l.t_trip
-        self.beta_u: SoC = l.beta_u
-        self.u: Node = l.u
-        self.b_u_v: SoCProfile = l.SoCProfile_u_v
-        self.c_u: ChargingCoefficient = charging_cofficient(G, l.u)
+    def __init__(self, path_cost: Wh, capacity: SoC):
+        """
+        Calculates the maximum SoC after traversing the path, which is
+        (for non-negative path costs) U - cost.
 
-    def __call__(self, t) -> SoC:
-        if t < self.t_trip:
+        :param path_cost: Cost of the path. The SoC Profile of
+            a single vertex has no cost.
+        :param capacity: The battery's capacity.
+        """
+        self.capacity: SoC = capacity
+        self.path_cost: Wh = path_cost
+        self.out: SoC = capacity - self.path_cost
+
+    def __call__(self, initial_soc: SoC) -> SoC:
+        """
+        :param initial_soc: The initial SoC.
+        :returns: The SoC after traversing the path.
+        """
+        if initial_soc < self.path_cost:
             return -inf
+        final_soc = initial_soc - self.path_cost
+
+        return final_soc if final_soc < self.capacity else self.capacity
 
-        return self.beta_u(self.beta_u + self.c_u * (t - self.t_trip))
+    def __add__(self, other: 'SoCProfile') -> 'SoCProfile':
+        """
+        Combines to SoC Profiles.
 
-    def get_minimum(self) -> Time:
-        """TODO: Explain."""
-        cost_p = self.b_u_v.cost
-        return max(self.t_trip, (cost_p - self.beta_u) / self.c_u + self.t_trip)
+        The for the combined SoC Profile, given a SoC Profile for a path a
+        and a path b, holds:
 
+            cost = cost_a + cost_b
+            out = U - cost
 
-class SoCProfile:
+        :return: Combined SoC Profile.
+        """
+        return SoCProfile(self.path_cost + other.path_cost, self.capacity)
+
+
+class ChargingFunction:
     """
-    Describe SoC profile with two parameters:
-        - cost: Cost of going from u to v.
-        - out: Maximal SoC after passing the path from u to v.
+    Charging functions map charging time to resulting SoCs. Since they are
+    monotonic, there exists also an inverse mapping SoC to charging time.
+
+    Dummy Charging Station
+    ======================
+
+    Special case is a so called dummy charging station. This is the case
+    if the charging coefficient is 0. Then there is no actual charging and
+    the value of the charging station is always the same as the arrival SoC.
+
+    A dummy charging station is necessary for initialization of the problem
+    to trigger spawning of new labels.
     """
 
-    def __init__(self, G: nx.Graph, U: SoC, u: Node, v: Node = None):
-        if v is None:
-            self.cost: Wh = 0
-            self.out: Wh = U
+    def __init__(self, c: ChargingCoefficient, capacity: SoC,
+                 initial_soc: SoC = None):
+        """
+
+        :param c: The stations charging coefficient. If c=0, the this becomes
+            a so called dummy charging station, that exists to trigger label
+            creation in the algorithm.
+        :param capacity: The battery's capacity, respectively the maximum of
+            the charging function.
+        :param initial_soc: The SoC at arriving at the charging station. This is
+            optional for dummy charging stations, that do not actually charge:
+
+                cf(b) = soc
+
+        """
+        self.c: ChargingCoefficient = c
+        self.capacity: SoC = capacity
+        self.initial_soc: SoC = initial_soc
+
+    @property
+    def is_dummy(self) -> bool:
+        """Tell if function is a dummy function."""
+        return self.c == 0
+
+    def __call__(self, t: Time, initial_soc: SoC = 0) -> SoC:
+        """
+        :param t: Charging time
+        :param initial_soc: Initial SoC when starting to charge
+        :return: SoC after charging.
+        """
+        if self.is_dummy:
+            if self.initial_soc is None:
+                raise ValueError(
+                    'Charging coefficient is 0 but no initial SoC given.'
+                    )
+            soc = self.initial_soc
         else:
-            self.cost: Wh = consumption(G, u, v)
-            self.out: Wh = U - self.cost
+            soc = initial_soc + self.c * t
+
+        return soc if soc < self.capacity else self.capacity
+
+    @property
+    def inverse(self) -> Callable[[SoC], Time]:
+        """
+        :returns: Inverse charging function mapping SoC to charging
+            time (assuming initial SoC=0)
+        """
+        if self.is_dummy:
+            raise ValueError('Dummy Carging function has no inverse.')
+
+        c = self.c
+        capacity = self.capacity
+
+        def cf_inverse(soc: SoC) -> Time:
+            if soc > capacity:
+                # Return max charge time
+                return capacity / c
+            elif soc < 0:
+                # Return min charge time
+                return 0
+
+            return soc / c
+
+        return cf_inverse
 
-    def __call__(self, beta) -> SoC:
-        if beta < self.cost:
+
+class Label(NamedTuple):
+    """
+    Label used for the Algorithm.
+
+    The (paleto optimal) label where u=t is the
+    contains the minimum trip time necessary to get to t.
+
+    The label of node v consists of a tuple:
+
+        (t_trip, soc_last_cs, last_cs, soc_profile_cs_v)
+
+    Where:
+
+        :t_trip: Trip time to node v without charging time at the last
+            charging station.
+        :soc_last_cs: Arrival SoC at the last charging station.
+        :last_cs: (Node ID of) The last charging station.
+        :soc_profile_cs_v: The SoC Profile describing the costs going from
+            the charging station to current node v.
+    """
+    t_trip: Time
+    soc_last_cs: SoC
+    last_cs: Node
+    soc_profile_cs_v: SoCProfile
+
+
+class SoCFunction:
+    """
+    SoC Function of a node's label maps trip time plus an additional charging
+    time at the last charging station to a SoC at the node.
+
+    """
+
+    def __init__(self, label: Label, cf_cs: ChargingFunction):
+        """
+        :param label: Label containing to a node. It has the fields:
+
+            :t_trip: Trip time. Includes time to reach v from the last
+                charging station in the path but excludes charging at u.
+            :soc_last_cs: The SoC at reaching the last charging station
+                before any charging.
+            :last_cs: The last charging station in the path to current node.
+            :soc_profile_cs_v: The SoC Profile of the path cs -> v.
+            :cf_cs: Charging function of cs.
+
+        :param cf_cs: The charging function of the last charging station.
+        """
+        # Unpack label
+        self.t_trip: Time = label.t_trip
+        self.last_cs: Node = label.last_cs
+        self.soc_last_cs: SoC = label.soc_last_cs
+        self.soc_profile_cs_v: SoCProfile = label.soc_profile_cs_v
+
+        self.cf_cs: ChargingFunction = cf_cs
+
+    def __call__(self, t: Time) -> SoC:
+        """
+        Maps a new trip time to a SoC at the current node. The new trip time
+        then includes and fixes charging time at the last charging station.
+
+        :param t: t = trip time + charging at the last charging station
+        :return: SoC at current node at time t after spending t - t_trip at
+            the last charging station to charge the battery.
+
+        """
+        if t < self.t_trip:
+            # Impossible to reach the current node for times < trip time
             return -inf
-        return beta - self.cost
 
-    def __add__(self, other: 'SoCProfile') -> 'SoCProfile':
-        new = copy(self)
-        new.cost = self.cost + other.cost
-        new.out = self.out - other.cost
+        return self.soc_profile_cs_v(
+            self.cf_cs(t - self.t_trip, self.soc_last_cs)
+            )
+
+    @property
+    def minimum(self) -> Time:
+        """
+        :returns: Least feasible trip time. That is, the minimum time when
+            the SoC functions yields a SoC value that is not -inf.
+
+            This is either the trip time, or if energy needs to be charged
+            at the previous charging station to traverse the path, trip time
+            plus charging time until the battery holds the minimum energie to
+            traverse the path to the current node (which is the cost of the
+            path). This time is:
+
+            t = t_trip + cf_cs^(-1)(cost_cs_v) - cf_cs^(-1)(soc_last_sc)
+
+            Thus, for t_min holds:
+
+            t_min = max(t_trip, t)
+
+        """
+        cost_p = self.soc_profile_cs_v.path_cost
+
+        if cost_p > self.soc_last_cs:
+            if self.cf_cs.is_dummy:
+                # Not feasible. Dummy stations do not load.
+                return -inf
+
+            return self.t_trip + \
+                   self.cf_cs.inverse(cost_p) - \
+                   self.cf_cs.inverse(self.soc_last_cs)
 
-        return new
+        return self.t_trip