Поиск графика по шаблону - PullRequest
0 голосов
/ 01 марта 2019

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

У меня есть некоторый однонаправленный граф с уникальным идентификатором и его типом, пример A, B, C.

Мне нужно найти все идентификаторы в соответствии с шаблоном.Например,

Поиск (A, B, C) должен возвращать все идентификаторы в случае, если типы узлов подключены в этом направлении.Возврат может быть как [1,4,6] [4,6,8] и т. Д.

Bfs и dfs могут помочь, когда я смотрю какой-то определенный тип узла, но как я могу искать, если у меня есть шаблон с соединениями между этими узлами.

Мой тест выглядит так:

Vertex<Integer, String> vertex1 = new Vertex<Integer, String>(1, "A");
Vertex<Integer, String> vertex2 = new Vertex<Integer, String>(2, "B");
Vertex<Integer, String> vertex3 = new Vertex<Integer, String>(3, "D");
Vertex<Integer, String> vertex4 = new Vertex<Integer, String>(4, "A");
Vertex<Integer, String> vertex5 = new Vertex<Integer, String>(5, "C");
Vertex<Integer, String> vertex6 = new Vertex<Integer, String>(6, "B");
Vertex<Integer, String> vertex7 = new Vertex<Integer, String>(7, "E");
Vertex<Integer, String> vertex8 = new Vertex<Integer, String>(8, "C");


vertex1.setNeighbors(Collections.singletonList(vertex2));
vertex2.setNeighbors(Arrays.asList(vertex3, vertex5));
vertex3.setNeighbors(Collections.singletonList(vertex2));
vertex4.setNeighbors(Arrays.asList(vertex5, vertex6, vertex7));
vertex5.setNeighbors(Arrays.asList(vertex2, vertex4, vertex6));
// vertex5.setNeighbors(Arrays.asList(vertex2, vertex3, vertex4, vertex6));
vertex6.setNeighbors(Arrays.asList(vertex4, vertex5, vertex8));
vertex7.setNeighbors(Collections.singletonList(vertex4));
vertex8.setNeighbors(Collections.singletonList(vertex6));

List<List<String>> expectedAnswers = new ArrayList<List<String>>();
List<String> answer = new ArrayList<String>();
answer.add("1");
answer.add("2");
answer.add("5");
expectedAnswers.add(answer);
answer = new ArrayList<String>();
answer.add("4");
answer.add("6");
answer.add("5");
expectedAnswers.add(answer);
answer = new ArrayList<String>();
answer.add("4");
answer.add("6");
answer.add("8");
expectedAnswers.add(answer);

List<String> typePattern = new ArrayList<String>();
typePattern.add("A");
typePattern.add("B");
typePattern.add("C");
// typePattern.add("D");


Graph<Integer, String> graph = new Graph<Integer, String>();
List<List<String>> resutls = graph.search(vertex1, typePattern);

assertResults(resutls, expectedAnswers);

1 Ответ

0 голосов
/ 01 марта 2019

Как в вашем примере:

  • Используйте BFS или DFS, чтобы найти все буквы.Добавьте любой найденный «A» в некоторый контейнер C1.
  • Для каждого элемента в C1 проверьте, есть ли у него соседи «B».Добавьте любой найденный путь «AB» в C2.
  • Для каждого элемента в C2 проверьте, есть ли у его последнего узла соседи «C».Добавьте любой найденный путь ABC в C3.
  • Сообщите все элементы в C3
...