J'ai besoin d'obtenir tous les points descendants des liens représentés avec side_a - side_b (dans un dataframe) jusqu'à atteindre pour chaque side_a leur end_point (dans un autre dataframe). Donc:

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

Le point est d'obtenir tous les points pour chaque valeur side_a jusqu'à atteindre end_point à partir de df2 pour cette valeur. S'il a deux valeurs de point d'extrémité (comme le fait "k"), il doit s'agir de deux listes.

J'ai du code mais il n'est pas écrit avec cette approche, il supprime toutes les lignes de df1 si df1['side_a'] == df2['end_points'] et cela provoque certains problèmes. Mais si quelqu'un veut que je poste le code, je le ferai, bien sûr.

La sortie souhaitée serait quelque chose comme ceci:

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]

Et encore une chose, s'il y a le même côté, ce point n'a pas besoin d'être répertorié du tout, je peux l'ajouter plus tard, quoi que ce soit plus facile.

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)

Ainsi, le problème avec ce code est que cela fonctionne si je laisse tomber des lignes où side_a est égal à end_point de df2. Je ne sais pas comment implémenter la condition que si attrapez le df2 dans la colonne side_b, puis arrêtez, n'allez pas plus loin.

Toute aide ou indice est le bienvenu ici, vraiment. Merci d'avance.

9
jovicbg 17 avril 2018 à 23:40

3 réponses

Meilleure réponse

Vous pouvez utiliser la bibliothèque et les graphiques networkx:

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)

Production:

  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 avril 2018 à 14:53

Si vous êtes d'accord avec une importation supplémentaire, cela peut être posé comme un problème de chemin sur un graphique et résolu dans une poignée de lignes en utilisant 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 ressemble à ceci. Notez que cela contient des ensembles au lieu de listes comme dans votre sortie souhaitée - cela permet à tous les chemins d'être combinés de manière simple.

  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 avril 2018 à 16:36

Vos règles sont incohérentes et vos définitions ne sont pas claires, vous devrez donc peut-être ajouter des contraintes ici et là, car ce que vous demandez n'est pas clair. En organisant la structure de données pour l'adapter au problème et créant une fonction plus robuste pour la traversée (illustrée ci-dessous), il sera plus facile d'ajouter / modifier des contraintes selon les besoins - et de résoudre complètement le problème.

Transformez le df en un dict pour mieux représenter une structure arborescente

Ce problème est beaucoup plus simple si vous transformez la structure de données pour être plus intuitive au problème, au lieu d'essayer de résoudre le problème dans le contexte de la structure actuelle.

## 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']))

Traverser l'arbre

C'est beaucoup plus simple maintenant que la structure des données est intuitive. Tout algorithme de recherche en profondeur w / sauvegarde de chemin fera l'affaire. J'ai modifié celui du lien pour travailler avec cet exemple.

Modifier: En relisant, il semble que vous ayez une condition pour la fin de la recherche dans endpoint (vous devez être plus clair dans votre question sur ce qui est entré et ce qui est sorti). Vous pouvez ajuster dfs_path(tree,**target**, root) et modifier la condition de terminaison pour ne renvoyer que les bons chemins.

## 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]))

Construire une trame de données à partir des générateurs que nous avons générés

Si vous n'êtes pas très à l'aise avec les générateurs, vous pouvez structurer la traversée DFS afin qu'elle sorte dans une liste. au lieu d'un générateur

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')

Production

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 avril 2018 à 19:34