java - 如何使用 JGraphT 引用自定义顶点来添加边

Question

我有一个图表 SimpleWeightedGraph<Vertex, DefaultWeightedEdge> g其中 Vertex 是自定义类。我在 postgresql 空间数据库中拥有所有顶点和边。
我只需要加载它们的一个子集，以从两个顶点找到一条路径，因此我使用了一些查询。

Vertex 类有一个 String作为我从数据库加载的标识符和其他参数。我稍后需要它们。

我首先使用一些查询加载所有需要的顶点。第二次我添加了边(使用其他查询)，但我需要引用图中已经存在的顶点。

现在的问题是:我该怎么做？

这是我的代码的一些摘录。

Vertex 类:
(如果 Vertex 具有相同的 ID，我希望 Vertex 是相等的，并且它们的排序与字符串的自然顺序相同，按它们的 ID。我希望也可以做 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 之外的所有参数。

如何引用它们？谢谢。

Answer 1

该图并没有明确知道您存储在顶点中的 id 的任何信息。特别是，它不知道这是以后识别Vertex 对象的“键”。当只有顶点的 id 已知时，无法从图中“提取”现有顶点(除了迭代和检查每个顶点 - 即使对于相对较小的图也是不可行的)

一个非常简单实用的解决方案是将所有顶点存储在 map 中。这样，您只需查找给定 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 方法具有特殊行为:

I want it's also possible do vertex.equals("something"))

如果不严重违反 equals 方法的约定，这是不可能可能的。如果你能做到这一点，你还必须确保

"something".equals(vertex);

但显然不是这样的。平等是一个非常强大的概念，正确实现 equals 方法的细节可能很棘手。无论您打算在那里实现什么:尝试为此寻找不同的方法! (也许上述代码片段中的 idToVertex 映射在这里也有帮助...)