| Set Operations on A and B [message #45700] |
Sat, 01 October 2005 20:30  |
mxd1007
Messages: 3
Registered: October 2005
|
Junior Member |
|
|
Hello
I'm doing a programming project in computational Graph Theory. I'm
trying to implement an algorithm to color the vertices of a graph, a
pentagon, and will be using a greedy coloring algorithm as detailed
below:
************************************************************ ******************
GreedyColor( G = (Vertices, Edges))
global color
k = 0
for i = 0 to n -1
h = 0
while h < k and A[i] INTERSECTION ColorClass[h] not eqaul to NULL
do h = h+1
if h = k then
k = k+1
ColorClass[h] = NULL
ColorClass[h] = ColorClass[h] UNION {i}
color[i] = h
return(k)
************************************************************ ******************
Graph coloring is where you color the vertices of a graph with a
particular color, using a different color for vertices that ARE
connected to each other. So for a regular pentagon, you can apply at
least 3 different colors( for set of vertices (0,1,2,3,4), 0 = red, 1 =
blue, 2 = red, 3 = blue, 4 = green
the actual k-coloring is stored in the array color
ColorClass is defined as:
ColorClass[h]={i is an element of Vertices : color[i] = h}
UNION and INTERSECTION is of course the typical union and interesection
relating to sets
I have no problem implementing the pseudocode as is except for the
intersection and union computations. I did find a nice website on this
by Fanning Consulting:
http://www.dfanning.com/tips/set_operations.html
so I used the setuUnion and setIntersection funtions within my program.
when ready to compile, I got this error:
IDL> graphcolor
% HISTOGRAM: Expression must be an array in this context: A.
% Execution halted at: SETINTERSECTION 36
/Applications/rsi/graphcolor.pro
% GRAPHCOLOR 76
/Applications/rsi/graphcolor.pro
% $MAIN$
My question and confusion is about this A array since I'm passing an
array(actually a sub array) into the function setIntersection. Or are
these set functions useless for my application to graph coloring? any
suggestions would be appreciated. I do think these set functions are
very useful, just that I don't understand why it can't be applied to my
arrays I'm passing in.
~Michael
My code as follows( I indicated with ** where the error happened in
SetIntersection function):
FUNCTION SetUnion, a,b
;A union NULL = a
IF a[0] LT 0 THEN RETURN, b
;B union NULL = b
IF b[0] LT 0 THEN RETURN, a
;Return combined set
RETURN, Where(Histogram([a,b], OMin = omin)) + omin
END
FUNCTION SetIntersection, a,b
;only need intersection of ranges
minab = Min(a, Max=maxa) > Min(b, Max=maxb)
maxab=maxa < maxb
;If either set is empty, or their ranges don't intersect:
;result = NULL
IF maxab LT minab OR maxab LT 0 THEN RETURN, -1
** r = WHERE((Histogram(a, Min=minab, Max=maxab) NE 0) AND $
(Histogram(b, Min=minab, Max=maxab) NE 0), count)
IF count EQ 0 THEN RETURN, -1 ELSE RETURN, r + minab
END
PRO GRAPHCOLOR
;construct an array to hold the set of vertices adjacent
;to any particular vertex. for example for vertex 0,
; vertices 1 and 4 would be a set of vertices adjacent
;to vertex 0, hence a[0] = [1,4]
setA = [[1,4], [0,2], [1,3], [2,4], [0,3]]
;create a color array to hold colors of vertices
;in a undirected regular pentagon graph
color = BYTARR(5,1)
colorClass = BYTARR(5, 1)
k = 0
FOR i = 0, 4 DO BEGIN
h = 0
WHILE ( h < k AND setIntersection(setA[i], colorClass[h])$
NE -1) DO BEGIN
h = h + 1
IF ( h EQ k) THEN BEGIN
k = k+1
colorClass[h] = NULL
ENDIF
colorClass[h] = setUnion(colorClass[h], i)
color[i] = h
ENDWHILE
ENDFOR
print, k
END
|
|
|
|
comp.lang.idl-pvwave archive
Members
Search
Help
Login
Home
