본문으로 바로가기

A modified Label Correcting Algorithm (FIFO , Deque) with Python

Label correcting algorithm은 single source shortest path problem 입니다. Label correcting algorithm 은 dijkstra algorithm과 달리 cost 가 음수일 때도 iteration 을 통해 노드간 최소 거리 (cost)를 구할 수 있습니다. negative cost가 있는 부분에서 cycle 이 발생한다면 반복이 진행될 때 unbounded로 낮아지기 때문에 graph의 negative cost가 있는 부분에서 cycle이 발생하면 안됩니다.

 

기존 Label Correcting Algorithm은 반복 회수가 n-1 회( n = number of nodes ) 진행되나, modified label correcting algorithm은 LIST를 이용하여 반복 회수를 줄여주게 됩니다.

 

1. Graph 및 cost 생성

  • cost는 모두 정수
    • -10 <= negative cost < 0 , 1<= positive cost < 20 
  • cycle 발생 X
  • arcs = ( i node, j node, cost from i node to j node )
# cycle check fuction : DFS 통해 확인 
def cycle_check( arcs, stack, edge ) : 
    if edge in stack :
        global IsCycle
        IsCycle = True
        return True
    
    stack.append( edge )
    successive_edges = [ arc for arc in arcs if arc[0] == edge[1] ]
    
    for edge in successive_edges : 
        cycle_check( arcs, stack, edge )
    stack.pop()
    
    return IsCycle
def get_node_arc_set( total_num_arcs, total_num_nodes, negative_ratio , negative_cost_range, positive_cost_range ) :
    num_arcs = 0 
    arcs = []

    negative_cost = np.random.choice( negative_cost_range , int( total_num_arcs * negative_ratio) )
    positive_cost = np.random.choice( positive_cost_range , int( total_num_arcs * (1- negative_ratio))  )
    costs = np.concatenate( [negative_cost,positive_cost] )
    np.random.shuffle(costs)


    while num_arcs != total_num_arcs : 
        i, j = np.random.choice( np.arange(0, total_num_nodes ) , 2 , replace = False) # 랜덤으로 서로 다른 두 노드 i,j 선택
        if (i,j) in list(map( lambda x : x[:2] , arcs ) ) : # 이미 존재하는 arc 뽑았을 경우 continue
            continue

        temp_arcs = copy.deepcopy(arcs) 
        temp_arcs.append( (i,j) )
 
        global IsCycle 
        IsCycle = False
        IsCycle = cycle_check( temp_arcs, [] , (i,j) ) # 전역 변수 통해 Cycle 이 있는지 아닌지 확인

        
        if IsCycle == True: 
            continue   
        else : # (i,j) 를 arcs에 추가했을 때 Cycle이 발생하지 않으므로 arcs 에 (i,j)를 추가 ( arcs := temp_arcs ) 
            arcs.append( (i,j, costs[num_arcs]) )
            num_arcs += 1  
            
    return arcs

 

2. Generic modified label correcting algorithm

LIST is the list of all arcs that might violate their optimality conditions( = d(j) > d(i) + c_ij ).

LIST에 arc를 어떻게 담을지에 따라 구체적인 구현이 다른데, 크게 FIFO ( First In First Out ) 과 Dequeue ( Double-ended Queue ) 를 통해 구현 합니다. 다음은 FIFO 와 Dequeue를 통한 구현을 보도록 하겠습니다.

 

3. FIFO

LIST 로 Queue를 이용하고 담는 방식으로 First In First Out 을 사용하는 방식입니다. 수도 코드는 다음과 같습니다.

 

Code 는 다음과 같습니다.

def init_FIFO(s, total_num_nodes ) :
    inf = 99999
    d    = [ inf if idx != s else 0 for idx in range(total_num_nodes) ]
    pred = [ inf if idx != s else 0 for idx in range(total_num_nodes) ]
    q = [s]
    return q, d, pred

def MLC_FIFO( q, d, pred, arcs ):
    while q != [] : 
        i = q.pop(0)
        i_arcs = [ arc for arc in arcs if arc[0] == i]

        for arc in i_arcs :
            j = arc[1] ; cost = arc[2]
            if d[j] > d[i] + cost : 
                d[j] = d[i] + cost
                pred[j] = i
                if j not in q : 
                    q.append(j)   
    return d, pred

 

4. Dequeue

LIST로 Dequeue를 사용하고 j node가 LIST에 없을 때 j node가 예전에 LIST에 존재하지 않았으면 j를 LIST 맨 뒤에 j node를 추가하고 j node가 예전에 존재했었으면 LIST 맨 처음에 j node를 추가 합니다. 수도 코드는 다음과 같습니다.

 

코드는 다음과 같습니다.

def init_Deque(s, total_num_nodes):
    inf = 99999
    d    = [ inf if idx != s else 0 for idx in range(total_num_nodes) ]
    pred = [ inf if idx != s else 0 for idx in range(total_num_nodes) ]
    visit= [ 0   if idx != s else 1 for idx in range(total_num_nodes) ]
    q = deque([s])
    return q,d, pred ,visit 

def MLC_Deque(q,d, pred, visit,  arcs):
    while q != deque() : 
        i = q.popleft()
        i_arcs = [ arc for arc in arcs if arc[0] == i]

        for arc in i_arcs : 
            j = arc[1] ; cost = arc[2]
            if d[j] > d[i] + cost : 
                d[j] = d[i] + cost
                pred[j] = i
                if j not in q :
                    if visit[j] == 0 :
                        q.append(j)
                        visit[j] = 1
                    else:
                        q.appendleft(j)
    return d, pred