Ich muss alle Nachkommenpunkte von Links erhalten, die mit side_a - side_b (in einem Datenrahmen) dargestellt werden, bis für jede Seite_a ihr Endpunkt (in einem anderen Datenrahmen) erreicht ist. So:

df1:
side_a   side_b
  a        b
  b        c
  c        d
  k        l
  l        m
  l        n
  p        q
  q        r
  r        s

df2:
side_a    end_point
  a          c
  b          c
  c          c
  k          m
  k          n
  l          m
  l          n
  p          s
  q          s
  r          s

Der Punkt ist, alle Punkte für jeden side_a-Wert zu erhalten, bis der Endpunkt von df2 für diesen Wert erreicht ist. Wenn es zwei end_point-Werte hat (wie "k"), sollten es zwei Listen sein.

Ich habe etwas Code, aber er ist nicht mit diesem Ansatz geschrieben, er löscht alle Zeilen von df1, wenn df1['side_a'] == df2['end_points'] und das verursacht bestimmte Probleme. Aber wenn jemand möchte, dass ich den Code poste, werde ich das natürlich tun.

Die gewünschte Ausgabe wäre ungefähr so:

side_a    end_point
  a          [b, c]
  b          [c]
  c          [c]
  k          [l, m]
  k          [l, n]
  l          [m]
  l          [n]
  p          [q, r, s]
  q          [r, s]
  r          [s]

Und noch etwas: Wenn es auf beiden Seiten dasselbe gibt, muss dieser Punkt überhaupt nicht aufgeführt werden. Ich kann ihn später anhängen, was auch immer einfacher ist.

import pandas as pd
import numpy as np
import itertools

def get_child_list(df, parent_id):
    list_of_children = []
    list_of_children.append(df[df['side_a'] == parent_id]['side_b'].values)
    for c_, r_ in df[df['side_a'] == parent_id].iterrows():
        if r_['side_b'] != parent_id:
            list_of_children.append(get_child_list(df, r_['side_b']))

    # to flatten the list 
    list_of_children =  [item for sublist in list_of_children for item in sublist]
    return list_of_children

new_df = pd.DataFrame(columns=['side_a', 'list_of_children'])
for index, row in df1.iterrows():
    temp_df = pd.DataFrame(columns=['side_a', 'list_of_children'])
    temp_df['list_of_children'] = pd.Series(get_child_list(df1, row['side_a']))
    temp_df['side_a'] = row['side_a']

    new_df = new_df.append(temp_df)

Das Problem mit diesem Code ist also, dass es funktioniert, wenn ich Zeilen lösche, in denen side_a gleich end_point von df2 ist. Ich weiß nicht, wie ich die Bedingung implementieren soll, dass ich nicht weiter gehe, wenn ich den df2 in der Spalte side_b abfange und dann aufhöre.

Jede Hilfe oder jeder Hinweis ist hier wirklich willkommen. Danke im Voraus.

9
jovicbg 17 Apr. 2018 im 23:40

3 Antworten

Beste Antwort

Sie können die networkx-Bibliothek und Diagramme verwenden:

import networkx as nx
G = nx.from_pandas_edgelist(df, source='side_a',target='side_b')
df2.apply(lambda x: [nx.shortest_path(G, x.side_a,x.end_point)[0],
                     nx.shortest_path(G, x.side_a,x.end_point)[1:]], axis=1)

Ausgabe:

  side_a  end_point
0      a     [b, c]
1      b        [c]
2      c         []
3      k     [l, m]
4      k     [l, n]
5      l        [m]
6      l        [n]
7      p  [q, r, s]
8      q     [r, s]
9      r        [s]
4
Scott Boston 26 Apr. 2018 im 14:53

Wenn Sie mit einem zusätzlichen Import einverstanden sind, kann dies als Pfadproblem in einem Diagramm dargestellt und in wenigen Zeilen mithilfe von NetworkX:

import networkx

g = networkx.DiGraph(zip(df1.side_a, df1.side_b))

outdf = df2.apply(lambda row: [row.side_a, 
                               set().union(*networkx.all_simple_paths(g, row.side_a, row.end_point)) - {row.side_a}], 
                  axis=1)    

