Структура данных графика

Question

Допустим, у меня есть MyClass{ private LargeMatrix mtrx; hashCode(){...}}

JGraphT (возможно, все структуры данных Graph), похоже, использует Hash-таблицу для отображения вершин. Так повлияет ли это на скорость, когда я использую MyClass вместо String l1,l2,l3?

Какие плюсы и минусы в этом случае? Должен ли я переопределить хэш-код (удалить хэш-код матрицы)? Есть ли график, который использует ссылки вместо хеш-таблицы?

так Мой код был:

package ann;

import org.jgrapht.DirectedGraph;
import org.jgrapht.graph.DefaultEdge;
import org.jgrapht.graph.SimpleDirectedGraph;

/**
 * @author marmoush
 * 
 */
public class Network
{
    DirectedGraph<String, DefaultEdge>  diGraph;
    String l1="hello1";
    String l2="hello1";
    String l3="hello3";
    /**
     * 
     */
    public Network()
    {

        diGraph = new SimpleDirectedGraph<String, DefaultEdge>(DefaultEdge.class);
        diGraph.addVertex(l1);
        diGraph.addVertex(l2);
        diGraph.addVertex(l3);

        diGraph.addEdge(l1, l2);
        System.out.println(diGraph.containsEdge(l1,l2));
        // TODO Auto-generated constructor stub
    }

}


Exception in thread "main" java.lang.IllegalArgumentException: loops not allowed
    at org.jgrapht.graph.AbstractBaseGraph.addEdge(Unknown Source)
    at ann.Network.<init>(Network.java:28)
    at test.TestNetwork.main(TestNetwork.java:9)

Потому что (я думаю) l1.hashCode()==l2.hashCode()

EDIT: Иногда матрицы могут быть нулями или единицами, они меняются со временем, поэтому я бы попытался придумать что-то, что отличает эти объекты, и это кажется глупым решением. Почему граф не может просто выбрать вершины по положению в векторе или чем-то еще?

Должен ли я заново изобрести колесо? с графиком, который использует Векторы вместо хеш-таблиц? или есть работа вокруг?

Answer 1

Я бы создал класс Vertex и соответственно реализовал equals() и hashcode(). Влияние скорости не так велико, оно может быть даже быстрее, если идентификатор вершины числовой.

Answer 2

Проблема в том, что этот тип графиков не допускает циклов. Вы должны изменить тип графика на AbstractBaseGraph, где вы можете установить переменную loopAllowed на true, или вы можете попробовать изменить эту переменную в вашем SimpleDirectedGraph.

Проблема: мне не удалось изменить переменную в SimpleDirectedGraph, но вы можете использовать другие типы графиков, которые позволяют вам это делать.

Я надеюсь, что смогу вам помочь.

Answer 3

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

Вот почему вы получаете исключение цикла. Я подозреваю, что вам нужна структура неориентированного графа.

Для справки см. Спецификацию языка Java , раздел 3.10.5 :

• Литеральные строки в одном классе (§8) в одном пакете (§7) представлять ссылки на то же
  Строковый объект (§4.3.1).
• Литеральные строки в разных классах в одном пакете представлять ссылки на то же самое Строковый объект.
• Литеральные строки в разных классах в разных пакетах аналогичным образом представляют ссылки на тот же объект String.

Answer 4

ну, это имеет смысл, ваш объект l1 совпадает с l2, даже если он хранится в памяти в другом месте, для графа это та же самая вершина.

есть ли причина, по которой вам нужны одинаковые вершины в графе? может быть, есть обходной путь