Module:SMILES2IUPAC/Chain

Module documentationcreatepurge

You might want to create a documentation page for this Scribunto module.
Editors can experiment in this module's sandbox (create | mirror) and testcases (create) pages.
Add categories to the /doc subpage. Subpages of this module.

-- Module:SMILES2IUPAC/Chain
--
-- Generic acyclic-tree algorithms used to select an IUPAC
-- parent chain and its substituents.
--
-- Supports:
--   * acyclic carbon trees
--   * longest-chain selection
--   * priority nodes
--   * substituent detection
--   * lowest-locant comparison

local p = {}

----------------------------------------------------------------------
-- Build adjacency list
----------------------------------------------------------------------

function p.buildAdjacency(nodeSet, edges)
	local adj = {}
	local inSet = {}

	for _, n in ipairs(nodeSet) do
		adj[n] = {}
		inSet[n] = true
	end

	for _, e in ipairs(edges) do
		if inSet[e.a] and inSet[e.b] then
			table.insert(adj[e.a], e.b)
			table.insert(adj[e.b], e.a)
		end
	end

	return adj
end

----------------------------------------------------------------------
-- Check whether graph is a connected tree
----------------------------------------------------------------------

function p.isTree(nodeSet, adj)
	if #nodeSet == 0 then
		return false, 'empty graph'
	end

	local edgeCount = 0

	for _, n in ipairs(nodeSet) do
		edgeCount = edgeCount + #(adj[n] or {})
	end

	edgeCount = edgeCount / 2

	if edgeCount ~= #nodeSet - 1 then
		return false,
			'not a tree (contains a ring, or is disconnected)'
	end

	local visited = {
		[nodeSet[1]] = true
	}

	local queue = {
		nodeSet[1]
	}

	local qi = 1
	local count = 1

	while qi <= #queue do
		local cur = queue[qi]
		qi = qi + 1

		for _, nb in ipairs(adj[cur] or {}) do
			if not visited[nb] then
				visited[nb] = true
				count = count + 1
				table.insert(queue, nb)
			end
		end
	end

	if count ~= #nodeSet then
		return false, 'disconnected graph'
	end

	return true
end

----------------------------------------------------------------------
-- Find leaves
----------------------------------------------------------------------

function p.leaves(nodeSet, adj)
	if #nodeSet == 1 then
		return {
			nodeSet[1]
		}
	end

	local result = {}

	for _, n in ipairs(nodeSet) do
		if #(adj[n] or {}) <= 1 then
			table.insert(result, n)
		end
	end

	return result
end

----------------------------------------------------------------------
-- Find path between two nodes
----------------------------------------------------------------------

function p.pathBetween(adj, startNode, endNode)
	if startNode == endNode then
		return {
			startNode
		}
	end

	local visited = {
		[startNode] = true
	}

	local parent = {}

	local queue = {
		startNode
	}

	local qi = 1

	while qi <= #queue do
		local cur = queue[qi]
		qi = qi + 1

		if cur == endNode then
			break
		end

		for _, nb in ipairs(adj[cur] or {}) do
			if not visited[nb] then
				visited[nb] = true
				parent[nb] = cur
				table.insert(queue, nb)
			end
		end
	end

	if not visited[endNode] then
		return nil
	end

	local path = {
		endNode
	}

	local cur = endNode

	while cur ~= startNode do
		cur = parent[cur]

		if not cur then
			return nil
		end

		table.insert(
			path,
			1,
			cur
		)
	end

	return path
end

----------------------------------------------------------------------
-- Find every longest leaf-to-leaf path
--
-- Important:
-- The parent chain must be the LONGEST possible carbon chain.
-- A shorter chain with more convenient substituents must never
-- replace a longer chain.
----------------------------------------------------------------------

function p.findLongestChains(nodeSet, adj)
	if #nodeSet == 1 then
		return {
			{
				nodeSet[1]
			}
		}
	end

	local leafNodes = p.leaves(
		nodeSet,
		adj
	)

	local bestLength = 0
	local candidates = {}

	for i = 1, #leafNodes do
		for j = i + 1, #leafNodes do

			local path = p.pathBetween(
				adj,
				leafNodes[i],
				leafNodes[j]
			)

			if path then
				local length = #path

				if length > bestLength then
					bestLength = length

					candidates = {
						path
					}

				elseif length == bestLength then
					table.insert(
						candidates,
						path
					)
				end
			end
		end
	end

	return candidates
end

----------------------------------------------------------------------
-- Check whether a path contains any priority node
----------------------------------------------------------------------

local function containsPriorityNodes(
	path,
	prioritySet
)
	if not prioritySet then
		return false
	end

	for _, node in ipairs(path) do
		if prioritySet[node] then
			return true
		end
	end

	return false
end

----------------------------------------------------------------------
-- Get all nodes belonging to a substituent subtree
----------------------------------------------------------------------

