igraph-help
[Top][All Lists]

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

 From: Tamas Nepusz Subject: Re: [igraph] an ad-hoc edge property similar to weight Date: Mon, 30 May 2011 15:00:42 +0200 User-agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.17) Gecko/20110424 Lightning/1.0b2 Thunderbird/3.1.10

```> 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.

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

```