+++ /dev/null
-*
-* $Id$
-*
-* $Log$
-* 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
git://git.uio.no / u / mrichter / AliRoot.git / blobdiff