Введение в график

1. Обзор

В большинстве случаев, когда мы реализуем алгоритмы на основе графов, нам также необходимо реализовать некоторые полезные функции.

JGraphT -это библиотека классов Java с открытым исходным кодом, которая не только предоставляет нам различные типы графов, но и множество полезных алгоритмов для решения наиболее часто встречающихся графовых задач.

В этой статье мы рассмотрим, как создавать различные типы графиков и насколько удобно использовать предоставляемые утилиты.

2. Зависимость Maven

Давайте начнем с добавления зависимости в наш проект Maven:


    org.jgrapht
    jgrapht-core
    1.0.1

Последнюю версию можно найти в Maven Central .

3. Создание графиков

JGraphT поддерживает различные типы графиков.

3.1. Простые графики

Для начала давайте создадим простой граф с вершиной типа String :

Graph g 
  = new SimpleGraph<>(DefaultEdge.class);
g.addVertex("v1");
g.addVertex("v2");
g.addEdge(v1, v2);

3.2. Направленные/Неориентированные графики

Это также позволяет нам создавать направленные/неориентированные графики.

В нашем примере мы создадим ориентированный граф и будем использовать его для демонстрации других функций полезности и алгоритмов:

DirectedGraph directedGraph 
  = new DefaultDirectedGraph<>(DefaultEdge.class);
directedGraph.addVertex("v1");
directedGraph.addVertex("v2");
directedGraph.addVertex("v3");
directedGraph.addEdge("v1", "v2");
// Add remaining vertices and edges

3.3. Полные графики

Аналогично, мы также можем сгенерировать полный график:

public void createCompleteGraph() {
    completeGraph = new SimpleWeightedGraph<>(DefaultEdge.class);
    CompleteGraphGenerator completeGenerator 
      = new CompleteGraphGenerator<>(size);
    VertexFactory vFactory = new VertexFactory() {
        private int id = 0;
        public String createVertex() {
            return "v" + id++;
        }
    };
    completeGenerator.generateGraph(completeGraph, vFactory, null);
}

3.4. Мультиграфы

Помимо простых графов, API также предоставляет нам мультиграфы (графики с несколькими путями между двумя вершинами).

Кроме того, мы можем иметь взвешенные/невзвешенные или определенные пользователем ребра в любом графике.

Давайте создадим мультиграф с взвешенными ребрами:

public void createMultiGraphWithWeightedEdges() {
    multiGraph = new Multigraph<>(DefaultWeightedEdge.class);
    multiGraph.addVertex("v1");
    multiGraph.addVertex("v2");
    DefaultWeightedEdge edge1 = multiGraph.addEdge("v1", "v2");
    multiGraph.setEdgeWeight(edge1, 5);

    DefaultWeightedEdge edge2 = multiGraph.addEdge("v1", "v2");
    multiGraph.setEdgeWeight(edge2, 3);
}

В дополнение к этому, мы можем иметь немодифицируемые (только для чтения) и прослушиваемые (позволяет внешним слушателям отслеживать изменения) графики, а также подграфы. Кроме того, мы всегда можем создать все композиции этих графиков.

Более подробную информацию об API можно найти здесь .

4. Алгоритмы API

Теперь, когда у нас есть полные объекты графа оперения, давайте рассмотрим некоторые общие проблемы и их решения.

4.1. Итерация графика

Мы можем пересечь график, используя различные итераторы, такие как widthfirstiterator , DepthFirstIterator , ClosestFirstIterator , RandomWalkIterator в соответствии с требованиями.
Нам просто нужно создать экземпляр соответствующих итераторов, передав объекты графа:

DepthFirstIterator depthFirstIterator 
  = new DepthFirstIterator<>(directedGraph);
BreadthFirstIterator breadthFirstIterator 
  = new BreadthFirstIterator<>(directedGraph);

Как только мы получим объекты итератора, мы сможем выполнить итерацию с помощью методов hasNext() и next () .

