Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*
   *
   *  *  Copyright 2014 Orient Technologies LTD (info(at)orientechnologies.com)
   *  *
   *  *  Licensed under the Apache License, Version 2.0 (the "License");
   *  *  you may not use this file except in compliance with the License.
   *  *  You may obtain a copy of the License at
   *  *
   *  *       http://www.apache.org/licenses/LICENSE-2.0
  *  *
  *  *  Unless required by applicable law or agreed to in writing, software
  *  *  distributed under the License is distributed on an "AS IS" BASIS,
  *  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  *  *  See the License for the specific language governing permissions and
  *  *  limitations under the License.
  *  *
  *  * For more information: http://www.orientechnologies.com
  *
  */
 package com.orientechnologies.orient.graph.sql.functions;
 
 
 import java.util.*;

Shortest path algorithm to find the shortest path from one node to another node in a directed graph.

Author(s):
Luca Garulli (l.garulli--at--orientechnologies.com)
 
   public static final String   NAME     = "shortestPath";
 
   protected static final float DISTANCE = 1f;
 
   public OSQLFunctionShortestPath() {
     super(, 2, 4);
   }
 
   public List<ORIDexecute(Object iThisfinal OIdentifiable iCurrentRecordObject iCurrentResultfinal Object[] iParams,
       final OCommandContext iContext) {
     final OModifiableBoolean shutdownFlag = new OModifiableBoolean();
     final OrientBaseGraph graph = OGraphCommandExecutorSQLFactory.getGraph(falseshutdownFlag);
     try {
       final ORecord record = (ORecord) (iCurrentRecord != null ? iCurrentRecord.getRecord() : null);
 
       Object source = iParams[0];
       if (OMultiValue.isMultiValue(source)) {
         if (OMultiValue.getSize(source) > 1)
           throw new IllegalArgumentException("Only one sourceVertex is allowed");
         source = OMultiValue.getFirstValue(source);
       }
       OrientVertex sourceVertex = graph.getVertex(OSQLHelper.getValue(sourcerecordiContext));
 
       Object dest = iParams[1];
       if (OMultiValue.isMultiValue(dest)) {
         if (OMultiValue.getSize(dest) > 1)
           throw new IllegalArgumentException("Only one destinationVertex is allowed");
         dest = OMultiValue.getFirstValue(dest);
       }
       OrientVertex destinationVertex = graph.getVertex(OSQLHelper.getValue(destrecordiContext));
 
       if (sourceVertex.equals(destinationVertex)) {
         final List<ORIDresult = new ArrayList<ORID>(1);
         result.add(destinationVertex.getIdentity());
         return result;
       }
 
       Direction direction = .;
       if (iParams.length > 2 && iParams[2] != null) {
         direction = Direction.valueOf(iParams[2].toString().toUpperCase());
       }
       Object edgeType = null;
       if (iParams.length > 3) {
         edgeType = iParams[3];
       }
 
       final ArrayDeque<OrientVertexqueue = new ArrayDeque<OrientVertex>();
       final Set<ORIDvisited = new HashSet<ORID>();
       final Map<ORIDORIDpreviouses = new HashMap<ORIDORID>();
 
       queue.add(sourceVertex);
       visited.add(sourceVertex.getIdentity());
      OrientVertex current;
      while (!queue.isEmpty()) {
        current = queue.poll();
        Iterable<Vertexneighbors;
        if (edgeType == null) {
          neighbors = current.getVertices(direction);
        } else {
          neighbors = current.getVertices(directionnew String[] { "" + edgeType });
        }
        for (Vertex neighbor : neighbors) {
          final OrientVertex v = (OrientVertexneighbor;
          final ORID neighborIdentity = v.getIdentity();
          if (!visited.contains(neighborIdentity)) {
            previouses.put(neighborIdentitycurrent.getIdentity());
            if (destinationVertex.equals(neighbor))
              return computePath(previousesneighborIdentity);
            queue.offer(v);
            visited.add(neighborIdentity);
          }
        }
      }
      return new ArrayList<ORID>();
    } finally {
      if (shutdownFlag.getValue())
        graph.shutdown(false);
    }
  }
  public String getSyntax() {
    return "shortestPath(<sourceVertex>, <destinationVertex>, [<direction>, [ <edgeTypeAsString> ]])";
  }
  private List<ORIDcomputePath(final Map<ORIDORIDdistancesfinal ORID neighbor) {
    final List<ORIDresult = new ArrayList<ORID>();
    ORID current = neighbor;
    while (current != null) {
      result.add(0, current);
      current = distances.get(current);
    }
    return result;
  }
New to GrepCode? Check out our FAQ X