Grafos dinámicos incrementales
Agregar un arco aleatorio
Función solo para agregar un nuevo arco al grafo dado un nodo fuente y un nodo destino
def insert_edge(self, source, target, weight=1):
self.clean_vars()
self.source = np.append(self.source, source)
self.target = np.append(self.target, target)
self.weight = np.append(self.weight, weight)
self.last_edge_updated = np.array([source, target, weight])
self.last_edge_action = "ADD"
self.sort_sources()
return {
"last_edge_updated": self.last_edge_updated,
"last_edge_action": self.last_edge_action
}
Busca todos los pares de nodos que no tengan arco y elige dos aleatorios
def insert_random_edge(self, weights=[1, 2, 3, 4, 5, 6, 7, 8, 9]):
count_max = 100
flag = 0
while True:
source = np.random.choice(self.nodes, 1)[0]
index_for_target = np.invert(np.logical_or(np.in1d(self.nodes, self.target[source == self.source]), self.nodes == source))
choisen = self.nodes[index_for_target]
if choisen.size != 0:
target = np.random.choice(choisen, 1)[0]
break
flag = flag + 1
if flag >= count_max:
return -2
Agregar arco peor caso
Función para encontrar el total de nodos descedentes o ascendetes de un nodo dado. Si to_find es sources entonces encuetra los descendentes, si es targets entonces encuentra los nodos ascendentes
def find_total(self, node, to_find="sources"):
sources = 0
vis = [False for i in self.nodes]
Q = deque([node])
vis[node] = True
while len(Q) > 0:
x = Q.popleft()
list = self.source[self.target == x] if to_find == 'sources' else self.target[self.source == x]
for z in list:
if not vis[z]:
vis[z] = True
Q.append(z)
sources += 1
return sources
Encontramos los nodos que poseen peor escenario. Para esto calculamos el total de nodos descendientes y ascendentes de todos los nodos, buscamos entre los pares que no posee un arco entre sí y elegimos aquel que su producto entre nodos descendes y ascendentes sea mayor.
def find_source_target_worst_scenary_incremental_edge(self):
node_sources = {}
node_targets = {}
for node in self.nodes:
node_sources[node] = self.find_total(node, "sources")
node_targets[node] = self.find_total(node, "targets")
max_path_long = 0
node_source = 0
node_target = 0
for x in self.nodes:
for y in self.nodes:
if x == y:
continue
if self.get_weight(x, y) != np.inf:
continue
total_path_long = node_sources[x] * node_targets[y]
if total_path_long > max_path_long:
max_path_long = total_path_long
node_source = x
node_target = y
return {
"source": node_source,
"target": node_target
}
Función para correrlo:
def insert_worst_edge(self, weight=1):
self.clean_vars()
result_found = self.find_source_target_worst_scenary_incremental_edge()
source = result_found['source']
target = result_found['target']
return self.insert_edge(source, target, weight)
Disminuir el peso de un arco aleatorio
Recibe dos nodos que poseean un arco entre sí y le establece un peso. Por defecto es 1.
def decrease_weight(self, source, target, weight=1):
self.clean_vars()
if weight > self.get_weight(source, target):
return -2
self.weight[np.logical_and(self.source == source, self.target == target)] = weight
if not self.directed:
self.weight[np.logical_and(self.source == target, self.target == source)] = weight
self.last_edge_updated = np.array([source, target, weight])
self.last_edge_action = "DECREASE"
self.sort_sources()
return {
"last_edge_updated": self.last_edge_updated,
"last_edge_action": self.last_edge_action
}
Busca entre dos nodos con arco y disminuye el peso. Lo establece en 0. Si el peso anterior es 0, lo hace -1
def decrease_random_weight(self, weight=1):
count_max = 100
flag = 0
while True:
source = np.random.choice(self.nodes, 1)[0]
index_for_target = np.logical_or(np.in1d(self.nodes, self.target[source == self.source]), self.nodes == source)
choisen = self.nodes[index_for_target]
if choisen.size != 0:
target = np.random.choice(choisen, 1)[0]
weight_current = self.get_weight(source, target)
if weight_current > 1:
weight = 0 if weight_current > 0 else -1
break
flag = flag + 1
if flag >= count_max:
return -2
return self.edge_update(source, target, weight=weight)
Disminuir el peso de un arco en el peor escenario
Usamos la misma función de find_total. Encontramos dos nodos el cual su producto entre nodos descendentes y ascendentes, es el mayor.
def find_edge_worst_scenary_update_edge(self):
node_sources = {}
node_targets = {}
for node in self.nodes:
node_sources[node] = self.find_total(node, "sources")
node_targets[node] = self.find_total(node, "targets")
max_path_long = 0
node_source = 0
node_target = 0
for x in self.nodes:
for y in self.nodes:
if x == y:
continue
if self.get_weight(x, y) == np.inf:
continue
total_path_long = node_sources[x] + node_targets[y]
if total_path_long > max_path_long:
max_path_long = total_path_long
node_source = x
node_target = y
return {
"source": node_source,
"target": node_target
}
Luego de encontrar esos nodos, se disminuye su peso
def decrease_worst_weight(self):
self.clean_vars()
result_found = self.find_edge_worst_scenary_update_edge()
source = result_found['source']
target = result_found['target']
weight_current = self.get_weight(source, target)
weight_new = 0 if weight_current > 0 else -1
return self.decrease_weight(source, target, weight=weight_new)
Correr Algoritmo
Una clase que tiene como objetivo correr todos los algoritmos diseñados. Se arman en una lista y se corre con run_algorithm cada algoritmo
class Algorithm():
def __init__(self, values):
self.attempt = 30
self.graph = Graph.import_values(values)
def list(self):
return {
'static': ['dijkstra-apsp', 'floyd-warshall'],
'incremental': [
'abm',
'rr-bfs-truncated',
'even-gazit',
'quinca',
'forest'
]
}
def run_algorithm(self, algorithm, dist=[[]]):
if algorithm == 'dijkstra-apsp':
return self.run_algorithm_dijkstra_apsp()
if algorithm == 'floyd-warshall':
return self.run_algorithm_floyd_warshall()
if algorithm == 'rr-bfs-truncated':
return self.run_algorithm_rr_bfs_truncated(dist)
if algorithm == 'even-gazit':
return self.run_algorithm_eg(dist)
if algorithm == 'quinca':
return self.run_algorithm_quinca(dist)
if algorithm == 'abm':
return self.run_algorithm_abm(dist)
if algorithm == 'forest':
return self.run_algorithm_forest(dist)
def run_algorithm_floyd_warshall(self):
t = time()
Floyd_Warshall(self.graph)
time_seconds = (time() - t) * 1000
return self.export_algorithm(dist, time_seconds)
def run_algori ...
Correr grafo dinámicos y algoritmos
Antes de correr el laboratorio debes tener unas funciones predeterminadas necesarias:
Preparar carpetas de resultados
Está función genera las carpetas necesarias para guardas los resultados. Sea para exportar el grafo o exportar los resultados y gráficas.
Crea sub carpetas dentro divididos por el tipo de dinamismo del grafo y más adentro por el tipo de grafo en relación con su densidad.
def get_folder(folder, type_incremental, num_nodes, probability_edges=0):
dirType = folder + "/" + type_incremental + "/"
if not os.path.exists(dirType):
os.mkdir(dirType)
dirNode = dirType + str(num_nodes) + "/"
if not os.path.exists(dirNode):
os.mkdir(dirNode)
if probability_edges == 0:
return dirNode
dirEdge = dirNode + str(probability_edges) + "/"
if not os.path.exists(dirEdge):
os.mkdir(dirEdge)
return dirEdge
Exportar matrix
Para exportar la matrix de resultados (matris de distancia) de un grafo. Listo para un archivo
def export_matrix(matrix_result):
matrix_to_export = []
for row in matrix_result:
matrix_to_export.append([
str(a) if a == np.inf else str(int(a))
for a in row
])
return matrix_to_export
Laboratorio Parte 1
Prepara los valores de entrada, estos valores definen cómo será el laboratorio (tipo de grafo, si guarda los resultados, etc)
def run(
type_incremental,
num_nodes,
probability_edges,
num_try=30,
attempt=10,
saveFileExec=True,
labExec=True,
printer=True
):
## Define params
labExec = bool(labExec)
saveFileExec = bool(saveFileExec)
num_nodes = int(num_nodes)
num_try = int(num_try)
attempt = int(attempt)
probability_edges = float(probability_edges)
results = []
dirGraphs = get_folder("synthetics", type_incremental, num_nodes, probability_edges)
dirResults = get_folder("results", type_incremental, num_nodes, probability_edges)
if printer:
print("=============================================")
print("Num nodes: ", num_nodes)
print("Probability Edge: ", probability_edges)
print("Graph count: ", num_try)
print("Try algorithms: ", num_try)
print("Exporting graphs: ", saveFileExec)
print("Exec algorithms: ", labExec)
print("\n")
Laboratorio Parte 2
Aquí se genera el grafo por cada iteración. Se ejecuta el dinamismo del grafo y luego se corre en la clase de Algoritmo. Los resultados se guardan en la variable results.
### Define lab for exec
for i in range(num_try):
print("Loading graph [" + str(num_nodes) + ", " + str(probability_edges) + "]", i, " of ", num_try)
graph = Graph.creategraph(num_nodes, probability_edges)
dist_before = Dijkstra_apsp(graph)
if type_incremental == "decrease_worst_edge":
graph.decrease_worst_weight()
elif type_incremental == "insert_worst_edge":
graph.insert_worst_edge()
elif type_incremental == "decrease_edge":
graph.decrease_random_weight()
else:
graph.insert_random_edge(weights=[1])
calculate = Algorithm(graph.export_values())
calculate.attempt = attempt
### Save graph
if saveFileExec:
graph_values = {
"graph": graph.export_values(),
"dist": export_matrix(dist_before)
}
filename = dirGraphs + "g_" + str(i) + ".json"
with open(filename, 'w') as outfile:
json.dump(graph_values, outfile)
### Exec lab and save on results[]
if labExec:
for algorithm_name in calculate.list()['incremental']:
times = calculate.run_algorithm(algorithm_name, dist_before)
for time in times:
results.append({
"algorithm": algorithm_name,
"time": time,
"nodes": len(calculate.graph.nodes),
"edges": len(calculate.graph.source),
"density": probability_edges,
"type": type_incremental
})
Laboratorio Parte 3
Se exportan los resultados a un archivo csv y se devuelve el nombre del archivo
### Set Data Frame
df = pd.DataFrame(results)
filename = dirResults + "result.csv"
if labExec:
if printer:
print("To export: ", filename)
df.to_csv (filename, index=False, header=True)
print("END")
return {
"dataframe": df,
"filename": filename
}
Graficar resultados
Quizás laa parte más difícil. Antes del núcleo de este módulo hablemos de unas funciones que necesitamos:
Colores por algoritmo
Devuelve los colores para cada algoritmo
def return_colors(algorithms=[]):
colors = {
'rr-bfs-truncated': "#0000FF",
'even-gazit': "#808000",
'quinca': "#FFFF00",
'abm': "#FF0000",
'forest': "#008080"
}
colors_return = []
if algorithms:
for al in algorithms:
colors_return.append(colors[al])
else:
for c in colors:
colors_return.append(colors[c])
return colors
Indexar una lista
Ordena una lista dado un orden de indices
def sortListByIndexing(data, sorted):
newD = []
for iS in sorted:
newD.append(data[iS])
return newD
Calcular límites para partir la gráfica
Algunos datos quedan muy alejados del resto, para eso partimos la gráfica para poder apreciar mejor. Se calcula el dato más alto entre todos y luego el más alto entre todos las demás barras. Se utiliza para partir la gráfica.
def calcLimit(totalTimes):
timesByAlgoritmhs=[]
for ii in range(len(totalTimes[0])):
timesByAlgoritmhs.append([])
for jj in range(len(totalTimes)):
for ii in range(len(totalTimes[jj])):
timesByAlgoritmhs[ii].append(totalTimes[jj][ii])
max = 0
maxOtherLine = 0
min = np.inf
indexMax = -1
for ii in range(len(timesByAlgoritmhs)):
#print(timesByAlgoritmhs[ii])
for value in timesByAlgoritmhs[ii]:
if value > max:
max = value
indexMax = ii
maxOtherLineRead = []
count = 0
minDefined = False
while True:
for ii in range(len(timesByAlgoritmhs)):
if ii == indexMax:
if not minDefined:
for value in timesByAlgoritmhs[ii]:
if value < min:
min = value
continue
for value in timesByAlgoritmhs[ii]:
if value > maxOtherLine and value not in maxOtherLineRead:
maxOtherLine = value
if maxOtherLine > min:
count = count + 1
if count == 5:
break
min = maxOtherLine
minDefined = True
maxOtherLineRead.append(maxOtherLine)
maxOtherLine = 0
else:
break
return [maxOtherLine, min, max]
Algoritmos más rápidos
Otra manera de visualizar mejor las gráficas es deshaciendo los algoritmos que demoran demasiando, dejando solo unos más rápido. Tener en cuenta que el algoritmo abm siempre tiene que aparecer.
def algorithms_faster(data, fasterNum=3):
algoritms_selected = []
while True:
dd = data.groupby('algorithm')['time'].mean().to_frame().sort_values(by=['time'])
algoritms_selected = dd.index.tolist()[:fasterNum]
if 'abm' in algoritms_selected:
break
fasterNum += 1
return algoritms_selected
Graficar resultados Parte 1
Se definen todos valores, como el modo de importar una gráfica, entre otras.
def draw_plot_seaborn_bar(
data,
num_nodes=100,
type_incremental='insert_edge',
densityGroup=True,
densityTypes = 0
):
width = 0.85
colors_g = sns.xkcd_palette(['windows blue', 'amber', 'greyish', 'faded green', 'dusty purple'])
dir = get_folder("figs", type_incremental, num_nodes)
groupF = 'density' if densityGroup else 'algorithms'
densityF = 'small' if densityTypes == 0 else 'large'
densityValues = list(dict.fromkeys(data['density'].values.tolist()))
if densityTypes == 0:
densityValues = [i for i in densityValues if i < 0.08]
else:
densityValues = [i for i in densityValues if i > 0.08]
if densityValues:
data = data.loc[data['density'].isin(densityValues)]
filename = dir + "fig_" + type_incremental + "_" + str(num_nodes) + "_" + groupF + "_" + densityF
dataToPrint = None
Graficar resultados Parte 2
Grafica el primer tipo de gráfica.
if densityGroup:
### Print FIG Times vs Density, group Algorithms)
faster_al = algorithms_faster(data, fasterNum=4)
data_filter = data.loc[data['algorithm'].isin(faster_al)]
dataToPrint = data_filter
ax = sns.barplot(y='time', x='density', data=data_filter, hue="algorithm", capsize=.2, palette=return_colors())
ax.set(xlabel='Edge Density', ylabel='Time (Miliseconds)')
Algoritmos más rápido para densidades 0.1 y 0.5
Graficar resultados Parte 3
La siguiente parte es la que divide la gráfica para datos demasiado elevados.
else:
### Print FIG Times vs Algorithms (Group Density)
fig, ax = plt.subplots()
data_gg = data.groupby('algorithm')['time'].mean().to_frame()
densitySorted = sorted(densityValues)
totalLabels = []
totalTimes = []
totalDensity =[]
totalColor = []
valuesABM = []
dataToPrint = data
for index_d in range(len(densityValues)):
xLabels = data_gg.index.to_list()
density = densityValues[index_d]
indexForColor = densitySorted.index(densityValues[index_d])
color = colors_g[indexForColor]
data_filtered = data.loc[data['density'] == density]
data_filtered_g = data_filtered.groupby('algorithm')['time'].mean().to_frame()
listed = data_filtered_g['time'].to_list()
#listed, xLabels = [ list(tuple) for tuple in zip(*sorted(zip(listed, xLabels), reverse=True))]
totalDensity.append(density)
totalLabels.append(xLabels)
totalTimes.append(listed)
totalColor.append(color)
for jj in range(len(xLabels)):
if xLabels[jj] == 'abm':
valuesABM.append(listed[jj])
ABMsorted = sorted(range(len(valuesABM)), key=lambda k: valuesABM[k])
ABMsorted.reverse()
limit = calcLimit(totalTimes)
### Start to Draw
fig, (ax1,ax2) = plt.subplots(2,1,sharex=True, figsize=(5,6))
ax1.spines['bottom'].set_visible(False)
ax1.tick_params(axis='x',which='both',bottom=False)
ax2.spines['top'].set_visible(False)
ax2.set_ylim(0, limit[0])
ax1.set_ylim(limit[1],limit[2])
for i in ABMsorted:
density = round(totalDensity[i], 2)
xLabels = totalLabels[i]
listed = totalTimes[i]
color = totalColor[i]
bars1 = ax1.bar(xLabels, listed, width, label=str(density), color=color)
bars2 = ax2.bar(xLabels, listed, width, label=str(density), color=color)
for tick in ax2.get_xticklabels():
tick.set_rotation(0)
d = .015
kwargs = dict(transform=ax1.transAxes, color='k', clip_on=False)
ax1.plot((-d, +d), (-d, +d), **kwargs)
ax1.plot((1 - d, 1 + d), (-d, +d), **kwargs)
kwargs.update(transform=ax2.transAxes)
ax2.plot((-d, +d), (1 - d, 1 + d), **kwargs)
ax2.plot((1 - d, 1 + d), (1 - d, 1 + d), **kwargs)
for b1, b2 in zip(bars1, bars2):
posx = b2.get_x() + b2.get_width()/2.
if b2.get_height() > limit[0]:
ax2.plot((posx-3*d, posx+3*d), (1 - d, 1 + d), color='k', clip_on=False,
transform=ax2.get_xaxis_transform())
if b1.get_height() > limit[1]:
ax1.plot((posx-3*d, posx+3*d), (- d, + d), color='k', clip_on=False,
transform=ax1.get_xaxis_transform())
ax1.set_ylabel('Times (Miliseconds)')
ax1.legend()
plt.xticks(rotation=45)
Densidades 0.01 y 0.05
Graficar resultados Parte 4
Última parte, guarda la gráfica en un archivo y los resultados en un csv.
if True:
if dataToPrint is not None:
dataToPrint.to_csv (filename + '.csv', index=False, header=True)
plt.tight_layout()
plt.savefig(filename + '.png', dpi=150)
plt.cla()
plt.clf()
Graficar Resultados por dos tipos
Se expone las dos funciones para representar un modo o el otro.
def draw_all_plot(data, num_nodes, type_incremental, densityTypes = 0):
data_filter = data.loc[ (data['nodes'] == num_nodes) & (data['type'] == type_incremental)]
data_filter_one_calc = data_filter.groupby('algorithm')['time'].mean().to_frame()
data_filter_one_calc['algorithm'] = data_filter_one_calc.index.values
#PLOT
draw_plot_seaborn_bar(
data_filter,
num_nodes=num_nodes,
type_incremental=type_incremental,
densityGroup=False,
densityTypes=densityTypes
)
# Draw Group Density
def draw_group_plot(data, num_nodes, type_incremental, densityTypes=0):
data_filter = data.loc[ (data['nodes'] == num_nodes) & (data['type'] == type_incremental)]
data_filter_one_calc = data_filter.groupby('algorithm')['time'].mean().to_frame()
data_filter_one_calc['algorithm'] = data_filter_one_calc.index.values
draw_plot_seaborn_bar(
data_filter,
num_nodes=num_nodes,
type_incremental=type_incremental,
densityGroup=True,
densityTypes=densityTypes
)
Módulo Principal
Aquí sucede toda la magia, donde se unen todos los módulos anteriores y se establecen los parámetros a seguir
from generate_and_result import run
from export_fig import draw_all_plot, draw_group_plot
import pandas as pd
def read_files(files=[]):
datas = pd.DataFrame()
for filename in files:
data_import = pd.read_csv(filename)
datas = pd.concat([datas, data_import])
return datas
def exec(
num_graphs_random=30,
try_exec_each_graph=10
):
types = [
'insert_edge',
'decrease_edge',
'insert_worst_edge',
'decrease_worst_edge'
]
num_nodes = [
100,
1000,
10000
]
probability_edges = [
0.1,
0.2,
0.3,
0.4,
0.5,
0.01,
0.02,
0.03,
0.04,
0.05
]
files = []
for type in types:
for num_node in num_nodes:
for pp in probability_edges:
# Dataframe
result = run(
type,
num_node,
pp,
num_try = num_graphs_random,
attempt = try_exec_each_graph,
saveFileExec = True,
labExec=True
)
files.append(result['filename'])
df = read_files(files)
for type in types:
for num_node in num_nodes:
draw_all_plot(df, num_node, type, densityTypes=0)
draw_group_plot(df, num_node, type, densityTypes=0)
draw_all_plot(df, num_node, type, densityTypes=1)
draw_group_plot(df, num_node, type, densityTypes=1)
exec()
Comentarios