Составление графика для алгоритма Дейкстры

Question

Я реализовал алгоритм Дейкстры, но я также хочу реализовать графический интерфейс для него. Итак, у меня есть несколько вопросов для вас, ребята.

public class Dijkstra {

public static void main(String args[]) {

    Vertex v0 = new Vertex("A");
    Vertex v1 = new Vertex("B");
    Vertex v2 = new Vertex("C");
    Vertex v3 = new Vertex("D");
    Vertex v4 = new Vertex("E");
    Vertex v5 = new Vertex("F");
    Vertex v6 = new Vertex("G");
    Vertex v7 = new Vertex("H");

    v0.adjacencies = new Edge[]{new Edge(v1, 9), new Edge(v2, 1), new Edge(v6, 9), new Edge(v3, 2)};
    v1.adjacencies = new Edge[]{new Edge(v0, 9), new Edge(v4, 4)};
    v2.adjacencies = new Edge[]{new Edge(v0, 1), new Edge(v4, 2), new Edge(v5, 5)};
    v3.adjacencies = new Edge[]{new Edge(v0, 2), new Edge(v6, 5), new Edge(v7, 1)};
    v4.adjacencies = new Edge[]{new Edge(v1, 4), new Edge(v2, 2), new Edge(v5, 1)};
    v5.adjacencies = new Edge[]{new Edge(v4, 1), new Edge(v2, 5), new Edge(v6, 1), new Edge(v7, 4)};
    v6.adjacencies = new Edge[]{new Edge(v0, 9), new Edge(v5, 1), new Edge(v3, 5), new Edge(v7, 2)};
    v7.adjacencies = new Edge[]{new Edge(v5, 4), new Edge(v6, 2), new Edge(v3, 1)};

    Vertex[] vertices = {v0, v1, v2, v3, v4, v5, v6, v7};

    computePaths(v0);

    for (Vertex v : vertices) {
        System.out.println("Distance to " + v + ": " + v.getMinDistance());
        List<Vertex> path = getShortestPathTo(v);
        System.out.println("Path: " + path);
    }

}

public static void computePaths(Vertex source) {
    source.setMinDistance(0);

    PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
    vertexQueue.add(source);

    while (!vertexQueue.isEmpty()) {
        Vertex u = vertexQueue.poll();

        for (Edge e : u.adjacencies) {
            Vertex v = e.target;
            int weight = e.weight;
            int distanceThroughU = u.getMinDistance() + weight;

            if (distanceThroughU < v.getMinDistance()) {
                vertexQueue.remove(v);
                v.setMinDistance(distanceThroughU);
                v.previous = u;
                vertexQueue.add(v);
            }
        }
    }
}

public static List<Vertex> getShortestPathTo(Vertex target) {
    List<Vertex> path = new ArrayList<Vertex>();

    for (Vertex vertex = target; vertex != null; vertex = vertex.previous) {
        path.add(vertex);
    }

    Collections.reverse(path);
    return path;
}

}

Так выглядят реализации (без графического интерфейса). Я видел, что есть библиотека под названием JUNG для графиков, и я скачал ее. Я попытался нарисовать свой график, добавив следующий код в мой основной метод.

SimpleGraphDraw f = new SimpleGraphDraw();

    DirectedSparseGraph g = new DirectedSparseGraph();
    g.addVertex(v0);
    g.addVertex(v1);
    g.addVertex(v2);
    g.addVertex(v3);
    g.addVertex(v4);
    g.addVertex(v5);
    g.addVertex(v6);
    g.addVertex(v7);
    g.addEdge("Edge1", v0, v1);
    g.addEdge("Edge2", v0, v2);
    g.addEdge("Edge3", v0, v6);
    g.addEdge("Edge4", v0, v3);
    g.addEdge("Edge5", v1, v0);
    g.addEdge("Edge6", v1, v4);
    g.addEdge("Edge7", v2, v0);
    g.addEdge("Edge8", v2, v4);
    g.addEdge("Edge9", v2, v5);

    VisualizationImageServer vs = new VisualizationImageServer(new CircleLayout(g), new Dimension(200, 200));

    JFrame frame = new JFrame();
    frame.getContentPane().add(vs);
    frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
    frame.pack();
    frame.setVisible(true);

Как я могу расположить все свои вершины так, как я хочу (они сейчас находятся в круге)?

Как я могу поместить название вершины "A" внутри красного круга в графическом интерфейсе, чтобы отображалось каждое имя вершины.

Как я могу добавить каждый вес внутри GUI в верхней части линии между двумя вершинами?

заранее спасибо

Answer 1

Хотя я не знаком с JUNG, я реализовал графический интерфейс для алгоритма Дейкстры для моего проекта колледжа ( Исходный код).

Он основан на объекте Graphics2D Java Swing для рисования краев. Поскольку вы уже реализовали алгоритм Дейкстры, вас может заинтересовать только приведенный ниже код для рисования ребра (линия со стрелкой и меткой). Он использует тригонометрию, чтобы нарисовать стрелку направления.

private void drawLineSegment(Point from, Point to, Color c, int size, String label, Graphics2D g) {
    g.setColor(c);
    g.setStroke(new BasicStroke(size));
    int x1 = from.getX();
    int y1 = from.getY();
    int x2 = to.getX();
    int y2 = to.getY();
    g.drawLine(x1, y1, x2, y2);
    int sx = (int) ((x1 + x2) / 2.1);
    int sy = (int) ((y1 + y2) / 2.1);
    int cx = (int) ((x1 + x2) / 2);
    int cy = (int) ((y1 + y2) / 2);
    int d = 10;
    double angle = Util.angle360(from, to);
    double anglePlus45 = angle + 45;
    if (anglePlus45 > 360)
        anglePlus45 = anglePlus45 % 360;
    double angleMinus45 = angle - 45;
    if (angleMinus45 < 360)
        angleMinus45 = angleMinus45 + 360;
    anglePlus45 = Math.toRadians(anglePlus45);
    angleMinus45 = Math.toRadians(angleMinus45);
    int ax1 = (int) (cx - d * Math.cos(anglePlus45));
    int ay1 = (int) (cy - d * Math.sin(anglePlus45));
    int ax2 = (int) (cx - d * Math.cos(angleMinus45));
    int ay2 = (int) (cy - d * Math.sin(angleMinus45));
    g.drawLine(cx, cy, ax1, ay1);
    g.drawLine(cx, cy, ax2, ay2);
    g.drawString(label, sx, sy);
}

Это находится в `src/wban/simulate/view/SwingViewer.java. Если вы заинтересованы в запуске кода, вы можете загрузить исполняемый файл. Проектная документация доступна здесь и здесь.

Answer 2

Чтобы использовать другой алгоритм компоновки, замените ссылку на CircleLayout в вашем коде к другому Layout реализация; JUNG предоставляет несколько вариантов.

Пример кода, включенного в состав дистрибутива JUNG, включает в себя несколько примеров, демонстрирующих использование меток вершин и ребер.

Вас также может заинтересовать пример кода JUNG ShortestPathDemo.

Смежные вопросы (по меткам вершин / ребер JUNG):

Метка вершины в визуализации графика JUNG

Как добавить пользовательские метки вершин в визуализацию графов JUNG?