4.2. Нахождение кратчайшего пути

Он предоставляет реализации различных алгоритмов, таких как Dijkstra, Bellman-Ford, A star и Floyd Warshall в пакете org.jgrapht.alg.shortestpath .

Давайте найдем кратчайший путь, используя алгоритм Дейкстры:

@Test
public void whenGetDijkstraShortestPath_thenGetNotNullPath() {
    DijkstraShortestPath dijkstraShortestPath 
      = new DijkstraShortestPath(directedGraph);
    List shortestPath = dijkstraShortestPath
      .getPath("v1","v4").getVertexList();
 
    assertNotNull(shortestPath);
}

Аналогично, чтобы получить кратчайший путь, используя алгоритм Беллмана-Форда:

@Test
public void 
  whenGetBellmanFordShortestPath_thenGetNotNullPath() {
    BellmanFordShortestPath bellmanFordShortestPath 
      = new BellmanFordShortestPath(directedGraph);
    List shortestPath = bellmanFordShortestPath
      .getPath("v1", "v4")
      .getVertexList();
 
    assertNotNull(shortestPath);
}

4.3. Нахождение Сильно Связанных Подграфов

Прежде чем мы перейдем к реализации, давайте кратко рассмотрим, что означают сильно связанные подграфы. Подграф считается сильно связанным только в том случае, если между каждой парой его вершин существует путь.

В нашем примере {v1, v2,v3,v4} можно считать сильно связанным подграфом,если мы можем перейти к любой вершине, независимо от того, какова текущая вершина.

Мы можем перечислить четыре таких подграфа для ориентированного графа, показанного на рисунке выше: {v9}, {v8},{v5,v6,v7},{v1,v2,v3,v4}

Реализация для перечисления всех сильно связанных подграфов:

@Test
public void 
  whenGetStronglyConnectedSubgraphs_thenPathExists() {

    StrongConnectivityAlgorithm scAlg 
      = new KosarajuStrongConnectivityInspector<>(directedGraph);
    List> stronglyConnectedSubgraphs 
      = scAlg.stronglyConnectedSubgraphs();
    List stronglyConnectedVertices 
      = new ArrayList<>(stronglyConnectedSubgraphs.get(3)
      .vertexSet());

    String randomVertex1 = stronglyConnectedVertices.get(0);
    String randomVertex2 = stronglyConnectedVertices.get(3);
    AllDirectedPaths allDirectedPaths 
      = new AllDirectedPaths<>(directedGraph);

    List> possiblePathList 
      = allDirectedPaths.getAllPaths(
        randomVertex1, randomVertex2, false,
          stronglyConnectedVertices.size());
 
    assertTrue(possiblePathList.size() > 0);
}

4.4. Эйлерова схема

Эйлерова схема в графе G – это схема, которая включает в себя все вершины и ребра G . Граф, у которого он есть, является эйлеровым графом.

Давайте взглянем на график:

public void createGraphWithEulerianCircuit() {
    SimpleWeightedGraph simpleGraph 
      = new SimpleWeightedGraph<>(DefaultEdge.class);
    IntStream.range(1,5)
      .forEach(i-> simpleGraph.addVertex("v" + i));
    IntStream.range(1,5)
      .forEach(i-> {
        int endVertexNo = (i + 1) > 5 ? 1 : i + 1;
        simpleGraph.addEdge("v" + i,"v" + endVertexNo);
    });
}

Теперь мы можем проверить, содержит ли граф эйлерову схему, используя API:

@Test
public void givenGraph_whenCheckEluerianCycle_thenGetResult() {
    HierholzerEulerianCycle eulerianCycle 
      = new HierholzerEulerianCycle<>();
 
    assertTrue(eulerianCycle.isEulerian(simpleGraph));
}
@Test
public void whenGetEulerianCycle_thenGetGraphPath() {
    HierholzerEulerianCycle eulerianCycle 
      = new HierholzerEulerianCycle<>();
    GraphPath path = eulerianCycle.getEulerianCycle(simpleGraph);
 
    assertTrue(path.getEdgeList()
      .containsAll(simpleGraph.edgeSet()));
}

