2

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

Vertex 类有一个Stringas 标识符和我从 db 加载的其他参数。我以后需要它们。

我首先用一些查询加载所有需要的顶点。在第二次我添加边（与其他查询），但我需要参考已经在图中的顶点。

现在的问题是：我怎样才能做到这一点？

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

Vertex 类：（
如果 Vertex 具有相同的 id，我希望它们是相等的，并且它们按照它们的 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 之外的所有参数。

我如何参考它们？谢谢。

4

1 回答 1

2

该图并不明确知道id您存储在顶点中的任何内容。特别是，它不知道这是Vertex以后应该识别对象的“关键”。当仅知道顶点的 时，无法从图中“提取”现有顶点id（迭代和检查每个顶点除外 - 即使对于相对较小的图也不可行）

一个非常简单实用的解决方案是将所有顶点存储在地图中。这样，您只需查找给定 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("something"))

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

"something".equals(vertex);

但这显然不是这样。平等是一个非常强大的概念，正确实施该equals方法的细节可能很棘手。无论您打算在那里实现什么：尝试为此找到不同的方法！（也许idToVertex上面代码片段中的地图在这里也可能会有所帮助......）

于 2014-05-23T23:33:14.320 回答