Определение вершин и ребер на основе элементов матрицы и библиотеки jgrapht

У меня есть матрица, представляющая сетку, состоящую из 0, 1 и 2. Существует 0, когда в сетке нет ни одного элемента, 1, когда есть элемент, который можно переместить, и 2, когда это элемент, который нельзя переместить.

Например:

0 0 0 0 2 2 0 0 0 0 
0 0 1 1 2 2 1 1 1 0 
0 0 1 0 0 0 1 0 1 0 
0 0 1 0 0 0 1 1 1 0 
0 0 1 1 1 1 1 0 0 0 
0 0 0 0 1 0 1 0 0 0 
0 0 0 0 1 1 1 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 0 0

Я хотел бы превратить это в ориентированный граф, где каждая 1 является вершиной, а ребра - это связи между двумя вершинами. Для этого я хочу использовать библиотеку jgrapht, и я пытаюсь использовать их демонстрационный код:

package org.jgrapht.demo;

import java.util.*;

import org.jgrapht.*;
import org.jgrapht.generate.*;
import org.jgrapht.graph.*;
import org.jgrapht.traverse.*;


public final class CompleteGraphDemo
{


    static Graph<Object, DefaultEdge> completeGraph;

    //Number of vertices
    static int size = 10;



    public static void main(String [] args)
    {
        //Create the graph object; it is null at this point
        completeGraph = new SimpleGraph<Object, DefaultEdge>(DefaultEdge.class);

        //Create the CompleteGraphGenerator object
        CompleteGraphGenerator<Object, DefaultEdge> completeGenerator =
            new CompleteGraphGenerator<Object, DefaultEdge>(size);

        //Create the VertexFactory so the generator can create vertices
        VertexFactory<Object> vFactory =
            new ClassBasedVertexFactory<Object>(Object.class);

        //Use the CompleteGraphGenerator object to make completeGraph a
        //complete graph with [size] number of vertices
        completeGenerator.generateGraph(completeGraph, vFactory, null);

        //Now, replace all the vertices with sequential numbers so we can ID
        //them
        Set<Object> vertices = new HashSet<Object>();
        vertices.addAll(completeGraph.vertexSet());
        Integer counter = 0;
        for (Object vertex : vertices) {
            replaceVertex(vertex, (Object) counter++);
        }

        //Print out the graph to be sure it's really complete
        Iterator<Object> iter =
            new DepthFirstIterator<Object, DefaultEdge>(completeGraph);
        Object vertex;
        while (iter.hasNext()) {
            vertex = iter.next();
            System.out.println(
                "Vertex " + vertex.toString() + " is connected to: "
                + completeGraph.edgesOf(vertex).toString());
        }
    }

    public static boolean replaceVertex(Object oldVertex, Object newVertex)
    {
        if ((oldVertex == null) || (newVertex == null)) {
            return false;
        }
        Set<DefaultEdge> relatedEdges = completeGraph.edgesOf(oldVertex);
        completeGraph.addVertex(newVertex);

        Object sourceVertex;
        Object targetVertex;
        for (DefaultEdge e : relatedEdges) {
            sourceVertex = completeGraph.getEdgeSource(e);
            targetVertex = completeGraph.getEdgeTarget(e);
            if (sourceVertex.equals(oldVertex)
                && targetVertex.equals(oldVertex))
            {
                completeGraph.addEdge(newVertex, newVertex);
            } else {
                if (sourceVertex.equals(oldVertex)) {
                    completeGraph.addEdge(newVertex, targetVertex);
                } else {
                    completeGraph.addEdge(sourceVertex, newVertex);
                }
            }
        }
        completeGraph.removeVertex(oldVertex);
        return true;
    }
}

// End CompleteGraphDemo.java

Однако этот код создает случайный орграф на основе количества вершин, объявленных с помощью size, тогда как мне нужно добавить элементы матрицы (1s) в качестве вершин, а затем использовать программу для создания орграфа и возврата количества циклов (в матрица выше будет 3 цикла).

Я не могу понять, как заменить строку:

completeGenerator.generateGraph(completeGraph, vFactory, null);

взять на вход элементы матрицы. Кто-нибудь знает как это сделать ? (Я использую обработку, основанную на java)


