[Networkit] request for comments: edge ids and attributes

Marvin Ritter marvin.ritter at gmail.com
Tue Jun 10 17:03:10 CEST 2014


Do you ever want to use GraphWithEdgeAttributes in Python or should it only
be used by in algorithms in C++?

Because if you start with inheriting from Graph and templates I promise you
a lot of fun with Cython if you ever want to make those classes available
to in Python ;)




On Tue, Jun 10, 2014 at 4:37 PM, Florian Weber <uagws at student.kit.edu>
wrote:

> Hi,
>
> > - Every edge is already uniquely identified by a pair {u,v} or tuple
> (u,v) of node identifiers. Can we come up with a clever scheme for
> combining u and v in an integer to serve as edge id?
>
> This would also have been my first idea. To get somewhat more concrete,
> I would do this by inheriting with a template from graph and adding a
> hashmap:
>
> //TODO: Better names
> template<typename Attribute>
> class GraphWithEdgeAttributes: public Graph {
> public:
>         using Graph::Graph; // pull in the ctors again
>         using EdgeID = std::pair<node, node>;
>
>         void setEdgeAttribute(node u, node v, Attribute attr) {
>                 if (v < u) {
>                         std::swap(u, v);
>                 }
>                 attributes[EdgeID{u, v}] = std::move(attr));
>         }
>
> private:
>         std::unordered_map<EdgeID, Attribute> attributes;
> };
>
> Advantages of this approach:
>
> * Doesn't increase the already quite bloaty Graph if unused
> * Attributes of arbitrary types (can be selected by the users)
> * defining a good hashing-algorithm for EdgeID is quite manageable
> * Thanks to inheritance the actual necessary changes are quite small
> * Little overhead if only few Edges have Attributes
>
> Disadvantages:
>
> * Algorithms that want to work with arbitrary Attributes must be
>   implemented as templates (Alternative would be type-erasure, but that
>   implies other disadvantages)
> * If we want to make sure that we only hold attributes for existing
>   edges, we would have to make removeEdge virtual and add some
>   code there. (Alternative: keep the Attributes and provide a
>   gcAttributes-method that removes all unused Attributes;
>   Runtime: O(attributes.size())
> * I guess it could lead to further limitations with the Python-bindings,
>   but I don't know enough about them to comment on these.
> * Some functions currently return Graphs by value (which is a good
>   thing!). If we start using inheritance this might lead to slicing
>   (uncool), so some reviews would be absolutely mandatory.
>
> Further Notes:
>
> * Graph is currently marked as final and doesn't hold virtual methods,
>   this would have to be changed.
>
> Regards,
> Florian
>
>
> _______________________________________________
> NetworKit mailing list
> NetworKit at ira.uni-karlsruhe.de
> https://lists.ira.uni-karlsruhe.de/mailman/listinfo/networkit
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20140610/226e533e/attachment.html>


More information about the NetworKit mailing list