Search code examples
constraintsgraph-theory

Creating a tree based on constraints

I would appreciate any help with problem bellow. Even a direction of what I should read about. Thank you!

I need to create a a graph (tree) given a set of rules which indicates the relationship between vertices, where the relationship does not have to be direct.

Constraints:

  • Vertex rules should be met. In the example bellow, A<-D indicates that A is the parent of D, though it doesn't have to be a direct parent.
  • The distance between vertices should be as low as possible.
  • Each vertex can only have one parent, therefore the outcome will be a tree.

Example set of rules: [A<-D, D<-E, E<-F, A<-B, B<-C, E<-C, F<-C]

First image is a possible outcome, but it is not the best one given the distance between vertex C to F and C to E is too far. Therefore a better solution is the 2nd image.

enter image description here enter image description here

Solution

  • You have the rules:

    1. The distance between vertices should be as low as possible; and
    2. Each vertex can only have one parent.

    and the syntax:

    1. A<-D indicates that A is an ancestor of D.

    (Note: the change of terminology to ancestor.)

    Then for the graph generated by A<-D, D<-E, E<-F, A<-B, B<-C, E<-C, F<-C

    This gives 3 paths from A to C (using the syntax (X -> Y) as X is the [direct] parent of Y):

    • (A -> D), (D -> E), (E -> C) and
    • (A -> D), (D -> E), (E -> F), (F -> C) and
    • (A -> B), (B -> C)

    However, by the 2nd rule ("Each vertex can only have one parent") then there must only be a single path from A to C which passes through D, E, F (in that order) and also through B so the possible paths have the order A,D,E,F,C with B inserted somewhere:

    • Path 1: (A -> B), (B -> D), (D -> E), (E -> F), (F -> C)
    • Path 2: (A -> D), (D -> B), (B -> E), (E -> F), (F -> C)
    • Path 3: (A -> D), (D -> E), (E -> B), (B -> F), (F -> C)
    • Path 4: (A -> D), (D -> E), (E -> F), (F -> B), (B -> C)

    You can then calculate the distances for each of the rules (assuming a constant distance between each vertex):

    Rule Path1 Path2 Path3 Path4
    A<-D 2 1 1 1
    D<-E 1 2 1 1
    E<-F 1 1 1 2
    A<-B 1 2 3 4
    B<-C 4 3 2 1
    E<-C 2 2 3 3
    F<-C 1 1 1 2
    Total 12 12 12 12

    Since the total distance for all the paths is identical then any/all of the four solutions is equally valid against your rules.