[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[igraph] igraph_vector_union_size
From: 
John Lapeyre 
Subject: 
[igraph] igraph_vector_union_size 
Date: 
Fri, 19 Feb 2010 14:21:14 +0100 
Useragent: 
KMail/1.12.4 (Linux/2.6.31.9; KDE/4.3.4; x86_64; ; ) 
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 igraph0.5.3/src/vector.h igraph0.5.3.new/src/vector.h
 igraph0.5.3/src/vector.h 20090303 14:06:57.000000000 +0100
+++ igraph0.5.3.new/src/vector.h 20100219 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 igraph0.5.3/src/vector.pmt igraph0.5.3.new/src/vector.pmt
 igraph0.5.3/src/vector.pmt 20090704 17:52:00.000000000 +0200
+++ igraph0.5.3.new/src/vector.pmt 20100219 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+v2count
+ *
+ * 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;
+}
[Prev in Thread] 
Current Thread 
[Next in Thread] 
 [igraph] igraph_vector_union_size,
John Lapeyre <=