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.List;
 import java.util.Map;
 import java.util.Set;
 
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, 3);
   }
 
   public Object execute(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)
         direction = Direction.valueOf(iParams[2].toString().toUpperCase());
 
       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();
        final Iterable<Vertexneighbors = current.getVertices(direction);
        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>])";
  }
  private Object computePath(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