MSTcreator/GenGraph.py at master · usbogie/MSTcreator · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#!/usr/bin/python

from Node import Node
import random

def generateNodes(graphSize, totalNodes, k):
	nodeSet = list()
	n = 0
	while (n<totalNodes):
		nodeSet.append(randomNode(graphSize, k))
		n += 1
	return nodeSet

def randomNode(graphSize , k):
	x = random.randrange(0, graphSize+1)
	y = random.randrange(0, graphSize+1)
	kval = random.randrange(1, (10*k)+1)
	return Node(x, y, kval, dict())

def generateEdges(nodeSet, maxWeight, k, edgeMethod):
	outer = 0
	for n in nodeSet:
		inner = 0
		for m in nodeSet:
			if inner > outer and abs(n.kval - m.kval) <= k:
				weight = 0
				if edgeMethod == 2:
					weight = random.randrange(1,maxWeight+1)
				elif edgeMethod == 1:
					weight = ((n.xloc - m.xloc)**2 + (n.yloc - m.yloc)**2)**.5
				n.adjList[m] = weight
				m.adjList[n] = weight
			inner += 1
		outer += 1

def generateTrees(nodeSet):
	nodes = list(nodeSet)
	trees = list()
	for n in reversed(nodeSet):
		if n in nodes:
			tree = runDFS({}, n)
			for m in tree:
				nodes.remove(m)
			trees.append(tree)
	return trees

def runDFS(tree, node):
	if node in tree:
		return dict()
	else:
		tree[node] = node.adjList
		newTree = dict()
		for n in node.adjList:
			newTree = merge_two_dicts(newTree, runDFS(tree, n))
		newTree[node] = node.adjList
		return newTree

def merge_two_dicts(x, y):
    z = x.copy()
    z.update(y)
    return z

def filterNodes(nodes):
	for n in reversed(nodes):
		if not n.adjList:
			nodes.remove(n)
	return nodes

def GenerateGraph(totalNodes, graphSize, maxWeight, kval, edgeMethod):
	nodes = generateNodes(graphSize, totalNodes, kval)
	generateEdges(nodes, maxWeight, kval, edgeMethod)
	trees = generateTrees(filterNodes(nodes))
	return trees