Как мне организовать этот код (ООП, интерфейс)

Question

Я пытаюсь создать структуру для графика. Пока что я пытаюсь придумать, как создать классы для ребер.

Края на графиках могут быть

Regular, Направленный, взвешенный (или любой из вышеперечисленных).

Так что, как вы думаете, лучший способ организовать этот класс, я думал о создании интерфейса IEdge, а затем создать классы

public interface IEdge{
}

public class DirectedEdge implements IEdge{}
public class WeightedEdge implements IEdge{}

Но теперь у меня возникла проблема, она не очень гибкая, что если мне нужно следующее

public class DirectedWeightedEdge implements IEdge{}

Как бы вы это закодировали?

Answer 1

Это не упражнение ООП - я имею в виду, сначала используйте логику, а затем посмотрите на паттерны.Направленные и неориентированные графы очень разные звери.Направленный край имеет начало и конец, а ненаправленный - только два узла.Вы можете назвать их началом и концом, чтобы получить общую базу, но нет такой вещи, как направленность , которая будет добавлена ​​к ребру.

В то же время ребра могут иметь цвета, веса, цены, длина, вместимость и т. д. Вы действительно хотите реализовать ColoredWeightedPricedHavingLenghtCapacityLimitedEdge?Или вы хотите использовать 5 декораторов?Надеюсь, вы этого не сделаете.

Мое первое замечание: «направленность» не вписывается ни в одну модель.Вы можете использовать атрибут isDirected или любой другой, и, возможно, он вам вообще не нужен, так как большинство графиков не смешивают разные виды ребер.Таким образом, один атрибут на Graph должен делать.Довольно часто ненаправленное ребро представляется парой двух направленных.

Мое второе замечание заключается в том, что такие вещи, как вес, как правило, не должны принудительно вставляться в ребро.Использование Map<IEdge, Double> в качестве свойства Graph делает работу лучше.Вы по-прежнему можете использовать такие объекты, как Edge и Node, что исключает путаницу с ними (что может легко произойти в C, когда вы, вероятно, используете их id s), но сохраняете их свойства внешними.

Answer 2

Зачем вам вообще явно создавать ребра?В каждой реализации графа, которую я делал до сих пор, ребра существовали просто неявно в объектах узла.В каждом узле вам нужен массив смежных узлов - если вам нужно, чтобы они взвешивались, просто добавьте целое число.

Направление также вполне естественно следует из этого (хорошо, двунаправленный граф легко представляется однонаправленным).).Очевидно, что вы также можете сохранить их как матрицу смежности, если график достаточно мал - это очень хорошо для параллельных алгоритмов ... но тогда, если важна производительность, мы говорим о размерах, где полная матрица не может использоваться.

Изменить: После комментариев, я думаю, я должен уточнить, что немного: Использование класса Edge, который хранит дополнительную информацию о крае (цвет, вес), хорошо, но я всегда буду использовать его как часть определенного узла: Т.е. что-то вроде этого- в C я бы использовал структуру для этого.

class Node {
    List<Edge> children;

    class Edge {
        int weight;
        Color color;
        Node dest;
    }
}

Answer 3

Я бы использовал смесь наследования и вышеупомянутого шаблона декоратора.

Направленные и ненаправленные ребра ведут себя совершенно по-разному, они являются обязательными и взаимоисключающими. Поэтому они должны быть единственными двумя реализациями интерфейса Edge.

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

Но вернемся на минутку к квадрату, в зависимости от того, сколько будет иметь направленный и ненаправленный ребер совместно используемого кода, возможно, абстрактный класс Edge будет лучше интерфейса. Конечно, «правильное» решение состоит в том, чтобы иметь и то и другое: интерфейс, реализованный абстрактным классом, расширенный двумя конкретными классами. Но в этом случае это звучит как переобучение.

Answer 4

Вы можете отделить информацию о границе от информации о смежности.Это означает, что вы не дублируете данные ребер и вместо этого сохраняете их в списке смежности.

public class Node<TEdge> {
    class AdjacencyInfo {
       Node<TEdge> node;
       TEdge edge;

       public AdjacencyInfo(Node<TEdge> node, TEdge edge) {
          // ....
       }
    }

    bool isDiGraph; 
    List<AdjacencyInfo> adj;
    ///.... constructor, other methods

    public TEdge ConnectTo(Node<TEdge> node) {
       TEdge e = new TEdge();
       AdjacencyInfo a0 = new AdjacencyInfo(node, e);
       this.adj.Add(a0);
       if (!isDiGraph) {
           AdjacencyInfo a1 = new AdjacencyInfo(this, e);
           node.adj.Add(a1);
       }
       return e; // return the edge so caller is able to set edge properties (weight, color, etc)
    }
}

Нечто подобное должно работать и четко решает направленную / ненаправленную проблему.Я не знаю, сколько из этого может быть достигнуто с помощью обобщений Java, так как они в основном непригодны для других целей, кроме предотвращения типов в контейнерах, но в случае, если вам нужно обрабатывать только взвешенные ребра, вы можете избежать обобщений с помощьюустановка веса на 1 или что-то еще имеет смысл.

Answer 5

один тип, с двумя свойствами

type Edge
    boolean directed = false;
    number  weight = 1;

Answer 6

Использование шаблона декоратора может быть уместным здесь: http://en.wikipedia.org/wiki/Decorator_pattern

По сути, у вас будет базовый класс, реализующий IEdge, и классы DirectedEdgeDecorator и WeightedEdgeDecorator, которые также реализуют интерфейс IEdge. Классы * Decorator «обернут» базовый класс ребер и добавят к нему дополнительную функциональность. С помощью этого шаблона вы можете размещать несколько декораторов в IEdge, один поверх другого, чтобы по-разному изменять его поведение.