Суммирование цепочки транзакций в кадре данных, строки, связанные значениями столбцов

Question

Я пытаюсь связать несколько строк из DataFrame, чтобы получить все возможные пути, сформированные путем подключения идентификаторов получателей к идентификаторам отправителей.

Вот пример моего DataFrame:

   transaction_id sender_id receiver_id  amount
0          213234       002         125      10
1          223322       017         354      90
2          343443       125         689      70
3          324433       689         233       5
4          328909       354         456      10

создано с помощью:

df = pd.DataFrame(
    {'transaction_id': {0: '213234', 1: '223322', 2: '343443', 3: '324433', 4: '328909'},
     'sender_id': {0: '002', 1: '017', 2: '125', 3: '689', 4: '354'},
     'receiver_id': {0: '125', 1: '354', 2: '689', 3: '233', 4: '456'},
     'amount': {0: 10, 1: 90, 2: 70, 3: 5, 4: 10}}
)

Результатом моего кода должен быть список связанных идентификаторов и общая сумма для цепочки транзакций. Для первых двух строк в приведенном выше примере это выглядит примерно так:

[('002', '125', '689', '233'), 85]
[('017', '354', '456'), 100]

Я уже пытался перебирать строки и преобразовывать каждую строку в экземпляр класса Node, а затем использовал методы дляОбход связанного списка, но я понятия не имею, какой здесь следующий шаг:

class Node:
    def __init__(self,transaction_id,sender,receiver,amount):
        self.transac = transaction_id
        self.val = sender_id
        self.next = receiver_id
        self.amount = amount
    def traverse(self):
        node = self # start from the head node
        while node != None:
            print (node.val) # access the node value
            node = node.next # move on to the next node

for index, row in customerTransactionSqlDf3.iterrows():
    index = Node( 
        row["transaction_id"],
        row["sender_id"],
        row["receiver_id"],
        row["amount"]
    )

Дополнительная информация:

• Значения sender_id уникальны, для каждого идентификатора отправителя существуеттолько одна возможная цепочка транзакций.
• Нет циклов, нет цепочки, в которой идентификатор получателя указывает на идентификатор отправителя в том же пути.

Answer 1

Я понятия не имею, какой здесь следующий шаг

Используя текущую реализацию, вы можете соединить два объекта Node, повторяя каждый узел. Вы также можете добавить свойство visited в класс Node, чтобы вы могли идентифицировать уникальную цепочку при прохождении по дереву, т. Е. Нет ни одной цепочки, являющейся подцепью другой цепочки. Однако, если вы хотите знать цепочку для каждого sender_id, это может быть необязательно.

Редактировать: я заметил, что вы упомянули пример ожидаемого результата для первогодва ряда. Это означает, что каждый sender_id должен иметь свою собственную цепочку. Изменение метода traverse, чтобы его можно было использовать после подключения всех узлов.

Редактировать: Переопределить свойство visited для получения уникальной цепочки

df = pd.DataFrame(
    {'transaction_id': {0: '213234', 1: '223322', 2: '343443', 3: '324433', 4: '328909'},
     'sender_id': {0: '002', 1: '017', 2: '125', 3: '689', 4: '354'},
     'receiver_id': {0: '125', 1: '354', 2: '689', 3: '233', 4: '456'},
     'amount': {0: 10, 1: 90, 2: 70, 3: 5, 4: 10}}
)

class Node:
    def __init__(self,transaction_id,sender_id,receiver_id,amount):
        self.transac = transaction_id
        self.sender = sender_id
        self.receiver = receiver_id
        self.next = None
        self.amount = amount
        self.visited = False
    def traverse(self, chain=None, total=0):
        if (self.visited): # undo visited nodes
            return
        self.visited = True
        if chain is None: # this is the beginning of the traversal
            chain = [self.sender]
        chain += [self.receiver]
        total += self.amount
        if self.next is not None:
            return self.next.traverse(chain, total)
        return chain, total

transc = [Node( 
        row["transaction_id"],
        row["sender_id"],
        row["receiver_id"],
        row["amount"]
    ) for i, row in df.iterrows()]

