Databases
StackOverflow2013
Postsdbo
POIn search of an algorithm for sorting collection in nodes to satisfy a layout constraint
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POIn search of an algorithm for sorting collection in nodes to satisfy a layout constraint
    primarykey
    data
    text
    <p>Firstly, I apologize for the poor title; I cannot think of a good name for this algorithm.</p> <p>I have an ordered list of <em>stages</em>. Each stage has a <em>cast</em> of <em>characters</em>, unordered. Characters can occur in multiple stages.</p> <p>A <em>crossing</em> occurs when two consecutive stages cannot have their casts concatenated, with overlap allowed where it would unify the same character on both casts, in a way that leaves a character duplicated in the concatenation. Or, informally, a crossing is when a character would need to be at two different spots at once in a line-up of the combined casts. In code:</p> <pre class="lang-py prettyprint-override"><code>uncrossed = [D, F], [N, V, S] overlap = [D, F, V], [V, N, S] crossed = [D, V, F], [N, V, S] </code></pre> <p>In the first example, V isn't with D and F, so there aren't any crossings. In the second example, V is with D and F and then with N and S, but this isn't a problem because the ordering permits (with overlap) a crossing-less concatenation. On the third example, though, the ordering forces a crossing.</p> <p>For my purposes, crossings can occur on non-consecutive stages as if characters did not actually stray from their previous order in the cast when they are not "on-stage."</p> <p>I would like to order each stage's cast such that there are as few crossings as possible, understanding that it is definitely possible to have situations where crossings are inevitable. An example series which requires crossings:</p> <pre class="lang-py prettyprint-override"><code>required = [A, B], [B, C], [A, C], [A, B] </code></pre> <p>This all sounds very abstract and silly, so I'll provide a concrete example of a human solving this algorithm for a purpose similar to mine: <a href="http://xkcd.com/657/" rel="nofollow">http://xkcd.com/657/</a> In this case, the constraint is deliberately ignored for aesthetic purposes, but it's still possible to get a visual idea of what I'm talking about.</p> <p>I already have some crude ideas for how to solve this, but nothing affordable, and I'm wondering if this is isomorphic to some problem already covered in the literature. It sounds vaguely topological as well.</p> <p>Since people asked, this algorithm appears to be key to automatically generating pretty timelines for storyboards of characters in stories, and that's what I'm intending to use it for.</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USCorbin
    1. USCorbin
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POIn search of an algorithm for sorting collection in nodes to satisfy a layout constraint
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POIn search of an algorithm for sorting collection in nodes to satisfy a layout constraint
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POIn search of an algorithm for sorting collection in nodes to satisfy a layout constraint
      1. This table or related slice is empty.
      1. VTUpMod
    1. COPlease provide an example of what *you* are looking for. The cartoon you are linking to bears no apparent relationship to your description. In particular it's not at all obvious what one of your "nodes" is supposed to be in these illustrations. The closest thing might be the barely discernible "events" in the pictures, but they are not at all laid out "horizontally". It may be "*possible to get an idea of what I'm talking about*" by looking at it, but it's far from likely.
      singulars
      1. POIn search of an algorithm for sorting collection in nodes to satisfy a layout constraint
      1. USRBarryYoung
    2. COIs there ever a case where a member appears in node A and node C but not node B, so you need a line connecting A to C and skipping B? If not, there's no reason for lines to ever cross as long as you keep the members in the same order each time.
      singulars
      1. POIn search of an algorithm for sorting collection in nodes to satisfy a layout constraint
      1. USDagg Nabbit
    3. COThis does sound topological and I would guess that a general optimal solution to this particular problem is unknown and pretty hard. If you manage to hack something ad-hoc together that works reasonably well, that might be the best you can do. (Of course you could brute-force an exhaustive search solution for a particular input, and this may not be so bad either since it doesn't sound like you need a real-time solution.)
      singulars
      1. POIn search of an algorithm for sorting collection in nodes to satisfy a layout constraint
      1. USAndrey Mishchenko
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload