COIN-OR::LEMON - Graph Library

Opened 9 years ago

Last modified 4 years ago

#250 assigned enhancement

Extensions for the interface of paths

Reported by: kpeter Owned by: kpeter
Priority: major Milestone: LEMON 1.4 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description (last modified by kpeter)

  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.
  1. 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).

Attachments (2)

250-fix-e2cb320ed082.patch (1.3 KB) - added by kpeter 8 years ago.
250-eb2f42b62296.patch (9.4 KB) - added by kpeter 5 years ago.

Download all attachments as: .zip

Change History (14)

comment:1 Changed 9 years ago by alpar

  • Milestone changed from LEMON 1.1 release to LEMON 1.2 release
  • Owner changed from alpar to deba

comment:2 in reply to: ↑ description ; follow-up: Changed 8 years ago by deba

  1. 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.

comment:3 in reply to: ↑ 2 Changed 8 years ago by kpeter

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.

Changed 8 years ago by kpeter

comment:4 follow-up: Changed 8 years ago by kpeter

  • Owner changed from deba to kpeter
  • Status changed from new to assigned

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

comment:5 in reply to: ↑ 4 Changed 8 years ago by alpar

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.

comment:6 Changed 8 years ago by kpeter

  • Milestone changed from LEMON 1.2 release to LEMON 1.3 release

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

comment:7 Changed 8 years ago by kpeter

  • Description modified (diff)

Changed 5 years ago by kpeter

comment:8 Changed 5 years ago by kpeter

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)?
Last edited 5 years ago by kpeter (previous) (diff)

comment:9 Changed 5 years ago by alpar

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

comment:10 follow-up: Changed 5 years ago by 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.

comment:11 in reply to: ↑ 10 Changed 5 years ago by kpeter

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.

comment:12 Changed 4 years ago by deba

  • Milestone changed from LEMON 1.3 release to LEMON 1.4 release
Note: See TracTickets for help on using tickets.