0

I've some texts that the sequence follows a specific order. Some texts change in consequence of the traversed trail. My goal is generate static pages for each page, interconnecting them through links.

The question is to solve a problem for a tool that will generate text for printed books (that is static, obviously). So imagine you are reading a book that is represented in the Example 1 (on the image bellow). Initially, you're in the node A, and the text of this page is "Go to page B or page C". Choosing the node C, followed of F -> B -> E -> H, you'll see a content in the node H that should be different than what you would see whether you have been traversed by A -> B -> D -> H, for instance. As it is a printed book, I need to duplicate some paths to make possible change the content of some nodes according with the path traversed.

Example:

Example

In this example, I have two possibilities for traversing:

A -> B -> D
A -> C -> D

Expected result:

Page 1: A (link to page 2 and 3)
Page 2: B (link to page 4)
Page 3: C (link to page 5)
Page 4: D
Page 5: DD'

This simple example generates 5 pages, once the page 4 has a part of text that should be displayed only whether the reading passes through page 3.

To model this problem I chose use the Graph Theory. For a better understanding, I drew in the below graph two examples of the problem I'm trying to solve :

enter image description here

Note that the red dashed edges are not edges in fact. These are a way that I've used to represent when the content of the a given node X changes in consequence of visiting the node Y (reads "the content of node X changes if the path to arrive in X passes by Y").

I read a lot about graphs, traversing strategies (BFS and DFS) and some other topics. My goal is develop a algorithm that rearranges a given graph in a manner to be possible generate the pages mentioned previously. I didn't find any well-known problem that solves this problem, but I believe it should already exist. My research didn't find anything useful, so I tried to solve by myself.

My successfully approach consisted in traversing the graph up to find a node that contains a content that depends of others nodes. Once this node has been found, finds all paths from the dependent nodes to the current node. Traverses these paths duplicating all nodes that contains more than one incoming edge, removing the previous connection and connecting the current node with the duplicated one, and so on until consume all nodes of the path. This algorithm works well, but this approach is not efficient and can be very slow with long texts.

My question is: do you know any other better way to solve this problem? Is there any theory or known algorithm that can solve this kind of problem?

Thanks in advance.

4

2 回答 2

0

做一个 DFS，当你看到一个访问过的节点时，复制它，断开你刚刚访问过的链接并将新节点标记为已访问，然后从这个节点继续 dfs。这种方法不会多次访问节点，因此是最快的（这意味着它只会访问 H1 2 次而不是 n 次或 k 次）。

这在输出图方面是线性的。也就是说，如果输出图有 V' 个顶点和 E' 个边，它的顺序是 O(V'+E')。您无法取得更好的成绩，因为您必须至少访问输出图中的所有内容一次。

于 2013-08-27T23:58:35.510 回答
0

我假设这些红色边缘的规则是有条理的。将多个内容保留在一个节点中，而不是复制它。现在，由于显示的内容取决于到达它所采用的路径，因此在每一步我们都可以检查 DFS 的“堆栈”以查看到达它所采用的路径。堆栈将为我们提供到达它所采用的确切路径（但请注意，它不会详细说明路径是否访问了父母的其他后代）。然后我们比较我们已有的静态规则并显示内容。

时间复杂度分析（最坏情况）：在 DFS 的每一步，我们都会根据规则检查整个堆栈。堆栈的最大长度可以是 h（其中 h 是树的高度）。因此时间复杂度为 O((V+E)*h)。

或者，如果 path 访问了父事项的其他后代（例如分析路径 A->B->E 并且如果它很重要 D 已经访问过），您可以根据规则在数据结构上自己引入红色边缘。再次在一个节点中保留多个内容。在决定显示哪些内容时，只需检查“源自该顶点的红色边”的“端点”是否已被访问。现在使用规则显示适当的内容

于 2013-08-28T10:42:12.397 回答