Как обратиться к пользовательским вершинам, чтобы добавить ребро, используя JGraphT

У меня есть график SimpleWeightedGraph<Vertex, DefaultWeightedEdge> g, где Vertex — это пользовательский класс. У меня есть все вершины и ребра в пространственной базе данных postgresql.
Мне нужно загрузить только их подмножество, чтобы найти путь из двух вершин, поэтому я использую некоторые запросы.

Класс Vertex имеет идентификатор String as и другие параметры, которые я загружаю из базы данных. Они нужны мне позже.

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

Теперь вопрос: как мне это сделать?

Вот некоторые выдержки из моего кода.

Класс Vertex:
(Я хочу, чтобы вершины были равны, если они имеют одинаковый идентификатор, и они упорядочены с тем же естественным порядком строк, по их идентификатору. Я хочу, чтобы это также возможно сделай vertex.equals("something"))

public class Vertex implements Comparable<Vertex>{
    private String id;      //identifier
    private double x;       //x in SRID 900913
    private double y;       //y in SRID 900913
    private String geom;    //geome in EWKT
    private int a;
    private int p;

    public Vertex(String id, double x, double y){
        [...constructor body...]
    }
    public Vertex(String id, Vertex v){
        [...constructor body...]
    }
    public Vertex(String id, double x, double y, int a, int p){
        [...constructor body...]
    }
    public Vertice(String id){
        this.id = id;
    }

    @Override
    public boolean equals(Object obj){
            boolean result;

            if (obj == this) {
                return true;
            }
            if (obj == null) {
                return false;
            }

            if (obj.getClass() != String.class)
            {
                if (obj.getClass() != this.getClass()) {
                    return false;
                }
                Vertex v = (Vertex) obj;
                result = this.id.equals(v.getId()); 
            }
            else
            {
                String s = (String) obj;
                result = this.id.equals(s);
            }

            return result;
    }

    @Override
    public int hashCode(){
        final int prime = 31;

        int result = 1;

        result = prime * result + ((id == null) ? 0 : id.hashCode());

        return result;
    }

    @Override
    public String toString(){
        return this.id;
    }

    public int compareTo(Vertex v){
        return this.id.compareTo(v.getId());
    }

    [...other methods...]
}


Выдержка из другой части кода, где я создаю вершины графа:

query = "select id_v, x, y from [table_name] where [conditions]";

rs = st.executeQuery(query);

while (rs.next())
{
    v = new Vertex("w"+rs.getInt("id_v"), rs.getDouble("x"), rs.getDouble("y"), start.getA(), 0);
    //start is a Vertex
    g.addVertex(v);
}

[...other parts of code like this one, but with different query...]


Теперь мне нужно создать ребро. Вот код:

query = "select v1, v2, weight from [table_name] where [conditions]";

rs = st.executeQuery(query);

DefaultWeightedEdge e;
String v1;
String v2;

while (rs.next())
{
    v1 = "w"+rs.getInt(1);    //source_vertex_of_edge.equals(v1) is true
    v2 = "w"+rs.getInt(2);    //target_vertex_of_edge.equals(v2) is true
    weight = rs.getDouble(3);

    //the next line doesen't work because addEdge wants (Vertex, Vertex) as parameter
    e = g.addEdge(v1, v2);

    g.setEdgeWeight(e, weight);
}


Я также пробовал:

query = "select v1, v2, weight from [table_name] where [conditions]";

rs = st.executeQuery(query);

DefaultWeightedEdge e;
Vertex v1;
Vertex v2;

while (rs.next())
{
    v1 = new Vertex("w"+rs.getInt(1));    //source_vertex_of_edge.equals(v1) is true
    v2 = new Vertex("w"+rs.getInt(2));    //target_vertex_of_edge.equals(v2) is true
    weight = rs.getDouble(3);

    e = g.addEdge(v1, v2);

    g.setEdgeWeight(e, weight);
}


Но это не работает: когда я добавляю ребро, исходная и целевая вершины (уже находящиеся в графе) теряют все параметры, кроме id.

Как я могу обратиться к ним? Спасибо.


person Merlinux    schedule 23.05.2014    source источник


Ответы (1)


Граф явно ничего не знает о id, которое вы храните в вершине. В частности, он не знает, что это "ключ", по которому Vertex объект должен быть идентифицирован позже. Невозможно «извлечь» существующую вершину из графа, когда известно только id вершины (за исключением повторения и проверки каждой вершины, что невозможно даже для относительно небольших графов)

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

Набросал здесь, примерно на основе вашего кода:

class TheClassThatLoadsTheGraph
{
    private final Map<String, Vertex> idToVertex =
        new LinkedHashMap<String, Vertex>();

    void readVertices()
    {
        ...
        rs = st.executeQuery(query);
        while (rs.next())
        {
            String id = "w"+rs.getInt("id_v");
            Vertex v = new Vertex(
                id, rs.getDouble("x"), rs.getDouble("y"), start.getA(), 0);
            g.addVertex(v);

            // Store the vertex in the map:
            idToVertex.put(id, v);
        }
    }

    void readEdges()
    {
        ...
        rs = st.executeQuery(query);
        while (rs.next())
        {
            String id1 = "w"+rs.getInt(1);
            String id1 = "w"+rs.getInt(2); 
            double weight = rs.getDouble(3);

            // Use the ids to look up the matching vertices
            Vertex v1 = idToVertex.get(id1);
            Vertex v2 = idToVertex.get(id2);
            DefaultWeightedEdge e = g.addEdge(v1, v2);

            g.setEdgeWeight(e, weight);
        }
    } 
}

ЗАМЕТКА:

Вы упомянули, что хотите особого поведения для метода equals:

Я хочу, чтобы также можно было сделать vertex.equals("что-то"))

Это невозможно без серьезного нарушения контракта метода equals. Если бы вы могли это сделать, вы также должны были бы убедиться, что

"something".equals(vertex);

но это явно не так. Равенство — очень сильная концепция, и детали правильной реализации метода equals могут быть непростыми. Чего бы вы там ни хотели добиться: попробуйте найти для этого другой подход! (Возможно, карта idToVertex из приведенного выше фрагмента кода также может быть полезна здесь...)

person Marco13    schedule 23.05.2014
comment
Большое спасибо, это то, что я ищу. Я также изменил метод equals. Теперь vertex.equals("something") больше не доступен и возвращает false: с Map он мне больше не нужен. - person Merlinux; 24.05.2014