4.5. Гамильтонова цепь

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

Гамильтонов цикл (или гамильтонова цепь) – это гамильтонов путь, такой, что существует ребро (в графе) от последней вершины до первой вершины пути.

Мы можем найти оптимальный гамильтонов цикл для полного графа с помощью Гамильтонова цикла.getApproximateOptimalForCompleteGraph() метод.

Этот метод вернет приблизительный минимальный тур коммивояжера (гамильтонов цикл). Оптимальное решение является NP-полным, поэтому это приличное приближение, которое выполняется за полиномиальное время:

public void 
  whenGetHamiltonianCyclePath_thenGetVerticeSequence() {
    List verticeList = HamiltonianCycle
      .getApproximateOptimalForCompleteGraph(completeGraph);
 
    assertEquals(verticeList.size(), completeGraph.vertexSet().size());
}

4.6. Детектор циклов

Мы также можем проверить, есть ли какие-либо циклы на графике. В настоящее время Детектор циклов поддерживает только направленные графики:

@Test
public void whenCheckCycles_thenDetectCycles() {
    CycleDetector cycleDetector 
      = new CycleDetector(directedGraph);
 
    assertTrue(cycleDetector.detectCycles());
    Set cycleVertices = cycleDetector.findCycles();
 
    assertTrue(cycleVertices.size() > 0);
}

5. Визуализация графика

JGraphT позволяет нам создавать визуализации графиков и сохранять их в виде изображений , сначала давайте добавим зависимость расширения jgrapht-ext от Maven Central:


    org.jgrapht
    jgrapht-ext
    1.0.1

Далее, давайте создадим простой ориентированный граф с 3 вершинами и 3 ребрами:

@Before
public void createGraph() {

    File imgFile = new File("src/test/resources/graph.png");
    imgFile.createNewFile();

    DefaultDirectedGraph g = 
      new DefaultDirectedGraph(DefaultEdge.class);

    String x1 = "x1";
    String x2 = "x2";
    String x3 = "x3";

    g.addVertex(x1);
    g.addVertex(x2);
    g.addVertex(x3);

    g.addEdge(x1, x2);
    g.addEdge(x2, x3);
    g.addEdge(x3, x1);
}

Теперь мы можем визуализировать этот график:

@Test
public void givenAdaptedGraph_whenWriteBufferedImage_thenFileShouldExist() throws IOException {

    JGraphXAdapter graphAdapter = 
      new JGraphXAdapter(g);
    mxIGraphLayout layout = new mxCircleLayout(graphAdapter);
    layout.execute(graphAdapter.getDefaultParent());
    
    BufferedImage image = 
      mxCellRenderer.createBufferedImage(graphAdapter, null, 2, Color.WHITE, true, null);
    File imgFile = new File("src/test/resources/graph.png");
    ImageIO.write(image, "PNG", imgFile);

    assertTrue(imgFile.exists());
}

Здесь мы создали JGraphXAdapter , который получает наш график в качестве аргумента конструктора, и мы применили к нему mxCircleLayout . Это создает визуализацию в круговом порядке.

Кроме того, мы используем mxCellRenderer для создания BufferedImage , а затем записываем визуализацию в файл png.

Мы можем увидеть окончательное изображение в браузере или в вашем любимом рендере:

Более подробную информацию мы можем найти в официальной документации .

6. Заключение

JGraphT предоставляет почти все типы графиков и различные алгоритмы графов. Мы рассмотрели, как использовать несколько популярных API. Однако вы всегда можете ознакомиться с библиотекой на официальной странице /.

Реализацию всех этих примеров и фрагментов кода можно найти на Github .