Блог

У меня есть входной фрейм данных в приведенном ниже формате:

 input_data = [[1000, 1002], [1002, 1003], [1004, 1000],[1010,1050],[1060,1002],[1050,1100],[1200,1250],[1300,1200]]
input_df = pd.DataFrame(input_data, columns = ['Value1', 'Value2']) 
print(input_df)
 

Игнорируется индекс для удобства чтения,

 Value1  Value2
1000    1002
1002    1003
1004    1000
1010    1050
1060    1002
1050    1100
1200    1250
1300    1200
 

Результат, который я ожидаю, показан ниже. Мне нужно сопоставить все связанные значения (будь то значение1 -> значение2 или значение2 -> значение1) и собрать их все в упорядоченные индексы (начиная с 1), как показано ниже:

 Index Value
1   1000
1   1002
1   1003
1   1004
1   1060
2   1010
2   1050
2   1100
3   1200
3   1250
3   1300
3   1200
 

Что я пробовал?
Я пробовал перебирать строки во входных данных. Я могу связать, связаны ли значения в одной строке. Но мне трудно использовать эту логику, когда отношения охватывают несколько строк и несколько столбцов (Value1 и Value2)

convert_matrix.from_pandas_edgelist connected_components Сначала используйте с, затем создайте словарь для сопоставления, измените форму по DataFrame.melt , сопоставьте значения по группам по Series.map , удалите дубликаты DataFrame.drop_duplicates и последнюю сортировку:

 import networkx as nx

# Create the graph from the dataframe
g = nx.Graph()
g = nx.from_pandas_edgelist(input_df,'Value1','Value2')

connected_components = nx.connected_components(g)

# Find the component id of the nodes
node2id = {}
for cid, component in enumerate(connected_components):
    for node in component:
        node2id[node] = cid

df = input_df.melt()
df['g'] = df['value'].map(node2id)
df = df.drop_duplicates(['value','g']).sort_values(['g','value'])
print (df)
   variable  value  g
0    Value1   1000  0
1    Value1   1002  0
9    Value2   1003  0
2    Value1   1004  0
4    Value1   1060  0
3    Value1   1010  1
5    Value1   1050  1
13   Value2   1100  1
6    Value1   1200  2
14   Value2   1250  2
7    Value1   1300  2
 

Ваша проблема может быть очень хорошо переведена в следующую проблему: «учитывая ребра неориентированного графа, найдите связанные компоненты». Для этого есть этот простой ответ на основе dfs в geeksforgeeks [1].

Теперь я использовал это и внес необходимые изменения, чтобы получить необходимый результат. Однако я избегаю фрейма данных pandas; поскольку, не проходя через pandas, мы можем решить эту проблему. Проверьте приведенный ниже код для решения:

 input_data = [[1000, 1002], [1002, 1003], [1004, 1000],[1010,1050], [1060,1002],[1050,1100],[1200,1250],[1300,1200]]

class Graph:
    def __init__(self, V):
        self.V = V
        self.adj = [[] for i in range(V)]
def DFSUtil(self, temp, v, visited):

    # Mark the current vertex as visited
    visited[v] = True
    # Store the vertex to list
    temp.append(v)
    # Repeat for all vertices adjacent
    # to this vertex v
    for i in self.adj[v]:
        if visited[i] == False:
            # Update the list
            temp = self.DFSUtil(temp, i, visited)
    return temp
# method to add an undirected edge
def addEdge(self, v, w):
    self.adj[v].append(w)
    self.adj[w].append(v)
# Method to retrieve connected components
# in an undirected graph
def connectedComponents(self):
    visited = []
    cc = []
    for i in range(self.V):
        visited.append(False)
    for v in range(self.V):
        if visited[v] == False:
            temp = []
            cc.append(self.DFSUtil(temp, v, visited))
    return cc
nodes = []
for tupl in input_data:
    nodes = nodes   tupl
nodes = list(set(nodes))
node_dict = {}
for i in range(len(nodes)):
    node_dict[nodes[i]] = i

g = Graph(len(nodes))
for tupl in input_data:
    g.addEdge(node_dict[tupl[0]],node_dict[tupl[1]])

cc = g.connectedComponents()
node_cc = []
for lis in cc:
    node_cc.append([nodes[elem] for elem in lis])

print("Following are connected components")
print(node_cc)
 

Результат этой программы выглядит следующим образом:
Ниже приведены связанные компоненты
[[1250, 1200, 1300], [1060, 1002, 1000, 1004, 1003], [1100, 1050, 1010]]

Важным изменением, которое я внес в решение geeks for geeks, является создание словаря nodes_dict, который принимает значение узла и выдает целое число узлов. номер узла. На графике мы в основном передаем эти целочисленные номера узлов; а затем мы снова меняем подключенные компоненты обратно, используя node_cc .

Пожалуйста, прокомментируйте, чтобы сообщить мне, если какая-либо другая часть программы нуждается в уточнении. Это все основные списки и словарь, поэтому я не объясняю подробно. Но хотелось бы уточнить, если это необходимо.
[1]: https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph /