Problem
I have a set of events, some of them connected and these connections define order. Events must be held in defined order. A connection may contain a min and/or a max requirement for distance between connected events. Let the distance be in days.
I use a directed acyclic graph for a representation of my model.
I need to order this events on the given number of days respecting the defined order and min/max requirements. The distribution should tend to be even. The events should be stretched all over the given distance.
What ways or algorithms may you suggest on solving this problem? I tried to find some solution with topological sorting or constraint ordering but had little to no results.
Example
We have a set of events a, b, c with the following connections a -> b, b -> c, a -> c
The given number of days for distribution is 7.
a. without any requirements for distance between connections.
Then the best solution would be
1 2 3 4 5 6 7
a b c
b. with requirement where distance in days between events (a, b) is [1, 2].
Then the best solution would be
1 2 3 4 5 6 7
a b c
c. with requirements where distance in days between events (a, b) is [1, 2] and between events (a, c) is <= 4.
Then the best solution would be
1 2 3 4 5 6 7
a b c
d. with requirements where distance in days between events (a, b) is [1, 2], between events (a, c) is <= 4, between events (b, c) is >= 3.
Then the best solution would be
1 2 3 4 5 6 7
a b c
CodePudding user response：
Find R = all events that have no in edges
LOOP while R contains one or more event
SELECT N from R with the largest number of out edges
IF first time through
Place N on day 1
ELSE
Place N in middle of largest gap between events
LOOP M over descendants of N in required order
Place M as far from other events as possible, within M's allowed range
CodePudding user response：
Evenness ?
If unevenness is defined by looking at all the differences between days and event_days calculated and returning the max minus the min days difference then your problem with your answer of:
1 2 3 4 5 6 7
a b c
Has the values off to the left w.r.t. the days.
A better answer might be:
1 2 3 4 5 6 7
a b c
With the one shift to the left, theeir is less of a stretch from day 7 to any event day.
If you think the above is equivalent then you need to better define evenness - is it evennness over the extent of the event days perhaps?
======
Code
The source is set to run your example if you just return on each prompt.
# -*- coding: utf-8 -*-
"""
Even distribution of directed acyclic graph with respect to edge length
https://stackoverflow.com/questions/71532362/even-distribution-of-directed-acyclic-graph-with-respect-to-edge-length
Created on Sat Mar 26 08:53:19 2022
@author: paddy
"""
# https://pypi.org/project/python-constraint/
from constraint import Problem
from functools import lru_cache
from itertools import product
#%% Inputs
days = input("Days: int = ")
try:
days = int(days.strip())
except:
days = 7
print(f"Using {days=}")
events = input("events: space_separated = ")
events = events.strip().split()
if not events:
events = list("abc")
print(f"Using {events=}")
constraint_funcs = []
while True:
constr = input("constraint string_expression (. to end) = ").strip()
if not constr:
constraint_funcs = ["1 <= abs(b - a) <=2",
"abs(c - a) <= 4",
"abs(c - b) >= 3"]
break
if constr == '.':
break
constraint_funcs.append(constr)
print(f"\nUsing {constraint_funcs=}")
#%% Constraint Setup
print()
problem = Problem()
problem.addVariables(events, range(1, days 1))
for constr in constraint_funcs:
constr_events = sorted( set(events) & set(compile(constr, '<input>',
mode='eval').co_names))
expr = f"lambda {', '.join(constr_events)}: {constr}"
print(f" Add Constraint {expr!r}, On {constr_events}")
func = eval(expr)
problem.addConstraint(func, constr_events)
#%% Solution optimisation for "evenness"
print()
@lru_cache
def unevenness(event_days, all_days):
"Max - min diff between days and events"
maxdiff, mindiff, sumdiff, n = -1, all_days 1, 0, 0
for day, event in product(range(1, all_days 1), event_days):
n = 1
diff = abs(day - event)
maxdiff = max(maxdiff, diff)
mindiff = min(mindiff, diff)
sumdiff = diff
return abs(maxdiff - mindiff) # Or whatever unnevenness means??!
def printit(solution, all_days):
drange = range(1, all_days 1)
# print(solution)
print(' '.join(str(i)[0] for i in drange))
for event, day in sorted(solution.items(), key=lambda kv: kv[::-1]):
print(' ' * (day - 1) event )
print()
current_best = None, 9e99
for ans in problem.getSolutionIter():
unev = unevenness(tuple(sorted(ans.values())), days)
if current_best[0] is None or unev < current_best[1]:
current_best = ans, unev
print("Best so far:")
printit(ans, days)
Output
Sample run using another interpretation of your constraints (no use of abs(...), and using longer event names).
Days: int = 7
Using days=7
events: space_separated = arch belt card
Using events=['arch', 'belt', 'card']
constraint string_expression (. to end) = 1 <= (belt - arch) <= 2
constraint string_expression (. to end) = (card - arch) <= 4
constraint string_expression (. to end) = (card - belt) >= 3
constraint string_expression (. to end) = .
Using constraint_funcs=['1 <= (belt - arch) <= 2', '(card - arch) <= 4', '(card - belt) >= 3']
Add Constraint 'lambda arch, belt: 1 <= (belt - arch) <= 2', On ['arch', 'belt']
Add Constraint 'lambda arch, card: (card - arch) <= 4', On ['arch', 'card']
Add Constraint 'lambda belt, card: (card - belt) >= 3', On ['belt', 'card']
Best so far:
1 2 3 4 5 6 7
arch
belt
card
Best so far:
1 2 3 4 5 6 7
arch
belt
card
Note: The first letter of event names align with the day columns.