[Networkit] request for comments: edge ids and attributes

Christian Staudt christian.staudt at kit.edu
Tue Jun 10 13:32:58 CEST 2014

Hi NetworKit developers,

in the following I will summarize and comment on a proposal by Michael Hamann. The goal is to improve support for edge attributes by assigning identifiers to edges. Edge attributes of arbitrary type could then be stored outside the graph data structure, e.g. in a std::vector<T>.

Proposed solution:

- Assign an integer id to each edge.
- Store it in a structure analog to the adjacencies: Node u has two vectors associated with it. If there is an edge {u,v}, the adjacency v is appended to one vector and a new node id is appended to the other vector.
- Iterator methods are provided that (optionally) pass the edge id to a handle function:
	G.forEdgesWithIds([&](node u, node v, index edgeId) {

Open questions:

a) Should it be possible to map an edge id back to the source and target nodes?
b) Is it problematic that the order of edge ids depends on the order of edge insertions, which may not be the same as the read access order, leading to inefficient memory access patterns? Proposed solution: Assign edge ids in the correct order after the graph is completely built.

(Michael, did I summarize this correctly?)

My comments:

- Support for edge attributes beyond simple weights is probably a necessary feature for many real-world network studies. We should provide this soonish.
- Edge ids would effectively double the memory footprint of a graph. They should therefore be optional, just as weights are currently.

a) I suppose this is not strictly necessary.
b) It is possible to wait with the enumeration of edges until the graph has been built to improve the memory access patterns. (When dealing with dynamic graphs, the problem returns however).

Vague alternative ideas:

- 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? 

Everybody is invited to comment on this - especially the team currently working on the new directed graph.

Best regards

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 495 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <https://lists.ira.uni-karlsruhe.de/mailman/private/networkit/attachments/20140610/c4e2bd87/attachment.sig>

More information about the NetworKit mailing list