<commit_before>class DijkstraAlgorithm(object):

    def __init__(self):
        self.large_number = 1e4            # large number greater than any distance in the tree
        self.minimum = 0
        self.G = None
        self.source = None
        self.target = None

    def reset(self, G, source, target):
        self.G = G
        self.source = source
        self.target = target
        self.dist = {}
        self.dist[source] = self.minimum
        self.previous = {}

        # build distance and previous node dictionaries
        for v in self.G:
            if v != self.source:
                self.dist[v] = self.large_number
            self.previous[v] = None

    def dijkstra(self):
        unvisited_nodes = set(self.G)

        while len(unvisited_nodes):
            # pick the node closest to source that has not been picked
            min_dist = [None, self.large_number]

            for n in unvisited_nodes:
                if self.compare(self.dist[n], min_dist[1]):
                    min_dist = [n, self.dist[n]]
            u = min_dist[0]
            unvisited_nodes.remove(u) # remove the node you picked from unvisited_nodes

            for v in u.v_refs:
                if v:
                    alt = self.update_distance(self.dist[u], v)
                    # update dist of the neighbor if this is a closer route
                    if self.compare(alt, self.dist[v]):
                        self.dist[v] = alt
                        self.previous[v] = u

    def find_path(self, G, source, target):
        """Return the path to target from the source node
        Inputs:
            G - a list containing all nodes in the graph
            source - start node for the path
            target - node to end at
        """
        if target != self.target:
            self.target = target
        if source != self.source or G != self.G:
            self.reset(G, source, target)
            self.dijkstra()

        path = [self.target]
        u = self.target
        while self.previous[u]:
            u = self.previous[u]
            path.append(u)
        if path[-1] != self.source:
            raise ValueError('%s does not equal the expected start node, %s'
                             % (path[-1], self.source))
        return path[::-1]

    @staticmethod
    def update_distance(x, v):
        return x + v.weight

    @staticmethod
    def compare(x, y):
        return x <= y

class DijkstraResourceAlgorithm(DijkstraAlgorithm):

    def __init__(self):
        DijkstraAlgorithm.__init__(self)
        self.large_number = [1e4, 1e4, 1e4, 1e4]            # large number greater than any distance in the tree
        self.minimum = [0, 0, 0, 0]

    @staticmethod
    def compare(x, y):
        return sum([v **2 for v in x]) <= sum([v**2 for v in y])

    @staticmethod
    def update_distance(x, v):
        return [res_val + v.resources[i] for i, res_val in enumerate(x)]<commit_msg>Settlement path finding algorithm<commit_after>class DijkstraAlgorithm(object):

    def __init__(self):
        self.large_number = 1e4            # large number greater than any distance in the tree
        self.minimum = 0
        self.G = None
        self.source = None
        self.target = None

    def reset(self, G, source, target):
        self.G = G
        self.source = source
        self.target = target
        self.dist = {}
        self.dist[source] = self.minimum
        self.previous = {}

        # build distance and previous node dictionaries
        for v in self.G:
            if v != self.source:
                self.dist[v] = self.large_number
            self.previous[v] = None

    def dijkstra(self):
        unvisited_nodes = set(self.G)

        while len(unvisited_nodes):
            # pick the node closest to source that has not been picked
            min_dist = [None, self.large_number]

            for n in unvisited_nodes:
                if self.compare(self.dist[n], min_dist[1]):
                    min_dist = [n, self.dist[n]]
            u = min_dist[0]
            unvisited_nodes.remove(u) # remove the node you picked from unvisited_nodes

            v_refs = self.get_refs(u)
            for v in v_refs:
                if v:
                    alt = self.update_distance(self.dist[u], v)
                    # update dist of the neighbor if this is a closer route
                    if self.compare(alt, self.dist[v]):
                        self.dist[v] = alt
                        self.previous[v] = u

    @staticmethod
    def get_refs(v):
        return v.v_refs

    def find_path(self, G, source, target):
        """Return the path to target from the source node
        Inputs:
            G - a list containing all nodes in the graph
            source - start node for the path
            target - node to end at
        """
        if target != self.target:
            self.target = target
        if source != self.source or G != self.G:
            self.reset(G, source, target)
            self.dijkstra()

        path = [self.target]
        u = self.target
        while self.previous[u]:
            u = self.previous[u]
            path.append(u)
        if path[-1] != self.source:
            raise ValueError('%s does not equal the expected start node, %s'
                             % (path[-1], self.source))
        return path[::-1]

    @staticmethod
    def update_distance(x, v):
        return x + v.weight

    @staticmethod
    def compare(x, y):
        return x <= y

class DijkstraResourceAlgorithm(DijkstraAlgorithm):

    def __init__(self):
        DijkstraAlgorithm.__init__(self)
        self.large_number = [1e4, 1e4, 1e4, 1e4]            # large number greater than any distance in the tree
        self.minimum = [0, 0, 0, 0]

    @staticmethod
    def compare(x, y):
        return sum([v **2 for v in x]) <= sum([v**2 for v in y])

    @staticmethod
    def update_distance(x, v):
        return [res_val + v.resources[i] for i, res_val in enumerate(x)]

class DijkstraSettlementAlgorith(DijkstraAlgorithm):
    @staticmethod
    def get_refs(v):
        return v.s_refs
{'fraction_non_alphanumeric': 0.09457035708462416, 'fraction_numerical': 0.0071743029512473504, 'mean_word_length': 1.6611713665943602, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5908001', 'n_tokens_mistral': 1820, 'n_tokens_neox': 1736, 'n_words': 544}