3680947894

Build Type

github

Committed by GitHub

Commit Message

Merge a6cd61918 into b40be3bdd

Pull Request Pull Request #81: Updates coveralls.io configuration

Run Details

845 of 1796 relevant lines covered (47.05%)

0.47 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

24.6

/src/Utility/functions.py

# -*- coding: utf-8 -*-
"""
Created on Wed Aug 11 16:40:56 2021

@author: Yufeng Xin (yxin@renci.org)
"""

import copy
import random

import networkx as nx
from networkx.algorithms import approximation as approx

import Utility.global_name as global_name


class GraphFunction:
    def __init__(self, g=None) -> None:
        self.graph = g

    def set_graph(self, g=None):
        self.graph = g

    # set weight (cost) per link, assuming the objective is minizing a function of weight
    #   flag:
    #       1: bw: weight = alpha*(1.0/bw)
    #       2: latency: weight = latency
    #       3: random: weight = random cost
    #       4: cost: given from outside (static) definition
    #       0 and default: hop: weight =1
    def weight_assign(self, flag=0, cost=None):

        distance_list = []

        if flag == 1:
            for (u, v, w) in self.graph.edges(data=True):
                # w[global_name.weight] = global_name.Max_L_BW - w[global_name.bandwidth]
                w[global_name.weight] = global_name.alpha * (
                    1.0 / w[global_name.bandwidth]
                )
                distance_list.append(w[global_name.weight])
        elif flag == 2:
            for (u, v, w) in self.graph.edges(data=True):
                w[global_name.weight] = w[global_name.latency]
                distance_list.append(w[global_name.weight])
        elif flag == 3:
            for (u, v, w) in self.graph.edges(data=True):
                w[global_name.weight] = random.randint(1, 2**24)
                distance_list.append(w[global_name.weight])
        elif flag == 4:
            for (u, v, w) in self.graph.edges(data=True):
                w[global_name.weight] = cost[u, v]
                distance_list.append(w[global_name.weight])
        else:
            for (u, v, w) in self.graph.edges(data=True):
                w[global_name.weight] = 1.0
                distance_list.append(w[global_name.weight])
        self.distance_list = distance_list
        return distance_list

    # if u and v connected
    def nodes_connected(g, u, v):
        return u in g.neighbors(v)

    def get_connectivity(self):
        con = approx.node_connectivity(self.graph)
        return con

    def biconnectivity(self):
        pass


# use dijsktra to get the primary shortest path
def dijnew(graph, start_node, end_node):
    graph_new = graph_simplify(graph)
    shortest_distance = {}
    predecessor = {}
    unseenNodes = graph_new
    infinity = 9999999
    path = []
    for node in unseenNodes:
        shortest_distance[node] = infinity
    shortest_distance[start_node] = 0

    while unseenNodes:  # loop all the nodes in the list
        minNode = None
        for node in unseenNodes:
            if minNode is None:
                minNode = node
            elif shortest_distance[node] < shortest_distance[minNode]:
                minNode = node  # find the current node

        for childNode, weight in graph[minNode].items():
            if weight + shortest_distance[minNode] < shortest_distance[childNode]:
                shortest_distance[childNode] = weight + shortest_distance[minNode]
                predecessor[childNode] = minNode
        unseenNodes.pop(minNode)

    currentNode = end_node  # run path backwards to get the real path
    while currentNode != start_node:
        try:
            path.insert(0, currentNode)
            currentNode = predecessor[currentNode]
        except KeyError:
            print("Path not reachable")
            break
    path.insert(0, start_node)
    if (
        shortest_distance[end_node] != infinity
    ):  # check if the end_node has been reached
        print("Shortest distance is " + str(shortest_distance[end_node]))
        print("And the path is " + str(path))
    return path


# make the non-simple graph to be the simple graph
def graph_simplify(graph):
    for node in graph:
        for endpoint in graph[node]:
            try:
                if len(graph[node][endpoint]) > 1:
                    shortest = min(graph[node][endpoint])
                    graph[node][endpoint] = shortest
            except TypeError:
                pass
    return graph


# remove the primary shortest path and redo the dijsktra to get the backup path
def backup_path(graph, start_node, end_node):
    backupstart_node = start_node
    backupend_node = end_node
    graphprimary = copy.deepcopy(graph)
    graph_original = copy.deepcopy(graph)
    graph_new = graph_simplify(graph)
    print("The primary path: ")
    path = dijnew(graphprimary, start_node, end_node)
    path_new = path.copy()
    path_new.pop()

    for (
        ele
    ) in path_new:  # update the graph, delete the path that was used in primary path
        index = path.index(ele)
        try:
            graph_original[ele][path[index + 1]].remove(graph_new[ele][path[index + 1]])
        except AttributeError:
            del graph_original[ele][path[index + 1]]

    for start_node in graph_original:  # reformat the updated graph list
        for end_node in graph_original[start_node]:
            try:
                if len(graph_original[start_node][end_node]) == 1:
                    graph_original[start_node][end_node] = graph_original[start_node][
                        end_node
                    ][0]
            except TypeError:
                continue

    print("The back up path: ")
    dijnew(graph_original, backupstart_node, backupend_node)


def create_unvisited_list(link_list):
    unvisited_list = []
    for keys in link_list:
        unvisited_list.append(keys)
    return unvisited_list


def create_unvisited_node(my_list):
    unvisited_node = {}
    for keys in my_list:
        unvisited_node[keys] = 0
    return unvisited_node


def get_graph_info(link_list):
    key_list = []
    for keys in link_list:
        key_list.append()
    print(key_list)

