Algorithm for creating dedicated paths between two nodes

Question

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:

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 :

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.

Answer 1

I am assuming the rules of these red edges are stactic. Keep multiple content in one node instead of duplicating it. Now as the content displayed depends on the path taken to reach it, at each step we can check the "stack" of the DFS to see the path taken to reach it.The stack will give us the exact path taken to reach it (but note that it will not give details whether path visited other decendants of the parent). Then we compare to our static rules that we already have and display the content.

Time complexity analysis(Worst case): At each step of DFS we check the entire stack against the rules. The maximum length of stack can be h(where h is the hight of tree). Hence the time complexity is O((V+E)*h).

Alternatively, if path visited other decendants of the parent matters(like analysing path A->B->E and if it matters D was already visted ), you can introduce the red edges yourself on the data-structure based upon the rules. Again keep multiple content in a node. While deciding which content to display simply check if the "endpoint" of "red edges originating from this vertice" are already visited. Now use the rules to display the appropriate content

Answer 2

Do a DFS and when you see a visited node, duplicate it, break the link through which you just visited and mark the new node as visited and continue dfs from this node. This method does not visit node multiple times and hence is the fastest(meaning it will visit H1 just exacyly 2 times not n or k times).

This is linear in terms of output graph. That is if the output graph has V' vertices and E' edges its order is O(V'+E'). You can not achieve better as you must visit everything in output graph atleast once.