* * $Id: graph.F,v 1.1.1.1 1996/04/01 15:02:57 mclareni Exp $ * * $Log: graph.F,v $ * Revision 1.1.1.1 1996/04/01 15:02:57 mclareni * Mathlib gen * * #include "gen/pilot.h" SUBROUTINE GRAPH(H, IE, INOD, ISL, NPTR, NISL) C C DESCRIPTION OF PARAMETERS C C H(3,96) INP MUST CONTAIN THE INCIDENCE-MATRIX OF THE GRAPH IN C BIT FORMAT, I.E. THE MATRIX IS PACKED INTO A BITSTRIN C (USE *SETBIT* FOR THIS PURPOSE. C CALLING SEQUENCE IS 'CALL SETBIT(N, A, BIT)' C SETS THE N-TH BIT OF STRING A (COUNTED FROM LEFT TO C RIGHT) TO THE VALUE OF 'BIT' (0 OR 1)) C H(I,J) = 1 IF THERE'S AN EDGE FROM NODE I TO NODE J C H(I,J) = 0 ELSE C IE INP NUMBER OF EDGES IN THE GRAPH C THIS VALUE IS USED FOR PLAUSIBILITY-CONTROL ONLY C INOD INP NUMBER OF NODES IN THE GRAPH C ISL(96) OUT ONE SOLUTION EXTRACTED OUT OF THE GRAPH C IF H(I,J) REPRESENTS AN INCOMPATIBILITY GRAPH, THEN C ISL(1) ... ISL(NPTR) CONTAINS THE REMAINING COMPATIBL C NODES, IF THE NODES ISL(NPTR+1) ... ISL(NISL) ARE C REMOVED FROM THE GRAPH. C N O T E : ISL CONTAINS, HOWEVER, ONLY NODES WITHIN C THE CURRENT SUBGRAPH, IF NISL WAS 0 IN THE FIRST CALL C NPTR OUT CONFER *ISL* C NISL I/O CONTROLS THE FLOW OF THE ROUTINE AND INDICATES C THE TYPE OF RESULT ON OUTPUT. C INPUT.. 0 IF H, IE, INOD DESCRIBE A NEW GRAPH, FROM WHICH TH C FIRST SOLUTION OF ITS FIRST SUBGRAPH IS TO BE EXTR C -1 THE GRAPH WON'T BE SPLIT UP INTO SUBGRAPHS. THE C GRAPH IS THEREFORE TREATED AS A SINGLE SUBGRAPH C INCLUDING ALL ITS ISOLATED NODES. IF THERE ARE C MANY SUBGRAPHS, THEN THE NUMBER OF SOLUTIONS MAY C BECOME QUITE LARGE. C 1 IF THE NEXT SOLUTION OF THE CURRENT SUBGRAPH IS TO C EXTRACTED C 2 IF FURTHER SOLUTIONS OF THE CURRENT SUBGRAPH ARE T C BE DROPPED AND THE NEXT SOLUTION OF THE NEXT SUBGR C IS TO BE EVALUATED. C OUTPUT. -1 THERE'S NO FURTHER SOLUTION AVAILABLE IN THE GRAPH C ('END-OF-GRAPH' - INDICATION) C 0 LAST SOLUTION GIVEN WAS THE LAST ONE IN THE CURREN C SUBGRAPH ('END-OF-SUBGRAPH' - INDICATION) C .GT.0 CONFER *ISL* C IF NISL IS EQUAL TO 0 OR -1, THE CONTENTS OF ISL ARE C UNDEFINED.(THERE'S NO SOLUTION STORED) C C WRONG CALLING SEQUENCE OR UNBELIEVABLE PARAMETER VALUES FORCE C A RETURN WITH NISL = NPTR = -1. (ISL REMAINS UNDEFINED) C C DESCRIPTION OF IMPORTANT PROGRAM VARIABLES C C IV(3), IF(3) THESE TWO BITSTRINGS ARE USED BY THE ALGORITHM TO EXT C SUBGRAPHS OUT OF THE GRAPH GIVEN (BY H, IE, INOD) C IV(I)=1,IF(I)=0 NODE I HASN'T YET BEEN INVESTIGATED BY THE AL C IV(I)=0,IF(I)=1 THIS NODE SURELY BELONGS TO THE SUBGRAPH NOW C UNDER CONSTRUCTION AND THERE MIGHT BE EDGES LEADING C TO ADJACENT NODES C IV(I)=0,IF(I)=0 THIS NODE (I) IS DEACTIVATED, I.E. ALL INCIDEN C EDGES HAVE BEEN REMOVED AND ADDED TO THE SUBGRAPH. C IPTR GIVES THE CURRENT LENGTH OF THE EDGE INCLUSION TABLE(EIT) WHI C DESCRIBES THE SUBGRAPH. (THE EIT IS THEN PASSED TO *PGRAPH* C FOR EVALUATION). C IZ CONTROL VARIABLE FOR PGRAPH (SEE DESCRIPTION OF *PGRAPH*) C NINFO, INFO(96) SINCE PGRAPH REQUIRES THE NODES OF THE DELIVERED GR C TO BE SEQUENTIALLY NUMBERED, EACH SUBGRAPH GENERATED BY GRAPH C MUST BE RENUMBERED, BEFORE IT IS PASSED TO PGRAPH. WHEN PGRAP C RETURNS A SOLUTION, THE ORIGINAL NUMBERS OF THE NODES MUST BE C RECONSTRUCTED PRIOR TO THE RETURN-TO-MAINLINE. TO PROVIDE C THIS, FOR NODE I INFO(I) CONTAINS ITS SEQUENTIAL NUMBER WITHI C THE SUBGRAPH. THE SEQU. NUMBER IS UPDATED IN NINFO. C INTEGER EIT(652,2) +, IV(3) +, IF(3) +, INFO(96) +, ISL(96) +, H(3,96) LOGICAL BYPASS,SPLIT COMMON /BITSXB/ NBITPW, NBYTPW DATA BYPASS /.FALSE./ DATA NOLD /-1/ DATA IZ/0/ #if defined(CERNLIB_CDC) DATA IFILWD/-0/ NBITPW=60 #endif #if defined(CERNLIB_NORD) DATA IFILWD / 37777777777B/ NBITPW=32 #endif #if (!defined(CERNLIB_DOUBLE))&&(!defined(CERNLIB_CDC)) DATA IFILWD/-1/ NBITPW=64 #endif #if (defined(CERNLIB_DOUBLE))&&(!defined(CERNLIB_NORD)) DATA IFILWD/-1/ NBITPW=32 #endif NPTR = -1 IF(NISL - 1) 999,555,111 C C DO SOME ERROR CHECKING C DON'T PROCESS GRAPH ON IMPROPER CALLING SEQUENCE C 999 IF(IE.GT.652*(NBITPW/8)) GOTO 888 IF(IE.LT.0) GOTO 888 IF(INOD.GT.96) GOTO 888 IF(INOD.LE.1) GOTO 888 NOLD = 0 IF(BYPASS) GOTO 777 NBYTPW = NBITPW/8 BYPASS = .TRUE. 777 CONTINUE C C CHECK, WHETHER TO SPLIT UP INTO SUBGRAPHS OR NOT. C IF(NISL.NE.-1) GOTO 666 C C DON'T SPLIT C SPLIT = .FALSE. IPTR = 0 C C CONSTRUCT EIT C DO 40 I = 2,INOD II = I - 1 DO 40 K = 1,II CALL GETBIT(K, H(1,I), IBIT) IF(IBIT.EQ.0) GOTO 40 CALL SETBIT(K, H(1,I), 0) CALL SETBIT(I, H(1,K), 0) IPTR = IPTR + 1 CALL TUP(EIT(1,1), IPTR, I) CALL TUP(EIT(1,2), IPTR, K) 40 CONTINUE IF(IPTR.EQ.0) GOTO 888 IZ = 0 CALL UZERO(IV, 1, 3) NINFO = INOD GOTO 556 666 CONTINUE SPLIT = .TRUE. C C SET INITIAL VALUES C CALL UZERO(IF, 1, 3) CALL UFILL(IV,1,3,IFILWD) 111 IPTR = 0 IF(NOLD.NE.0) GOTO 888 C*UL 112 NINFO = 0 NINFO = 0 CALL UZERO(INFO, 1, INOD) DO 1 I = 1,INOD CALL GETBIT(I, IV, IBIT) IF(IBIT.EQ.1) GOTO 2 1 CONTINUE C THERE ARE NO FURTHER NODES LEFT IN THE GRAPH NPTR = 1 888 NISL = -1 RETURN C A NODE HAS BEEN FOUND. ALL ITS INCIDENT EDGES ARE DETERMINED, C REMOVED FROM THE GRAPH AND STORED INTO THE EIT 2 NODE = I DO 3 I = 1,INOD CALL GETBIT(NODE, H(1,I), IBIT) IF(IBIT.EQ.0) GOTO 3 CALL SETBIT(NODE, H(1,I), 0) CALL SETBIT(I, H(1,NODE), 0) C MARK THIS ADJACENT NODE FOUND TO PROVIDE FURTHER EXPANSION C OF THE (SUB)GRAPH CALL SETBIT(I, IV, 0) CALL SETBIT(I, IF, 1) C STORE THE EDGE (NODE,I) INTO THE EIT C REMARK.. THE FIRST 'CALL TUP(..)' MEANS EIT(IPTR,1) = NODE IPTR = IPTR + 1 CALL TUP(EIT(1,1), IPTR, NODE) CALL TUP(EIT(1,2), IPTR, I) 3 CONTINUE C SET UP ARRAY TO PROVIDE SEQUENTIAL NUMBERING OF THE NODES OF C EACH SUBGRAPH BEFORE ENTERING SUBROUTINE PGRAPH NINFO = NINFO + 1 INFO(NODE) = NINFO C MARK THE NODE AS INACTIVE. (ALL INCIDENT EDGES HAVE BEEN REMOVED) CALL SETBIT(NODE, IV, 0) CALL SETBIT(NODE, IF, 0) C IS THERE STILL A NODE IN THE GRAPH, FROM WHICH THE CURRENT C SUBGRAPH MIGHT BE EXPANDED DO 4 I = 1,INOD CALL GETBIT(I, IF, IBIT) IF(IBIT.EQ.1) GOTO 2 4 CONTINUE C NO, THE SUBGRAPH IS COMPLETE. CHECK, IF IT IS ONLY AN ISOLATED NODE IF(IPTR.GT.0) GOTO 6 NPTR = 1 NISL = 1 IZ = 0 ISL(1) = NODE RETURN C REARRANGE THE NUMBERS WITHIN THE SUBGRAPH FOUND TO BE SEQUENTIAL 6 CONTINUE DO 7 I = 1,IPTR DO 7 J = 1,2 JX = IGET(EIT(1,J), I) NEW = INFO(JX) CALL TUP(EIT(1,J), I, NEW) 7 CONTINUE IZ = 0 GOTO 556 555 IF(IZ.EQ.0) GOTO 111 556 CALL PGRAPH(EIT, IPTR, NINFO, ISL, NPTR, IZ) IF(IZ.EQ.0) GOTO 8 IF(.NOT. SPLIT) GOTO 8 C RE-REARRANGE THE NUMBERS IN THE EIT FROM SEQUENTIAL TO ORIGINAL DO 9 I = 1,IZ NEW = ISL(I) DO 11 J = 1,INOD IF(INFO(J).EQ.NEW) GOTO 12 11 CONTINUE 12 ISL(I) = J 9 CONTINUE 8 NISL = IZ RETURN END