Graph search by pattern

Question

Could you please give the direction where I could learn about how to search in graph by some pattern.

I have some unidirectional graph with unique ID and it's type, example A, B, C.

I need to search all ID's accordance to pattern. For example

Search (A, B, C) should return all ID's in case if node types connected in this direction. Return could be as [1,4,6] [4,6,8], etc.

Bfs and dfs could help when I am looking some certain type of node, but how could I search if I have a pattern with connections between those nodes.

My test looks like this:

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);

Answer 1

As for your example:

• Use BFS or DFS to find all A's. Add any 'A' found to some container C1.
• For each element in C1, check if it has 'B' neighbors. Add any 'AB' path found to C2.
• For each element in C2, check if its last node has 'C' neighbors. Add any 'ABC' path found to C3.
• Report all elements in C3