[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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.
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