Examples of DijkstraShortestPath

edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath

Calculates distances and shortest paths using Dijkstra's single-source-shortest-path algorithm. This is a lightweight extension of DijkstraDistance that also stores path information, so that the shortest paths can be reconstructed.

The elements in the maps returned by getIncomingEdgeMap are ordered (that is, returned by the iterator) by nondecreasing distance from source.
@author Joshua O'Madadhain @author Tom Nelson converted to jung2 @see DijkstraDistance

Examples of edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath

  private ConverterImpl getConverter(String inType, String outType) {
    Vertex sourceVertex = dataTypeToVertex.get(inType);
    Vertex targetVertex = dataTypeToVertex.get(outType);


    if (sourceVertex != null && targetVertex != null) {
      DijkstraShortestPath shortestPathAlg =
          new DijkstraShortestPath(graph);
      
      // Documentation of DijkstraShortestPath indicates that this returns a list of Edge.
      @SuppressWarnings("unchecked")
      List<Edge> edgeList = shortestPathAlg.getPath(sourceVertex, targetVertex);


      if (edgeList.size() > 0) {
        List<ServiceReference<AlgorithmFactory>> serviceReferences = Lists.newArrayList();
        for (Edge edge : edgeList) {
          AbstractList converterList =

View Full Code Here

Examples of edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath

  }
  
  
  
  public static Vertex getTempRed(DirectedSparseGraph model, Vertex r, DirectedSparseGraph temp){
    DijkstraShortestPath p = new DijkstraShortestPath(model);
    List<Edge> pathToRed = p.getPath(DeterministicDirectedSparseGraph.findInitial(model), r);
    Set<List<String>> pathToRedStrings = new HashSet<List<String>>();
    Vertex tempRed = null;
    if(!pathToRed.isEmpty()){
      pathToRedStrings = getPaths(pathToRed);
      List<String> prefixString = (List<String>)pathToRedStrings.toArray()[0];

View Full Code Here

Examples of edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath

  protected List<List<String>> generateQuestions(DirectedSparseGraph model, DirectedSparseGraph temp, OrigStatePair pair){
    Vertex q = pair.getQ();
    Vertex r = pair.getR();
    if(q==null || r ==null)
      return new ArrayList<List<String>>();
    DijkstraShortestPath p = new DijkstraShortestPath(temp);
    Vertex tempRed = getTempRed(model, r, temp);
    Vertex tempInit = DeterministicDirectedSparseGraph.findInitial(temp);
    Set<List<String>> prefixes = new HashSet<List<String>>();
    if(!tempRed.equals(tempInit)){
      List<Edge> prefixEdges = p.getPath(tempInit, tempRed);
      prefixes = getPaths(prefixEdges);
    }
    Set<List<String>> suffixes = computeSuffixes(tempRed, temp);
    List<List<String>> questions =new ArrayList<List<String>>();
    questions.addAll(mergePrefixWithSuffixes(prefixes, suffixes));
    Edge loopEdge = findEdge(tempRed, tempRed);
    if(loopEdge!=null){
      Collection<String> looplabels = (Collection<String>)loopEdge.getUserDatum(JUConstants.LABEL);
      questions.addAll(mergePrefixWithSuffixes(prefixes, looplabels,suffixes));
    }
    
    DirectedSparseGraph questionPrefixes = augmentPTA(DeterministicDirectedSparseGraph.initialise(), questions, true);
    Iterator<Vertex> questionIt = getEndPoints(questionPrefixes).iterator();
    p = new DijkstraShortestPath(questionPrefixes);
    questions =new ArrayList<List<String>>();
    Vertex init = DeterministicDirectedSparseGraph.findInitial(questionPrefixes);
    while(questionIt.hasNext()){
      List<Edge> edgePath = p.getPath(init, questionIt.next());
      Set<List<String>> pathsToPoint = getPaths(edgePath);
      if(pathsToPoint.isEmpty())
        continue;
      List<String> pathToPoint = (List<String>)getPaths(edgePath).toArray()[0];
      Vertex tempV = getVertex(temp, pathToPoint);

View Full Code Here

Examples of edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath

    return questions;
  }
  
  public static Set<List<String>> computeSuffixes(Vertex v, DirectedSparseGraph model){
    Set<List<String>> returnSet = new HashSet<List<String>>();
    DijkstraShortestPath p = new DijkstraShortestPath(model);
    Iterator<DirectedSparseEdge> edgeIt = model.getEdges().iterator();
    while(edgeIt.hasNext()){
      DirectedSparseEdge e = edgeIt.next();
      List<Edge> sp = null;
      sp = p.getPath(v, e.getSource());
      if(sp!=null){
        if(!sp.isEmpty()){
          sp.add(e);
          Set<List<String>> paths = getPaths(sp);
          returnSet.addAll(paths);

View Full Code Here

Examples of edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath

   */
  protected Set<List<String>> getSuffixes(DirectedSparseGraph graph, Vertex r, boolean accepted){
    Set<List<String>> setOfPaths = new HashSet<List<String>>();
    Iterator<Vertex> vertexIt = graph.getVertices().iterator();
    Set<Vertex> endVertices = new HashSet<Vertex>();
    DijkstraShortestPath p = new DijkstraShortestPath(graph);
    while(vertexIt.hasNext()){
      Vertex v = vertexIt.next();
      if(v.getSuccessors().isEmpty()&& DeterministicDirectedSparseGraph.isAccept(v) == accepted)
        endVertices.add(v);
    }
    for(Vertex v:endVertices)
    {
      List<Edge> l = p.getPath(r, v);
      if(!l.isEmpty())
        setOfPaths.addAll(getPaths(l));
    }
    return setOfPaths;
  }

View Full Code Here

Examples of edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath

  }
  
  @SuppressWarnings("unchecked")
  private static Vertex getTempRed_DijkstraShortestPath(DirectedSparseGraph model, Vertex r, DirectedSparseGraph temp)
  {
    DijkstraShortestPath p = new DijkstraShortestPath(model);
    List<Edge> pathToRed = p.getPath(DeterministicDirectedSparseGraph.findInitial(model), r);
    Vertex tempRed = null;
    if(!pathToRed.isEmpty()){
      List<Label> pathToRedString = new LinkedList<Label>();
      for(Edge e:pathToRed)
        pathToRedString.add( ((Collection<Label>)e.getUserDatum(JUConstants.LABEL)).iterator().next() );

View Full Code Here

Examples of edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath

   */
  protected Set<List<String>> getSuffixes(DirectedSparseGraph graph, Vertex r, boolean accepted){
    Set<List<String>> setOfPaths = new HashSet<List<String>>();
    Iterator<Vertex> vertexIt = graph.getVertices().iterator();
    Set<Vertex> endVertices = new HashSet<Vertex>();
    DijkstraShortestPath p = new DijkstraShortestPath(graph);
    while(vertexIt.hasNext()){
      Vertex v = vertexIt.next();
      if(v.getSuccessors().isEmpty()&& DeterministicDirectedSparseGraph.isAccept(v) == accepted)
        endVertices.add(v);
    }
    for(Vertex v:endVertices)
    {
      List l = p.getPath(r, v);
      if(!l.isEmpty())
        setOfPaths.addAll(getPaths(l));
    }
    return setOfPaths;
  }

View Full Code Here

Examples of edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath

        "S-m->B-d->B0-a->B1-b->B2-c->B3\n"+
        "B0-d->C0-a->C1-b->C2-c->C3\nC2-f->C4",6,"testNewLearner_4_13");
  }
  
  private static Vertex getTempRed_DijkstraShortestPath(DirectedSparseGraph model, Vertex r, DirectedSparseGraph temp){
    DijkstraShortestPath p = new DijkstraShortestPath(model);
    List<Edge> pathToRed = p.getPath(DeterministicDirectedSparseGraph.findInitial(model), r);
    Vertex tempRed = null;
    if(!pathToRed.isEmpty()){
      List<String> pathToRedString = new LinkedList<String>();
      for(Edge e:pathToRed)
        pathToRedString.add( ((Collection<String>)e.getUserDatum(JUConstants.LABEL)).iterator().next() );

View Full Code Here

Examples of edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath

        "S-m->B-d->B0-a->B1-b->B2-c->B3\n"+
        "B0-d->C0-a->C1-b->C2-c->C3\nC2-f->C4",6,"testNewLearner_4_13");
  }
  
  private static Vertex getTempRed_DijkstraShortestPath(DirectedSparseGraph model, Vertex r, DirectedSparseGraph temp){
    DijkstraShortestPath p = new DijkstraShortestPath(model);
    List<Edge> pathToRed = p.getPath(DeterministicDirectedSparseGraph.findInitial(model), r);
    Vertex tempRed = null;
    if(!pathToRed.isEmpty()){
      List<String> pathToRedString = new LinkedList<String>();
      for(Edge e:pathToRed)
        pathToRedString.add( ((Collection<String>)e.getUserDatum(JUConstants.LABEL)).iterator().next() );

View Full Code Here

Examples of edu.uci.ics.jung.algorithms.shortestpath.DijkstraShortestPath

  }
  
  
  
  public static Vertex getTempRed(DirectedSparseGraph model, Vertex r, DirectedSparseGraph temp){
    DijkstraShortestPath p = new DijkstraShortestPath(model);
    List<Edge> pathToRed = p.getPath(DeterministicDirectedSparseGraph.findInitial(model), r);
    Set<List<String>> pathToRedStrings = new HashSet<List<String>>();
    Vertex tempRed = null;
    if(!pathToRed.isEmpty()){
      pathToRedStrings = getPaths(pathToRed);
      List<String> prefixString = (List<String>)pathToRedStrings.toArray()[0];

View Full Code Here

0 1 2 3

TOP

All source code are property of their respective owners. Java is a trademark of Sun Microsystems, Inc and owned by ORACLE Inc. Contact coftware#gmail.com.