outdf sieht so aus. Beachten Sie, dass dies Mengen anstelle von Listen enthält, wie in Ihrer gewünschten Ausgabe. Auf diese Weise können alle Pfade auf einfache Weise kombiniert werden.

  side_a  end_point
0      a     {c, b}
1      b        {c}
2      c         {}
3      k     {l, m}
4      k     {l, n}
5      l        {m}
6      l        {n}
7      p  {r, q, s}
8      q     {r, s}
9      r        {s}
2
chthonicdaemon 26 Apr. 2018 im 16:36

Ihre Regeln sind inkonsistent und Ihre Definitionen sind unklar. Daher müssen Sie möglicherweise hier und da einige Einschränkungen hinzufügen, da nicht klar ist, was genau Sie fragen. Durch Organisieren der Datenstruktur entsprechend dem Problem und Erstellen einer robusteren Funktion für das Durchlaufen (siehe unten) wird es einfacher, Einschränkungen nach Bedarf hinzuzufügen / zu bearbeiten - und zu lösen das Problem vollständig.

Transformieren Sie das df in ein dict , um eine Baumstruktur besser darzustellen

Dieses Problem ist viel einfacher, wenn Sie die Datenstruktur so transformieren, dass sie intuitiver für das Problem ist, anstatt zu versuchen, das Problem im Kontext der aktuellen Struktur zu lösen.

## Example dataframe
df = pd.DataFrame({'side_a':['a','b','c','k','l','l','p','q','r'],'side_b':['b','c','d','l','m','n','q','r','s']})

## Instantiate blank tree with every item
all_items = set(list(df['side_a']) + list(df['side_b']))
tree = {ii : set() for ii in all_items}

## Populate the tree with each row
for idx, row in df.iterrows():
    tree[row['side_a']] =  set(list(tree[row['side_a']]) + list(row['side_b']))

Überquere den Baum

Dies ist jetzt viel einfacher, da die Datenstruktur intuitiv ist. Jeder Standard-Algorithmus für die Tiefensuche w / Pfad speichern reicht aus. Ich habe den Link geändert, um mit diesem Beispiel zu arbeiten.

Bearbeiten: Beim erneuten Lesen scheint es, dass Sie eine Bedingung für die Beendigung der Suche in endpoint haben (Sie müssen in Ihrer Frage klarer sein, was eingegeben und was ausgegeben wird). Sie können dfs_path(tree,**target**, root) anpassen und die Beendigungsbedingung ändern, um nur die richtigen Pfade zurückzugeben.

## Standard DFS pathfinder
def dfs_paths(tree, root):
    stack = [(root, [root])]
    while stack:
        (node, path) = stack.pop()
        for nextNode in tree[node] - set(path):
            # Termination condition. 
            ### I set it to terminate search at the end of each path.
            ### You can edit the termination condition to fit the 
            ### constraints of your goal
            if not tree[nextNode]:
                yield set(list(path) + list(nextNode)) - set(root)
            else:
                stack.append((nextNode, path + [nextNode]))

Erstellen Sie einen Datenrahmen aus den Generatoren, die wir geliefert haben

Wenn Sie mit Generatoren nicht besonders vertraut sind, können Sie die DFS-Durchquerung so strukturieren, dass sie in einer Liste ausgegeben wird. anstelle eines Generators

set_a = []
end_points = []
gen_dict = [{ii:dfs_paths(tree,ii)} for ii in all_items]
for gen in gen_dict:
    for row in list(gen.values()).pop():
        set_a.append(list(gen.keys()).pop())
        end_points.append(row)

## To dataframe
df_2 = pd.DataFrame({'set_a':set_a,'end_points':end_points}).sort_values('set_a')

Ausgabe

df_2[['set_a','end_points']]


set_a   end_points
a       {b, c, d}
b       {c, d}
c       {d}
k       {n, l}
k       {m, l}
l       {n}
l       {m}
p       {s, r, q}
q       {s, r}
r       {s}
3
Brendan Frick 24 Apr. 2018 im 19:34