[igraph] igraph_vector_union_size

[John Lapeyre]

Hi,

This routine finds the number of elements in the
union of two sets (represented by vectors).

I don't have a routine to return the union itself.  The
present routine is useful as a separate routine because it
does not require any extra storage.

I didn't write any systematic test code.

The routine is given as a patch against 0.5.3

Regards,
John

-------------
diff -rupN igraph-0.5.3/src/vector.h igraph-0.5.3.new/src/vector.h
--- igraph-0.5.3/src/vector.h   2009-03-03 14:06:57.000000000 +0100
+++ igraph-0.5.3.new/src/vector.h       2010-02-19 12:37:15.000000000 +0100
@@ -224,4 +224,5 @@ int FUNCTION(igraph_vector,get_interval)
 int FUNCTION(igraph_vector,intersect_sorted)(const TYPE(igraph_vector) *v1,
   const TYPE(igraph_vector) *v2, TYPE(igraph_vector) *result,
   igraph_bool_t keep_multiplicity);
-
+long int FUNCTION(igraph_vector,union_size)(const TYPE(igraph_vector) *v1, 
+                                            TYPE(igraph_vector) *v2);
diff -rupN igraph-0.5.3/src/vector.pmt igraph-0.5.3.new/src/vector.pmt
--- igraph-0.5.3/src/vector.pmt 2009-07-04 17:52:00.000000000 +0200
+++ igraph-0.5.3.new/src/vector.pmt     2010-02-19 12:37:07.000000000 +0100
@@ -1978,3 +1978,38 @@ int FUNCTION(igraph_vector,intersect_sor
   return 0;
 }
 
+/**
+ * \function vector_union_size
+ * \brief Calculates the number of elements in the union of two sets 
represented by vectors
+ *
+ * It is assumed that all elements of v1 are unique
+ * and likewise with v2. The vector v2 will be sorted by this routine.
+ * \param v1 the first vector
+ * \param v2 the second vector
+ * \return the number of elements in the union of v1 and v2
+ * algorithm: Note that the size (cardinality) of the union is the sum of the 
sizes
+ * v1 and v2 minus the number of elements that appear in both v1 and v2.
+ * 1) sort v2.  2) loop over elements of v1, doing a binary search for v1
+ * in v2, counting success in count. 3) return |v1|+|v2|-count
+ * 
+ * Time complexity -- O(n*log_2(n)+n)
+ * For very large n, most of the time is take by qsort ( O(n*ln(n)) );
+ * this is the 'typical' qsort time-- worst case is O(n^2). But this is
+ * implementation dependent since the C standard does not require quicksort
+ * to be used in qsort.
+ * Space complexity -- O(1)
+ */
+
+long int FUNCTION(igraph_vector,union_size)(const TYPE(igraph_vector) *v1, 
+                                            TYPE(igraph_vector) *v2) {
+  int count;
+  int i;
+  int n1;
+  n1 = FUNCTION(igraph_vector,size)(v1);
+  FUNCTION(igraph_vector,sort)(v2);
+  count = n1 + FUNCTION(igraph_vector,size)(v2);
+  for(i=0;i<n1;i++) {
+    if ( FUNCTION(igraph_vector,binsearch2)(v2,VECTOR(*v1)[i]) ) count--;
+  }
+  return count;
+}