CODEWITHSUNDEEP
pythonpython-3.xnetworkxgraph-theory
DSS
DSS

Reputation: 35

How to show the diameter in the graph?

I have a complete graph G with 5 nodes and I have to find the diameter of the G (randomly selected node) and also draw this diameter in the red colour. How can I do that with Networkx and Python? These are my attempts. Also I need to say there were more of them but the only difference is instead of shortest path I tried to use other functions(subgraph, algorithms, etc.) Also, I need to explain that random node means that you choose a start for the diameter randomly

Attempt 1

import networkx as nx

G = nx.complete_graph(5)

dg = nx.shortest_path(G)

edge_colors = ['red' if e in dg.edges else 'black' for e in G.edges]

nx.draw(G, edge_color=edge_colors)

Attempt 2

def get_diameters(graph):
    diams = []
    for g in nx.connected_component_subgraphs(graph):
        diams.append(nx.diameter(g))
    diams = list(filter(lambda a: a != 0, diams))
    return np.array(diams) Graph.number_of_nodes()

Upvotes: 1

Views: 2412

Answers (1)

CDJB
CDJB

Reputation: 14506

As I understand your question, you're not looking for the diameter of the graph itself, but for the longest shortest path in a graph given a random starting node. This can be achieved using nx.shortest_path with the source keyword argument, giving it a random starting node. We can look through the resultant dictionary, find the longest shortest path, and plot the edges which form this path in red.

Code

import networkx as nx
import random

# Create graph
G = nx.fast_gnp_random_graph(10, 0.3)

# Pick a random node
source = random.choice(list(G.nodes))

# Find the longest shortest path from the node
shortest_paths = nx.shortest_path(G, source=source)
target = max(shortest_paths, key=lambda i: len(shortest_paths[i]))
l_s_path = shortest_paths[target]
l_s_path_edges = list(zip(l_s_path, l_s_path[1:]))

# Draw the graph, then draw over the required edges in red.
pos = nx.spring_layout(G)
nx.draw(G, pos=pos, with_labels=True)
nx.draw_networkx_edges(G, edge_color='r', edgelist=l_s_path_edges, pos=pos)

Output

Note that in this example, the diameter of the graph is 4; the longest shortest path is from node 6 to node 4. The randomly selected source node was 7 - the longest shortest path from node 7 is of length 3.

enter image description here

Upvotes: 2

Related Questions