graphlib icon indicating copy to clipboard operation
graphlib copied to clipboard

Fixed 'sinks' method for undirected graph

Open lynxaegon opened this issue 6 years ago • 3 comments

Fixes #101

lynxaegon avatar Apr 24 '19 10:04 lynxaegon

interesting issue :) I'm trying to think is there is a meaning of sinks and sources in undirected graph as they are equal right?

assafsun avatar Apr 10 '20 09:04 assafsun

interesting issue :) I'm trying to think is there is a meaning of sinks and sources in undirected graph as they are equal right?

What should sources() and sinks() return for a list of nodes without edges? Both return all the nodes?

dforsber avatar Jan 12 '21 13:01 dforsber

interesting issue :) I'm trying to think is there is a meaning of sinks and sources in undirected graph as they are equal right?

What should sources() and sinks() return for a list of nodes without edges? Both return all the nodes?

@dforsber from the API Reference:

# graph.sources()
Returns those nodes in the graph that have no in-edges. Takes O(|V|) time.

# graph.sinks()
Returns those nodes in the graph that have no out-edges. Takes O(|V|) time.

@assafsun is right, in an undirected graph, in-edges and out-edges are the same.

I was using graphlib for a mesh network graph (undirected ofc) and i was using sinks to determine that a node in the network wasn't connected to anything anymore (on disconnects). The sinks term was just better for me. Looking back, i should probably update the PR to make the sources() and sinks() do the same thing for an undirected graph

lynxaegon avatar Jan 20 '21 13:01 lynxaegon