diff tools/myTools/bin/FVS_python3/FVS_localsearch_10_python.py @ 1:7e5c71b2e71f draft default tip

Uploaded

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/tools/myTools/bin/FVS_python3/FVS_localsearch_10_python.py	Wed Dec 22 16:00:34 2021 +0000
@@ -0,0 +1,193 @@
+'''
+This file contains functions used to calculate feedback vertex set for directed graph
+
+The major function is the FVS_local_search(), which calculate maximum sub topological ordering of a graph
+The algorithm is given by "Applying local search to feedback vertex set problem"
+Author of the paper Philippe Galinier, Eunice Lemamou, Mohamed Wassim Bouzidi
+The code mimic the pseudocode given in Page 805 in that paper
+The code is written by Gang Yang, Penn State University
+'''
+
+
+import networkx as nx
+import random
+import math
+import array
+
+
+
+#the following two function calculate the position for the candidate given the existing topological ordering S
+def get_position_minus(candidate_incoming_neighbour, S):
+  '''
+  get_position_minus return position as just after its numbered in-coming neighbours
+  As in the paper, the function return i_minus(v)
+  '''
+  position = 1
+  for x in range(len(S)-1,-1,-1):             #we loop through index from the end as we try to find the largest index of numbered incoming neighbour
+    if S[x] in candidate_incoming_neighbour:
+      position = x+2                          #2 comes from we need to put candidate after the incoming neighbour and also the position count from 1 instead of 0
+      return position
+  return position                             #put the candidate in the first position if there is no numbered incoming neighbour
+
+
+
+def get_position_plus(candidate_outgoing_neighbour, S):
+  '''
+  get_position_plus return position as just before its numbered out-going neighbours
+  As in the paper, the function return i_plus(v)
+  '''
+  position = 1+len(S)
+  for x in range(len(S)):                     #we loop through index from the beginning as we try to find the smallest index of numbered outgoing neighbour
+    if S[x] in candidate_outgoing_neighbour:
+      position = x+1                          #1 comes from the fact position count from 1 instead of 0
+      return position
+  return position                             #put the candidate in the first position if there is no numbered outgoing neighbour
+
+
+
+def FVS_local_search(G_input, T_0, alpha, maxMvt, maxFail, randomseed=None):
+  '''
+  Returns an maximum sub topological ordering of a DiGraph G.
+  FVS is G_input \ the topological ordering
+  A topological ordering of a graph is an ordering of vertices such that
+  the starting point of every arc occurs earlier in the ordering than
+  the endpoint of the art.
+
+  This algorithm is a fast approximation based on simulating annealing(SA) of a noval local search strategy [1]_.
+  The code follows the pseudocode given in Page 805 in that paper.
+
+
+  Parameters
+  ----------
+  G : NetworkX Graph/DiGraph, result for MultiGraph is not tested
+  T_0 : the initial temperature  in SA
+  alpha : the cooling multiplier for temperatue in the geometric cooling regime
+  maxMvt_factor : maxMvt_factor times network size is the number of iterations for the inner loop given a fixed temperatue
+  maxFail : FVS_local_search stops when maxFail number of outloops (temperatue) fail to improve the result
+  randomseed: random seed for generating random numbers
+
+  Returns
+  -------
+  An approximation of the maximum ordering of the given graph as a list.
+
+
+  Notes
+  -----
+  The code is written by Gang Yang, Department of Physics, Penn State University
+
+
+  References
+  ----------
+  ..[1] Galinier, P., Lemamou, E. & Bouzidi, M.W. J Heuristics (2013) 19: 797. doi:10.1007/s10732-013-9224-z
+
+  '''
+  #set a random seed
+  random.seed(randomseed)
+  G=G_input.copy()
+  N= len(G.nodes())           #number of nodes in the graph
+  edges=G.edges()
+
+
+  #Initialization
+  T = T_0                     #set initial temperatue
+  nbFail = 0                  #Outer loop counter to record failure times
+  S = []                      #list to record the ascending ordering
+  S_optimal = []              #list to record the optimal ordering
+
+
+  #calculate parent and child node for each node
+  parent = [{} for i in range(N)]
+  child = [{} for i in range(N)]
+
+  for edge in edges:
+    child[int(edge[0])][int(edge[1])]=None
+    parent[int(edge[1])][int(edge[0])]=None
+
+  #all the nodes that are self_loops
+  self_loops = [edge[0] for edge in edges if edge[0]==edge[1]]
+  print(self_loops)
+  #all the nodes that is not in S
+  unnumbered=[x for x in range(N) if x not in self_loops]
+  N_unnumbered = len(unnumbered)
+  while nbFail< maxFail:
+    nbMvt = 0       #Inner loop counter to record movement times
+    failure = True  #if cardinal of S increase after one inner loop, failure will be set to false
+    while nbMvt < maxMvt:
+      candidate_index = random.randint(0, N_unnumbered-1)
+      candidate = unnumbered[candidate_index]         #random pick a node from all unnumbered node
+      position_type = random.randint(0,1)             #random choose a position type
+      #calculate incoming/outgoing neighbour for the candidate node, store as keys in the dict
+      candidate_incoming_neighbour = parent[candidate]
+      candidate_outgoing_neighbour = child[candidate]
+      #see how to find the position on Page 803 of the paper
+      #position_type=1 means just after incoming neighbours
+      if position_type==1:
+        position = get_position_minus(candidate_incoming_neighbour,S)
+      #position_type=0 means just before outgoint neighbours
+      elif position_type==0:
+        position = get_position_plus(candidate_outgoing_neighbour,S)
+
+      #first, insert the candidate to the given position
+      S_trail = S[:]  #copy the list
+      S_trail.insert(position-1,candidate)
+
+      #second remove all the conflict
+      #break the sequence into two parts: before and after the candidate node and
+      S_trail_head= S_trail[:position-1]
+      S_trail_tail= S_trail[position:]
+      #determine conflict node See page 801
+      if position_type==1:
+        CV_pos=[]    #conflict before the newly inserted node in the topological ordering
+        for x in range(len(S_trail_head)):
+          nodetemp=S_trail_head[x]
+          #print nodetemp,candidate_outgoing_neighbour,nodetemp in candidate_outgoing_neighbour
+          if nodetemp in candidate_outgoing_neighbour:
+            CV_pos.append(nodetemp)
+        conflict=CV_pos   #there won't be conflict after the inserted node as the node inserted after its incoming neighbour
+      elif position_type==0:
+        CV_neg=[]    #conflict after the newly inserted node in the topological ordering
+        for x in range(len(S_trail_tail)):
+          nodetemp=S_trail_tail[x]
+          #print nodetemp,candidate_incoming_neighbour,nodetemp in candidate_incoming_neighbour
+          if nodetemp in candidate_incoming_neighbour:
+            CV_neg.append(nodetemp)
+        conflict=CV_neg   #there won't be conflict before the inserted node as the node inserted before its outgoing neighbour
+      #finally remove the conflict node
+      N_conflict=len(conflict)
+      if N_conflict>0:
+        for i in range(N_conflict):
+          S_trail.remove(conflict[i])
+
+      #third, evaluate the move
+      #delta_move=-len(S_trail)+len(S)
+      delta_move=N_conflict-1
+      #accept all the move that is not harmful, otherwise use metrospolis algorithm
+      if delta_move<=0 or math.exp(-delta_move/float(T))>random.random():
+        S = S_trail[:]
+        #update unnumbered nodes
+        unnumbered.remove(candidate)   #remove the node just inserted
+        if N_conflict>0:               #add all the conflict node just removed
+          for i in range(N_conflict):
+            unnumbered.append(conflict[i])
+        N_unnumbered+=delta_move
+        nbMvt = nbMvt+1
+        #update S_optimal only when there is increase in cardinal of the sequence
+        if len(S)>len(S_optimal):
+          S_optimal = S[:]
+          failure = False
+        if N_unnumbered==0:
+          return S_optimal
+
+    #Increment the failure times if no progress in size of the sequence
+    if failure==True:
+      nbFail+=1
+    else:    #otherwise reset the num of failure times
+      nbFail=0
+    #shrink the temperatue by factor alpha
+    T=T*alpha
+    #print T
+    #print nbFail
+  return S_optimal
+
+
+