It's impossible to get all edges at once for {v: a, w: b} when multigraph:true about graphlib HOT 5 CLOSED

This should help: https://github.com/cpettitt/graphlib/wiki/API-Reference#nodeEdges.

from graphlib.

Yes this will works, but this method has two drawbacks:

1. Does not respect direction
2. takes O(|E|)

I've implemented this in other way:

var g = new Graph(); //multigraph: false

//adding first edge - with id "edge1"
g.setEdge("a", "b", {"edge1": {otherInfo: "..."}});

//get info about all edges between "a", "b"
var edgeInfo = g.edge("a", "b"); // -> {"edge1": {otherInfo: "..."}}

//adding second edge
edgeInfo["edge2"] = {"otherInfo": "..."}

//check all edges between a, b:
var edgeInfo = g.edge("a", "b"); // -> {"edge1": {otherInfo: "..."}, "edge2": {otherInfo: ""}}

This works, but it also has drawbacks:

1. I need to manually handle edges object
2. Algorithms such as dijkstra will not work correctly since they do not know about that surrogate edges.

UPD: with my solution dijkstra will works if edgeFn will be correctly implemented.

from graphlib.

https://github.com/cpettitt/graphlib/wiki/API-Reference#inEdges and https://github.com/cpettitt/graphlib/wiki/API-Reference#outEdges give you directionality. Storing multi-edges directly in the label will have the same worst case time complexity as the above. In practice the above might be faster - it'd have to be measured.

from graphlib.

Well i thought that this operation:

//check all edges between a, b:
var edgeInfo = g.edge("a", "b"); // -> {"edge1": {otherInfo: "..."}, "edge2": {otherInfo: ""}}

takes constant O(1) time

What is the worst case you are talking about?

from graphlib.

@sprilukin You're right, the access itself is going to take constant time. The linear time complexity comes in when you try to scan the list. Your approach is fine, but you may or may not get a speed up in practice to compensate for having to carry additional traversal logic along with the graph (e.g. edgeFn).

from graphlib.