gerrit.onap Code Review - appc.git/blob

   1 /*-
   2  * ============LICENSE_START=======================================================
   3  * APPC
   4  * ================================================================================
   5  * Copyright (C) 2017 AT&T Intellectual Property. All rights reserved.
   6  * Copyright (C) 2017 Amdocs
   7  * ================================================================================
   8  * Licensed under the Apache License, Version 2.0 (the "License");
   9  * you may not use this file except in compliance with the License.
  10  * You may obtain a copy of the License at
  11  *
  12  *      http://www.apache.org/licenses/LICENSE-2.0
  13  *
  14  * Unless required by applicable law or agreed to in writing, software
  15  * distributed under the License is distributed on an "AS IS" BASIS,
  16  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  17  * See the License for the specific language governing permissions and
  18  * limitations under the License.
  19  * ============LICENSE_END=========================================================
  20  * ECOMP is a trademark and service mark of AT&T Intellectual Property.
  21  */
  22
  23 package org.openecomp.appc.dg.flowbuilder.impl;
  24
  25 import java.util.*;
  26
  27 import org.openecomp.appc.dg.flowbuilder.exception.InvalidDependencyModel;
  28 import org.openecomp.appc.domainmodel.Vnfc;
  29
  30
  31 public class ReverseFlowStrategy extends AbstractFlowStrategy {
  32
  33     @Override
  34     protected List<List<Vnfc>> orderDependencies() {
  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 colIndex=0;colIndex<graph.getSize();colIndex++){
  45             Integer sum = 0;
  46             for(int rowIndex=0;rowIndex<graph.getSize();rowIndex++){
  47                 sum+= graph.getDependencyMatrix()[rowIndex][colIndex];
  48             }
  49             if(sum==0){
  50                 Vnfc vnfc = graph.getVertexList().get(colIndex);
  51                 queue1.add(vnfc);
  52             }
  53         }
  54         if(queue1.isEmpty()){
  55             throw new InvalidDependencyModel("There seems to be no leaf 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 rowIndex = graph.getIndex(listItem);
  67                 for(Integer index =0;index<graph.getSize();index++){
  68                     Integer value = graph.getDependencyMatrix()[rowIndex][index];
  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 InvalidDependencyModel("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=0;i<arrayList.size();i++){
 100                     List<Vnfc> list = arrayList.get(i);
 101                     if(list.contains(vnfc)){
 102                         if(firstOccurrence){
 103                             firstOccurrence =false;
 104                             list.remove(vnfc);
 105                         }
 106                         else{
 107                             continue;
 108                         }
 109                     }
 110
 111                 }
 112             }
 113         }
 114         return  arrayList;
 115     }
 116 }