Mapping graph/relationship based values in a DataFrame in python

user_7616649 0
Viewed 312

I have an input DataFrame in the below format:

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)

Ignored the index for readability,

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

The output I am expecting is shown below. I need to map all related values (be it value1 -> value2 or value2 -> value1) and collect them all to ordered indexes(starting from 1) like below:

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

What I have tried? I did try looping over the rows in input. I'm able to relate if values in a single row are related. But I'm finding it hard to use this logic when the relationships spans across multiple rows and multiple columns(Value1 and Value2)

pandas dataframe python-3.x python
2 Answers

Use convert_matrix.from_pandas_edgelist with connected_components first, then create dictionary for mapping, reshape by DataFrame.melt, map values per groups by Series.map, remove duplicates DataFrame.drop_duplicates and last sorting:

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
user_29010020

Your problem can be very well translated to the following problem: "given the edges of an undirected graph, find out the connected components." For that, there is this simple dfs based answer in geeksforgeeks[1].

Now, I used that and made the necessary changes to get your needed output. I am avoiding pandas dataframe though; as without going through pandas we can solve this problem. Check the code below for solution:

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)

The output of this program is as below: Following are connected components [[1250, 1200, 1300], [1060, 1002, 1000, 1004, 1003], [1100, 1050, 1010]]

The important change I made from the geeks for geeks solution is to create a nodes_dict dictionary which takes the node value and gives out an integer node number. In the graph we basically pass these integer node numbers; and then we again change the connected components back using the node_cc.

Please comment to let me know if any other part of the program needs clarification. Its all basic lists and dictionary, that's why I am not explaining in details. But would love to clarify if needed.
[1]: https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/

user_130458770
Related