重み付き有向グラフを作成する必要があります。私が見た実装は、頂点を単純な整数として表し、エッジは隣接リストで表されます。しかし、私はカスタムクラスのオブジェクトによって表される頂点が必要です。このグラフでは、一般的な操作(具体的にはDijkstra)を実行する必要があります。Java:頂点がOBJECTSである加重指向グラフ
私のアイデアは何とかオブジェクトを整数として表現していましたが、両方向に変換できるハッシュ関数(頂点からint、頂点からint)を考え出す方法はわかりません。
重み付き有向グラフを作成する必要があります。私が見た実装は、頂点を単純な整数として表し、エッジは隣接リストで表されます。しかし、私はカスタムクラスのオブジェクトによって表される頂点が必要です。このグラフでは、一般的な操作(具体的にはDijkstra)を実行する必要があります。Java:頂点がOBJECTSである加重指向グラフ
私のアイデアは何とかオブジェクトを整数として表現していましたが、両方向に変換できるハッシュ関数(頂点からint、頂点からint)を考え出す方法はわかりません。
グラフ内で頂点を(一意の)整数として表現したい場合は、ArrayList
を使用して頂点からオブジェクトにマッピングし、HashMap<MyObject, Integer>
を使用してマップし直すことができます。このペアを独自のクラスにラップして、getIndex()
とgetElement()
(下図)を作成すると、可読性が向上する可能性があります。
それでは、なぜhttp://jgrapht.orgまたはそれに類するライブラリを使用しないのですか?
public class IndexMap<T> {
private List<T> elements = new ArrayList<>();
private Map<T, Integer> indices = new HashMap<>();
public int add(T element) {
int index = elements.size();
elements.add(element);
indices.put(element, index);
return index;
}
public int getIndex(T element) {
Integer index = indices.get(element);
return index == null ? -1 : index;
}
public T getElement(int index) {
return elements.get(index);
}
あなたは、既存の整数ベースのグラフを使用して、ライブラリを使用することはできません(再)する必要がない場合は、あなたが代わりに店よりオブジェクトを、独自の頂点クラスを実装することができます:
class Vertex<T> {
T element;
List<Vertex<T>> edges = new ArrayList<>();
Vertex(T element) {
this.element = element;
}
void addEdge(Vertex<t> to) {
edges.add(to);
}
...
}
学校の割り当てですが、そのライブラリを使用できるかどうかはわかりません。私の問題は、私のオブジェクト(2つの文字列)を一意のintにマップする関数を使用していましたが、逆も可能です。 –
ああ、そのIndexMapは理にかなっています。ありがとう。 –