an ad-hoc edge property derived from weight [closed]

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 3 years ago.

Improve this question

I am using igraph (via python) for graph clustering.

I have a tree (a minimal spanning tree of a开发者_如何学编程 geometric graph) with weighted-edges, and want to calculate weight times the smaller number of vertices of the two components if the edge is deleted:

def sep(graph, e):
    h = copy(graph)
    w = h.es[e]['weight']
    h.delete_edges(e)
    return w * min(h.components().sizes())

# 'graph' is the tree I am dealing with
ss = [sep(graph,x) for x in range(len(graph.es))]

My questiones are:

1. Is this a known (and named) property in graph theory? If so, what is it?

2. My piece of code is very inefficient if I calculate this for all the edges, as shown above. If the graph becomes 50000 edges and vertices, memory consumption becomes huge. Do you have some suggestions for optimizing?

---

Elaborating a bit more on yurib's answer, I would do something like this (also posted on the igraph mailing list):

I will use two attributes, one for the vertices and one for the edges. The edge attribute is simple, it will be called cut_value and it is either None or contains the value you are looking for. Initially, all these values are Nones. We will call edges with cut_value=None unprocessed and edges where ``cut_value is not None``` processed.

The vertex attribute will be called cut_size, and it will be valid only for vertices for which there exists exactly one unprocessed incident edge. Since you have a tree, you will always have at least one such vertex unless all the edges are processed (where you can terminate the algorithm). Initially, cut_size will be 1 for all the vertices (but remember, they are valid only for vertices with exactly one unprocessed incident edge).

We will also have a list deg that contains the number of unprocessed edges incident on a given node. Initially all the edges are unprocessed, hence this list contains the degrees of the vertices.

So far we have this:

n, m = graph.vcount(), graph.ecount()
cut_values = [None] * m
cut_sizes = [1] * n
deg = graph.degree()

We will always process vertices with exactly one incident unprocessed edge. Initially, we put these in a queue:

from collections import deque
q = deque(v for v, d in enumerate(deg) if d == 1)

Then we process the vertices in the queue one by one as follows, until the queue becomes empty:

1. First, we remove a vertex v from the queue and find its only incident edge that is unprocessed. Let this edge be denoted by e

2. The cut_value of e is the weight of e multiplied by min(cut_size[v], n - cut_size[v]).

3. Let the other endpoint of e be denoted by u. Since e now became processed, the number of unprocessed edges incident on u decreased by one, so we have to decrease deg[u] by 1. If deg[u] became 1, we put u in the queue. We also increase its cut_size by one because v is now part of the part of the graph that will be separated when we later remove the last edge incident on u.

In Python, this should look like the following code (untested):

weights = graph.es["weight"]
while q:
    # Step 1
    v = q.popleft()
    neis = [e for e in graph.incident(v) if cut_value[e] is None]
    if len(neis) != 1:
        raise ValueError("this should not have happened")
    e = neis[0]

    # Step 2
    cut_values[e] = weights[e] * min(cut_sizes[v], n - cut_sizes[v])

    # Step 3
    endpoints = graph.es[e].tuple
    u = endpoints[1] if endpoints[0] == v else endpoints[0]
    deg[u] -= 1
    if deg[u] == 1:
        q.append(u)
    cut_sizes[u] += 1

---

I don't know about your 1st question but i might have an idea about the 2nd.
Since we're dealing with a minimal spanning tree, you can use the information you get about one edge to calculate the required property for for the edges adjacent to it (from now on i'll refer to this property as f(e) for an edge e).
Lets look at the the edges (A,B) and (B,C). When you calculate f(A,B), lets assume that after removing the edge from the graph you find out that the smaller component is the one on the A side, you know that:
f(B,C) = (f(A,B) / weight(A,B) + 1) * weight(B,C)
This is true because (B,C) is adjacent to (A,B) and after removing it you will get the "almost" same two components, the only difference is that B moved from the larger component to the smaller one. This way, you can do the full calculation (including removal of the dge and discovery of components and their size) for one edge and then only a short calculation for every other edge connected to it.
You will need to take special notice of the case where the smaller component (which grows as we go along the chain of edges) becomes the larger.

Update:
After some more thought i realized that if you can find a leaf node in the tree, then you don't need to search for components and their size at all. You start by calculating f(e) for the edge attached to this node. Since its a leaf:
f(e) = weight(e) * 1 (1 because it's a leaf node and after removing the edge you get a component with only the leaf and a component which is the rest of the graph.)
From here you continue as discussed previously...
Excluding the resources and time needed to find a leaf node, the rest of the computations will be done in O(m) (m being the number of edges) and using constant memory.