Кадр данных со столбцами FROM и TO. Неупорядоченный, получите правильные комбинации
df = pd.DataFrame({
'from': ['Start', '21', '73', 'Start', '55', '1', '2', '3'],
'to': ['21', '73', '55', '1', '54', '2', '3', '4']
})
желаемый результат
[['Start', '21', '73', '55', '54'], ['Start', '1', '2', '3', '4']]
[РЕДАКТИРОВАТЬ]
Итак, вы начинаете с «Начало» в столбце «От» и находите «21» в столбце «До» этой строки. Теперь вам нужно найти «21» в столбце «от» и перейти к «73». Затем повторяйте шаги, пока в поле «from» ничего не будет найдено, что указывает на то, что соединение установлено.
Связи ацикличны и неразветвлены.
[КОНЕЦ РЕДАКТИРОВАНИЯ]
строки не обязательно должны быть в правильном порядке, как в случае 55, 54.
Вам нужен список списков в качестве вывода?
@mozway да, список всех соединений в фрейме данных. В примере их всего два.
Понятно, тогда можно считать это проблемой графа и использовать networkx (см. ниже)
@PandaKim, что непонятно? вы начинаете с «Начала», затем получаете 21 в «до», затем возвращаетесь к столбцу «от», находите 21 и получаете соответствующее 73 и т. д. то же самое для другого «Начала».
@Пол, возможно, ты захочешь разобрать свой полный пример, чтобы продемонстрировать логику (как я это сделал в комментарии выше).
@mozway Это также имеет смысл, поскольку это дает общий результат.
Ответы 1
Это проблема с графами, для ее решения вы можете использовать networkx.
Сначала дедуплицируйте начало, затем создайте ориентированный граф, получите слабо_подключенные_компоненты , затем dag_longest_path :
import networkx as nx
# deduplicate the Start
m = df['from'].eq('Start')
from_ = df['from'].mask(m, 'Start'+m.cumsum().astype(str))
# ['Start1', '21', '73', 'Start2', '55', '1', '2', '3']
# create a graph
G = nx.from_edgelist(zip(from_, df['to']),
create_using=nx.DiGraph)
# get isolated paths
out = [nx.dag_longest_path(G.subgraph(c))
for c in nx.weakly_connected_components(G)]
Выход:
[['Start1', '21', '73', '55', '54'], ['Start2', '1', '2', '3', '4']]
График:
Вы также можете использовать функцию Python, чтобы вручную следовать по пути для каждого запуска:
def find_path(df, frm='from', to='to'):
# create a Series with from as index, to as values
s = df.set_index(frm)[to]
out = []
# for each Start, follow the path
for val in s[s.index=='Start']:
out.append(['Start', val])
while (val := s.get(val)) is not None:
out[-1].append(val)
return out
out = find_path(df)
# [['Start', '21', '73', '55', '54'], ['Start', '1', '2', '3', '4']]
Примечание. это предполагает, что графы нециклические и неразветвленные. В этом случае вы можете обнаружить циклы, сохранив набор видимых узлов. Ветви также можно обрабатывать, но необходимы более подробные сведения об ожидаемой логике.
@ouroboros1 это правда, но я предположил здесь ациклический неразветвленный граф (как показано в примере). С помощью первого подхода можно обрабатывать разветвленные графы, но это похоже на другой вопрос.
Под «неупорядоченным» я предполагаю, что OP имел в виду, что выходные данные не обязательно содержат узлы в числовом порядке, но они должны быть упорядочены по пути.
Вы правы, это должно быть четко указано. @Пол, не могли бы вы подтвердить в вопросе, что граф ациклический и неразветвленный?
Этот вопрос нуждается в более ясной логике. Будет множество случаев неупорядоченности, и, пожалуйста, приложите логику того, как с этим следует обращаться. Было бы неплохо привести и другой пример.