[Networkit] request for comments: edge ids and attributes

Florian Weber uagws at student.kit.edu
Tue Jun 10 16:37:14 CEST 2014


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

-------------- n?chster Teil --------------
Ein Dateianhang mit Bin?rdaten wurde abgetrennt...
Dateiname   : signature.asc
Dateityp    : application/pgp-signature
Dateigr??e  : 901 bytes
Beschreibung: OpenPGP digital signature
URL         : <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20140610/1bc3adac/attachment-0001.sig>


More information about the NetworKit mailing list