in Graph

How to discover sink nodes in a graph

We all understand graphs or networks are composed of nodes and edges. Some of these nodes can exist in a directed or undirected structure. In a directed graph, their edges can be either incoming or outgoing from a given node. A sink refers to a node in a directed graph with no outgoing edges. Simply, you can view a sink as someone who receives a lot but never chooses to give. Or, is obsessed with hoarding.

In a social network, a sink or from a friendship node will be poor in passing on important information to the group. On the other hand, they might be great at keeping secrets and avoiding allowing things to slip up. A sink could either be local or global. Local sinks are also referred to as a terminal and are directed graphs with no departing edge. A global sink is usually viewed as a sink and is a node that is reached by all the nodes in a given directed graph. 

Simple illustration of a sink node

We do understand sink nodes do not have an edge emanating from them to other nodes in the specific graph. It will be important to express local and global nodes with two diagrams to drive home the point.

Local sink: In a local sink situation, all nodes are connected and lead to the sink. As earlier stated, the sink node exists because no edges are emanating from the orange coloured vertex. In a friendship network, imagine a friend is the source of exciting news of employment. This information is then shared from one blue node to the next with an instruction to keep the exciting update or development within the network. From the illustration below, it is clear to see that the orange node receives this great news from other friends in the same social network or community, but is unable to share that with any other node due to the command to keep the news within and the facts that every friend in the network is fully acquainted with the news. In this case, the network is considered local and the orange node is a sink due to the absence of an outgoing edge. 

Universal Sink: In the illustration below, clearly indicates the shaded node appears to be the sink in this graph. It is because all nodes are pointing towards the sink and there are no outgoing edges from the sink. A key differentiator between this structure in comparison to that of the local sink is the limited connection between the non-sink nodes. Unlike in a local sink node graph, all nodes are mostly connected whilst pointed towards the designated sink. 

Here is a simple code implementation in Python and inspired by source

# Actual return of the number of sink nodes.
def presentSink(a, m, edgeFrom, edgeTo):
	# Array for marking the non-sink node.
	mark = [0] * (a + 1)

	# Indicating the non-sink node.
	for i in range(m):
		mark[edgeFrom[i]] = 1

	# Actual count of the sink nodes.
	count = 0
	for i in range(1, a + 1):
		if (not mark[i]):
			count += 1

	return count

# Graph connection
if __name__ == '__main__':
	a = 4
	m = 2
	edgeFrom = [2, 4]
	edgeTo = [3, 3]

	print(presentSink(a, m, edgeFrom, edgeTo))

# This code is inspired by PranchalK

Write a Comment