### Finding a subgraph with given properties.

Posted:

**Fri Jan 19, 2018 2:37 am UTC**I am currently writing a program where I have a graph and want to find the minimal sub-graph which satisfies my requirements.

The graph is directed with four types of nodes. It has many cycles but no 1 cycles. There are hundreds to low thousands of nodes. Nodes generally connected to around ten other nodes, but that can vary a lot.

The types of node and how they are connected:

Root nodes which may point to any number of Process nodes

Leaf nodes which may be pointed to by any number of Process nodes

Process nodes which may be pointed to by any number of Root or Product nodes and may point to any number of Product or Leaf nodes.

Product nodes which may be pointed to by any number of Process nodes and which may point to any number of Process nodes.

I wish to find the sub-graph which satisfies the following requirements:

Any Root or Leaf which is adjacent to a node in the sub-graph must be in the sub-graph

For every Process node in the sub-graph, all Product nodes which point to it must be included in the sub-graph

For every Product node in the sub-graph, at least one Process node which points to that Product must be present in the sub-graph

Medium priority: Minimize Root, Product, and Process nodes included in sub-graph

Low priority: Maximize Leaf nodes

Could use some help from smart people on xkcd with this algorithm.

The graph is directed with four types of nodes. It has many cycles but no 1 cycles. There are hundreds to low thousands of nodes. Nodes generally connected to around ten other nodes, but that can vary a lot.

The types of node and how they are connected:

Root nodes which may point to any number of Process nodes

Leaf nodes which may be pointed to by any number of Process nodes

Process nodes which may be pointed to by any number of Root or Product nodes and may point to any number of Product or Leaf nodes.

Product nodes which may be pointed to by any number of Process nodes and which may point to any number of Process nodes.

I wish to find the sub-graph which satisfies the following requirements:

Any Root or Leaf which is adjacent to a node in the sub-graph must be in the sub-graph

For every Process node in the sub-graph, all Product nodes which point to it must be included in the sub-graph

For every Product node in the sub-graph, at least one Process node which points to that Product must be present in the sub-graph

Medium priority: Minimize Root, Product, and Process nodes included in sub-graph

Low priority: Maximize Leaf nodes

Could use some help from smart people on xkcd with this algorithm.