TIL-20220704

DSNA

• (pythonds3) 8.6. Implementation

class Vertex:
	def __init__(self, key):
		self.id = key
		self.connectedTo = {}

	def addNeighbor(self, nbr, weight=0):
		self.connectedTo[nbr] = weight

	def __str__(self):
		return str(self.id) + ' connected to: ' + str([x.id for x in self.connectedTo])

	def getConnections(self):
		return self.connectedTo.keys()

	def getId(self):
		return self.id

	def getWeight(self, nbr):
		return self.connectedTo[nbr]

class Graph:
	def __init__(self):
		self.vertList = {}
		self.numVertices = 0

	def addVertex(self, key):
		self.numVertices = self.numVertices + 1
		newVertex = Vertex(key)
		self.vertList[key] = newVertex
		return newVertex

	def getVertex(self, n):
		if n in self.vertList:
			return self.vertList[n]
		else:
			return None

	def __contains__(self, n):
		return n in self.vertList

	def addEdge(self, f, t, weight=0):
		if f not in self.vertList:
			nv = self.addVertex(f)
		if t not in self.vertList:
			nv = self.addVertex(t)
		self.vertList[f].addNeighbor(self.vertList[t], weight)

	def getVertices(self):
		return self.vertList.keys()

	def __iter__(self):
		return iter(self.vertList.values())

• (pythonds3) 8.7. The Word Ladder Problem

  FOOL
  POOL
  POLL
  POLE
  PAGE
  SALE
  SAGE

  • BFS(Breadth First Search)를 사용하면 쉽게 해결

• (pythonds3) 8.8. Building the Word Ladder Graph

  

  

from pythonds.graphs import Graph

def buildGraph(wordFile):
	d = {}
    g = Graph()
    
    wfile = open(wordFile, 'r')
    
    # create buckets of words that differ by one letter
    for line in wfile:
    	word = line[:-1]
        for i in range(len(word)):
        	bucket = word[:i] + '_' + word[i+1:]
            if bucket in d:
            	d[bucket].append(word)
            else:
            	d[bucket] = [word]
    
    # add vertices and edges for words in the same bucket
    for bucket in d.keys():
    	for word1 in d[bucket]:
        	for word2 in d[bucket]:
            	if word1 != word2:
                	g.addEdge(word1, word2)
    
    return g

• 5,110 * 5,110 = 26,112,110 (adjacency matrix)
• 53,286 (adjacency list, 0.20% -> sparse)

LINKS