TADM2E 5.19 - Revision history

Matt: Undo revision 808 by Hdyldhdlgzos (talk)

2020-07-23T15:58:15Z

Undo revision 808 by Hdyldhdlgzos (talk)

Hdyldhdlgzos: Blanked the page

2020-07-16T06:28:17Z

Blanked the page

MagalooXX: Created page with " for any node in the tree, there are two possibilities # either the diameter is contained in one of the subtrees # or the node itself is at the top of the longest path in the..."

2014-10-21T15:38:18Z

Created page with " for any node in the tree, there are two possibilities # either the diameter is contained in one of the subtrees # or the node itself is at the top of the longest path in the..."

New page

for any node in the tree, there are two possibilities
# either the diameter is contained in one of the subtrees
# or the node itself is at the top of the longest path in the tree that defines the diameter

in the second case, the diameter is equal to the sum of depth of the two deepest sub-trees of that node

the following algorithm calculates the diameter in <math>O(n)</math> time

<source lang="python">

class Node:

def __init__(self, value, children):
self.value = value
self.children = children

@classmethod
def preorder(cls, lists):
return cls(
lists[0],
[cls.preorder(l) for l in lists[1:]]
)

def dd(root):
"""
returns depth, diameter for tree with given root node

>>> dd(Node.preorder([0, [1], [2]]))
(1, 2)
>>> dd(Node.preorder([1, [2, [3]], [4, [5]]]))
(2, 4)
>>> dd(Node.preorder([1, [2, [3, [4]], [5, [6, [7], [8]]]], [9]]))
(4, 5)
"""
d1 = d2 = -1
md = 0
for child in root.children:
depth, diameter = dd(child)
if diameter > md:
md = diameter
if depth >= d1:
d2 = d1
d1 = depth
elif depth > d2:
d2 = depth
return d1 + 1, max(md, d1 + d2 + 2)

if __name__ == "__main__":
import doctest
doctest.testmod()

</source>

← Older revision		Revision as of 06:28, 16 July 2020
Line 1:		Line 1:

−	~~for any node in the tree, there are two possibilities~~
−	~~# either the diameter is contained in one of the subtrees~~
−	~~# or the node itself is at the top of the longest path in the tree that defines the diameter~~
−
−	~~in the second case, the diameter is equal to the sum of depth of the two deepest sub-trees of that node~~
−
−	~~the following algorithm calculates the diameter in <math>O(n)</math> time~~
−
−	~~<source lang="python">~~
−
−	~~class Node:~~
−
−	~~def __init__(self, value, children):~~
−	~~self.value = value~~
−	~~self.children = children~~
−
−	~~@classmethod~~
−	~~def preorder(cls, lists):~~
−	~~return cls(~~
−	~~lists[0],~~
−	~~[cls.preorder(l) for l in lists[1:]]~~
−	)
−
−
−	~~def dd(root):~~
−	~~"""~~
−	~~returns depth, diameter for tree with given root node~~
−
−	~~>>> dd(Node.preorder([0, [1], [2]]))~~
−	~~(1, 2)~~
−	~~>>> dd(Node.preorder([1, [2, [3]], [4, [5]]]))~~
−	~~(2, 4)~~
−	~~>>> dd(Node.preorder([1, [2, [3, [4]], [5, [6, [7], [8]]]], [9]]))~~
−	~~(4, 5)~~
−	~~"""~~
−	~~d1 = d2 = -1~~
−	~~md = 0~~
−	~~for child in root.children:~~
−	~~depth, diameter = dd(child)~~
−	~~if diameter > md:~~
−	~~md = diameter~~
−	~~if depth >= d1:~~
−	~~d2 = d1~~
−	~~d1 = depth~~
−	~~elif depth > d2:~~
−	~~d2 = depth~~
−	~~return d1 + 1, max(md, d1 + d2 + 2)~~
−
−
−	~~if __name__ == "__main__":~~
−	~~import doctest~~
−	~~doctest.testmod()~~
−
−	~~</source>~~

← Older revision	Revision as of 15:58, 23 July 2020
Line 1:	Line 1:

	+	for any node in the tree, there are two possibilities
	+	# either the diameter is contained in one of the subtrees
	+	# or the node itself is at the top of the longest path in the tree that defines the diameter
	+
	+	in the second case, the diameter is equal to the sum of depth of the two deepest sub-trees of that node
	+
	+	the following algorithm calculates the diameter in <math>O(n)</math> time
	+
	+	<source lang="python">
	+
	+	class Node:
	+
	+	def __init__(self, value, children):
	+	self.value = value
	+	self.children = children
	+
	+	@classmethod
	+	def preorder(cls, lists):
	+	return cls(
	+	lists[0],
	+	[cls.preorder(l) for l in lists[1:]]
	+	)
	+
	+
	+	def dd(root):
	+	"""
	+	returns depth, diameter for tree with given root node
	+
	+	>>> dd(Node.preorder([0, [1], [2]]))
	+	(1, 2)
	+	>>> dd(Node.preorder([1, [2, [3]], [4, [5]]]))
	+	(2, 4)
	+	>>> dd(Node.preorder([1, [2, [3, [4]], [5, [6, [7], [8]]]], [9]]))
	+	(4, 5)
	+	"""
	+	d1 = d2 = -1
	+	md = 0
	+	for child in root.children:
	+	depth, diameter = dd(child)
	+	if diameter > md:
	+	md = diameter
	+	if depth >= d1:
	+	d2 = d1
	+	d1 = depth
	+	elif depth > d2:
	+	d2 = depth
	+	return d1 + 1, max(md, d1 + d2 + 2)
	+
	+
	+	if __name__ == "__main__":
	+	import doctest
	+	doctest.testmod()
	+
	+	</source>