thbighead’s gists

thbighead / busca_em_largura.py

Last active July 4, 2022 13:01

Snippet em Python para criar uma busca em largura de Grafos

	grafo = {
	'a': ['b', 'd', 'e'],
	'b': ['a', 'c', 'e'],
	'c': ['b', 'e'],
	'd': ['a', 'e'],
	'e': ['a', 'b', 'c', 'd', 'f'],
	'f': ['e']
	}

	def busca_em_largura(grafo, vertice_do_grafo):

thbighead / busca_em_profundidade.py

Last active October 29, 2019 22:55

Snippet em Python para criar uma busca em profundidade de Grafos

thbighead / criador_de_grafos.py

Created April 17, 2017 00:55

Criador de grafos em representacao de matriz de adjacencias feito com Python

	def cria_grafo(lista_de_vertices, lista_de_arestas):
	grafo = {}
	for vertice in lista_de_vertices:
	grafo[vertice] = []
	for aresta in lista_de_arestas:
	grafo[aresta[0]].append(aresta[1])
	return grafo

thbighead / transpor_digrafo.py

Created April 17, 2017 02:48

Calcular a transposicao de um digrafo feito com Python

	def transpor_digrafo(digrafo):
	digrafo_t = {}
	for vertice in digrafo:
	digrafo_t[vertice] = []
	for vertice in digrafo:
	for vizinho in digrafo[vertice]:
	digrafo_t[vizinho].append(vertice)
	return digrafo_t

thbighead / classificacao_arestas_profundidade_digrafo.py

Last active April 20, 2017 01:30

Classificando arestas da arvore de busca em profundidade feita em um digrafo com Python

	# coisos globais
	valor_profundidade_entrada = 0 # contador da profundidade em que os vertices entram da pilha (chamado recursivamente)
	valor_profundidade_saida = 0 # contador da profundidade em que os vertices saem da pilha (termina sua chamada recursiva)
	# dicionario com as profunfidades em que cada vertice entrou e saiu da pilha numa lista [profundidade_entrada, profundidade_saida]
	profundidades_entrada_saida = {}
	pai = {} # dicionario com os pais de cada vertice na arvore de busca em profundidade
	aresta = {} # classificacao das arestas na arvore de busca em profundidade do grafo
	niveis = {} # nivel de cada vertice na arvore de busca em profundidade
	# conjunto de vertices ainda nao visitados (nunca entraram (e portanto nem sairam) da pilha)
	nao_visitados = set()

thbighead / k_s.py

Last active April 20, 2017 01:27

Algoritmo k-s feito em Python (usado para descobrir os CFCs de um digrafo)

	# coisos globais
	valor_profundidade_entrada = 0 # contador da profundidade em que os vertices entram da pilha (chamado recursivamente)
	valor_profundidade_saida = 0 # contador da profundidade em que os vertices saem da pilha (termina sua chamada recursiva)
	# dicionario com as profunfidades em que cada vertice entrou e saiu da pilha numa lista [profundidade_entrada, profundidade_saida]
	profundidades_entrada_saida = {}
	pai = {} # dicionario com os pais de cada vertice na arvore de busca em profundidade
	aresta = {} # classificacao das arestas na arvore de busca em profundidade do grafo
	niveis = {} # nivel de cada vertice na arvore de busca em profundidade
	# conjunto de vertices ainda nao visitados (nunca entraram (e portanto nem sairam) da pilha)
	nao_visitados = set()

thbighead / encontrar_ciclos_digrafo.py

Last active April 20, 2017 14:53

Encontra e salva os ciclos de um digrafo usando uma busca em profundidade (complexidade nao piora, continua O(n+m))

	from copy import deepcopy

	# coisos globais
	valor_profundidade_entrada = 0 # contador da profundidade em que os vertices entram da pilha (chamado recursivamente)
	valor_profundidade_saida = 0 # contador da profundidade em que os vertices saem da pilha (termina sua chamada recursiva)
	# dicionario com as profunfidades em que cada vertice entrou e saiu da pilha numa lista [profundidade_entrada, profundidade_saida]
	profundidades_entrada_saida = {}
	pai = {} # dicionario com os pais de cada vertice na arvore de busca em profundidade
	aresta = {} # classificacao das arestas na arvore de busca em profundidade do grafo
	niveis = {} # nivel de cada vertice na arvore de busca em profundidade

thbighead / recursive_delete_folder.php

Created May 5, 2017 13:29

Function to delete a folder and every folders and files inside of it

	function recurse_delete($path)
	{
	if (is_dir($path) === true)
	{
	$files = array_diff(scandir($path), array('.', '..'));

	foreach ($files as $file)
	{
	recurse_delete(realpath($path) . '/' . $file);
	}

thbighead / recursive_copy_folder.php

Last active June 22, 2020 14:14

Copy a folder and every folders and files inside of it

	function recursive_copy($source, $destination)
	{
	if (is_dir($source) === true) {
	$success = true;

	if (!file_exists($destination)) {
	mkdir($destination, 0777, true);
	}

	$files = array_diff(scandir($source), ['.', '..']);

thbighead / disjoint_sets.py

Created May 7, 2017 00:20

disjoint sets meio torto escrito em Python (o que eu fiz em C eh que eh o bicho!)

	sets = {}
	setsRanked = {}

	def makeSet(x):
	sets[x] = set([x])

	def find(x):
	for representative,subset in sets.iteritems():
	if x in subset:
	return representative

Thales Nathan thbighead