CODEWITHSUNDEEP
constraintsgraph-theory
Lukas Povilonis
Lukas Povilonis

Reputation: 33

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:

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

Upvotes: 1

Views: 139

Answers (1)

MT0
MT0

Reputation: 168232

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.

Upvotes: 1

Related Questions