code: package ShapeAnalysis;
  
  import Graph.Graph;
  import java.util.ArrayList;
  import org.apache.jena.query.Query;
  import org.apache.jena.query.QueryFactory;
  import org.apache.jena.sparql.syntax.Element;
  import org.apache.jena.sparql.syntax.ElementVisitorBase;
  import org.apache.jena.sparql.syntax.ElementWalker;
  
  public class QueryShapeType {
  
      static public Graph graph = new Graph();
      
      public static boolean isSingleEdge(String queryString) { //if no. of edges = 1, it is a single edge
          if (queryToGraph(queryString).edges.size() == 1) //Graph is a list of edges
          {
              return true;
          }
          return false;
      }
  
      public static boolean isChain(String queryString) {
          if (isSingleEdge(queryString)) //  single edge e.g. 0----0
          {
              return true;
          }
  
          //if chain with mutiple edges, return true e.g.   0---0----0  0----0---0---0---0...---0 
          //degree for every vertex is 2 except 2 vertices: 1st and last have degree 1
          Graph graph = queryToGraph(queryString);
          ArrayList<Integer> verticesDegrees = graph.getVerticesDegrees();
  
          int degree_1 = 0;
          int degree_2 = 0;
          int degree_not_1_or_2 = 0;
  
          for (Integer verticesDegree : verticesDegrees) {
              if (verticesDegree == 1) {
                  degree_1++;
              } else if (verticesDegree == 2) {
                  degree_2++;
              } else {
                  degree_not_1_or_2++;
              }
          }
  
          if (degree_1 == 2 && degree_2 > 0 && degree_not_1_or_2 == 0) {
              return true;
          }
          return false;
      }
  
      public static boolean isChainSet(String queryString) {
          if (isChain(queryString)) {
              return true;
          }
  
          //if multiple chain with one or mutiple edges, return true e.g.   [0---0----0 0---0] [ 0----0---0---0---0...---0] 
          //(degree for every vertex is 2) or (degree 1 not greater than 1)
          Graph graph = queryToGraph(queryString);
          ArrayList<Integer> verticesDegrees = graph.getVerticesDegrees();
  
          int degree_1 = 0;
          int degree_2 = 0;
          int degree_not_1_or_2 = 0;
  
          for (Integer verticesDegree : verticesDegrees) {
              if (verticesDegree == 1) {
                  degree_1++;
              } else if (verticesDegree == 2) {
                  degree_2++;
              } else {
                  degree_not_1_or_2++;
              }
          }
  
          if (degree_1 >= 2 && degree_2 > 0 && degree_not_1_or_2 == 0) {
              return true;
          }
  
          return false;
      }
  
      public static boolean isTree(String queryString) {
  
          if (isChain(queryString)) {
              return true;
          }
  
          if (isCycle(queryString)) {
              return false;
          }
  
          Graph graph = queryToGraph(queryString);
          //if for every pair of nodes i and j, there exists only one path from i to j
          for (int i = 0; i < graph.vertices.size(); i++) {
              for (int j = 0; j < graph.vertices.size(); j++) {
                  if (graph.getAllPaths(graph.vertices.get(i), graph.vertices.get(j)).size() > 1
                          || graph.getAllPaths(graph.vertices.get(i), graph.vertices.get(j)).isEmpty()) {
                      return false;
                  }
              }
          }
  
          return true;
      }
  
      public static boolean isStar(String queryString) {
          if (isTree(queryString)) {
              //if there exists exactly one node with more than 2 neighbors
              //(u,u1), (u,u2), (u,u3), ..
              Graph graph = queryToGraph(queryString);
              ArrayList<Integer> verticesDegrees = graph.getVerticesDegrees();
  
              int degree_1 = 0;
              int degree_2 = 0;
              int degree_greater_2 = 0;
  
              for (Integer verticesDegree : verticesDegrees) {
                  if (verticesDegree > 2) {
                      degree_greater_2++;
                  }
              }
  
              if (degree_greater_2 == 1) {
                  //get node with dgree > 2
                  String u = "";
                  for (int i = 0; i < graph.vertices.size(); i++) {
                      if (verticesDegrees.get(i) > 2) {
                          u = graph.vertices.get(i);
                      }
                  }
                  for (int i = 0; i < graph.edges.size(); i++) {
                      if (graph.edges.get(i).source.equals(u) && graph.edges.get(i).destination.equals(u)) {
                          return false;
                      }
  
                  }
                  //get Vertices Connected To u
                  ArrayList<String> vs = new ArrayList<>();
                  for (int i = 0; i < graph.edges.size(); i++) {
                      if (graph.edges.get(i).source.equals(u)) {
                          if (vs.contains(graph.edges.get(i).destination)) {
                              return false;
                          }
                          vs.add(graph.edges.get(i).destination);
                      }
  
                      if (graph.edges.get(i).destination.equals(u)) {
                          if (vs.contains(graph.edges.get(i).source)) {
                              return false;
                          }
                          vs.add(graph.edges.get(i).source);
                      }
  
                  }
                  return true;
              }
          }
          return false;
      }
  
      public static boolean isForest(String queryString) {
          if (isTree(queryString)) {
              return true;
          }
  
          //if separated graphs are tree, return true
          Graph graph = queryToGraph(queryString);
          //if for every pair of nodes i and j, there exists only one path from i to j or no paths
          for (int i = 0; i < graph.vertices.size(); i++) {
              for (int j = 0; j < graph.vertices.size(); j++) {
                  if (graph.getAllPaths(graph.vertices.get(i), graph.vertices.get(j)).size() > 1) {
                      return false;
                  }
              }
          }
          return true;
      }
  
      public static boolean isCycle(String queryString) {
          //if the same rules of chain with 1st and last nodes connected
          //All nodes have degree 2
          Graph graph = queryToGraph(queryString);
          ArrayList<Integer> verticesDegrees = graph.getVerticesDegrees();
  
          int degree_2 = 0;
          int degree_not_1_or_2 = 0;
  
          for (Integer verticesDegree : verticesDegrees) {
              if (verticesDegree == 2) {
                  degree_2++;
              } else {
                  degree_not_1_or_2++;
              }
          }
  
          if (degree_2 > 0 && degree_not_1_or_2 == 0) {
              return true;
          }
          return false;
      }
  
      private static boolean isPetal(String queryString) {
          if (isCycle(queryString)) {
              return true;
          }
          //if the same rules of chain with 1st and last nodes connected
          //All nodes have degree 2 except 2 nodes has degrees more than 2
          Graph graph = queryToGraph(queryString);
          ArrayList<Integer> verticesDegrees = graph.getVerticesDegrees();
  
          int degree_2 = 0;
          int degree_greater_2 = 0;
  
          for (Integer verticesDegree : verticesDegrees) {
              if (verticesDegree == 2) {
                  degree_2++;
              } else if (verticesDegree > 2) {
                  degree_greater_2++;
              }
          }
  
          if (degree_2 > 0 && degree_greater_2 == 2) {
              return true;
          }
          return false;
      }
  
      private static boolean isPetal(Graph graph) {
          ArrayList<Integer> verticesDegrees = graph.getVerticesDegrees();
  
          int degree_2 = 0;
          int degree_greater_2 = 0;
  
          for (Integer verticesDegree : verticesDegrees) {
              if (verticesDegree == 2) {
                  degree_2++;
              } else if (verticesDegree > 2) {
                  degree_greater_2++;
              }
          }
  
          if (degree_2 > 0 && degree_greater_2 == 2) {
              return true;
          }
          return false;
      }
  
      public static boolean isFlower(String queryString) {
          //flower is a graph consisting of a node x with three types of attachements:
          //chains, trees, petals(has nodes (s,t) with 2 or more pathes between them)
          if (isChain(queryString)) {
              return true;
          }
          if (isTree(queryString)) {
              return true;
          }
          if (isPetal(queryString)) //is a petal?
          {
              return true;
          }
          //pruning the graph: remove elements with degree 1
          // if the remaining graph is petal, it is a flower
          Graph graph = queryToGraph(queryString);
          boolean changed = false;
          while (!changed) {
              changed = false;
              ArrayList<Integer> verticesDegrees = graph.getVerticesDegrees();
  
              for (int i = 0; i < verticesDegrees.size(); i++) {
                  if (verticesDegrees.get(i) == 1) {
                      verticesDegrees.remove(i);
                      graph.vertices.remove(i);
                      changed = true;
                  }
              }
          }
          if (isPetal(graph)) //is a petal?
          {
              return true;
          }
  
          return false;
      }
  
      public static boolean isFlowerSet(String queryString) {
          //if separate graphs are flowers
          if (isFlower(queryString)) {
              return true;
          }
  
          //pruning the graph: remove elements with degree 1
          // if the remaining graphs are petals, it is a flowerset
          Graph graph = queryToGraph(queryString);
          ArrayList<Integer> verticesDegrees = graph.getVerticesDegrees();
          boolean changed = true;
          while (changed) {
              changed = false;
              verticesDegrees = graph.getVerticesDegrees();
  
              for (int i = 0; i < verticesDegrees.size(); i++) {
                  if (verticesDegrees.get(i) == 1) {
                      verticesDegrees.remove(i);
                      graph.vertices.remove(i);
                      changed = true;
                  }
              }
          }
          verticesDegrees = graph.getVerticesDegrees();
  
          int degree_2 = 0;
          int degree_greater_2 = 0;
  
          for (Integer verticesDegree : verticesDegrees) {
              if (verticesDegree == 2) {
                  degree_2++;
              } else if (verticesDegree > 2) {
                  degree_greater_2++;
              }
          }
  
          if (degree_2 > 0 && degree_greater_2 >= 2) {
              return true;
          }
  
          return false;
      }
  
      private static Graph queryToGraph(String queryString) {
          //Define Graph as a set of edges
          graph = new Graph();
          try {
              Query q = QueryFactory.create(queryString);
              Element e = q.getQueryPattern();
  
              ElementVisitorBase visitor = new ElementVisitorShapeImpl();
              ElementWalker.walk(e, visitor);
  
          } catch (Exception e) {
          }
          return graph;
      }
  
  }
  