COIN-OR::LEMON - Graph Library

Opened 10 years ago

Closed 2 weeks ago

#250 closed enhancement (done)

Extensions for the interface of paths

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

Description (last modified by 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.
  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 (5)

250-fix-e2cb320ed082.patch (1.3 KB) - added by Peter Kovacs 9 years ago.
250-eb2f42b62296.patch (9.4 KB) - added by Peter Kovacs 6 years ago.
250-new-ba6afb21b6fd.patch (7.2 KB) - added by Peter Kovacs 9 months ago.
250-new-dbf9eee91ed2.patch (2.8 KB) - added by Peter Kovacs 9 months ago.
250-new-ac89b1685fbc.patch (3.3 KB) - added by Peter Kovacs 8 months ago.

Download all attachments as: .zip

Change History (23)

comment:1 Changed 10 years ago by Alpar Juttner

Milestone: LEMON 1.1 releaseLEMON 1.2 release
Owner: changed from Alpar Juttner to Balazs Dezso

comment:2 in reply to:  description ; Changed 9 years ago by Balazs Dezso

  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 9 years ago by 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.

Changed 9 years ago by Peter Kovacs

Attachment: 250-fix-e2cb320ed082.patch added

comment:4 Changed 9 years ago by Peter Kovacs

Owner: changed from Balazs Dezso to Peter Kovacs
Status: newassigned

[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 9 years ago by 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.

comment:6 Changed 9 years ago by Peter Kovacs

Milestone: LEMON 1.2 releaseLEMON 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 9 years ago by Peter Kovacs

Description: modified (diff)

Changed 6 years ago by Peter Kovacs

Attachment: 250-eb2f42b62296.patch added

comment:8 Changed 6 years ago by 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)?
Last edited 6 years ago by Peter Kovacs (previous) (diff)

comment:9 Changed 6 years ago by Alpar Juttner

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

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

comment:11 in reply to:  10 Changed 6 years ago by 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.

comment:12 Changed 5 years ago by Balazs Dezso

Milestone: LEMON 1.3 releaseLEMON 1.4 release

Changed 9 months ago by Peter Kovacs

Attachment: 250-new-ba6afb21b6fd.patch added

Changed 9 months ago by Peter Kovacs

Attachment: 250-new-dbf9eee91ed2.patch added

comment:13 Changed 9 months ago by 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 (see the files 250-new-*.patch).

  • [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.)
Last edited 9 months ago by Peter Kovacs (previous) (diff)

comment:14 Changed 8 months ago by Alpar Juttner

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

Changed 8 months ago by Peter Kovacs

Attachment: 250-new-ac89b1685fbc.patch added

comment:15 in reply to:  14 ; Changed 8 months ago by 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?

comment:16 in reply to:  15 Changed 8 months ago by Alpar Juttner

Should we do it?

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

comment:17 Changed 8 months ago by 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.

comment:18 Changed 2 weeks ago by Alpar Juttner

Resolution: done
Status: assignedclosed

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

Note: See TracTickets for help on using tickets.