person Graham Slick    schedule 24.07.2015    source источник


Ответы (1)


Хотя неясно, что именно вы хотите сделать (что происходит с двойками? какие ребра соединены? это полный граф? какое это имеет отношение к сетке?), ответ на ваш вопрос, вероятно, не использовать готовый процесс. Да, метод в примере создает полный график, как следует из его названия, в чем я не уверен. как указано выше, это то, что вы хотите.

Что вы можете сделать, так это обработать матрицу самостоятельно и использовать другие методы в этой библиотеке, чтобы вручную добавить вершины и ребра, такие как в одном из примеров на домашняя страница библиотеки (адаптировано здесь, чтобы создать направленный граф строк и распечатать его)

    DirectedGraph<String, DefaultEdge> g =
        new DefaultDirectedGraph<String, DefaultEdge>(DefaultEdge.class);

    String v1 = "v1";
    String v2 = "v2";
    String v3 = "v3";
    String v4 = "v4";

    // add the vertices
    g.addVertex(v1);
    g.addVertex(v2);
    g.addVertex(v3);
    g.addVertex(v4);

    // add edges to create a circuit
    g.addEdge(v1, v2);
    g.addEdge(v2, v3);
    g.addEdge(v3, v4);
    g.addEdge(v4, v1);


    //Print the edges
    Iterator<String> iter =
        new DepthFirstIterator<String, DefaultEdge>(g);
    String vertex;
    while (iter.hasNext()) {
        vertex = iter.next();
        System.out.println(
            "Vertex " + vertex + " is connected to: "
            + g.edgesOf(vertex));
    }

Дополнительное примечание: обратите внимание, что в этом примере тип узла — «String». Это может быть любой не-примитивный тип или новый класс. Например, я прикрепляю ниже тот же код для «Целое число».

    DirectedGraph<Integer, DefaultEdge> g =
        new DefaultDirectedGraph<Integer, DefaultEdge>(DefaultEdge.class);

    Integer v1 = 2367;
    Integer v2 = 56799;
    Integer v3 = 78678;
    Integer v4 = 343;

    // add the vertices
    g.addVertex(v1);
    g.addVertex(v2);
    g.addVertex(v3);
    g.addVertex(v4);

    // add edges to create a circuit
    g.addEdge(v1, v2);
    g.addEdge(v2, v3);
    g.addEdge(v3, v4);
    g.addEdge(v4, v1);

    //Print out the graph to be sure it's really complete
    Iterator<Integer> iter =
        new DepthFirstIterator<Integer, DefaultEdge>(g);
    Integer vertex;
    while (iter.hasNext()) {
        vertex = iter.next();
        System.out.println(
            "Vertex " + vertex + " is connected to: "
            + g.edgesOf(vertex));
    }
person Petros Koutsolampros    schedule 24.07.2015
comment
Будет ли это работать, если я захочу создать вершины на основе пары координат (округленных до целых)? Я пробовал DirectedGraph‹Integer, Integer, DefaultEdge› g = new DefaultDirectedGraph‹Integer, Integer, DefaultEdge›(DefaultEdge.class); Но я получаю сообщение об ошибке, говорящее о том, что это неправильное количество аргументов для типа DirectedGraph (V, E) - person Graham Slick; 25.07.2015
comment
В этом случае вам не нужно создавать класс с двумя целыми числами и использовать новый класс или просто использовать PVector. - person Petros Koutsolampros; 25.07.2015
comment
Смогу ли я использовать функции jgrapht, если создам новый класс? Как мне создать его, чтобы иметь возможность использовать, например, DijkstraShortestPath и cycledetector? Они оба не принимают координаты в качестве параметров. Должен ли я создать класс и определить объект Point с двумя параметрами типа int, а затем выполнить следующие действия: DirectedGraph‹ Point, DefaultEdge› g = new DefaultDirectedGraph‹Point, DefaultEdge›(DefaultEdge.class); ? - person Graham Slick; 25.07.2015
comment
Лучший ответ, который я могу вам дать: попробуйте несколько вещей, и если вы застряли, вернитесь и задайте другой вопрос :) - person Petros Koutsolampros; 25.07.2015