Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Jim lives a boring life. Everyday after leaving work, he buys gas for his car and eats dinner at a diner on his way home. Sometimes he stops at a book store after work. Since the store closes soon after he gets off work, Jim's first stop is always the store when he chooses to go there. He always goes to both the diner and the gas station, but he sometimes goes to one before the other to add some variety to his otherwise dull life. He always goes home after the end of each day and never visits any location twice in the same day. How could the data for Jim's dull life be best structured?

What we have is a multidigraph with five nodes and nine arcs. Obviously, work is the source, and home is the sink. $A$=store, $B$=diner, $C$=gas. Nodes $B$ and $C$ are necessary, they must be transversed before arriving home (the sink). I want to create a data model that will allow me to add weights that will determine the order of events as well as the occurrence of non-necessary events. I will also need to express the impossibility of going back and forth between the diner and gas station all night.

share|improve this question
I'd think of it as a finite-state machine rather than a graph. You can have a state representing going to the diner without having gone to the gas station first, and another state representing going to the diner after going to the gas station. –  Gerry Myerson Mar 3 '13 at 4:46
Everybody stand back. $A?(BC|CB)$. Now you have two problems. –  Rahul Mar 3 '13 at 5:53
Ok, finite-state makes sense. Does Jim go to the store?(y/n) Does Jim get gas before dinner?(y/n) Thus we have two problems and four possible states. However, I'm sure how I would weigh the problems. There are at least several hundred things that could affect Jim's decision. I was thinking I would graph Jim's life and attach values to the nodes/arcs. Then I could use a hidden markov model to weight the nodes. Is there any kind of hybrid between a weighted digraph and a finite-state machine? –  parap Mar 3 '13 at 11:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.