CODEWITHSUNDEEP
graphpattern-matchinggraph-algorithmsubgraph
Raj
Raj

Reputation: 3462

Finding Subgraph in a Graph

I have a graph shown here. Just to node that nodes B_0, B_1, belong to node of type B, C_0, C_1. C_2, C_3 belong to node of type C and so on. Now, I want to find multiple subgraphs, which could satify criteria like defined by this example -

Criteria -

  1. subgraph contains 1 node of type A, 1 node of type B, 1 node of type C, one node of type D.
  2. subgraph has one edge from node of type A to one node of type B, one edge connecting type B and type C and one node connecting type C and type D.
  3. subgraph contains one edge from type A going out of subgraph to type B node, one edge from type B to type C node outside, one edge from type D to type E outside.

Now this description should give result as -

  1. subgraph :: A_0, B_0, C_1, D_1
  2. subgraph :: A_0, B_0, C_0, D_0
  3. subgraph :: A_0, B_1, C_2, D_2
  4. subgraph :: A_0, B_1, C_3, D_3

I want to know, if there is any algorithm, by which I can find such sub-graphs? I tried to figure out an algorithm by making all possible combinations. However, this would be exponential to number of nodes in subgraph. Thus, I want to know if there exists an efficient way to calculate it. Or if there exists a problem of similar nature in Graph Theory?

Graph

Upvotes: 3

Views: 3277

Answers (1)

Gato
Gato

Reputation: 671

You can start by visiting all nodes of type A. For each A node, look at all nodes connected to it which are of type B. From there look all nodes of type C and so on, keeping track of the nodes you've visited from the last A node. Then whenever you reach a subnode that completes the criteria of your search, you add all the list of nodes from the A node until the point where you are. Essentially you're doing a depth-first search where you keep traversing into the graph as long as a node meets the criteria of what should follow and backtrack whenever there's no more valid nodes (ie. which would produce a valid subgraph) going out from your current node.

Upvotes: 3

Related Questions