Найти скрытые узлы между двумя узлами - graph - java

Question

Мой английский не очень хорошо, НО я сделаю все возможное, чтобы объяснить мою проблему здесь. Я работаю над приложением, в котором я должен создать график. Сейчас я использую GraphStream,

Требования к моему графику очень сложны, а именно:

У меня есть таблица с именем CDR(Call Data Record), в которой у меня есть 2 столбца ANUMBER и BNUMBER. Структура таблицы очень ясна, так как она показывает, что Anumber называется Bnumber, и есть еще один столбец для DATETIME, который показывает дату и время вызова. НО мне нужны здесь только две колонки.

Допустим, у нас есть 4 числа: 123, 456,789,000, и структура таблицы такая

Anumber    Bnumber
-------    -------
123        456
123        789
456        789
789        000
456        000

Моя таблица здесь ясно показывает, что 123 не звонил 000, но 123 звонил 456 и 789, и эти два числа назывались 000, поэтому я должен показать ориентированный график между 123 и 000, который, вероятно, показывает вот так 123->456->000 а также 132->789->000

Так что проблема в том, что я не знаю, как найти этот путь между 123 и 000. Может быть больше 2 чисел, таких как 5 или 6 чисел, и мне нужно найти скрытые числа между всеми данными 5 или 6 числами AS в Приведенный выше сценарий 456 и 789 являются скрытыми числами от 132 до 000.

И еще одна вещь: моя таблица содержит более 20 миллионов строк, и в будущем, очевидно, число строк будет расти очень быстро, когда пользователь вызывает друг друга.

Что я сделал так далеко:

Я провел некоторые исследования и разработки по этому вопросу, но не смог найти ни одной хорошей библиотеки или решения для этого. Пока что думаю Dijkstra's Algorithm лучше всего подходит для моего сценария GraphStream к счастью, предоставляет этот алгоритм здесь.

Ребята, что я хочу от вас, дайте мне понять, что этот алгоритм даст мне требуемый результат ИЛИ мне нужно найти любую другую библиотеку алгоритмов или графов, которая лучше всего подойдет для моей задачи. Я не очень хорош в ALGO, поэтому я здесь для любой помощи или рекомендаций, если вы, ребята, можете дать мне. Спасибо

Answer 1

Вам вообще не нужен алгоритм Дейкстры, поскольку у вас нет затрат на ребра. Вам нужен простой алгоритм BFS. Вот простая реализация, но вы должны добавить массив меток, чтобы отметить посещенные узлы. Таким образом, после BFS вы можете восстановить передачу от каждого узла к исходному узлу (123 в вашем случае) или сказать, что узел не может быть достигнут с данного узла (если метка для этого узла остается 0). Вы должны добавить метку следующим образом:

все метки равны 0 на старте

при посещении нового узла вы устанавливаете его метку как current_node_label+1

Но Dijkstra может помочь вам, если вы установите стоимость каждого ребра равной 1. Это просто не эффективный способ решить вашу проблему.