appc-dg/appc-dg-shared/appc-dg-dependency-model/src/main/java/org/onap/appc/dg/flowbuilder/impl/ForwardFlowStrategy.java

   1 /*-
   2  * ============LICENSE_START=======================================================
   3  * ONAP : APPC
   4  * ================================================================================
   5  * Copyright (C) 2017-2018 AT&T Intellectual Property. All rights reserved.
   6  * ================================================================================
   7  * Copyright (C) 2017 Amdocs
   8  * =============================================================================
   9  * Licensed under the Apache License, Version 2.0 (the "License");
  10  * you may not use this file except in compliance with the License.
  11  * You may obtain a copy of the License at
  12  *
  13  *      http://www.apache.org/licenses/LICENSE-2.0
  14  *
  15  * Unless required by applicable law or agreed to in writing, software
  16  * distributed under the License is distributed on an "AS IS" BASIS,
  17  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  18  * See the License for the specific language governing permissions and
  19  * limitations under the License.
  20  *
  21  * ============LICENSE_END=========================================================
  22  */
  23
  24 package org.onap.appc.dg.flowbuilder.impl;
  25
  26 import java.util.*;
  27
  28 import org.onap.appc.dg.flowbuilder.exception.InvalidDependencyModelException;
  29 import org.onap.appc.domainmodel.Vnfc;
  30
  31
  32 public class ForwardFlowStrategy extends AbstractFlowStrategy {
  33     @Override
  34     protected List<List<Vnfc>> orderDependencies() throws InvalidDependencyModelException{
  35         ArrayList<List<Vnfc>> arrayList = new ArrayList<>();
  36
  37         Queue<Vnfc> queue1 = new LinkedList();
  38         Set<Vnfc> queue2 = new LinkedHashSet<>();
  39
  40         Set<Vnfc> uniqueElementSet = new HashSet<>();
  41         Set<Vnfc> duplicateElementSet = new HashSet<>();
  42
  43         // identifying independent nodes in queue1
  44         for(int rowIndex=0;rowIndex<graph.getSize();rowIndex++){
  45             Integer sum = 0;
  46             for(int colIndex=0;colIndex<graph.getSize();colIndex++){
  47                 sum+= graph.getDependencyMatrix()[rowIndex][colIndex];
  48             }
  49             if(sum==0){
  50                 Vnfc vnfc = graph.getVertexList().get(rowIndex);
  51                 queue1.add(vnfc);
  52             }
  53         }
  54         if(queue1.isEmpty()){
  55             throw new InvalidDependencyModelException("There seems to be no Root/Independent node for Vnfc dependencies");
  56         }
  57         arrayList.add((List<Vnfc>)queue1);
  58         queue1 = new LinkedList<>(queue1);
  59
  60         boolean flag = true;
  61
  62         while(flag){
  63             // iterating over queue1 and for each node in it finding all dependent nodes and putting them on queue2
  64             while(!queue1.isEmpty()){
  65                 Vnfc listItem = queue1.remove();
  66                 Integer colIndex = graph.getIndex(listItem);
  67                 for(Integer index =0;index<graph.getSize();index++){
  68                     Integer value = graph.getDependencyMatrix()[index][colIndex];
  69                     if(value ==1){
  70                         Vnfc vnfc = graph.getVertexList().get(index);
  71                         queue2.add(vnfc);
  72                     }
  73                 }
  74             }
  75             for(Vnfc vnfc:queue2){
  76                 if(!uniqueElementSet.add(vnfc)){
  77                     duplicateElementSet.add(vnfc);
  78                 }
  79             }
  80             if(queue2.isEmpty()){
  81                 flag= false; // empty queue2 indicates that all leaf nodes have been identified, i.e. stop the iteration
  82             }
  83             else{
  84                 arrayList.add(new ArrayList<Vnfc>(queue2));
  85                 if(arrayList.size()>graph.getSize()){
  86                     // dependency list cannot be larger than total number of nodes
  87                     // if it happens indicates cycle in the dependency
  88                     throw new InvalidDependencyModelException("Cycle detected in the VNFC dependencies");
  89                 }
  90                 queue1.addAll(queue2);
  91                 queue2 = new LinkedHashSet<>();
  92             }
  93         }
  94         // If any node depends on multiple nodes present in different execution sequence,
  95         // its execution should happen on the higher order, removing its presence on lower execution sequence
  96         if(!duplicateElementSet.isEmpty()){
  97             for(Vnfc vnfc:duplicateElementSet){
  98                 boolean firstOccurrence= true;
  99                 for(int i=arrayList.size()-1;i>=0;i--){
 100                     List<Vnfc> list = arrayList.get(i);
 101                     if(list.contains(vnfc)){
 102                         if(firstOccurrence){
 103                             firstOccurrence =false;
 104                             continue;
 105                         }
 106                         else{
 107                             list.remove(vnfc);
 108                         }
 109                     }
 110
 111                 }
 112             }
 113         }
 114         return  arrayList;
 115     }
 116 }