Потокобезопасные библиотеки графов

Question

Я ищу хорошую библиотеку графов Java, которая является поточно-ориентированной для одновременного доступа.JGraphT, JUNG, JTS очень хороши, но опять же для одновременного доступа мне придется синхронизировать его извне, что становится болью.Это неприятно, потому что, скажем, если нить A должна получить доступ к 50 вершинам, нить B - еще к 50 с пересечением вершин, равным 20 вершинам.Теперь при написании кода мне нужно знать это 20 раньше, чтобы я мог синхронизировать его соответствующим образом.Pl предложить

Answer 1

Рассматривали ли вы Neo4J

Вот фрагмент описания их продукта.

Neo4j - это высокопроизводительная графическая база данных NOSQL со всеми функциями зрелой и надежной базы данных.

Answer 2

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

Допустим, в вашей библиотеке графов есть основной класс Graph с множеством методов, каждый из которых synchronized. Например, addVertex(), removeVertex(), addEdge(), removeEdge() и т. Д. Предположим также, что класс Vertex имеет несколько полезных методов, таких как, например, getAdjacentEdges(), которые также синхронизируются с Graph. экземпляр.

Теперь ясно, потому что все синхронизировано, невозможно повредить структуру данных. Например, у вас никогда не будет ситуации, когда v.getAdjacentEdges() дает вам ребро, которого на самом деле нет в графе, содержащем вершину v. Структура графа всегда внутренне согласована благодаря его внутренней синхронизации.

Однако ваши алгоритмы, работающие на графике, все еще могут легко сломаться. Например, допустим, вы пишете:

for (Edge e : v.getAdjacentEdges()) {
  g.removeEdge(e);
}

Вызов getAdjacentEdges() является атомарным, как и каждый вызов removeEdge() в цикле, но сам алгоритм - нет. Другой поток может добавить новое ребро рядом с v, пока выполняется этот цикл, или удалить ребро, или что-то еще. Чтобы быть в безопасности, вам все еще нужен способ гарантировать, что цикл в целом является атомарным, а сам граф не может этого обеспечить.

Мой лучший совет, я думаю, это использовать JGraphT в сочетании с реализацией Akka STM (или аналогичной), чтобы вы могли писать свои алгоритмы без необходимости заранее определять, какие объекты будут нуждаться в блокировке , Если вы не знакомы с STM и его характеристиками производительности, Статья в Википедии на тему неплохо объяснит.

Answer 3

Посмотрите на charts4j API.Мы используем его в нашем приложении с достаточным количеством одновременных пользователей, и проблем пока не было.Я не уверен, является ли API поточно-ориентированным или нет.

Одна проблема, которую мы заметили, заключается в том, что URL сгенерированного графика будет указывать на http://www.google.com/..., что может быть проблемой, если вы работаетевнутри VPN и интернета нет. (Может быть, есть выход из этого).

Answer 4

Если вы хотите изменить узлы только локально, вы можете поддерживать индивидуальную блокировку для каждого узла.Самый простой способ сделать это - реализовать собственный класс узла с синхронизированными методами (вы также можете использовать ReentrantLock), то есть что-то вроде этого:

public class SynchronizedNode extends Node {

    public synchronized void localOp1() { ... }

    public synchronized void localOp2() { ... }

}

или

public class SynchronizedNode extends Node {

    ReentrantLock lock ....;

    public synchronized void localOp1() { lock.lock() try { ... } finally { lock.unlock } }

    public synchronized void localOp2() { lock.lock() try { ... } finally { lock.unlock } }

}

Answer 5

Самое простое решение - создать один большой монитор.

public Object theBigGraphMonitor = new Object();

Перед выполнением ЛЮБОЙ операции над графиком выполните синхронизацию на этом отдельном мониторе.

Поиграть с отдельными вершинами кажется труднымчтобы получить право ... По меньшей мере.

Answer 6

Как насчет того, чтобы позволить нескольким потокам делать все, что они могут, а затем передавать свое решение одному главному контроллеру, который собирает результаты и предлагает лучшее решение.