1

I have a directed acyclical graph. Each node represents an event with start and end dates and each edge represents a constraint between to events with 2 properties:

  • max interval between previous event end and next event start
  • min interval between previous event end and next event start

When an event's date is updated, all edge constraints should be respected and every other event's date should be recalculated if those constraints are violated. Problem is that there might be multiple conflicting constraints and I'm struggling to find best way to traverse the graph updating events without breaking previously satisfied constraints.

I have no formal CS education and my knowledge in this area is quite limited. Is there an existing algorithm to solve my problem?

package
  • 111
  • 1
  • Are you sure that your graph model is at all useful? – Raphael Jul 22 '14 at 08:09
  • Do you have any alternative models in mind? – package Jul 22 '14 at 10:03
  • I'd look at scheduling and timetable problems/algorithms and see how they model things. Contraint satisfaction may also be worth checking out, but that's more abstract. – Raphael Jul 22 '14 at 10:20
  • I don't understand what an edge represents. What constraint does an edge represent, specifically? Is it always the same constraint? Is there some space of possible constraints, and each edge might represent a different constraint? (Telling me that an edge represents some unspecified constraint, but that the constraint satisfies two properties, doesn't help me visualize the constraint -- why don't you just tell me the constraint explicitly? It doesn't help that I can't understand what your two listed properties are trying to say.) Also, adding an example might help. – D.W. Jul 22 '14 at 17:26
  • Also, I can't understand what you want the algorithm to compute. What is the input to the algorithm, and what is the desired output? When you say "When an event's date is updated, all edge constraints should be respected", what if the constraint isn't respected? Is the algorithm supposed to fix things up, e.g., by cancelling the update, or by changing the dates of some other events? Are there any limits on which events' dates can be changed or how they're allowed to be changed? For me, the problem isn't well-defined yet. Working through an example might help. – D.W. Jul 22 '14 at 17:27
  • Maybe you could give an example. – babou Jul 22 '14 at 20:02

0 Answers0