Modelling with Graphs
A set of algorithms on graphs
Mar 08, 2019
3 minutes
Built with
A set of algorithms on graphs
Mar 08, 2019
3 minutes
In this coursework I implemented a range of graph algorithms using Python and NetworkX.
This can be found in the file Part A/greedy_col_basic.py
This is designed to:
For this I implemented two functions
find_smallest_color - Given the graph and a given vertex, return the smallest colour that can be assigned
def find_smallest_color(G,i):
n = len(G.nodes())
keys = G.adj[i]
list = []
for key in keys:
list.append(G.nodes[key]['color'])
color=1
while color in list:
color += 1
return color
greedy - Actually perform the greedy algorithm
def greedy(G):
global kmax
for i in G.nodes():
G.nodes[i]['color'] = find_smallest_color(G,i)
kmax = max(G.nodes[i]['color'] for i in G.nodes)
for i in G.nodes():
print('vertex', i, ': color', G.node[i]['color'])
print()
print('The number of colors that Greedy computed is:', kmax)
This can be found in the file Part A/greedy_col_variation.py
Instead of visiting the nodes sequentially, this should visit the vertices such that the next visited node is adjacent to at least one visited node. Amongst the list of adjacent vertices, the smallest should be chosen. Then the rest of the algorithm will be carried out as before.
For this the function find_smallest_color doesn’t require any editing, but the function greedy is changed to look like this
def greedy(G):
n = len(G.nodes())
global kmax
global visited_counter
G.nodes[1]['color']=1
G.nodes[1]['visited']='yes'
for i in range(1,len(G)):
next_vertex=find_next_vertex(G)
G.nodes[next_vertex]['color']=find_smallest_color(G,next_vertex)
G.nodes[next_vertex]['visited'] = 'yes'
visited = nx.get_node_attributes(G, 'color')
kmax=(max([v for k, v in visited.items()]))
print()
for i in G.nodes():
print('vertex', i, ': color', G.node[i]['color'])
print()
print('The number of colors that Greedy computed is:', kmax)
print()
This also has the newly implemented function find_next_vertex which provides the index of the vertex to choose next
def find_next_vertex(G):
visited = nx.get_node_attributes(G, 'visited')
visited=[k for k, v in visited.items() if v=="yes"]
adjacent=set()
for item in visited:
adjacent=adjacent|(set(G.neighbors(item)))
visited=set()
for item in adjacent:
if G.nodes[item]['visited']=='yes':
visited.add(item)
adjacent-=visited
return min(adjacent)
This can be found in the file Part B/breadth_first.py
This performs a breadth first search from a given node a to a given node b
This is implemented in just one function
def bfs(G,a,b):
G.add_nodes_from(G.nodes(), label = -1) # initialization of all labels
G.node[a]['label'] = 0
i=0
while G.node[b]['label']==-1:
vertex_list=[node for node in G.nodes() if G.node[node]['label']==i]
for u in vertex_list:
adjacent=list(G.adj[u])
for v in adjacent:
G.node[v]['label']=i+1
i+=1
return G.node[b]['label']
This can be found in the file Part B/depth_first_pair_nodes.py
This performs a depth first search starting from a given node a to a given node b
At every step, among the neighbours of the currently visited vertex, the algorithm chooses the smallest one to continue the exploration from it.
In addition, it adds a label to each of the visited vertices with the path length
This is implemented with just one function
def dfs(G,a,b,u):
if a==u:
G.node[u]['label']=0
else:
G.node[u]['label']=G.node[a]['label']+1
G.node[u]['visited'] = 'yes'
print(u)
if u==b:
return
sort_list = list(G.neighbors(u))
sort_list.sort()
for v in sort_list:
if G.node[v]['visited'] == 'no':
dfs(G,u,b, v)
The code for this can be found in the file Part B/Diameter.py
The diameter is the greatest distance between any pair of vertices in the input graph. This is implemented with the breadth first algorithm seen before, along with an additional function
def max_distance(G):
max=0
nodes=list(G.nodes())
pairs=[[i,j] for i in nodes for j in nodes]
for i in pairs:
distance=bfs(G,i[0],i[1])
if distance>max:
max=distance
return max