Calculate graph center

graph-tool
1

I am new to using graph-tools and am currently trying to an adapt my running code in networkx to graph-tools in the hopes of improving runtime.

Currently I am stuck at implementing networkx’s center function in graph-tools.

The center would be the set of nodes with eccentricity equal to radius. Unfortunately I have not found a function to calculate either the eccentricity of all vertices nor the graph center.

Any help would be appreciated.
Cheers
Sophia

2

I have looked at the problem some more and have written some code which for the moment gives me the same results I would get with the networkx function.

def get_center_nodes(g):
    
    nodes = g.get_vertices()
    if len(nodes) > 2:
        
        distances = topology.shortest_distance(g)
        eccentricities = [x.a.max() for x in distances]
        
        centers = nodes[eccentricities.index(min(eccentricities))]

        return(centers)
        
    else:
        return(nodes[0])

In the long run I want to be able to run this on very large graphs so I am not sure if my current solution is the most efficient.

So a follow-up question:

  1. how can I improve the efficiency of my code?

For context, this is the code I am wanting to call the centers function in:

c = gt.topology.label_components(gtG)[0]
components = np.unique(c.a)

centers = []
for i in components:
    u = gt.GraphView(gtG, vfilt=c.a == i)
    #graph_draw(u, vertex_text=u.vertex_index, ink_scale = 0.5)
    
    center = get_center_nodes(u)
    centers.append(center)
3

It looks fine to me.

1 Like