# connect the nodes
for i, v in enumerate(transc):
    for j, k in enumerate(transc):
        # if the receiver v same as the sender from j
        if v.receiver == k.sender:
            v.next = k


summary = [i.traverse() for i in transc]
summary = [i for i in summary if i is not None] # removing None

print(summary)

Вывод:

[
    (['002', '125', '689', '233'], 85), 
    (['017', '354', '456'], 100)
]

Answer 2

У вас есть ориентированный граф с ребрами, образованными id -> id связями. Вы пытаетесь перечислить все пути через этот график. Это на самом деле намного проще на не с использованием связанных списков.

Обратите внимание, что ваша реализация связанного списка на самом деле не связывает узлы;Ваши значения next должны ссылаться на другие Node экземпляры, а не на id.

Поскольку ваши пути не могут иметь циклов, график называется ациклическим ,Ваши пути также очень просты, так как вы говорите, что никогда не может быть более одного идентификатора получателя на идентификатор отправителя.

Создайте новое представление в вашем фрейме данных с индексом sender_id вместе с идентификатором и количеством получателя. колонны;это позволит очень легко найти следующие элементы пути. Затем вы можете перебирать эти столбцы, обходить их пути и тривиально суммировать их суммы. В следующем коде используются уже найденные пути , чтобы избежать необходимости повторного обхода этих путей:

# receiver and amount rows, indexed by sender
edges = df[['sender_id', 'receiver_id', 'amount']].set_index('sender_id')
paths = {}   # sender -> [sender, receiver, receiver, receiver, ...]
totals = {}  # sender -> total amount

for sender, next_, amount in edges.itertuples():
    path = paths[sender] = [sender, next_]
    totals[sender] = amount
    while True:
        if next_ in paths:
            # re-use already found path
            path += paths[next_]
            totals[sender] += totals[next_]
            break

        try:
            next_, amount = edges.loc[next_]
        except KeyError:
            break  # path complete

        path.append(next_)
        totals[sender] += amount

Код можно сделать еще более эффективным, обновляя каждый встреченный подпуть, поэтому, когда выобработайте 3-ю строку для идентификатора отправителя 125, этот путь уже обработан, потому что вам пришлось пройти его по пути, начинающемуся с 002 для первой строки:

for sender, next_, amount in edges.itertuples():
    if sender in paths:
        # already handled as part of a longer path
        continue

    paths[sender], totals[sender] = [sender, next_], amount
    senders = [sender]  # all sender ids along the path

    while True:
        if next_ in paths:
            # re-use already found path
            for sender in senders:
                paths[sender] += paths[next_]
                totals[sender] += totals[next_]
            break

        if next_ not in edges.index:
            break  # path complete

        # start a new path from this sender id
        paths[next_], totals[next_] = [next_], 0
        senders.append(next_)

        next_, amount = edges.loc[next_]
        for sender in senders:
            paths[sender].append(next_)
            totals[sender] += amount

В любом случае, вы сейчасиметь полные пути и итоги для всех ваших транзакций. Вы можете превратить их обратно в дополнительные столбцы:

df['path'], df['total'] = df.sender_id.map(paths), df.sender_id.map(totals)

Для вашего входного фрейма данных, который выдает:

   transaction_id sender_id receiver_id  amount                  path  total
0          213234       002         125      10  [002, 125, 689, 233]     85
1          223322       017         354      90       [017, 354, 456]    100
2          343443       125         689      70       [125, 689, 233]     75
3          324433       689         233       5            [689, 233]      5
4          328909       354         456      10            [354, 456]     10

В качестве альтернативы, вы можете объединить пути и итоги, зацикливая либословарь:

for id, path in paths.items():
    print(id, path, totals[id])

, который, опять же для вашего конкретного примера, выдает:

002 ['002', '125', '689', '233'] 85
125 ['125', '689', '233'] 75
689 ['689', '233'] 5
017 ['017', '354', '456'] 100
354 ['354', '456'] 10