function p.substituentSubtree(
	adj,
	root,
	pathSet
)
	local visited = {}
	local result = {}

	local function dfs(node)
		if visited[node] then
			return
		end

		visited[node] = true

		if pathSet[node] then
			return
		end

		table.insert(
			result,
			node
		)

		for _, nb in ipairs(adj[node] or {}) do
			if not visited[nb]
				and not pathSet[nb]
			then
				dfs(nb)
			end
		end
	end

	dfs(root)

	return result
end

----------------------------------------------------------------------
-- Find branches attached to each parent-chain atom
----------------------------------------------------------------------

function p.branchesAlongPath(
	path,
	adj
)
	local pathSet = {}

	for _, n in ipairs(path) do
		pathSet[n] = true
	end

	local branches = {}

	for index, n in ipairs(path) do
		branches[index] = {}

		for _, nb in ipairs(adj[n] or {}) do
			if not pathSet[nb] then

				local nodes =
					p.substituentSubtree(
						adj,
						nb,
						pathSet
					)

				table.insert(
					branches[index],
					{
						root = nb,
						nodes = nodes
					}
				)
			end
		end
	end

	return branches
end

----------------------------------------------------------------------
-- Count substituent branches
----------------------------------------------------------------------

function p.countSubstituents(branches)
	local count = 0

	for _, list in pairs(branches) do
		count = count + #list
	end

	return count
end

----------------------------------------------------------------------
-- Get substituent locants for a numbering direction
----------------------------------------------------------------------

function p.locantsForDirection(
	path,
	branches,
	reversed
)
	local n = #path
	local locants = {}

	for index = 1, n do

		local locant

		if reversed then
			locant = n - index + 1
		else
			locant = index
		end

		for _ = 1, #(branches[index] or {}) do
			table.insert(
				locants,
				locant
			)
		end
	end

	table.sort(locants)

	return locants
end

----------------------------------------------------------------------
-- Compare two locant lists
--
-- Returns:
--   -1 if a is better
--    0 if equal
--    1 if b is better
----------------------------------------------------------------------

function p.compareLocantLists(a, b)
	local n = math.min(
		#a,
		#b
	)

	for i = 1, n do
		if a[i] ~= b[i] then

			if a[i] < b[i] then
				return -1
			else
				return 1
			end
		end
	end

	if #a ~= #b then
		if #a < #b then
			return -1
		else
			return 1
		end
	end

	return 0
end

----------------------------------------------------------------------
-- Determine whether forward numbering is better
----------------------------------------------------------------------

function p.forwardIsBetter(
	path,
	branches
)
	local forward =
		p.locantsForDirection(
			path,
			branches,
			false
		)

	local backward =
		p.locantsForDirection(
			path,
			branches,
			true
		)

	return p.compareLocantLists(
		forward,
		backward
	) <= 0
end

----------------------------------------------------------------------
-- Select the best parent chain
--
-- Priority:
--
-- 1. Longest chain
-- 2. Contains required functional-group/priority atom
-- 3. Greatest number of substituents
-- 4. Lowest locant set
--
-- Since findLongestChains() ONLY returns longest chains,
-- criterion #1 is guaranteed here.
----------------------------------------------------------------------

function p.chooseBestChain(
	nodeSet,
	adj,
	priorityNodes
)
	local candidates =
		p.findLongestChains(
			nodeSet,
			adj
		)

	if #candidates == 0 then
		return nil
	end

	------------------------------------------------------------------
	-- Functional-group priority
	------------------------------------------------------------------

	if priorityNodes
		and next(priorityNodes)
	then

		local filtered = {}

		for _, path in ipairs(candidates) do
			if containsPriorityNodes(
				path,
				priorityNodes
			) then

				table.insert(
					filtered,
					path
				)
			end
		end

		if #filtered > 0 then
			candidates = filtered
		end
	end

	------------------------------------------------------------------
	-- Compare longest-chain candidates
	------------------------------------------------------------------

	local best = nil
	local bestBranches = nil
	local bestLocants = nil
	local bestSubCount = -1

	for _, path in ipairs(candidates) do

		local branches =
			p.branchesAlongPath(
				path,
				adj
			)

		local subCount =
			p.countSubstituents(
				branches
			)

		local forward =
			p.locantsForDirection(
				path,
				branches,
				false
			)

		local backward =
			p.locantsForDirection(
				path,
				branches,
				true
			)

		local locants

		if p.compareLocantLists(
			forward,
			backward
		) <= 0 then
			locants = forward
		else
			locants = backward
		end

		local better = false

		if not best then
			better = true

		elseif subCount > bestSubCount then
			better = true

		elseif subCount == bestSubCount
			and p.compareLocantLists(
				locants,
				bestLocants
			) < 0
		then
			better = true
		end

		if better then
			best = path
			bestBranches = branches
			bestLocants = locants
			bestSubCount = subCount
		end
	end

	return best
end

return p