COIN-OR::LEMON - Graph Library

Opened 10 years ago

Closed 10 years ago

#190 closed task (fixed)

Standard maps should be reference maps

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

Description (last modified by Peter Kovacs)

Should we state in the graph structure concepts that node and arc/edge maps must be reference maps for all graph types?

It would make writing a general algorithm easier and more convenient since we would have to use set() functions instead of operator[] only for the "external" map types, and all the "internal" maps, which are created by the algorithm could be used as reference maps. Maybe it could also improve the efficiency in some cases, but it is not clear and wasn't tested.

Attachments (6)

ref-maps1-add8195ad331.patch (59.3 KB) - added by Peter Kovacs 10 years ago.
Various improvements and fixes (mainly in the doc)
ref-maps2-63e0373c4caa.patch (8.9 KB) - added by Peter Kovacs 10 years ago.
Perform changes
ref-maps3-43e06cc62cca.patch (60.8 KB) - added by Peter Kovacs 10 years ago.
Exploit changes
ref-maps-48158db1b640-77a77781b04b-bf918e729ee7.2.bundle (11.8 KB) - added by Peter Kovacs 10 years ago.
Fixed changesets
ref-maps-d11bf7998905-2313edd0db0b-aa1804409f29.bundle (11.8 KB) - added by Peter Kovacs 10 years ago.
ref-maps-d11bf7998905--7a28e215f715.bundle (12.7 KB) - added by Peter Kovacs 10 years ago.

Download all attachments as: .zip

Change History (19)

comment:1 Changed 10 years ago by Peter Kovacs

Description: modified (diff)
Priority: majorcritical

I checked the graph adaptors and they all conform to this concept, so I see no reason for not adding this restriction to the graph concepts.

What do you think?

If we accept this idea, the following modifications should be made:

  • concepts/graph.h, concepts/digraph.h
    • it should be checked in the concept checking classes
    • it should noted in the documentation of the graph concepts
  • list_graph.h, smart_graph.h, full_graph.h, grid_graph.h, hypercube_graph.h
    • remove the comments saying: "It also has an important extra feature that its maps are real reference maps."
  • algorithm classes that use internal maps
    • check the writing operations of internal maps using set() and modify them to use the reference map syntax if it is simplier or possibly more efficient (e.g. map[i]++ instead of map.set(i, map[i] + 1)).

comment:2 Changed 10 years ago by Peter Kovacs

Type: enhancementtask

comment:3 in reply to:  1 ; Changed 10 years ago by Alpar Juttner

Replying to kpeter:

I checked the graph adaptors and they all conform to this concept, so I see no reason for not adding this restriction to the graph concepts.

What do you think?

I support this change.

comment:4 Changed 10 years ago by Alpar Juttner

Owner: changed from Alpar Juttner to Peter Kovacs

comment:5 Changed 10 years ago by Peter Kovacs

Status: newassigned

comment:6 in reply to:  3 Changed 10 years ago by Alpar Juttner

Replying to alpar:

I support this change.

Let's do it, then.

Changed 10 years ago by Peter Kovacs

Various improvements and fixes (mainly in the doc)

Changed 10 years ago by Peter Kovacs

Perform changes

Changed 10 years ago by Peter Kovacs

Exploit changes

comment:7 Changed 10 years ago by Peter Kovacs

I attached three pathces:

comment:8 in reply to:  7 ; Changed 10 years ago by Alpar Juttner

Replying to kpeter:

I attached three pathces:

Some of the changes results in a warning.

g++ -DHAVE_CONFIG_H   -I. -I.  -Wall -W -Wall -W -Wunused -Wformat=2 -Wctor-dtor-privacy -Wnon-virtual-dtor -Wno-char-subscripts -Wwrite-strings -Wno-char-subscripts -Wreturn-type -Wcast-qual -Wcast-align -Wsign-promo -Woverloaded-virtual -ansi -fno-strict-aliasing -Wold-style-cast -Wno-unknown-pragmas -g -O2 -MT test/graph_utils_test.o -MD -MP -MF $depbase.Tpo -c -o test/graph_utils_test.o test/graph_utils_test.cc &&\
	mv -f $depbase.Tpo $depbase.Po
./lemon/bits/graph_extender.h: In member function 'void lemon::concepts::IterableDigraphComponent<BAS>::Constraints<_Digraph>::constraints() [with _Digraph = lemon::GridGraph, BAS = lemon::concepts::BaseGraphComponent]':
./lemon/bits/graph_extender.h:576: warning: 'iait.lemon::GraphExtender<lemon::GridGraphBase>::InArcIt::<anonymous>.lemon::GridGraphBase::Arc::_id' is used uninitialized in this function
./lemon/concepts/graph_components.h:750: note: 'iait.lemon::GraphExtender<lemon::GridGraphBase>::InArcIt::<anonymous>.lemon::GridGraphBase::Arc::_id' was declared here
./lemon/bits/graph_extender.h:562: warning: 'oait.lemon::GraphExtender<lemon::GridGraphBase>::OutArcIt::<anonymous>.lemon::GridGraphBase::Arc::_id' is used uninitialized in this function
./lemon/concepts/graph_components.h:751: note: 'oait.lemon::GraphExtender<lemon::GridGraphBase>::OutArcIt::<anonymous>.lemon::GridGraphBase::Arc::_id' was declared here

