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.