Равенство краев графа Java - PullRequest
0 голосов
/ 04 августа 2020

Я создаю решение проблемы MST и столкнулся с проблемой: как логически представить равенство неориентированного взвешенного графа, т.е. два ребра равны, если они возникают из одних и тех же вершин и имеют одинаковые веса? Это верно? Кажется, это работает, однако мне трудно найти случаи, когда это не помогло бы.

@Override
public boolean equals(final Object o) {
    if (this == o) {
        return true;
    }
    if (!(o instanceof Edge)) {
        return false;
    }
    Edge<?> other = (Edge<?>) o;
    return areTheSame(other);
}

boolean areTheSame(Edge<?> other) {

    // Two edges are "the same" iff
    // V1 -> V2, weight X
    // V2 -> V1, weight X

    boolean symmetric = this.from.equals(other.from);
    boolean leftSym = this.to.equals(other.from);
    boolean rightSym = this.from.equals(other.to);
    boolean leftOtherSym = other.to.equals(this.from);
    boolean rightOtherSym = other.from.equals(this.to);

    boolean sameW = this.weight.equals(other.weight);

    boolean symmWeightSame = symmetric && sameW;

    boolean asymm = ((leftSym && rightSym) || (leftOtherSym && rightOtherSym)) && sameW;

    return asymm || symmWeightSame;
}
...