Достигнуть n-го преемника вершины в ветке

Question

Я создал орграф, используя библиотеку jgrapht. Я использую метод successorListOf() для доступа к преемнику вершины, но я хотел бы иметь возможность достигнуть n-го преемника данной вершины (которые являются объектами Point в моем случае). Мой орграф имеет две ветви (здесь B и C). Я сделал простой и короткий код, чтобы сделать его проще:

public static DirectedGraph<Point, DefaultEdge> directedGraph = new DefaultDirectedGraph<Point, DefaultEdge>(DefaultEdge.class); 
public static Point startPoint = new Point(2, 6, "S"); 
public static Point firstPoint = new Point(2, 7, "A"); 
public static Point secondPoint = new Point(2, 8, "B"); 
public static Point thirdPoint = new Point(2, 9, "B"); 
public static Point fourthPoint = new Point(2, 10, "B"); 
public static Point fifthPoint = new Point(3, 7, "C"); 
public static Point sixthPoint = new Point(4, 7, "C"); 
public static Point seventhPoint = new Point(5, 7, "C"); 


void setup()  { 
    directedGraph.addVertex(startPoint); 
    directedGraph.addVertex(firstPoint); 
    directedGraph.addVertex(secondPoint); 
    directedGraph.addVertex(thirdPoint); 
    directedGraph.addVertex(fourthPoint); 
    directedGraph.addVertex(fifthPoint); 
    directedGraph.addVertex(sixthPoint); 
    directedGraph.addVertex(seventhPoint); 
    directedGraph.addEdge(startPoint, firstPoint); 
    directedGraph.addEdge(firstPoint, secondPoint); 
    directedGraph.addEdge(firstPoint, thirdPoint); 
    directedGraph.addEdge(firstPoint, fourthPoint); 
} 

// -------------------------------------------------------------- 
public static ArrayList<Point> pointList = new ArrayList<Point>(); 
public static class Point { 

    public int x; 
    public int y; 
    public String iD; 
    public Point(int x, int y, String iD) 
    { 

    this.x = x; 
    this.y = y; 
    this.iD= iD; 
    } 
    @Override 
    public String toString() { 
    return ("[x="+x+" y="+y+" iD="+iD+ "]"); 
    } 

    @Override 
    public int hashCode() { 
    int hash = 7; 
    hash = 71 * hash + this.x; 
    hash = 71 * hash + this.y; 

    return hash; 
    } 



    @Override 
    public boolean equals(Object other) 
    { 
    if (this == other) 
     return true; 

    if (!(other instanceof Point)) 
     return false; 

    Point otherPoint = (Point) other; 
    return otherPoint.x == x && otherPoint.y == y; 
    } 
} 

Я хотел бы добавить ребро между FirstPoint и каждой точкой ветви «B», и вместо того, чтобы:

directedGraph.addEdge(firstPoint, secondPoint); 
    directedGraph.addEdge(firstPoint, thirdPoint); 
    directedGraph.addEdge(firstPoint, fourthPoint); 

Я хотел бы использовать:

for (Point successor : Graphs.successorListOf (directedGraph, firstPoint)) { 
     if (successor.type.equals("B") { 
       directedGraph.addEdge(firstPoint, successor); 
     } 
} 

Но здесь я могу только достигнуть первого преемника ветви В. Как я могу достичь преемника преемника и т.д., в случае п-го наследника? Количество вершин в ветви B может измениться, поэтому я ищу способ сделать это автоматически вместо Point by Point.

Как я мог это сделать?

На чертеже 1 был бы мой StartPoint, 2 будет моим FirstPoint, а затем есть две ветви, которые были бы мои B & C ветви

Answer 1

Я написал следующий код, но он не протестирован, и вам может потребоваться изменить его в соответствии с вашими требованиями.

Этот код запускает DFS (поиск по глубине первого уровня) до предопределенной глубины с использованием переменных и экземпляров, которые вы использовали в приведенных примерах.

public void getSuccessor(DirectedGraph<Point, DefaultEdge> graph, Point point, String type, int depth) { 
    List<Point> visitedPoints = new ArrayList<>(); 
    _getSuccessor(graph, point, visitedPoints, type, depth); 
} 

private void _getSuccessor(DirectedGraph<Point, DefaultEdge> graph, Point point, List<Point> visitedPoints, String type, int depth){ 

    if(depth == 0) 
     return; 

    // Mark node as visited 
    visitedPoints.add(point); 

    // Loop on all its successors 
    for(Point successor : Graphs.successorListOf (directedGraph, point)){ 

     // If node not already visited 
     if(!visitedPoints.contains(successor) && successor.type.equals(type)) { 
      directedGraph.addEdge(firstPoint, successor); 
      _getSuccessor(graph, successor, visitedPoints, type, depth-1); 
     } 
    } 
}