хранение ребер в структуре данных

Question

У меня есть класс с именем Edge, который имеет идентификатор источника атрибута, идентификатор цели и вес.Я хочу сохранить это ребро в заданной структуре данных, чтобы в наборе не было дубликатов ребер (т.е. ребер с одинаковым исходным и целевым идентификаторами).

Проблема заключается в следующем: я хочу добавить Edge к этой структуре данных.Если ребро уже существует в структуре данных, мне не нужно добавлять его снова, мне просто нужно добавить вес существующего ребра с ребром, которое я пытаюсь добавить.

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

Answer 1

Несколько предложений.

Основная структура данных, которую вы хотите, - это, вероятно, карта (с HashMap, вероятно, лучшая конкретная реализация), а не набор.Ключ должен быть парой (источник, цель), а значением может быть ваш объект Edge.Если вас очень беспокоит дублирование, есть способы борьбы с этим, один из которых заключается в том, чтобы на самом деле хранить только вес в качестве значения.

Во-вторых, это вызов класса Graph.Если вы хорошо спроектировали интерфейс, он скрывает внутренние детали реализации.Я настоятельно рекомендую использовать композицию, а не наследование.Другими словами, у вашего Графа есть карта, а не карта.

Также взгляните на существующий код, такой как JGraphT , который уже имеет взвешенный ориентированный граф,тот же зверь, что вы описали выше.Иногда лучше не изобретать вещи с нуля.

Удачи.

Answer 2

Что ж, метод Set.add () возвращает логическое значение, указывающее, был ли новый элемент успешно добавлен в набор. Если он возвращает false, это потому, что элемент уже был там. Исходя из этого, вы можете легко написать свой алгоритм. Уродливой части приходится повторять набор для обновления значения, верно?

if(!edges.add(newEdge)){
   Iterator<Edge> iter = edges.iterator();
   while(iter.hasNext()){
    Edge edge = iter.next();
    if(edge.equals(newEdge)){
        edge.updateWeight(newEdge.getWeight()); //this.weight+=moreWeight
    }
   }
}

Исходя из этого, я предполагаю, что то, что вы хотите, это просто способ украсить весь этот итерационный шаблонный код.

Мне нравится решение, использующее LambdaJ Collections для обновления веса существующего Edge.

if (!edges.add(newEdge)) {
   with(edges).first(is(newEdge)).updateWeight(newEdge.getWeight());
}

Я не знаю, что вы ищете, но такой подход будет состоять из трех строк кода. Довольно просто с моей точки зрения.

Я написал небольшой пример, чтобы лучше проиллюстрировать идею:

Jedi obiwan = new Jedi("Obiwan", 30, 40); // name, age and power
Jedi luke = new Jedi("Luke", 18, 25);
Jedi mace = new Jedi("Mace-Windu", 100, 450);
Jedi yoda = new Jedi("Yoda", 150, 1000);

Jedi obiAgain = new Jedi("Obiwan", 11, 40);

Set<Jedi> jedis = new HashSet<Jedi>(asList(obiwan, luke, mace, yoda));

if (!jedis.add(obiAgain)) {
     with(jedis).first(is(obiAgain)).updatePower(obiAgain.getPower());
}

System.out.println(jedis);

Answer 3

Альтернативой является обертывание набора ребер в вашем собственном классе, который предоставляет именно тот интерфейс, который вы хотите поддерживать.

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

Например, вот примерный набросок возможного класса (РЕДАКТИРОВАТЬ: используя Карту)

   public class Edge { ... }

   public class EdgeData { 
       public Edge getEdge() { ... }
       public float getWeight() { ... }
   }

   public class Edges {
       private Map<Edge,EdgeData> m_edges = new HashMap<Edge,EdgeData>();
       public addEdge( EdgeData edge ) { 
            // Do what you've said above.

       }
       public Map<Edge,EdgeData> getEdges() { return Collections.unmodifiableMap( m_edges ); }
   }