python: Depth-First Search (6)

Abstract: Access all accessible nodes in a network.

























  A  B  C  D  E
A -1  1  1  0  1
B  1 -1  0  1  0
C  1  0 -1  0  1
D  0  1  0 -1  0
E  1  0  1  0 -1
Order of visiting all accessible nodes: ['A', 'D', 'B', 'E', 'C']


The script:
# -*- coding: utf-8 -*-
"""
Created on Tue Jul  7 15:11:31 2015

@author: yuan
"""
import numpy as np
import pandas as pd
#arrange network

       
#class:       
class network_pd:
    def __init__(self, connects):
        self.connects=np.array(connects)
        self.edges_num=len(self.connects)
        self.nodes=np.unique(np.array(self.connects))
        self.nodes_num=len(self.nodes)
   
    def read_connects(self):
        net=np.zeros((self.nodes_num,self.nodes_num))
        net=pd.DataFrame(net, columns=self.nodes, index=self.nodes)
        #print net
        #get 2-D marix to store network
        for row in range(self.edges_num):
            nodeA=self.connects[row][0]
            nodeB=self.connects[row][1]
            net[nodeA][nodeB]=1
            net[nodeB][nodeA]=1
            net[nodeA][nodeA]=-1#remove self-connection
            net[nodeB][nodeB]=-1
        #print net
        return net

#class:
class arrange_network:
    def __init__(self, net):
      self.net=pd.DataFrame(net)
      self.nodes=list(self.net.columns)
      self.nodes_num=len(self.net.columns)
      self.visited=[]
      print self.net

   
    def DFS(self, a_node, ways):
        if len(self.visited)==self.nodes_num:
            return
        #
        for b_node in self.nodes:
            if self.net[a_node][b_node]==1 and ways[a_node][b_node]==1 :
                ways[a_node][b_node]=0
                ways[b_node][a_node]=0
                #recursive
                self.DFS(b_node, ways)
                if b_node not in self.visited:
                    self.visited.append(b_node)
        return
       
    def arrange_nodes(self,start_node):
        ways=self.net
        self.visited.append(start_node)
        #recursive using DFS
        self.DFS(start_node, ways)
        print "Order of visiting all accessible nodes:", self.visited
       
#main program
connects=[['A','C'], ['A','B'], ['A','E'], ['C','E'], ['B','D']]


#store network into dat frame using panda
net=network_pd(connects)
netdf=net.read_connects()

#arrange all the nodes of the network
go=arrange_network(netdf)
start_node='A'
go.arrange_nodes(start_node)