1	# -- coding: utf-8 --
2	"""	1✔
3	Created on Wed Aug 11 16:40:56 2021
4
5	@author: Yufeng Xin (yxin@renci.org)
6	"""
7
8	import copy	1✔
9	import random	1✔
10
11	import networkx as nx	1✔
12	from networkx.algorithms import approximation as approx	1✔
13
14	import Utility.global_name as global_name	1✔
15
16
17	class GraphFunction:	1✔
18	def __init__(self, g=None) -> None:	1✔
19	self.graph = g	1✔
20
21	def set_graph(self, g=None):	1✔
22	self.graph = g	1✔
23
24	# set weight (cost) per link, assuming the objective is minizing a function of weight
25	# flag:
26	# 1: bw: weight = alpha*(1.0/bw)
27	# 2: latency: weight = latency
28	# 3: random: weight = random cost
29	# 4: cost: given from outside (static) definition
30	# 0 and default: hop: weight =1
31	def weight_assign(self, flag=0, cost=None):	1✔
32
33	distance_list = []	1✔
34
35	if flag == 1:	1✔
36	for (u, v, w) in self.graph.edges(data=True):	×
37	# w[global_name.weight] = global_name.Max_L_BW - w[global_name.bandwidth]
38	w[global_name.weight] = global_name.alpha * (	×
39	1.0 / w[global_name.bandwidth]
40	)
41	distance_list.append(w[global_name.weight])	×
42	elif flag == 2:	1✔
43	for (u, v, w) in self.graph.edges(data=True):	×
44	w[global_name.weight] = w[global_name.latency]	×
45	distance_list.append(w[global_name.weight])	×
46	elif flag == 3:	1✔
47	for (u, v, w) in self.graph.edges(data=True):	×
48	w[global_name.weight] = random.randint(1, 2**24)	×
49	distance_list.append(w[global_name.weight])	×
50	elif flag == 4:	1✔
51	for (u, v, w) in self.graph.edges(data=True):	×
52	w[global_name.weight] = cost[u, v]	×
53	distance_list.append(w[global_name.weight])	×
54	else:
55	for (u, v, w) in self.graph.edges(data=True):	1✔
56	w[global_name.weight] = 1.0	1✔
57	distance_list.append(w[global_name.weight])	1✔
58	self.distance_list = distance_list	1✔
59	return distance_list	1✔
60
61	# if u and v connected
62	def nodes_connected(g, u, v):	1✔
63	return u in g.neighbors(v)	×
64
65	def get_connectivity(self):	1✔
66	con = approx.node_connectivity(self.graph)	×
67	return con	×
68
69	def biconnectivity(self):	1✔
70	pass	×
71
72
73	# use dijsktra to get the primary shortest path
74	def dijnew(graph, start_node, end_node):	1✔
75	graph_new = graph_simplify(graph)	×
76	shortest_distance = {}	×
77	predecessor = {}	×
78	unseenNodes = graph_new	×
79	infinity = 9999999	×
80	path = []	×
81	for node in unseenNodes:	×
82	shortest_distance[node] = infinity	×
83	shortest_distance[start_node] = 0	×
84
85	while unseenNodes: # loop all the nodes in the list	×
86	minNode = None	×
87	for node in unseenNodes:	×
88	if minNode is None:	×
89	minNode = node	×
90	elif shortest_distance[node] < shortest_distance[minNode]:	×
91	minNode = node # find the current node	×
92
93	for childNode, weight in graph[minNode].items():	×
94	if weight + shortest_distance[minNode] < shortest_distance[childNode]:	×
95	shortest_distance[childNode] = weight + shortest_distance[minNode]	×
96	predecessor[childNode] = minNode	×
97	unseenNodes.pop(minNode)	×
98
99	currentNode = end_node # run path backwards to get the real path	×
100	while currentNode != start_node:	×
101	try:	×
102	path.insert(0, currentNode)	×
103	currentNode = predecessor[currentNode]	×
104	except KeyError:	×
105	print("Path not reachable")	×
106	break	×
107	path.insert(0, start_node)	×
108	if (	×
109	shortest_distance[end_node] != infinity
110	): # check if the end_node has been reached
111	print("Shortest distance is " + str(shortest_distance[end_node]))	×
112	print("And the path is " + str(path))	×
113	return path	×
114
115
116	# make the non-simple graph to be the simple graph
117	def graph_simplify(graph):	1✔
118	for node in graph:	×
119	for endpoint in graph[node]:	×
120	try:	×
121	if len(graph[node][endpoint]) > 1:	×
122	shortest = min(graph[node][endpoint])	×
123	graph[node][endpoint] = shortest	×
124	except TypeError:	×
125	pass	×
126	return graph	×
127
128
129	# remove the primary shortest path and redo the dijsktra to get the backup path
130	def backup_path(graph, start_node, end_node):	1✔
131	backupstart_node = start_node	×
132	backupend_node = end_node	×
133	graphprimary = copy.deepcopy(graph)	×
134	graph_original = copy.deepcopy(graph)	×
135	graph_new = graph_simplify(graph)	×
136	print("The primary path: ")	×
137	path = dijnew(graphprimary, start_node, end_node)	×
138	path_new = path.copy()	×
139	path_new.pop()	×
140
141	for (	×
142	ele
143	) in path_new: # update the graph, delete the path that was used in primary path
144	index = path.index(ele)	×
145	try:	×
146	graph_original[ele][path[index + 1]].remove(graph_new[ele][path[index + 1]])	×
147	except AttributeError:	×
148	del graph_original[ele][path[index + 1]]	×
149
150	for start_node in graph_original: # reformat the updated graph list	×
151	for end_node in graph_original[start_node]:	×
152	try:	×
153	if len(graph_original[start_node][end_node]) == 1:	×
154	graph_original[start_node][end_node] = graph_original[start_node][	×
155	end_node
156	][0]
157	except TypeError:	×
158	continue	×
159
160	print("The back up path: ")	×
161	dijnew(graph_original, backupstart_node, backupend_node)	×
162
163
164	def create_unvisited_list(link_list):	1✔
165	unvisited_list = []	×
166	for keys in link_list:	×
167	unvisited_list.append(keys)	×
168	return unvisited_list	×
169
170
171	def create_unvisited_node(my_list):	1✔
172	unvisited_node = {}	×
173	for keys in my_list:	×
174	unvisited_node[keys] = 0	×
175	return unvisited_node	×
176
177
178	def get_graph_info(link_list):	1✔
179	key_list = []	×
180	for keys in link_list:	×
181	key_list.append()	×
182	print(key_list)	×

atlanticwave-sdx / pce / 3680947894

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous