vladimir josef sykora wrote: > > > Having internal properties means the mapping edge_descriptor -> 'edge > > > color' and vertex_descriptor -> 'vertex color' is needed. > > > > I don't understand what you mean, <snip> > > I'm using customized-internal properties that do not have 'color' > information. Now, algorithms (undirected_dfs() for example) need to map > each vertex and edge to its respective color, so in the previous case, the > maps must be passed as arguments to the algorithms (OTOH, if I were using > color_maps for both vertex and edge internal properties, the > bgl_named_params<> version of the function would do the job, and I wouldn't > care about the mapping.) That's what I meant when I said that having > internal properties requires the mapping .
Understood. You can't attach vertex_color like adjacency_list class allows, right? > > > For vertex-color > > > mapping this is straightforward because vertex_descriptor is of type > > size_t > > > > (when using vectS) and the mapping can be easily implemented with a > > > random-access container. > > > > Unless your graph can grow! You'd have to automatically grow container > > then, > > > if you want to continue using the same property map. I've implemented > > such a property map, but so far, Jeremy has not commented. > > You're right. Did you overload add_vertex() and/or add_edge() functions to > receive the 'property' container or a std::back_insert_iterator (pointing > to the prop. cont.)? No, I've made the [] method of property map resize the underlying vector if index is out of range. Quite simple. > > > However, for edge-color mapping this is not the > > > case. I did it using std::map<std::pair<size_t, size_t>, color_type>, > > and > > > > of course, overloading put() and get(), not without first inspecting > > that > > > > edge_descriptor type has two data-members: m_source, and m_target, so > > the > > > > functions would look like: > > > > I always though that you should be able to add external edge / vertex > > property > > > to every graph. > > I guess you're saying "customized properties": i.e. properties that are not > provided by the BGL. I doubt that external properties could be attached to > the graph (at least I don't know how); once the internal properties are > taken, external maps are needed. One can concatenate properties though, but > then the bgl_named_params<> version of the algorithms won't work anymore. Rereading my sentence, I understand that is was poorly worded. I meant that I should be able to create, for every kind of graph, external property map that will work without requiring me to manually assign indices. > >Specifically, for all graphs both vertex_descriptor and > > edge_descriptor should be comparable, so that you can use map directly. > > Can you tell me more about this? AFAIK, vertex_descriptor is of type size_t > (vecS) and edge_descriptor is of type ::boost::detail::edge_base<>. I meant that std::map< typename graph_traits<G>::vertex_descriptor>, int> and std::map< typename graph_traits<G>::edge_descriptor>, int> should always work, regardless of the type 'G'. size_t will work now (although inefficient). But edge_base<> is not comparable, so it won't work. I think it should have operator< > > > For some kinds of graph, vertices and edges should have automatically > > assigned > > > indices. > > Of course, since vertices and edges are strored in Sequences, and they > inherently have indices. The point is how to enumerate them > comprehensively. For vertices is no problem: one can do: vertex-number = > sequence-index. But what happens with edges? For example, what happens when > I want to get the edge connecting v1 with v2? Which scalar should I assign > to that edge? What BGL does is navigate through the whole out-edge-list of > v1 until an edge is found that has v2 for target. Otherwise the edge is not > found. But there's no way in constant time to check if an edge exists or > not. I think that edge_descriptor should contain edge index inside it. When you create new edge, the next free index is allocated from a list of free indices (or num_edges(g) is used). When you delete edge, it's index is added to the list of free indices. This design requires one extra int per edge, plus the store of free indices --- the max number of edges graph ever had, in the worsts case, but probably quite little in practice. > > In both cases, you should be able to write > > > > edge_property_map<G, int>::type pm; > > > > and have it work. What do you think? > > AFAIK, that's for internal properties. Please correct me if I'm wrong. I don't know what this syntax does now :-) I mean that this or similiar syntax should be used to find the type suitable for external property map. > > I think that external property maps should be improved, like I describe > > above > > > or it some other way. It hits me quite often. > > I guess you're refering to the documentation; if that's the case, I agree. Documentation hits me too. But I would also like to be able to provide external properties for edges easily. As it is now, I prefer to assume edge_weight_t as internal property: not very generic, of course. - Volodya _______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
