Re: [igraph] an ad-hoc edge property similar to weight

[Tamas Nepusz]

> I have a tree with weighted-edges, and want to calculate weight times
> the smaller number of vertices of the two components if the edge is
> deleted:
Since you have a tree, you don't have to perform the deletion in order to
determine the number of nodes on each side of the cut. Just do the following:

1. Create an empty queue.

2. Add an edge attribute named "cut_value" to each edge. Initially, set
these attributes to None.

3. Add a node attribute named "cut_size" to each node. Initially, set these
attributes to 1.

4. Create a list L that contains the degrees of the nodes.

5. Add those nodes to the queue that have a single incident edge (thus
degree=1).

6. If the queue is empty, stop. Otherwise:

6a. Remove a node v from the head of the queue. The "cut_size" attribute of
this node tells us how large ONE side of the cut will be if we remove the
single edge incident on this node that has a "cut-value" attribute with
value None. You can then simply find the number of nodes on the SMALLER side
of the cut by taking the smaller of cut_size[v] and N-cut_size[v], where N
is the number of nodes. Multiply this number with the weight of the edge
incident on this nude that has a cut_value with value None, and store it in
the "cut_value" attribute of the edge.

6b. Find the other endpoint U of the edge you have just processed. Set its
"cut_size" to one larger than the "cut_size" of node V, and decrease the
value of node U in L. If the value became 1, add U to the queue.

5c. Return to step 5.


The key points here are as follows:

1. Each edge will be processed only once, so the whole algorithm should be
around O(m), where m is the number of edges.

2. Edges with cut_value = None are "unprocessed" edges. If cut_value is not
None, the edge has already been processed and we don't care about it any more.

3. The list L contains the number of "unprocessed" edges incident on each
vertex. If you have a tree, you will always have at least one node in L that
has only one unprocessed incident endge; if you don't, then you are finished.

4. The cut_size attribute of each vertex is always valid for vertices that
have only one unprocessed incident edge. For these edges, the value of
cut_size is always the size of one part of the cut of the graph if you
remove that single unprocessed incident edges.

I think this should work -- haven't tested or implemented it, though.

-- 
Tamas