comment:9 in reply to:  8 ; Changed 10 years ago by Peter Kovacs

Replying to alpar:

Some of the changes results in a warning.

I did not get these warnings, but I think I've found the reason for them. The attached bundle file contains three changesets ([48158db1b640], [77a77781b04b], [bf918e729ee7]), which are the same as the former ones except for the fixes for these warnings. Could you please check them?

Changed 10 years ago by Peter Kovacs

Fixed changesets

comment:10 in reply to:  9 Changed 10 years ago by Alpar Juttner

Replying to kpeter:

Replying to alpar:

Some of the changes results in a warning.

I did not get these warnings, but I think I've found the reason for them. The attached bundle file contains three changesets ([48158db1b640], [77a77781b04b], [bf918e729ee7]), which are the same as the former ones except for the fixes for these warnings. Could you please check them?

I still get warnings with gcc 4.3.2 in euler_test.cc

./lemon/adaptors.h: In member function 'void lemon::concepts::GraphIncIt<GR, Item, Base, sel>::Constraints<_GraphIncIt>::constraints() [with _GraphIncIt = lemon::GraphAdaptorExtender<lemon::UndirectorBase<const lemon::ListDigraph> >::InArcIt, GR = lemon::Undirector<const lemon::ListDigraph>, Item = lemon::UndirectorBase<const lemon::ListDigraph>::Arc, Base = lemon::ListDigraphBase::Node, char sel = 'i']':
./lemon/adaptors.h:1919: warning: 'it1.lemon::GraphAdaptorExtender<lemon::UndirectorBase<const lemon::ListDigraph> >::InArcIt::<anonymous>.lemon::UndirectorBase<const lemon::ListDigraph>::Arc::_forward' is used uninitialized in this function
./lemon/concepts/graph_components.h:572: note: 'it1.lemon::GraphAdaptorExtender<lemon::UndirectorBase<const lemon::ListDigraph> >::InArcIt::<anonymous>.lemon::UndirectorBase<const lemon::ListDigraph>::Arc::_forward' was declared here
./lemon/adaptors.h:1920: warning: 'it1.lemon::GraphAdaptorExtender<lemon::UndirectorBase<const lemon::ListDigraph> >::InArcIt::_adaptor' may be used uninitialized in this function
./lemon/concepts/graph_components.h:572: note: 'it1.lemon::GraphAdaptorExtender<lemon::UndirectorBase<const lemon::ListDigraph> >::InArcIt::_adaptor' was declared here
./lemon/list_graph.h:103: warning: 'it1.lemon::GraphAdaptorExtender<lemon::UndirectorBase<const lemon::ListDigraph> >::InArcIt::<anonymous>.lemon::UndirectorBase<const lemon::ListDigraph>::Arc::<anonymous>.lemon::ListDigraphBase::Arc::id' may be used uninitialized in this function
./lemon/concepts/graph_components.h:572: note: 'it1.lemon::GraphAdaptorExtender<lemon::UndirectorBase<const lemon::ListDigraph> >::InArcIt::<anonymous>.lemon::UndirectorBase<const lemon::ListDigraph>::Arc::<anonymous>.lemon::ListDigraphBase::Arc::id' was declared here

comment:11 Changed 10 years ago by Peter Kovacs

I attached another bundle. I don't get warnings with gcc 4.1, 4.2, 4.3.

Changed 10 years ago by Peter Kovacs

comment:12 Changed 10 years ago by Peter Kovacs

I've created another changeset [7a28e215f715] that removes notes from the doc of the graph structures mentioning reference maps as an extra feature.

The newest bundle file contains all these 4 changesets: [d11bf7998905], [2313edd0db0b], [aa1804409f29], [7a28e215f715].

comment:13 in reply to:  12 Changed 10 years ago by Alpar Juttner

Resolution: fixed
Status: assignedclosed

Replying to kpeter:

I've created another changeset [7a28e215f715] that removes notes from the doc of the graph structures mentioning reference maps as an extra feature.

The newest bundle file contains all these 4 changesets: [d11bf7998905], [2313edd0db0b], [aa1804409f29], [7a28e215f715].

All of them are in the main branch now.

Note: See TracTickets for help on using tickets.