Extensions for the interface of paths

[Peter Kovacs]

1. Path structures have a function nth(int n) for getting the n th arc of the path. I suggest operator[] as an alias for this function.

2. It would be nice to have source() and target() functions for paths. But it raise questions.
   • Is it necessary that all the arcs in a path are directed in the same direction? Or we could store oppositely directed arc in a path as well? How should we define the source/target? Would the source node be equal to gr.source(path.front()) and the target to gr.target(path.back())?
   • Should paths store source and target nodes explicitly? It would make it possible to handle paths of zero length (with a specified starting node).

[Balazs Dezso]

2. It would be nice to have source() and target() functions for paths. But it raise questions.
   • Is it necessary that all the arcs in a path are directed in the same direction? Or we could store oppositely directed arc in a path as well? How should we define the source/target? Would the source node be equal to gr.source(path.front()) and the target to gr.target(path.back())?
   • Should paths store source and target nodes explicitly? It would make it possible to handle paths of zero length (with a specified starting node).

This issue was discussed when the path concepts were designed and redesigned. The final conclusion was that the path type must be very simple, because it should be possible to store a large amount of paths efficiently. The paths must be strictly directed, i.e. s(p_n) = t(p_{n-1}). There are now some global functions to get the source and target of the path. There is also global iterator for the nodes of the path, and it allows to specify the starting node of the path.

I recommend that the 2nd issue let be "wont fix".

1. Path structures have a function nth(int n) for getting the n th arc of the path. I suggest operator[] as an alias for this function.

The nth() function can be linear in the size of the graph. The STL has a convention, that the operator[] must be sublinear. We should decide, where should we introduce this function, in every path types or in path types with sublinear running time.

[Peter Kovacs]

Replying to deba:

This issue was discussed when the path concepts were designed and redesigned. The final conclusion was that the path type must be very simple, because it should be possible to store a large amount of paths efficiently.

I see.

The paths must be strictly directed, i.e. s(p_n) = t(p_{n-1}).

Technically you could push oppositely directed arcs into e.g. lemon::Path. Are there path tools for which it could cause problems? Should we specify this requirement at least in the Path concept?

There are now some global functions to get the source and target of the path.

They actually return gr.source(path.front()) and gr.target(path.back()). If the paths must be directed and consistent, then these functions are surely right, but only for non-empty paths. It would be better if these functions would give back INVALID for empty paths.

There is also global iterator for the nodes of the path, and it allows to specify the starting node of the path.

I recommend that the 2nd issue let be "wont fix".

I agree.

1. Path structures have a function nth(int n) for getting the n th arc of the path. I suggest operator[] as an alias for this function.

The nth() function can be linear in the size of the graph. The STL has a convention, that the operator[] must be sublinear. We should decide, where should we introduce this function, in every path types or in path types with sublinear running time.

I think we should use this notation only for sublinear time methods.

[Peter Kovacs]

[e2cb320ed082] fixes pathSource() and pathTarget(): they return INVALID for empty paths. I think, this changeset should be merged into both branches.

[Alpar Juttner]

Replying to kpeter:

[e2cb320ed082] fixes pathSource() and pathTarget(): they return INVALID for empty paths. I think, this changeset should be merged into both branches.

I've rebased it ([41bdb4d6c8c3]) and merged it even into 1.0 branch.

[Peter Kovacs]

The only question left here is to add operator[] (as an alias) for path structures that have sublinear time nth() function.

[Peter Kovacs]

The attached patch [eb2f42b62296] adds operator[] to Path, SimplePath, and StaticPath, and contains minor API doc improvements. It is based on [15d7c5eadaca] from #408.

Two additional questions:

1. One constructor of PathNodeIt is rather strange for me (see at line 1127 here: source:/lemon/lemon/path.h@1043#L1127​). It seems that this constructor is intended to allow path node iteration starting from the specified node, but I don't see how this can work, because˛operator++() only depends on the value of the ArcIt field (_it), which is initialized in this constructor the same way as in the previous one. Did this feature ever work?
2. In case of empty path, pathSource() and pathTarget() functions now return INVALID. But what about front() and back()? Currently, their behavior is undefined, in fact, they cause segmentation errors. Should these functions also return INVALID for empty paths or should we stick with the current behavior (which is in accordance of STL containers)?

[Alpar Juttner]

Balazs, could you please comment on Peter's first question above? And possibly the second one, too.

[Balazs Dezso]

Currently, a path is stored as a sequence arc.

It has two limitations:

• it does not guarantee that the path is really connected, i.e. target(path.nth(i-1)) == source(path.nth(i)),
• and we don't know the starting and finishing node of an empty path.

Because of the second limitation, when we want to iterate over the path nodes, we needs to be able to specify the initial node if the path is empty. I think, this is not straightforward, but usually it can be used quite efficiently. For example, when I use Dijkstra algorithm, I know that my path starts from the source. Otherwise, if we add the initial node to the path, we should put more "if"s into the iteration, which would make the generated code inefficient.

I think, pathSource() and pathTarget() could also have an optional third parameter, which specifies what node should be returned if the path is empty.

[Peter Kovacs]

Replying to deba:

Currently, a path is stored as a sequence arc.

It has two limitations:

• it does not guarantee that the path is really connected, i.e. target(path.nth(i-1)) == source(path.nth(i)),
• and we don't know the starting and finishing node of an empty path.

Because of the second limitation, when we want to iterate over the path nodes, we needs to be able to specify the initial node if the path is empty. I think, this is not straightforward, but usually it can be used quite efficiently. For example, when I use Dijkstra algorithm, I know that my path starts from the source. Otherwise, if we add the initial node to the path, we should put more "if"s into the iteration, which would make the generated code inefficient.

I think, pathSource() and pathTarget() could also have an optional third parameter, which specifies what node should be returned if the path is empty.

I see, that is reasonable. Then we should make the purpose of this extra parameter clear in the doc of the constructor.

[Peter Kovacs]

Let's consider this task again!

I revised the old patch, fixed it (e.g. removed the accidentally added std::cout command) and split it into two patches:

• [ba6afb21b6fd] API doc improvements for Path structures - I think, this change can be applied without a doubt
• [dbf9eee91ed2] Add operator[] to Path structures - Adds operator[] as an alias of the nth() method in those Path structures, for which it runs in O(1) time. I know that aliases are generally not preferred, but in case of a method and an operator, it seems to be OK for me. (See e.g. the API of Random.)

[Alpar Juttner]

What if operator[] were implemented even if it is not an O(1) time operation?

[Peter Kovacs]

Replying to alpar:

What if operator[] were implemented even if it is not an O(1) time operation?

I attached this version as [ac89b1685fbc]: it adds operator[] to all of the four path implementations. However, it does not extend the Path concept with this operator. Should we do it?

[Alpar Juttner]

Should we do it?

Maybe not, because it's just a convenience feature. But I'm a bit unsure about it.

[Peter Kovacs]

If we consider the Path concept as a requirement for Path implementations, then changing or extending its interface can be considered as an incompatible change (theoretically 3rd-party implementations may also exist). So I would keep it unchanged, at least in versions 1.x.

[Alpar Juttner]

[ba6afb21b6fd] and [ac89b1685fbc] have been rebased as [1f4f01870c1e] and [4fd76139b69e], and pushed to the main branch.