How to use multi-root directed graphs

[hombit]

I have a problem to optimize a total weight of a positive-weight directed graph. The solution must keep all roots and leaves nodes, while maintaining them connected. Could I solve such a problem with the egg?

A simplest example of what I want is to replace this

graph TD;
    A -- 1 --> B;
    A -- 2 --> C;
    B -- 1 --> D;
    C -- 1 --> D;

Loading

with

graph TD;
    A -- 1 --> B;
    B -- 1 --> D;

Loading

Could you please help me to figure out how to build such graphs with egg and what kind of rules I need?

[yihozhang]

This sounds like a hard problem. It seems to me that the Steiner tree problem, which is NP-hard, can be viewed as an instance of this problem where the roots and the leaves contain the same set of vertices and the graph is undirected.

[hombit]

Thank you! Graph theory is new to me, and I believe you've given a right direction to me

[omidmohammdi]

I think you can solve this problem with the Steiner tree when your choice is based on the candidate node or in other words selective about the middle nodes.