Hi Luis,
try the method getDistance(String rid_from, String rid_to) in the attached
file LongestPath.java
Regards,
Alessandro
--
---
You received this message because you are subscribed to the Google Groups
"OrientDB" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/d/optout.
package PATH;
import java.util.ArrayList;
import java.util.List;
import com.tinkerpop.blueprints.Direction;
import com.tinkerpop.blueprints.Vertex;
import com.tinkerpop.blueprints.impls.orient.OrientGraph;
public class LongestPath {
private boolean stop=false;
private Vertex vertex_from=null;
private List<Vertex> vertexPreviousStep=new ArrayList<Vertex>();
private List<Vertex> vertexCurrently=new ArrayList<Vertex>();
private List<List<String>> paths=new ArrayList<List<String>>();
private OrientGraph g;
public LongestPath(OrientGraph g) {
this.g=g;
}
protected String getDistance(String rid_from, String rid_to) {
if(!checkIfExistsNodes(rid_from,rid_to))
return "rid_from or rid_to not found";
vertexPreviousStep.add(vertex_from);
List<String> p=new ArrayList<String>();
p.add(rid_from);
paths.add(p);
int step=1;
do{
stop=false;
for(Vertex v: vertexPreviousStep){
String rid_previousVertex=v.getId().toString();
List<String> rid_toAdd=new ArrayList<String>();
Iterable<Vertex> nodes = (Iterable<Vertex>) v.getVertices(Direction.OUT);
for(Vertex v1:nodes){
rid_toAdd.add(v1.getId().toString());
String rid=v1.getId().toString();
if(!rid.equals(rid_to)) // non sono arrivato al nodo finale
vertexCurrently.add(v1);
}
if(rid_toAdd.size()!=0)
setPaths(rid_previousVertex,rid_toAdd,step);
}
change();
step++;
}while(stop==true);
cleanPaths(rid_to);
return getLongestPath();
}
private boolean checkIfExistsNodes(String rid_from,String rid_to) {
boolean find_from=false;
boolean find_to=false;
for(Vertex v:g.getVertices()){
if(v.getId().toString().equals(rid_from)){
find_from=true;
vertex_from=v;
}
else if(v.getId().toString().equals(rid_to))
find_to=true;
}
if(find_from==false || find_to==false)
return false;
return true;
}
public void change(){
vertexPreviousStep.clear();
for(Vertex v:vertexCurrently)
vertexPreviousStep.add(v);
vertexCurrently.clear();
}
private void setPaths(String rid_previousVertexo,List<String> rid_toAdd,int step) {
for(int i=0;i<paths.size();i++){
List<String> list=paths.get(i);
String last=list.get(list.size()-1);
if(last.equals(rid_previousVertexo) && list.size()==step){
int j=0;
for(String rid:rid_toAdd){
boolean rid_found=false;
for(String p:list){
if(p.equals(rid))
rid_found=true;
}
if(rid_found==false){
List<String> p2=new ArrayList<String>();
for(String p:list)
p2.add(p);
p2.add(rid);
if(j==0){
stop=true;
paths.set(i, p2);
j++;
}
else
paths.add(p2);
}
}
}
}
}
public void cleanPaths(String rid_arrivo){
for(int i=0;i<paths.size();i++){
List<String> list=paths.get(i);
if(!list.get(list.size()-1).equals(rid_arrivo)){
paths.remove(i);
i--;
}
}
}
public String getLongestPath(){
String path="There aren't paths";
if(paths.size()==0)
return path;
else{
List<String> list=paths.get(0);
int max_size= list.size();
path=list.toString();
for(int i=1;i<paths.size();i++){
if(paths.get(i).size()>max_size){
max_size=paths.get(i).size();
path=paths.get(i).toString();
}
}
}
return path;
}
}
