verigraph/src/it/polito/verigraph/service/VerificationService.java

   1 /*******************************************************************************
   2  * Copyright (c) 2017 Politecnico di Torino and others.
   3  *
   4  * All rights reserved. This program and the accompanying materials
   5  * are made available under the terms of the Apache License, Version 2.0
   6  * which accompanies this distribution, and is available at
   7  * http://www.apache.org/licenses/LICENSE-2.0
   8  *******************************************************************************/
   9 package it.polito.verigraph.service;
  10
  11 import java.io.IOException;
  12 import java.util.Date;
  13 import java.util.ArrayList;
  14 import java.util.Calendar;
  15 import java.util.HashMap;
  16 import java.util.List;
  17 import java.util.Map;
  18 import java.util.logging.Logger;
  19 import java.util.regex.Matcher;
  20 import java.util.regex.Pattern;
  21 import java.util.stream.Collectors;
  22 import javax.xml.bind.JAXBException;
  23 import com.fasterxml.jackson.core.JsonParseException;
  24 import com.fasterxml.jackson.databind.JsonMappingException;
  25 import com.microsoft.z3.*;
  26 import it.polito.neo4j.exceptions.MyInvalidDirectionException;
  27 import it.polito.neo4j.jaxb.Paths;
  28 import it.polito.neo4j.manager.Neo4jDBManager;
  29 import it.polito.neo4j.manager.Neo4jLibrary;
  30 import it.polito.neo4j.translator.*;
  31 import it.polito.verigraph.exception.BadRequestException;
  32 import it.polito.verigraph.exception.DataNotFoundException;
  33 import it.polito.verigraph.exception.ForbiddenException;
  34 import it.polito.verigraph.model.Graph;
  35 import it.polito.verigraph.model.Node;
  36 import it.polito.verigraph.model.Test;
  37 import it.polito.verigraph.model.Verification;
  38 import it.polito.verigraph.resources.beans.VerificationBean;
  39 import it.polito.verigraph.solver.GeneratorSolver;
  40 import it.polito.verigraph.solver.Scenario;
  41
  42 public class VerificationService {
  43
  44     private Neo4jDBManager manager=new Neo4jDBManager();
  45     //private final static Logger LOGGER = Logger.getLogger(VerigraphLogger.class.getName());
  46     public static VerigraphLogger vlogger = VerigraphLogger.getVerigraphlogger();
  47
  48     public VerificationService() {}
  49
  50     private Paths getPaths(Graph graph, Node sourceNode, Node destinationNode) throws MyInvalidDirectionException {
  51
  52         String source = sourceNode.getName();
  53         String destination = destinationNode.getName();
  54         Paths paths;
  55         paths=manager.getPath(graph.getId(), source, destination, "outgoing");
  56         return paths;
  57     }
  58
  59     private List<List<String>> sanitizePaths(Paths paths) {
  60         List<List<String>> sanitizedPaths = new ArrayList<List<String>>();
  61         for (String path : paths.getPath()) {
  62             List<String> newPath = extractPath(path);
  63             sanitizedPaths.add(newPath);
  64         }
  65         return sanitizedPaths;
  66     }
  67
  68     private List<String> extractPath(String path) {
  69         List<String> newPath = new ArrayList<String>();
  70         // find all nodes, i.e. all names between parentheses
  71         Matcher m = Pattern.compile("\\(([^)]+)\\)").matcher(path);
  72         while (m.find()) {
  73             String node = m.group(1);
  74             newPath.add(node);
  75         }
  76         return newPath;
  77     }
  78
  79     private void printListsOfStrings(String message, List<List<String>> lists) {
  80         vlogger.logger.info(message);
  81         for (List<String> element : lists) {
  82             StringBuilder paths= new StringBuilder();
  83             for(String s : element){
  84                 paths.append(s+" ");
  85             }
  86             vlogger.logger.info(paths.toString());
  87             //System.out.println(element);
  88         }
  89     }
  90
  91     public Verification verify(long graphId, VerificationBean verificationBean) throws MyInvalidDirectionException, JsonParseException, JsonMappingException, JAXBException, IOException {
  92         if (graphId < 0) {
  93             throw new ForbiddenException("Illegal graph id: " + graphId);
  94         }
  95         GraphService graphService = new GraphService();
  96         Graph graph = graphService.getGraph(graphId);
  97         if (graph == null) {
  98             throw new DataNotFoundException("Graph with id " + graphId + " not found");
  99         }
 100         String source = verificationBean.getSource();
 101         String destination = verificationBean.getDestination();
 102         String type = verificationBean.getType();
 103         if (source == null || source.equals("")) {
 104             throw new BadRequestException("Please specify the 'source' parameter in your request");
 105         }
 106         if (destination == null || destination.equals("")) {
 107             throw new BadRequestException("Please specify the 'destination' parameter in your request");
 108         }
 109         if (type == null || type.equals("")) {
 110             throw new BadRequestException("Please specify the 'type' parameter in your request");
 111         }
 112
 113         Node sourceNode = graph.searchNodeByName(verificationBean.getSource());
 114         Node destinationNode = graph.searchNodeByName(verificationBean.getDestination());
 115
 116         if (sourceNode == null) {
 117             throw new BadRequestException("The 'source' parameter '" + source + "' is not valid, please insert the name of an existing node");
 118         }
 119         if (destinationNode == null) {
 120             throw new BadRequestException("The 'destination' parameter '" + destination + "' is not valid, please insert the name of an existing node");
 121         }
 122         if ((!type.equals("reachability")) && (!type.equals("isolation")) && (!type.equals("traversal"))) {
 123             throw new BadRequestException("The 'type' parameter '"+ type
 124                     + "' is not valid: valid types are: 'reachability', 'isolation' and 'traversal'");
 125         }
 126
 127         Verification v = null;
 128         String middlebox;
 129         Node middleboxNode;
 130         switch (type) {
 131         case "reachability":
 132             v = reachabilityVerification(graph, sourceNode, destinationNode);
 133             break;
 134         case "isolation":
 135             middlebox = verificationBean.getMiddlebox();
 136             if (middlebox == null || middlebox.equals("")) {
 137                 throw new BadRequestException("Please specify the 'middlebox' parameter in your request");
 138             }
 139
 140             middleboxNode = graph.searchNodeByName(middlebox);
 141             if (middleboxNode == null) {
 142                 throw new BadRequestException("The 'middlebox' parameter '" + middlebox + "' is not valid, please insert the name of an existing node");
 143             }
 144             if (middleboxNode.getFunctional_type().equals("endpoint")) {
 145                 throw new BadRequestException("'"+ middlebox
 146                         + "' is of type 'endpoint', please choose a valid middlebox");
 147             }
 148             v = isolationVerification(graph, sourceNode, destinationNode, middleboxNode);
 149             break;
 150         case "traversal":
 151             middlebox = verificationBean.getMiddlebox();
 152             if (middlebox == null || middlebox.equals("")) {
 153                 throw new BadRequestException("Please specify the 'middlebox' parameter in your request");
 154             }
 155
 156             middleboxNode = graph.searchNodeByName(middlebox);
 157             if (middleboxNode == null) {
 158                 throw new BadRequestException("The 'middlebox' parameter '" + middlebox + "' is not valid, please insert the name of an existing node");
 159             }
 160             if (middleboxNode.getFunctional_type().equals("endpoint")) {
 161                 throw new BadRequestException("'"+ middlebox
 162                         + "' is of type 'endpoint', please choose a valid middlebox");
 163             }
 164             v = traversalVerification(graph, sourceNode, destinationNode, middleboxNode);
 165             break;
 166         default:
 167             break;
 168         }
 169         return v;
 170     }
 171
 172     private Verification isolationVerification(Graph graph, Node sourceNode, Node destinationNode, Node middleboxNode) throws MyInvalidDirectionException {
 173         Long time_isolation=(long) 0;
 174         Calendar cal_isolation = Calendar.getInstance();
 175         Date start_time_isolation = cal_isolation.getTime();
 176         Paths paths = getPaths(graph, sourceNode, destinationNode);
 177         if (paths.getPath().size() == 0) {
 178             return new Verification("UNSAT",
 179                     "There are no available paths between '"+ sourceNode.getName() + "' and '"
 180                             + destinationNode.getName() + "'");
 181         }
 182
 183         List<List<String>> sanitizedPaths = sanitizePaths(paths);
 184         List<Test> tests = extractTestsFromPaths(graph, sanitizedPaths, "UNKNWON");
 185
 186         //printListsOfStrings("sanitizedPaths", sanitizedPaths);
 187
 188         if (sanitizedPaths.isEmpty()) {
 189             return new Verification("UNSAT",
 190                     "There are no available paths between '"+ sourceNode.getName() + "' and '"
 191                             + destinationNode.getName() + "'");
 192         }
 193         extractPathsWithoutMiddlebox(sanitizedPaths, middleboxNode.getName());
 194
 195         if (sanitizedPaths.isEmpty()) {
 196             return new Verification("UNSAT",
 197                     tests,
 198                     "There are no available paths between '"+ sourceNode.getName() + "' and '"
 199                             + destinationNode.getName() + "' which no traverse middlebox '"
 200                             + middleboxNode.getName() + "'. See below all the available paths.");
 201         }
 202
 203         //printListsOfStrings("Paths with middlebox '" + middleboxNode.getName() + "'", sanitizedPaths);
 204
 205         Map<Integer, GeneratorSolver> scenarios=createScenarios(sanitizedPaths, graph);
 206
 207         tests = run(graph, scenarios, sourceNode.getName(), destinationNode.getName());
 208         Verification isolation=evaluateIsolationResults(tests, sourceNode.getName(),
 209                 destinationNode.getName(),
 210                 middleboxNode.getName());
 211         Calendar cal_isolation_stop = Calendar.getInstance();
 212         time_isolation = time_isolation +(cal_isolation_stop.getTime().getTime() - start_time_isolation.getTime());
 213         vlogger.logger.info("Time to check reachability policy: " + time_isolation);
 214         //System.out.println("Time to check reachability policy: " + time_isolation);
 215         return isolation;
 216     }
 217
 218     private List<Test> extractTestsFromPaths(Graph graph, List<List<String>> paths, String result) {
 219         List<Test> tests = new ArrayList<Test>();
 220         for (List<String> path : paths) {
 221             List<Node> nodes = new ArrayList<Node>();
 222             for (String nodeName : path) {
 223                 nodes.add(graph.searchNodeByName(nodeName));
 224             }
 225             tests.add(new Test(nodes, result));
 226         }
 227         return tests;
 228     }
 229
 230     private Verification evaluateIsolationResults(List<Test> tests, String source, String destination,
 231             String middlebox) {
 232         Verification v = new Verification();
 233         boolean isSat = false;
 234         int unsatCounter = 0;
 235         for (Test t : tests) {
 236             v.getTests().add(t);
 237             if (t.getResult().equals("SAT")) {
 238                 isSat = true;
 239             }
 240             else if (t.getResult().equals("UNKNOWN")) {
 241                 v.setResult("UNKNOWN");
 242                 v.setComment("Isolation property with source '"+ source + "', destination '" + destination
 243                         + "' and middlebox '" + middlebox + "' is UNKNOWN because although '" + source
 244                         + "' cannot reach '" + middlebox + "' in any path from '" + source + "' to '"
 245                         + destination + "' which traverses middlebox '" + middlebox
 246                         + "' at least one reachability test between '" + source + "' and '" + middlebox
 247                         + "' returned UNKNOWN (see below all the paths that have been checked)");
 248             }
 249             else if (t.getResult().equals("UNSAT")) {
 250                 unsatCounter++;
 251             }
 252         }
 253         if (isSat) {
 254             v.setResult("SAT");
 255             v.setComment("Isolation property with source '"+ source + "', destination '" + destination
 256                     + "' and middlebox '" + middlebox + "' is SATISFIED because reachability between '" + source
 257                     + "' and '" + middlebox + "' is UNSATISFIED in all paths between '" + source + "' and '"
 258                     + destination + "' which traverse middlebox '" + middlebox
 259                     + "' (see below all the paths that have been checked)");
 260
 261         }
 262         else if (unsatCounter == tests.size()) {
 263             v.setResult("UNSAT");
 264             v.setComment("Isolation property with source '"+ source + "', destination '" + destination
 265                     + "' and middlebox '" + middlebox + "' is UNSATISFIED because reachability between '"
 266                     + source + "' and '" + middlebox + "' is SATISFIED in at least one path between '" + source
 267                     + "' and '" + destination + "' which traverses middlebox '" + middlebox
 268                     + "' (see below all the paths that have been checked)");
 269         }
 270         return v;
 271     }
 272
 273     private void extractPathsWithMiddlebox(List<List<String>> sanitizedPaths, String middleboxName) {
 274         List<List<String>> pathsToBeRemoved = new ArrayList<List<String>>();
 275         for (List<String> path : sanitizedPaths) {
 276             boolean middleboxFound = false;
 277             for (String node : path) {
 278                 if (node.equals(middleboxName)) {
 279                     middleboxFound = true;
 280                     break;
 281                 }
 282             }
 283             if (!middleboxFound) {
 284                 pathsToBeRemoved.add(path);
 285             }
 286         }
 287         for (List<String> path : pathsToBeRemoved) {
 288             sanitizedPaths.remove(path);
 289         }
 290
 291     }
 292
 293     private void extractPathsWithoutMiddlebox(List<List<String>> sanitizedPaths, String middleboxName) {
 294         List<List<String>> pathsToBeRemoved = new ArrayList<List<String>>();
 295         for (List<String> path : sanitizedPaths) {
 296             boolean middleboxFound = false;
 297             for (String node : path) {
 298                 if (node.equals(middleboxName)) {
 299                     middleboxFound = true;
 300                     break;
 301                 }
 302             }
 303             if (middleboxFound) {
 304                 pathsToBeRemoved.add(path);
 305             }
 306         }
 307         for (List<String> path : pathsToBeRemoved) {
 308             sanitizedPaths.remove(path);
 309         }
 310     }
 311
 312     private Verification traversalVerification(Graph graph, Node sourceNode, Node destinationNode, Node middleboxNode) throws MyInvalidDirectionException {
 313         Long time_traversal=(long) 0;
 314         Calendar cal_traversal = Calendar.getInstance();
 315         Date start_time_traversal = cal_traversal.getTime();
 316         Paths paths = getPaths(graph, sourceNode, destinationNode);
 317         if (paths.getPath().size() == 0) {
 318             return new Verification("UNSAT",
 319                     "There are no available paths between '"+ sourceNode.getName() + "' and '"
 320                             + destinationNode.getName() + "'");
 321         }
 322
 323         List<List<String>> pathsBetweenSourceAndDestination = sanitizePaths(paths);
 324
 325         //printListsOfStrings("Paths", pathsBetweenSourceAndDestination);
 326
 327         if (pathsBetweenSourceAndDestination.isEmpty()) {
 328             return new Verification("UNSAT",
 329                     "There are no available paths between '"+ sourceNode.getName() + "' and '"
 330                             + destinationNode.getName() + "'");
 331         }
 332
 333         List<Test> tests = extractTestsFromPaths(graph, pathsBetweenSourceAndDestination, "UNKNOWN");
 334
 335         List<List<String>> pathsWithMiddlebox = new ArrayList<List<String>>();
 336         for (List<String> path : pathsBetweenSourceAndDestination) {
 337             pathsWithMiddlebox.add(path);
 338         }
 339
 340         extractPathsWithMiddlebox(pathsWithMiddlebox, middleboxNode.getName());
 341
 342         if (pathsWithMiddlebox.isEmpty()) {
 343             return new Verification("UNSAT",
 344                     tests,
 345                     "There are no paths between '"+ sourceNode.getName() + "' and '"
 346                             + destinationNode.getName() + "' which traverse middlebox '"
 347                             + middleboxNode.getName() + "'. See below all the available paths");
 348         }
 349
 350         //printListsOfStrings("Paths with middlebox '" + middleboxNode.getName() + "'", pathsWithMiddlebox);
 351
 352         Map<Integer, GeneratorSolver> scenarios=createScenarios(pathsWithMiddlebox, graph);
 353
 354         tests = run(graph, scenarios, sourceNode.getName(), destinationNode.getName());
 355
 356         for (Test t : tests) {
 357             if (t.getResult().equals("UNSAT")) {
 358                 return new Verification("UNSAT",
 359                         tests,
 360                         "There is at least a path between '"+ sourceNode.getName() + "' and '"
 361                                 + destinationNode.getName() + "' traversing middlebox '"
 362                                 + middleboxNode.getName() + "' where '" + sourceNode.getName()
 363                                 + "' cannot reach '" + destinationNode.getName()
 364                                 + "'. See below the paths that have been checked");
 365             }
 366             if (t.getResult().equals("UNKNOWN")) {
 367                 return new Verification("UNKNOWN",
 368                         tests,
 369                         "There is at least a path between '"+ sourceNode.getName() + "' and '"
 370                                 + destinationNode.getName() + "' traversing middlebox '"
 371                                 + middleboxNode.getName() + "' where it is not guaranteed that '"
 372                                 + sourceNode.getName() + "' can effectively reach '"
 373                                 + destinationNode.getName()
 374                                 + "'. See below the paths that have been checked");
 375             }
 376         }
 377
 378         extractPathsWithoutMiddlebox(pathsBetweenSourceAndDestination, middleboxNode.getName());
 379         printListsOfStrings("Paths without middlebox '" + middleboxNode.getName() + "'", pathsBetweenSourceAndDestination);
 380
 381         if (pathsBetweenSourceAndDestination.isEmpty()) {
 382             return new Verification("SAT",
 383                     tests,
 384                     "All the paths between node '"+ sourceNode.getName() + "' and '"
 385                             + destinationNode.getName() + "' traverse middlebox '"
 386                             + middleboxNode.getName() + "'");
 387         }
 388
 389
 390         Map<Integer, GeneratorSolver> scenarios2=createScenarios( pathsBetweenSourceAndDestination, graph);
 391
 392         tests = run(graph, scenarios2, sourceNode.getName(), destinationNode.getName());
 393
 394         Verification traversal= evaluateTraversalResults(tests,
 395                 sourceNode.getName(),
 396                 destinationNode.getName(),
 397                 middleboxNode.getName());
 398
 399         Calendar cal_traversal_stop = Calendar.getInstance();
 400         time_traversal = time_traversal +(cal_traversal_stop.getTime().getTime() - start_time_traversal.getTime());
 401         vlogger.logger.info("Time to check traversal policy: " + time_traversal);
 402         //System.out.println("Time to check traversal policy: " + time_traversal);
 403         return traversal;
 404     }
 405
 406     private Verification evaluateTraversalResults(List<Test> tests, String source, String destination,
 407             String middlebox) {
 408         Verification v = new Verification();
 409         boolean isSat = false;
 410         int unsatCounter = 0;
 411         for (Test t : tests) {
 412             v.getTests().add(t);
 413
 414             if (t.getResult().equals("SAT")) {
 415                 isSat = true;
 416             }
 417             else if (t.getResult().equals("UNKNOWN")) {
 418                 v.setResult("UNKNWON");
 419                 v.setComment("There is at least one path from '"+ source + "' to '" + destination
 420                         + "' that doesn't traverse middlebox '" + middlebox
 421                         + "' (see below all the paths that have been checked)");
 422             }
 423             else if (t.getResult().equals("UNSAT")) {
 424                 unsatCounter++;
 425             }
 426         }
 427         if (isSat) {
 428             v.setResult("UNSAT");
 429             v.setComment("There is at least one path from '"+ source + "' to '" + destination
 430                     + "' that doesn't traverse middlebox '" + middlebox
 431                     + "' (see below all the paths that have been checked)");
 432         }
 433         else if (unsatCounter == tests.size()) {
 434             v.setResult("SAT");
 435             v.setComment("The only available paths from '"+ source + "' to '" + destination
 436                     + "' are those that traverse middlebox '" + middlebox
 437                     + "' (see below the alternative paths that have been checked and are unusable)");
 438         }
 439         return v;
 440     }
 441
 442     private Verification reachabilityVerification(Graph graph, Node sourceNode, Node destinationNode) throws MyInvalidDirectionException {
 443         Long time_reachability=(long) 0;
 444         Calendar cal_reachability = Calendar.getInstance();
 445         Date start_time_reachability = cal_reachability.getTime();
 446
 447         Paths paths = getPaths(graph, sourceNode, destinationNode);
 448
 449         if (paths.getPath().size() == 0) {
 450             return new Verification("UNSAT",
 451                     "There are no available paths between '"+ sourceNode.getName() + "' and '"
 452                             + destinationNode.getName() + "'");
 453         }
 454
 455         List<List<String>> sanitizedPaths = sanitizePaths(paths);
 456
 457         printListsOfStrings("Paths", sanitizedPaths);
 458
 459         if (sanitizedPaths.isEmpty()) {
 460             return new Verification("UNSAT",
 461                     "There are no available paths between '"+ sourceNode.getName() + "' and '"
 462                             + destinationNode.getName() + "'");
 463         }
 464
 465         Map<Integer, GeneratorSolver> scenarios=createScenarios(sanitizedPaths, graph);
 466
 467         List<Test> tests = run(graph, scenarios, sourceNode.getName(), destinationNode.getName());
 468
 469         Calendar cal_reachability_after_run = Calendar.getInstance();
 470         time_reachability = time_reachability +(cal_reachability_after_run.getTime().getTime() - start_time_reachability.getTime());
 471         vlogger.logger.info("Time reachability after run: " + time_reachability);
 472         //System.out.println("Time reachability after run: " + time_reachability);
 473
 474         Verification reachability= evaluateReachabilityResult(tests, sourceNode.getName(), destinationNode.getName());
 475
 476         Calendar cal_reachability_stop = Calendar.getInstance();
 477         time_reachability = time_reachability +(cal_reachability_stop.getTime().getTime() - start_time_reachability.getTime());
 478         vlogger.logger.info("Time to check reachability policy: " + time_reachability);
 479         //System.out.println("Time to check reachability policy: " + time_reachability);
 480
 481         return reachability;
 482     }
 483
 484     private List<Test> run(Graph graph, Map<Integer, GeneratorSolver> scenarios, String src, String dst) {
 485         List<Test> tests = new ArrayList<Test>();
 486         String result;
 487
 488         //estimation time
 489         //Long time=(long) 0;
 490         //Calendar cal = Calendar.getInstance();
 491         //Date start_time = cal.getTime();
 492
 493         for(Map.Entry<Integer, GeneratorSolver> t : scenarios.entrySet()){
 494
 495             result=t.getValue().run(src, dst);
 496
 497             List<Node> path = new ArrayList<Node>();
 498             for (String nodeString : t.getValue().getPaths()) {
 499                 Node node = graph.searchNodeByName(nodeString);
 500                 path.add(node);
 501             }
 502             Test test = new Test(path, result);
 503             tests.add(test);
 504         }
 505
 506         //Calendar cal2 = Calendar.getInstance();
 507         //time = time +(cal2.getTime().getTime() - start_time.getTime());
 508         //System.out.println("Time occur to run: " + time);
 509
 510         return tests;
 511     }
 512
 513     private Map<Integer, GeneratorSolver> createScenarios(List<List<String>> sanitizedPaths, Graph graph) {
 514         int index=0;
 515         Map<Integer, GeneratorSolver> scenarios=new HashMap<Integer, GeneratorSolver>();
 516         for(List<String> s : sanitizedPaths){
 517             Scenario tmp=new Scenario(graph, s);
 518             tmp.createScenario();
 519             GeneratorSolver gs=new GeneratorSolver(tmp, s);
 520             gs.genSolver();
 521             scenarios.put(index++, gs);
 522         }
 523         return scenarios;
 524     }
 525
 526     private Verification evaluateReachabilityResult(List<Test> tests, String source, String destination) {
 527         Verification v = new Verification();
 528         boolean sat = false;
 529         int unsat = 0;
 530         for (Test t : tests) {
 531
 532             if (t.getResult().equals("SAT")) {
 533                 sat = true;
 534             }
 535
 536             else if (t.getResult().equals("UNKNOWN")) {
 537                 v.setResult("UNKNWON");
 538                 v.setComment("Reachability from '"+ source + "' to '" + destination
 539                         + "' is unknown. See all the checked paths below");
 540
 541             }
 542             else if (t.getResult().equals("UNSAT")) {
 543                 unsat++;
 544             }
 545             v.getTests().add(t);
 546         }
 547         if (sat) {
 548             v.setResult("SAT");
 549             v.setComment("There is at least one path '"+ source + "' can use to reach '" + destination
 550                     + "'. See all the available paths below");
 551
 552         }
 553         else if (unsat == tests.size()) {
 554             v.setResult("UNSAT");
 555             v.setComment("There isn't any path '"+ source + "' can use to reach '" + destination
 556                     + "'. See all the checked paths below");
 557
 558         }
 559
 560         return v;
 561     }
 562
 563     public List<List<Node>> getPaths(long graphId, String source, String destination) throws JsonParseException, JsonMappingException, JAXBException, IOException, MyInvalidDirectionException {
 564         if (graphId < 0) {
 565             throw new ForbiddenException("Illegal graph id: " + graphId);
 566         }
 567         GraphService graphService = new GraphService();
 568         Graph graph = graphService.getGraph(graphId);
 569         if (graph == null) {
 570             throw new DataNotFoundException("Graph with id " + graphId + " not found");
 571         }
 572
 573         if (source == null || source.equals("")) {
 574             throw new BadRequestException("Please specify the 'source' parameter in your request");
 575         }
 576         if (destination == null || destination.equals("")) {
 577             throw new BadRequestException("Please specify the 'destination' parameter in your request");
 578         }
 579
 580         Node sourceNode = graph.searchNodeByName(source);
 581         Node destinationNode = graph.searchNodeByName(destination);
 582
 583         if (sourceNode == null) {
 584             throw new BadRequestException("The 'source' parameter '" + source + "' is not valid, please insert the name of an existing node");
 585         }
 586         if (destinationNode == null) {
 587             throw new BadRequestException("The 'destination' parameter '" + destination + "' is not valid, please insert the name of an existing node");
 588         }
 589
 590         Paths all_paths = getPaths(graph, sourceNode, destinationNode);
 591
 592         if (all_paths.getPath().size() == 0) {
 593             vlogger.logger.info("No path available");
 594             //System.out.println("No path available");
 595             return null;
 596         }
 597
 598         List<List<String>> sanitizedPaths = sanitizePaths(all_paths);
 599
 600         printListsOfStrings("Paths", sanitizedPaths);
 601
 602         if (sanitizedPaths.isEmpty()) {
 603             return null;
 604         }
 605
 606         List<List<Node>> paths=new ArrayList<List<Node>>();
 607         List<Node> p= new ArrayList<Node>();
 608
 609         for(int i=0; i<sanitizedPaths.size(); i++){
 610             List<String> name=sanitizedPaths.get(i);
 611             for(int j=0; j<name.size(); j++){
 612                 Node n=graph.searchNodeByName(name.get(j));
 613                 if(n!=null)
 614                     p.add(j, n);
 615             }
 616             if(!p.isEmpty())
 617                 paths.add(i, p);
 618         }
 619
 620         if(!paths.isEmpty())
 621             return paths;
 622         else
 623             return null;
 624     }
 625 }