Home

GHS Graph Handling System User Manual GHScore

Contents

1. 159 160 APPENDIX C GHS INTERNAL DATA STRUCTURES PHDR newphdr GRAPH graph char direction path c char name PTHA insertline2path PHDR phdr path c EDGE line VERTEX first char position BOOLEAN insertpath2path PHDR phdri path c PHDR phdr2 void removepath PHDR phdr path c void releasepathlist PHDR phdr path c PHDR readpath GRAPH graph pathutil c char filename PHDR readpathlist GRAPH graph pathutil c char filename void savepathlist PHDR list char filename pathutil c void printpathlist PHDR phdr pathutil c char stroption char filename Menger Functions MGDESCR mengerstr GRAPH graph VTSET vtsource menger c VTSET vtsink char mode char direction char name int bound char sep void mgprstd MGDESCR mgdescr int stroption mengerutil c char filename void releasesepdescrlist SEPDESCR sepdescr Distance Functions Red Black Trees BOOLEAN ntreeinsert RB tree RB elem rbtree c int key BOOLEAN rbtreeinsert RB tree RB elem rbtree c int key BOOLEAN rbtreedelete RB tree RB elem rbtree c int key BOOLEAN ntreedelete RB tree RB elem rbtree c int key RB rbtreefind RB tree RB elem rbtree c int key RB rbtree
2. include lt stdio h gt include lt GHSstructure h gt int main GRAPH graph GSET gset gsetl NULL graph readgraph if graph NULL printf Incorrect graph input n exit 0 gset gsetunion RB graph gt grvtlist SND RB gseti SND savegset gset return 0 Table 3 4 Command Procedure set02 cmd and Program set02a c 42 CHAPTER 3 SETS Program main Reads a graph and then the elements of a general set from standard input constructs the corresponding vertex set and generates the a graph from the vertex The names and the number of elements of both graphs printed include lt stdio h gt include lt GHSstructure h gt int main GRAPH graph graphl VTSET vtset GSET gset graph readgraph if graph NULL printf Incorrect graph input n exit 0 h printgrlist graph short gset readgset vtset gset2vtset gset graph graphi generatefromvt graph NEWGRAPH vtset gt vtsetlist printgrlist graphi short return 0 Graphi Type Vertices 22 Edges NEWGRAPH Type Vertices
3. 3 bk ak sk sk ok sk ak sk ok sk oR ak ak ak ak ak kkk kk kk kk kkk OR K Implicit functions in util c DCCC COO B General Service Functions VERTEX otherend EDGE edge VERTEX vertex1 util c B 1 void resetaux RB rb util c B 2 void collam size_t size char message util c B 3 void eerf void freepointer size_t size util c B 4 char mnewname char string char message util c B 5 void releasename char util c B 6 BOOLEAN boolstrcmp char stri char str2 util c B 7 int putsizeposition RELEM rel int pos util c B 8 int possize void initheader RB record util c B 9 161 162 APPENDIX C GHS INTERNAL DATA STRUCTURES int gcd int m int n util c B 10 void mkqufromrb RB rb QUSTA qu util c B 11 void mkstckfromrb RB rb QUSTA stck util c B 12 void memstatistics void util c B 13 void findcomponent GRAPH graph util c 14 char gstdname char colorname int clr util c B 15 C Functions for Allocating Records RELEM mnewrelem char message util c C 1 1 1 QUSTA mnewqusta char message util c C 1 3 1 Qs mnewqs char message util c C 1 3 2 GRAPH mnewgraph char message
4. 87 9 3 FUNCTIONS eos date 4 he ee 88 9 321 Dewphdr mar EN Der Be ns 88 9 3 2 insertline2path 88 9 3 3 removelinefrompath 89 93 4 Insertpath2p th u oq eu a 89 9 3 5 Teadpathr a re Rer eres ee 90 9 3 6 Teadp thlist u a z 024 2 4 arme 4 ROX o Y Poe g 90 9 3 savepathlisU 22 4 8 xe Geor RONDE rox we a 91 9 3 8 91 9 20 releasepathlist ren ukuta MONA ae DE 91 9 3 10 simplifypathii ko Rd Iw b p RUE RUE RECTE 91 9 3 11 generategraphfrompath 91 9A bxemples 24e von Daten er mes sehn 91 10 Menger Structures not yet released 95 10 1 Problem Description au se eek erp knew RE Rer aa spa dne umi US 95 10 2 Formats and Data Structures 96 10 3 FUNCIONS gus qk are ae a ne Arne 96 10 3 1 imengerstr zs see N Er d yb rw ee 96 10 4 Examples gt ars s a Das nf oe we ER 5 98 11 Higher Decompositions not yet released 11 1 Problem Description 11 2 Formats and Data Structures 11 3 Functions 11 3 1 highcomponents 11 3 2 prbiblocktrees 11 4 Examples 12 The Triblock Decomposition not yet released 12 1 Problem Description 12 2 Formats and Data S
5. type of higher component 1 not yet assigned 1 subgraph internally disjoint a paths 2 subgraph line disjoint a paths 3 vertex set internally disjoint a paths 4 vertex set line disjoint a paths b subgraph internally disjoint f paths 6 subgraph line disjoint f paths vertex set internally disjoint f paths 8 vertex set line disjoint f paths degree of connectedness k number of decomposition element in element of next lower degree of connectedness next lower decomposition element of type HCOMP or type BLN modes 1 3 type SUB modes 2 4 type SCOMP modes 5 6 7 8 pointer main higher decomposition record decomposition number of vertices number of edges number of arcs number of vertices in coelement number of edges in coelement number of arcs in coelement number of decomposition elements with next higher degree of connectedness list of decomposition elements with next higher degree of connectedness HVTSTD Vertex in a higher decomposition of a general graph HVTSTD hvtstdleft 187 188 APPENDIX C GHS INTERNAL DATA STRUCTURES HVTSTD hvtstdright HVTSTD hvtstdpar COLOR hvtstdcolor void hvtstdauxiliary for future extension VERTEX hvtstdp
6. AE LEX iux 2 9 2 saveeraphlist Prada a Sa urged oS 2 3 3 rel as sraphlist ura sa a ew a Tuta 2 9 4 Drinterlist Z kun yuqa atun ae ced ao een EE o ae bote de 2 3 9 Plintdis 4x pae Dayan ae real Bees SET 2 3 6 SPY BIS s Rs b Gee Qu SE SN SC an s et og dni 2 3 7 addvertex not yet released mer era 2 3 8 addline not yet implemented 2 3 9 deletevertex not yet 2 3 10 deleteline not yet implemented 2 4 Examples 254 30m us aR See a uie qus d obe cri Sede t dert 3 Sets 3 1 Problem Description 3 2 Formats and Data Structures 3 3 Functions for Vertex Sets Jub TEeadviset 222 50 ee A e Maec qha do ot y x 3 92 ABSCLZVISET usce dete ern et En ee 3 3 3 SAVEViSeh UA punc eee Z le ea up Bell ety mS eut 3 94 Teleasevtsetlist x cuc re ene AR elk Rem Sor PT s oe d 3 3 0 0 6 4 rne RR RE vob We 3 0 0 Addviset2vtset aa aa ua a A wo EIE RC T E RR Xe G 3 4 Functions for Edge Sets JzLI readedset pre uu veh ede debe et e e dA RS ep es 394 2 saveedset u 2 08 8 00 o U sdn e dep ew decem Bod at b ed etui 34L3 lt
7. i ee Mun Bok EXP Bux RN Eme ED Dc s 2 ee 3 4 4 releaseedsetlist 11 11 11 13 13 13 14 14 15 15 16 16 16 16 16 CONTENTS 34 5 aqa ese i 4 222 34 ash ar SES AS A OE A Gh BAS 35 3416 addedsel2edset enter oak war ir er D niy Tt itt 35 3 5 Functions for General Sets 222 Co Comm nn 35 9 9 Teadgset va 4 8A RR GG Bar aa 35 9 9 2 SAVOBSEL Sard oe denn wa e n ey ee S a 36 3 5 3 releasegsetlist 22224245285 depen dpa ex ROB RR veh k Uq deg 36 2 574 lt add2gseti orca a d a ROS bed Oe ops Eum E Gms 36 9 0 9 BSE UTON o dee Ete re eR loa T ed 37 3 0 6 o seed nice er ern rag merus 37 psebdifi u wag 3 B nie x he eus Ba alas 38 3 0 Examples He LS EN RAS a ode DER 38 Graph Generating Functions 43 4 1 Problem Deseription 22 ue BE aa Bo NRBIS E aue 43 4 11 General Remarks 43 4 1 2 Names and Adresses 43 4 2 Formats and Data Structures nn 44 4 3 EUHGLIONSE Zur A tir ote th te MER ui e u n AE ee 44 4 81 generatefromvt moe UR ERROR OR eee C Am UE 44 4 3 2 seneratefromed PO GO See a e 45 8785
8. GSTDD Weak and strong components C 4 1 WCOMP Weakly connected component C 4 2 SCOMP Strongly connected component C 4 3 GVTSTD Vertex extension for weak and C 4 4 strong components GEDSTD Edge arc extension for weak C 4 5 and strong components k sk sk sk ok ok ok sk k ak ok ok KK 3K aK OR aK aK 3K 3K 3K K aK aK 3K 3K 3K aK aK aK 2K 3K 3K K aK aK 2K 3K 3K 3K aK aK OR struct gstdd GSTDD Weak and strong components GSTDD gstdleft GSTDD gstdright GSTDD gstdpar COLOR gstdcolor void gstdauxiliary for future extensions GRAPH gstdgraph pointer to graph GVTSTD gvtstdlist red black tree of GVTSTD records int gisvtno number of isolated vertices RVERTEX gisvtlist list of isolated vertices int wcompno number of weak components int wacno number of a acyclic weak components without strong components WCOMP waclist list of a acyclic weak components without strong components int wacsno number of a acyclic weak components with strong components WCOMP wacslist list of a acyclic weak components with strong components int wccno number of a cyclic weak components without strong components WCOMP wcclist list of a cyclic weak components without strong components int wccsno number of a cyclic weak components with all strong components f acyclic WCOMP w
9. RR e em Eu 158 G 3 2 Implieit Functions 4 mis s omo Fete dos zumo le dy b q pus Y 161 C 3 3 Global Variables 163 C 4 Data Structures for Utilities 22 2 2 Coon nn 164 C 4 1 Data Structures for General Sevices 164 C 4 2 Data Structures for Red Black Trees 165 0 4 3 Data Structures for Stacks and 165 C 5 Basic Graph Data Structures 166 C 6 Data Structures for Sets 171 Data Structures for Weak and Strong Components 172 C 8 Data Structures for the Biblock Decomposition 176 C 9 Data Structures for Additional DFS 182 C 10 Data Structures for General Partitions 183 C 11 Data Structures for Paths nn 183 C 12 Data Structures for Menger Structures 184 C 13 Data Structures for the Higher A Decomposition 185 14 Sort Keys for Red Black 189 List of Figures 197 List of Tables 199 Bibliography 201 Index 203 viii CONTENTS Chapter 1 Introduction 1 1 General Remarks and Overview The Graph Handling System GHS consists of a core component GHScore and complementary programs This manual is concerned with GHScore some complementary programs are men
10. Eg Ras 69 6 4 Examples 2 4 acis 70 CONTENTS 7 Distances not yet released 79 GA Problem Description x Ze aUe RE Weg e asta 79 7 2 Formats and Data Structures 79 fed Eunetions air Cod a ea Fe 80 TA Examples sen wlan a ee ee 80 8 Edge and Vertex Partitions not yet released 83 8 1 Problem Description 83 8 2 Formats and Data Structures 84 8 3 BUNGtIONS ose na er AA A eee ee ON te ea a 84 8 3 1 edparigen a a ze t Se a E E P de eds 84 8 98 25 CDDAPULDIODA cn ceu See obi y a A ee 84 9 39 91 palitZpart x sa OX pem ex Bare EE aee uM 84 5 9 4 paint26part a ger na prego hem gode 85 8 9 5 add2edpart IRURE ee P Cc 85 8 2 6 add2clasSs i 9 oes aa Ww ob DR WIE ROMS Rer E RSS 85 8 5 7 releaseedpartlist 85 8 3 8 88 85 8 39 95 prpabtsUb x 4 oec Qupa AE ansa s UE ete ps 85 8 39 10 prpartvted z 2 eisdem Me delete Ev 85 8 4 Exemples sx RE BUR REG ook de YR m sua GR dos 85 9 Paths not yet released 87 9 1 Problem Description o nn dong RUE er o e e e ee an 87 9 2 Formats and Data Structures
11. AEDSTD Edge in a biblock decomposition C 8 DATA STRUCTURES FOR THE BIBLOCK DECOMPOSITION EDCLASS EDSTAT INCSQR POPTION STROPTION struct substr 1 SUB SUB SUB COLOR void WCOMP int int RVERTEX int REDGE int REDGE int BLB int RVERTEX int RVERTEX int RVERTEX int RVERTEX struct blbstr BLB BLB BLB COLOR void SUB int Edge classification Edge processing status List of incidences in biblocks Also used for general line partitions Print options for vertex list prstdvt Print options for the weak and strong decompostion and the biblock decomposition 3K K aK ak 2K 3K 3K K aK aK 2K 3K 3K 3K aK aK 2K 3K 3K aK aK K 3K 3K 3K K K K 3K 3K SUB Subcomponent xsubleft subright subpar subcolor subauxiliary subwcomp subnumber subvtno subvtlist subedno subedlist subdedno subdedlist subblbno subblblist subattno subattlist subborno subborlist subhinno subhinlist subcheno subchelist BLB Biblock blbleft blbright blbpar blbcolor blbauxiliary blbsub blbnumber for future extensions pointer to WCOMP identifying number SUB number of vertices list
12. 2 arc of a strong component gedstdelcmp points to strong component 3 arc of an external dag gedstdelcmp points to weak component void hedstdelcmp pointer to elementary component edge arc belongs to BOOLEAN hedstdmarked general mark indicator C 14 Sort Keys for Red Black Trees k 3k ok sk ak sk ak sk ak ak ak ak ak ak ak ak ak ak ak oko FOR 24 kk kk kk kkk kk kk kkk SORTKEY Sorting for red black trees Sokokokokokokokokokokokokokokookokokokookookoojokookookookokolokeojolojokelokookolojolelokeojelelokeotolojeleloleloetelejeleleeloejeleje enum sortkey SORTKEY Type of sorting key 1 ak ak Extension 2008 8 17 The function rbtreedelete is implicitly added to all keys which allow function rbtcomp sk ok ak ak ak ak ok ok ak ak ak I ICA I A I AK ak ok ok ak ak ak ok ok ak ak IA I AIC I AK AK kk kk Extension 2009 12 16 All keys which allow rbtreeinsert also allow ntreeinsert All keys which allow rbtreefind also allow rbtreepfind rbtreenext and rbtreeprevious ak ok ok ak ak ak ok ok ak ak ak ak ak A I AC ICA I AK kkk
13. 4 Graph Generating Functions 5 Weak and Strong Components typedef struct gstdd GSTDD decomposition into C 2 LITERAL CONSTANTS AND TYPE DEFINITIONS typedef typedef typedef typedef typedef 6 typedef typedef typedef typedef typedef typedef typedef typedef Cs typedef typedef typedef typedef 10 typedef typedef 11 typedef typedef typedef typedef struct wcomp struct scomp struct gvtstd struct gedstd struct gincsqrstr Biblock Decomposition struct clcstr struct substr struct blbstr struct itstr struct ptstr struct avtstd struct aedstd struct incsqrstr Additional DFS Structure struct dfsvtstr struct dfsedstr General Partitions Paths struct phdrstr struct pthastr Menger Structures WCOMP SCOMP GVTSTD GEDSTD GINCSQR CLC SUB BLB IT PT AVTSTD AEDSTD INCSQR DFSVT DFSED PHDR PTHA struct mgdescrstr MGDESCR struct mgsepdescrstr SEPDESCR Higher A Decomposition struct hstdd HSTDD struct hcomp HCOMP struct hvtstd HVTSTD struct hedstd HEDSTD weak and strong components weak component strong component vertex in a weak strong components decomposition of a general graph line in w
14. AVTSTD avtstdleft avtstdright avtstdpar avtstdcolor avtstdauxiliary avtstdp avtstdclass avtstdhinge avtstdcheck avtstdborder avtstdptedno avtstdptedlist avtstdptiedno avtstdptiedlist avtstdptoedno avtstdptoedlist avtstdpt avtstditedno avtstditedlist avtstditiedno avtstditiedlist avtstditoedno avtstditoedlist avtstdit avtstdblbno identifying number PT number of vertices pointer to vertex list number of edges pointer to list of edges number of arcs pointer to list of arcs border point vertex in a biblock decomposition for future extension pointer to vertex class of vertex see enum RVSTDCLASS hinge point check point border point number of peripheral tree edges pointer to incidence list of peripheral tree edges number of incoming peripheral tree arcs pointer to incidence list of incoming peripheral tree arcs number of outgoing peripheral tree arcs pointer to incidence list of outgoing peripheral tree arcs pointer to peripheral tree number of internal tree edges list of internal tree edges number of incoming internal tree arcs list of incoming internal tree arcs number of outgoing internal tree arcs list of outgoing internal tree arcs pointer to internal tree number of biblocks containing the ver
15. RELEM Generic substrucure 6 4 1 1 RELEMCLASS of elementary substructure ok oR ak ak ak ak ak ak ak R ak ak aka KOR I I A I aK aK aK KOR OK K struct relemstr RELEM Generic substructure RELEM relleft RELEM relright RELEM relpar COLOR relcolor void relauxiliary for future extensions int reltype type of substructure 1 no type assigned yet void relp pointer to substructure enum relemclass RELEMCLASS of elementary substructure TYGRA Graph TYSGR Subgraph TYSUB Subcomponent TYBLB BLB TYIT IT TYPT PT TYAP attachment point TYWCOMP weakly connected component TYSCOMP strongly connected component TYCLASS EDCLASS record TYHCOMP HCOMP record TYEDSTD EDSTD record TYDUMMY Points to no record class but carries a value in the auxiliary field enum COLORS Colors for processing and classifying CLRNONE uncolored CLRBROWN brown CLRGREEN green CLRRED red CLRBLUE blue CLRYELLOW yellow C 4 DATA STRUCTURES FOR UTILITIES CLRPINK pink x CLRORANGE orange CLRMAGENTA magenta CLRWHITE white CLRBLACK black J C 4 2 Data Structures for Red Black Trees k 3k k sk o
16. util c C 2 1 VERTEX mnewvt char message util c C 2 2 RVERTEX mnewrvertex char message util c C 2 3 EDGE mnewed char message util c C 2 4 REDGE mnewredge char message util c C 2 5 INC mnewinc char message util c C 2 6 VTSET mnewvtset char message util c C 3 1 EDSET mnewedset char message util c C 3 2 GSET mnewgset char message util c C 3 3 SETELEM mnewsetelem char message util c C 3 4 GSTDD mnewgstdd char message util c C 4 1 WCOMP mnewwcomp char message util c C 4 2 SCOMP mnewscomp char message util c C 4 3 GVTSTD mnewgvtstd char message util c C 4 4 GEDSTD mnewgedstd char message util c C 4 5 SUB mnewsub char message util c C 5 1 BLB mnewblb char message util c C 5 2 IT mnewit char message util c C 5 3 PT mnewpt char message util c C 5 4 AVTSTD mnewavtstd char message util c C 5 5 AEDSTD mnewaedstd char message util c C 5 6 INCSQR mnewincsqr char message util c C 5 7 DFSVT mnewdfsvt char message util c C 6 1 x DFSED mnewdfsed char message util c C 6 2 PHDR mnewphdr char message util c C 9 2 PTHA mnewptha char message util c C 9 3 MGDESCR mnewmgdescr char message util c C 10 1 D Functions for Releasing List of Records void releaserellist RELEM qusta util c D 1 1 1 vo
17. E SUA amp S OR 45 4 3 4 degreedelete a a 46 4 3 5 generatefromcomp 4T 4 3 0 generatefromchnm 48 AA Examples i uod Ba xe kN unse xD a ir WQ WI OE 48 Weak and Strong Components 53 5 1 Problem Description 53 Dll Survey Ol Mim ChiOns ses bee ern Be ha Dd ditte Du dns 55 5 2 Formats and Data Structures curen aama nn 55 53 cBuncbiods 2 5 M sana ya ss Be MESI adio EN 56 Ovo componens KR eq te tied dioe PS 56 5 912 amp DESU foie uro Ba a eee hey wh eer Qe dp dede Yd ge ee teda ade 56 512282 eprstdvt en t uec x an VD Bee Se ee we ELS 57 5 34 aa ras ak ene afe co pr aeta Etsi ae CUR aU t Toe zii ta 58 5 3 52 compsraphy 4 2 BUR eek UR tcd E eet ee Gb E ig is 58 54 Exemples osea eae B RR aa EUR 58 The Biblock Decomposition 63 6 1 Problem Description 63 6 2 Formats and Data Structures 67 6 3 Functions uu sa S u an a SE s ibm AC RE RUE 67 S PTT 67 6 39 20 aprstdir k u eee m bi eer e S S pier a U s 68 6 3 3 aprstd vies 2 p a y SM A eR uM RS EE p RAS Wi IT 68 6 3 4 blberapli ua eR uio
18. 192 RSTP RSUB NSUB RBLB NBLB RELBLB RLBLBSUB NELBLB RIT RPT RINCSQR NINCSQR PTNM PTNC 10 getname rbtcomp rbtreefind rbtreeinsert getname rbtcomp rbtreefind rbtcomp rbtreefind rbtreeinsert getname rbtcomp rbtreefind rbtcomp rbtreefind rbtreeinsert getname rbtcomp rbtreefind rbtreeinsert rbtcomp rbtreefind rbtcomp rbtreefind rbtreeinsert getname rbtcomp rbtreefind rbtreeinsert getname rbtcomp rbtreefind rbtreeinsert getname rbtcomp rbtreefind rbtreefind Name of wcomp with suffix STP Subcomponent sorted by subnumber subnumber compared to int Note Do not use parameters of mode int Biblock sorted by blbnumber blbnumber compared to int Note Do not use parameters of mode int RELEM of BLB type sorted by blb number RELEM of BLB type sorted by sub number and by blb number within sub number RELEM of BLB blbnumber compared to int Do not use mode int Internal tree sorted by itnumber Peripheral tree sorted by ptnumber INCSQR sorted by blbnumber INCSQR compared to blbnumber int Do not use mode int Higher A Decomposition General Partitions Paths Menger Structures rbtcomp rbtreefind rbtreeinsert getname rbtcomp rbtreefind PHD
19. 3 1 Problem Description GHS offers a number of set handling functions These are necessary mainly to generate subgraphs from sets of vertices or sets of lines In addition to sets of vertices and set of lines a third data type namely general sets whose elements a mere character strings are provided All three kinds of sets can be read in from a file saved to a file and released It is also possible to add a single element to them A set of vertices lines can be merged into another set of vertices lines Pure set operations union intersection difference are allowed with general sets only and yield a new general set as result Finally there are functions which transform a general set into a set of vertices lines 3 2 Formats and Data Structures For a general description and basic data types see section 2 2 page 11 The data structures used with the set handling functions are described in subsection C 6 page 171 The data types VTSET EDSET and GSET respectively respresent sets of vertices sets of lines and general sets Elements of general sets are represented by records of type SETELEM In contrast elements of vertex sets line sets are represented by records of type RVERTEX see chapter 2 3 3 Functions for Vertex Sets 3 3 1 readvtset Program Author G nther Stiege Universit t Oldenburg Syntax VTSET readvtset GRAPH graph char filename Description Reads a sequence of names from file filenam
20. P op d f trees f trees rooted rooted rooted N Ol OQ N gt gt F O O O F OF O E Table 6 2 Results of Program acomp01 c Part I 72 CHAPTER 6 THE BIBLOCK DECOMPOSITION BEGIN BIBLOCK DECOMPOSITION REDUCED STRUCTURE GRAPH Ugraphi TYPE UGSLF No_VERTICES 40 No_EDGES 44 No_ARCS No_ISOLATED_VERTICES 1 No_A ACYCLIC_WEAK_COMPONENTS 1 5V 4E OA No_A CYCLIC_WEAK_COMPONENTS 1 34V 40E OA A CYCLIC_WEAK_COMPONENT Ugraphi WCOMP1 34V 40E OA 2BP 2HP No_PERIPHERAL_TREES 2 PERIPHERAL TREE Ugraphi WCOMP1 PTO 5V 4E OA PERIPHERAL TREE Ugraph1 WCOMP1 PT1 2V 1E OA STOPFREE KERNEL Ugraphi WCOMP1 STP 29V 35E OA 5AP 2BP 3CP 2HP No_SUBCOMPONENTS 3 SUBCOMPONENT Ugraphi WCOMP1 SUBO 23V 27E OA 2AP 1BP 1CP 2HP No_BIBLOCKS 3 BIBLOCK Ugraphi WCOMP1 SUBO BLBO 3V 1AP OBP OCP 1HP BIBLOCK Ugraphi WCOMP1 SUBO BLB1 AV OA 1AP 1BP 1CP 1HP BIBLOCK Ugraphi WCOMP1 SUBO BLB2 18V 20E OA 2AP 1BP 1CP 2HP SUBCOMPONENT Ugraphi WCOMP1 SUB1 3V OA 2AP 1BP 1CP OHP No BIBLOCKS 1 BIBLOCK Ugraph1 WCOMP1 SUB1 BLBO 3V OA 2AP 1BP 1CP OHP SUBCOMPONENT Ugraphi WCOMP1 SUB2 3V OA 1AP OBP 1CP OHP No_BIBLOCKS 1 BIBLOCK Ugraphi WCOMP1 SUB2 BLBO 3V OA 1AP OBP 1CP OHP No INTERNAL TREES 1 INTERNAL TREE Ugraph1 WCOMP1 ITO 3V 2E OA
21. 2 _cOxci CLASS EDBB CLASS EDBB 2 _a0 al CLASS EDBB CLASS EDBB GRAPH Graph2 GRAPH Graph2 Table 11 8 Results of Program 5 1 Part III 11 4 EXAMPLES 113 Biblock trees for graph Graph2 Cyclic components only Cyclic component _ 0 1 34V 40E Level 0 Biblock a0 ai 18V 20E root Attachment point bO _a0 a1 Attachment point cO a0 a1 Biblock 3V 3E bO Peripheral tree 5V 4E Internal Tree 3V 2E c0 Biblock AV 4E Attachment point 40 _c0 d0 Attachment point f0 _c0 d0 Biblock 40 41 3V 3E d0 Biblock fO fi 3 0 Attachment point d2 _dO d1 Peripheral tree _d2 g 2V 1E d2 Level Level Level Level Level Level Level Level Level Level Level DOR 500 N N N N F Level End Biblock trees Table 11 9 Results of Program 5 1 Part IV 114 CHAPTER 11 HIGHER DECOMPOSITIONS NOT YET RELEASED Chapter 12 The Triblock Decomposition not yet released 12 1 Problem Description 12 2 Formats and Data Structures For a general description and basic data types see section 2 2 page 11 12 3 Functions Not yet implemented e hoptar 12 4 Examples 116 CHAPTER 12 THE TRIBLOCK DECOMPOSITION NOT YET RELEASED Chapter 13 Red Black Trees 13 1 Problem Description On the one hand the basic incidence structure of GHS graph representations as well as the multitude of derived structures e g weak and strong components biblock dec
22. 94 No SUBCOMPONENTS 2 SUBCOMPONENT wcompgraphi2 3 WCOMPO SUBO 3V 1E No_BIBLOCKS 1 BIBLOCK wcompgraphi2 3 WCOMPO SUBO BLBO SUBCOMPONENT wcompgraph12 3 WCOMPO SUB1 6V 1E No_BIBLOCKS 2 BIBLOCK wcompgraph12 3 WCOMPO SUB1 BLBO BIBLOCK wcompgraphi2 3 WCOMPO SUB1 BLB1 No INTERNAL TREES 1 2BP 2CP 1HP 2A 1AP OBP 1CP OHP 3V 1E 2A 1AP OBP 1CP OHP 7A 1BP 1CP 1HP 3V OE 3A 3AP 1BP 1CP 1HP 4V 1E 4A 1 OBP OCP 1HP INTERNAL TREE wcompgraphi2 3 WCOMPO ITO 4V 3E OA 3AP 1BP 2CP OHP END REDUCED STRUCTURE Table 6 8 Results of Program acomp02 c Part III Chapter 7 Distances not yet released Not yet released 7 1 Problem Description In this chapter functions for distances are presented We start considering a paths f paths b paths from vertex u to vertex v The length of such a path is defined as the a distance f distance b distance from u to v along that path If a path is not mentioned distance means the length of a shortest path where shortest is always understood as minimal number of lines It is easy to determine all shortes paths from a vertex u to a different vertex v An a path f path b path from u to v is called direct if it is either a shortest path or none of its inner vertices lies on a shorter direct path to be updated In this section the distance structure of the giant component of words dat especially the distance s
23. EDSET Edge set C 3 2 GSET General set C 3 3 SETELEM Element of general set C 3 4 K aK ak 2K 3K 3K 3K KOR OR KOR KOR a R 3K 3K K OR K K K K KOR 1 K K K KOK K K K struct vtsetstr VISET Vertex set t VTSET vtsetleft VTSET vtsetright VTSET vtsetpar COLOR vtsetcolor void vtsetauxiliary for future extensions int vtsetcard No of elements RVERTEX vtsetlist pointer to vertices struct edsetstr EDSET Edges set t EDSET edsetleft EDSET edsetright EDSET edsetpar COLOR edsetcolor void edsetauxiliary for future extensions int edsetcard No of elements REDGE edsetlist pointer to lines struct gsetstr GSET General set t GSET gsetleft GSET gsetright GSET gsetpar COLOR gsetcolor void gsetauxiliary for future extensions int gsetcard No of elements SETELEM gsetlist pointer to vertices struct setelem SETELEM Element of general set 1 SETELEM selleft SETELEM selright SETELEM selpar 172 APPENDIX C GHS INTERNAL DATA STRUCTURES COLOR selcolor void selauxiliary char selname C 7 Data Structures for Weak and Strong Components k ak sk ok sk ok sk ok ak ak ak ak ak ak ak ak OR ak OR ak ak ak 2 kk kkk kk kk kk
24. K K K K KKK K Program main Reads a graph reads 2 vertex sets joins the vertex sets adds additonal vertex to the set and uses the resulting vertex set to generate the correponding subgraph include lt stdio h gt include lt GHSstructure h gt main 1 GRAPH graph newgraph VTSET vtseti vtset2 graph readgraphlist xxx vtseti readvtset graph NULL printf No of elements in vertex set d n vtset1 gt vtsetcard savevtset vtseti NULL vtset2 readvtset graph NULL printf No of elements in vertex set d n vtset2 gt vtsetcard savevtset vtset2 NULL addvtset2vtset graph amp vtseti vtset2 vtsetlist add2vtset graph amp vtset1 K00 newgraph generatefromvt graph NEWGRAPH vtset1 gt vtsetlist printgrlist newgraph detailed Table 4 2 Program gen01 c 50 CHAPTER 4 GRAPH GENERATING FUNCTIONS No of elements in vertex set K06 K11 K13 No of elements in vertex set K14 K15 Statistics of graph NEWGRAPH Type GG Vertices 6 Edges Mult edges 2 Loops u 2 Mult loops u Arcs 8 Mult arcs 2 Loops d 3 Mult loops d Degree summary undirected loops are counted twice Mean total degree 3 67 Standard deviation of total degree 1 80 2 Vertices of total
25. SDIR menger c ODIR mengerutil o SDIR mengerutil c SDIR GHSstructure h CC fPIC I o ODIR mengerutil o c SDIR mengerutil c General Utilities ODIR util o SDIR util c SDIR GHSstructure h CC fPIC o ODIR util o c SDIR util c Red black trees ODIR rbtree o SDIR rbtree c SDIR GHSstructure h CC fPIC I o ODIR rbtree o c SDIR rbtree c Stacks and Queues ODIR qusta o SDIR qusta c SDIR GHSstructure h CC fPIC I o ODIR qusta o c SDIR qusta c clean rm f ODIR o rm f ghs Appendix B GHS External Data Structures B 1 File Format Files for graphs are ASCII files and must be structured according to the following syntax BNF An informal description of graph files is given in subsection 2 1 on page 11 lt graphfile gt lt sep gt lt graphname gt lt graphtype gt lt vertername gt lt edgespecification gt lt edgename gt GRAPH lt sep gt lt graphname gt lt sep gt TYPE lt sep gt lt graphtype gt lt sep gt VERTICES lt sep gt lt vertername gt lt sep gt lt vertername gt lt sep EDGES lt sep gt lt edgespecification gt lt sep gt lt edgespecification gt lt sep gt ARCS sep gt lt edgespecification gt lt sep gt edgespecification gt sep END characters separating string when reading with scanf string not containing characters from sep not sta
26. STRONG COMPONENT wcompgraph WCOMP10 SCOMPO uEOSEO3 1V 1E OA lv EXTERNAL DAG wcompgraph WCOMP10 EXD lt gt OV OE OA WEAK COMPONENT wcompgraph WCOMP11 lt 4 05 06 gt 2V OE 2A aper 1 MAXLV 1 rooted root E05 vertex No STRONG COMPONENTS 1 No f ACYCLIC STRONG COMPONENTS 0 No f CYCLIC STRONG COMPONENTS 1 STRONG COMPONENT wcompgraph WCOMP11 SCOMPO lt 4 06 06 gt 1V OE 1A WAP lv EXTERNAL wcompgraph WCOMP11 EXD lt dEOBEO6 2V OE 1A 1 WEAK COMPONENT wcompgraph WCOMP12 lt _EO7EO7 gt 20V 11E 144 aper 1 MAXLV 2 rooted root wcompgraph WCOMP12 SCOMP2 EOTEO7 strong component No STRONG COMPONENTS 5 No f ACYCLIC STRONG COMPONENTS 2 STRONG COMPONENT wcompgraph WCOMP12 SCOMPO lt _uE23E26 gt 2V 1E OA 1WAP lv STRONG COMPONENT wcompgraph WCOMP12 SCOMP1 lt _uE13E16 gt 2V 1E OA 1WAP lv No CYCLIC STRONG COMPONENTS 3 STRONG COMPONENT wcompgraph WCOMP12 SCOMP2 lt 07 07 gt 1V 1E OA 1WAP lv 0 STRONG COMPONENT wcompgraph WCOMP12 SCOMP3 4 08 12 gt 14V 8E 9A 4WAP lv STRONG COMPONENT wcompgraph WCOMP12 SCOMP4 4 20 20 gt 1V OE 1A WAP lv 2 fper EXTERNAL wcompgraph WCOMP12 EXD lt 4 07 09 gt 8V OE AA SWAP END REDUCED STRUCTURE Table 5 2 Weak and strong components of graph wcompgraph Part B 62 CHAPTER 5 WEAK AND STRONG COMPONENTS WEAK AND STRONG COMP
27. aper 1 rooted root wcompgraphi2 WCOMPO SCOMP2 strong component No STRONG COMPONENTS 5 No f ACYCLIC STRONG COMPONENTS 2 STRONG COMPONENT wcompgraphi2 WCOMPO SCOMPO 2V 1E OA 1WAP lv 2 fper STRONG COMPONENT wcompgraphi2 WCOMPO SCOMP1 2V 1E OA 1WAP lv 2 fper No CYCLIC STRONG COMPONENTS 3 STRONG COMPONENT wcompgraphi2 WCOMPO SCOMP2 1V 1E OA 1WAP lv 0 fper STRONG COMPONENT wcompgraphi2 WCOMPO SCOMP3 14V 8E 9A lv 1 fper STRONG COMPONENT wcompgraphi2 WCOMPO SCOMP4 1V OE 1A 1WAP lv 2 fper EXTERNAL wcompgraphi2 WCOMPO EXD 8V OE 4A 8WAP END REDUCED STRUCTURE Table 6 6 Results of Program acomp02 c Part I 6 4 EXAMPLES BEGIN BIBLOCK DECOMPOSITION REDUCED STRUCTURE GRAPH wcompgraphi2 TYPE GG No VERTICES 20 No_EDGES 11 No_ARCS 14 No_ISOLATED_VERTICES 0 No_A ACYCLIC_WEAK_COMPONENTS 0 0V OE 0A No A CYCLIC WEAK COMPONENTS 1 20V 11E 14A A CYCLIC WEAK COMPONENT wcompgraphi2 WCOMPO 20V 11E 14 9AP 5CP 1HP No PERIPHERAL TREES 4 PERIPHERAL TREE wcompgraphi2 WCOMPO PTO PERIPHERAL TREE wcompgraphi2 WCOMPO PT1 PERIPHERAL TREE wcompgraphi2 WCOMPO PT2 PERIPHERAL TREE wcompgraph12 WCOMPO PT3 STOPFREE KERNEL wcompgraphi2 WCOMPO STP No_SUBCOMPONENTS 4 SUBCOMPONENT wcompgraphi2 WCOMPO SUBO No BIBLOCKS 1 BIBLOCK wcompgraph12 WCOMPO SUBO BLBO 3V 1E 2A 2AP 1BP SUBCOMPONENT wcompgraph12 W
28. edset gset2edset gset graph saveedset edset printf Memory after building edge set Bytes n ghsmemsize Table 3 1 Program set01 c Part I 40 CHAPTER 3 releaseedsetlist edset releasegsetlist gset releasevtsetlist vtset printf Memory after releasing edge set general sets Mn printf and vertex set d Bytes n ghsmemsize strcpy mgrname graph gt grname releasegraph graph printf Memory after releasing graph fs Bytes n mgraphname ghsmemsize return 0 Table 3 2 Program 01 Part II Memory after reading graph Memory after reading first general set Memory after building vertex set Memory after releasing first general set Memory after building edge set Memory after releasing edge set general sets and vertex set Memory after releasing graph Graphi Table 3 3 Results of Program set01 c SETS 3 6 EXAMPLES 41 cd GHSsources cp GHStests set02a c maingraph c make cat GHSgraphs Graphi ghs gt XYYX rm GHSobjects maingraph o rm ghs cp GHStests set02b c maingraph c make cat GHSgraphs Graphi cat XYYX ghs rm XYYX Program main Reads a graph builds a general set from its vertex names and writes the general set to standard output
29. isa program which reads five graphs and builds a list of them 3 of the graphs are copied without type changes and then the list and the 3 individual graphs are released After each graph creation and after each graph releasing the actual amount of dynamic memory used is printed using variable ghsmemsize T he results are shown in table 2 13 2 4 EXAMPLES 17 Note Due to changes in the data structures of GHScore the memory values given by bas03 cmd may differ somewhat from those in table 2 13 2 4 EXAMPLES 19 GRAPH Graphi TYPE GG VERTICES KOO 01 02 04 06 KO7 KO8 KO9 K10 K11 12 K13 K14 K15 K16 K18 K19 K20 K21 EDGES _u K01 K02 _u K05 K18 _u K11 K13 u K14 K14a _u K14 K14b _urK16 K17a _u K16 K17b _u K19 K20 ARCS _d K00 K01 _d K00 K13 _d K00 K21 K21 _d K02 K03 _d K03 K09 _d K04 K05 _d K06 K00 _d K07 K19 _d K07 K21 _d K08 K08 _d K09 K02 _d K09 K08 _d K10 K18 _d K11 K00 _d K11 K06 _d K12 K11 _d K12 K13 _d K14 K14 _d K14 K15 _d K15 K15a _d K15 K15b _d K16 K04 _d K16 K17a d K16 Ki7b K16 K17 _d K17 K16 _d K18 K17 _d K19 K07 _d K19 K08 _d K21 K20 END Table 2 2 External File Description of Graph1 20 CHAPTER 2 BASIC GRAPH FUNCTIONS Program main Reads 4 graphs in sequence building
30. ok ok Gk ok ok KK KK KK K ok ck ck d dk dk Gb ck dk HHH dt dk dk HH OF Source Makefile Revision 2 12 Date 2009 02 01 18 52 35 Author G Stiege GHScore Makefile k k k k k Ck k k k KOK Ck Ck OK Graph Handling System GHS Copyright c 2000 2003 Guenther Stiege and Sergej Alekseev Universitaet Oldenburg Germany All rights reserved Redistribution and use in source and binary forms with or without modification are permitted provided that 1 source code distributions retain the above copyright notice and this paragraph in its entirety 2 distributions including binary code include the above copyright notice and this paragraph in its entirety in the documentation or other materials provided with the distribution 3 all advertising materials mentioning features or use of this software display the following acknowledgement This product includes software developed by Guenther Stiege et al and Sergej Alekseev Universitaet Oldenburg Germany Neither the name of the University nor the names of its authors may be used to endorse or promote products derived from this software without Specific prior written permission 4 changes are permissible only if the changed files are given a new name dif
31. pointer to vertex int hvtstdhcompno number of most connected decomposition elements of a given type vertex is contained in HCOMP hvtstdwcomp list of most connected decomposition elements of a given typevertex is contained in int gvtstdtype type of vertex 1 not yet assigned 0 isolated vertex 1 internal vertex of external dag no return 2 internal vertex of strong component 3 weak attachment point SCOMP gvtstdscomp pointer to strong component NULL not applicable int gvtstdexdino number of incoming external dag arcs REDGE gvtstdexdilist list of incoming external dag arcs int gvtstdexdono number of outgoing external dag arcs REDGE gvtstdexdolist list of outgoing external dag arcs int gvtstdlevel level number 1 Not yet assigned all vertices of a strong component have the level number of that component BOOLEAN gvtstdmarked General mark indicator h struct hedstd HEDSTD line in a weak and strong decomposition t HEDSTD hedstdleft HEDSTD hedstdright HEDSTD hedstdpar COLOR hedstdcolor void hedstdauxiliary EDGE hedstdp pointer to line int hedstdtype type of line 1 not yet assigned 1 edge gedstdelcmp points C 14 SORT KEYS FOR RED BLACK TREES to strong component
32. 2 The maximum number of internally vertex disjoint f paths from u to v equals the minimum number of vertices f separating u and v 3 The maximum number of line disjoint a paths from u to v equals the minimum number of lines a separating u and v 4 The maximum number of line disjoint f paths from u to v equals the minimum number of lines f separating u and v In the case of line disjoint paths vertices u and v are allowed to be adjacent Neither the paths nor the separating vertex line sets are uniquely determined We call such paths a system of Menger paths and the vertex line sets Menger separating sets It can always be assumed that the paths are simple For a given type a path f path internally vertex disjoint line disjoint a simple path from u to v is called a Menger path if it can be complemented by other simple paths such that a system of Menger paths of the given type results A single vertex line is called a Menger vertex Menger line for u and v ifit can be complemented by other vertices lines such that a Menger a separating set Menger f separating set for u and v results Menger vertices and Menger lines have nice ordering properties For two Menger vertices 2 and y we define Su y z lies before y in direction from u to v if z y or if there is a Menger path on which z comes before y in direction from u to v This definition holds without changes for Menger lines In most cases u and v are clear from the co
33. 6 1 PROBLEM DESCRIPTION 65 where these units are attached to each other are border points check points and hinge points These are called attachment points they are cut points The lines of the peripheral and internal trees are bridges All other lines are non bridges The biblock decomposition of a general graph leads to an important derived bipartite undirected graph the biblock graph The elementary connectedness elements namely improper connected components acyclic components peripheral trees internal trees and biblocks at the one hand and the attachment points at the other hand are the vertices An attachment point is joined by an edge to every connectedness element it is part of There are no other edges Isolated vertices and a acyclic weak components of the original graph become isolated vertices in the biblock graph It is easy to see that in the biblock graph of a general graph there are no a circuits and that the biblock graph is a connected if and only if the original graph is a connected Therefore the biblock graph of an a connected general graph is an a tree its biblock tree The tree structure of the biblock graph of an a connected general graph has important conse quences It allows a rather simple general and uniform treatment of most graph theoretic and many practical questions 1 Solve the problem for the biblock tree and 2 Solve the problem for each biblock In general step 1 is easy and step 2 is the hard core of
34. EDGE F struct incstr APPENDIX C GHS INTERNAL DATA STRUCTURES INC INC INC COLOR void EDGE rvtpat rvtcolor rvtauxiliary for future extensions rvtp pointer to vertex EDGE edleft edright edpar edcolor edauxiliary for future extensions edname line name edtype type directed or undirected u for undirected d for directed edfirst first vertex resp head edsec second vertex resp tail edptgstd decomposition extension of record weak and strong components edptastd decomposition extension of record biblock decomposition xedptdfs extension of record for additional dfs structure edattr pointer to attribute structure edattrtype type of attribute structure 1 No attributes 0 User specific attributes not supported by GHS REDGE redleft redright redpar redcolor redauxiliary for future extensions redp Pointer to line INC Incidence entry incleft incright incpar incolor incauxiliary for future extensions incedge pointer to line C 6 DATA STRUCTURES FOR SETS 171 C 6 Data Structures for Sets DRC ok sk ok sk ak ak ak ak ak ak ak ak ak OR ak oko OR ak ak ak OR 9k R ak ak R 24 kkk kk kk kk 2 VTSET Vertex set 6 3 1
35. Graph pointer NULL old and new graph have the same name incorrect graph type See also the warning under remarks below 46 CHAPTER 4 GRAPH GENERATING FUNCTIONS Remarks The sequences of specialization of the graph types are GG UG UGS UGSLF and GG DG DGS DGSLF for undirected graphs and for digraphs respectively see table 2 1 page 12 Changing a graph to a less specialized type will do nothing but change the graph type in the new graph Changing a graph to a more specialized type goes as follows 1 GG UG All edges are kept as they are All arcs are made edges and keep their names 2 GG DG All arcs are kept as they are All edges except loops are transformed into two arcs one in each direction One of the arcs keeps the edge s name the name of the other is built from the edge name adding the suffix _e2a Undirected loops are transformed into directed loops with the same name 3 UG UGS For all pairs of vertices all multiple edges but one joining the vertices are deleted It is not specified which edge is kept 4 DG DGS For any pair of a starting vertex and an end vertex all multiple arcs but one are deleted It is not specified which arc is kept 5 UGS UGSLF and DGS DGSLF All loops are deleted When type conversion encompasses several steps of a specializing sequence it is performed as such For instance conversion GG UGS is decomposed into the steps GG U
36. RB GHSwords GRNC graphwords cpchtp graph UGSLF Newgraphwords printf 81d int ghsmemsize printf Memory after copying graph GHSwords to Newgraphwords Wn Table 2 11 Program bas03 c Part II 2 4 EXAMPLES 29 releasegraphlist graph0 printf 8ld int ghsmemsize printf Memory after releasing Newgraph0 n releasegraphlist graphlist printf 81d int ghsmemsize printf Memory after releasing list of graphsNn releasegraphlist graphwords printf 8ld int ghsmemsize printf Memory after releasing Newgraphwords n releasegraphlist graph1b printf 81d int ghsmemsize printf Memory after releasing Newgraphib n return 0 Table 2 12 Program bas03 c Part III Memory before reading the graphs 1052 Memory after reading graph GraphO 6014 Memory after reading graph Graphl 10897 Memory after reading graph Graphla 1762027 Memory after reading graph GHSwords 1767030 Memory after reading graph Graphib 1768085 Memory after copying graph GraphO to NewgraphO 1773091 Memory after copying graph Graphib to Newgraphib 3524226 Memory after copying graph GHSwords to Newgraphwords 3523171 Memory after releasing NewgraphO 1756141 Memory after releasing list of graphs 5006 Memory after releasing Newgraphwords 0 Memory after releasing Newgraphib Table 2 13 Results of Program bas03 c 30 CHAPTER 2 BASIC GRAPH FUNCTIONS Chapter 3 Sets
37. basics c SDIR GHSstructure h CC fPIC I o ODIR basics o c SDIR basics c Set Functions ODIR gsets o SDIR gsets c SDIR GHSstructure h CC fPIC I o ODIR gsets o c SDIR gsets c Graph Generating Functions ODIR generate o SDIR generate c SDIR GHSstructure h CC fPIC I o ODIR generate o c SDIR generate c ODIR cpchtp o SDIR cpchtp c SDIR GHSstructure h CC fPIC I o ODIR cpchtp o c SDIR cpchtp c Functions for the Decomposition of General Graphs ODIR gcomponents o SDIR gcomponents c SDIR GHSstructure h CC fPIC I o ODIR gcomponents o c SDIR gcomponents c ODIR astd o SDIR astd c SDIR GHSstructure h CC fPIC I o ODIR astd o c SDIR astd c ODIR gstdutil o SDIR gstdutil CC fPIC I o ODIR gstdutil ODIR astdutil o SDIR astdutil CC fPIC I o ODIR astdutil Path functions C SDIR GHSstructure h c SDIR gstdutil c SDIR GHSstructure h c SDIR astdutil c ODIR path o SDIR path c SDIR GHSstructure h CC fPIC I o ODIR path o c SDIR path c ODIR pathutil o SDIR pathutil c SDIR GHSstructure h CC fPIC I o ODIR pathutil o c SDIR pathutil c Menger functions 151 152 APPENDIX A GHS MAKEFILE ODIR menger o SDIR menger c SDIR GHSstructure h CC fPIC I o ODIR menger o c
38. bl ntreeinsert amp root RB vt SND if bl printf rbtO1 As exists already Nn vt gt vtname Testing tree contructed bl testtree stdout root SND S Testing for correctness if bl printf rbtOl No correct binary search tree has been built in exit 0 else printf rbt01 Binary search tree is correct n bl testtree stdout root SND R Testing for correct red black tree if bl printf rbtO1 No correct red black tree has been built n printorder stdout root SND printrbtree stdout root 0 SND Table 13 1 Program rbt01 c 13 5 EXAMPLES 129 rbt01 HAT exists already rbt01 Binary search tree is correct testtree Blacklengths differ Blacklength to ANTON is 3 blacklength to BESUCH is 4 rbt01 No correct red black tree has been built ANTON BESUCH DER HAT HUT KNABE LAGE LUST NEIN NOCH PFAU QUARK ROT RUHEN SEHEN TANNE ZAHN ZANK Table 13 2 Results of Program rbt01 c Part I 130 e B O O O O Q Q 5 GO N S O N NUUN k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k e N Q N F oor CHAPTER 13 RED BLACK TREES Parent NULL Parent SEHEN Parent DER SEHEN color BLACK DER color BLACK ANTON color BLACK Leaf BESUCH color BLACK Leaf Leaf RUHEN color BLACK HAT color BLACK Leaf
39. check points and hinge points but not border points complete structure print attachment points but no other vertices and no lines reduced structure no vertices no lines only summary of number of attachment points print condensed statistics only for partitions with paintings only size color statistics of classes for partitions with paintings only condensed size color Statistics 181 182 APPENDIX C GHS INTERNAL DATA STRUCTURES C 9 Data Structures for Additional DFS Structure k 3k ok sk ok sk ok sk ok sk ak ak ak ak ak oko OR ak ak ak OR ak R ak ak A 2 FOR 2k 24 kk kkk kk kk kk kkk kk kk kkk DFSVT Vertex extension DFSED Edge extension K aK aK 2K 3K 3K 3K 3K 3K 3K aK aK 2K 3K struct dfsvtstr DFSVT vertex extension for dfs structure t DFSVT dfsvtleft DFSVT dfsvtright DFSVT dfsvtpar COLOR dfsvtcolor void dfsvtauxiliary for future extensions VERTEX dfsvtp pointer to vertex int dfslevel do not confound with gvtstdlevel 1 not yet assigned EDGE dfsiinctree incoming dfs tree arc at most one int dfs
40. tioned Essentially GHScore is a collection of C programs offering functions for a variety of graph oper ations and graph algorithms The collection is far from being complete and there is no intention to achieve completeness in the future Beside some functions for elementary graph manipulation the collection contains mainly functions to decompose graphs into simpler components With respect to this problem however there are some new ideas and algorithms not available in other packages For an example see chapter 6 The Biblock Decomposition GHScore is being implemented in C Users are assumed to have a working knowledge of this programming language and familiarity with an Unix operating system A basic knowledge of graph theory and graph algorithms is of course assumed too The system has been tested and is as stable or unstable as a continualy evolving system which is used as research tool is expected to be The function groups supported by GHScore are reflected in the chapters following this introduc tion Chapter 2 Basic Graph Functions Reading a graph from a file Saving a graph to a file Graph printing programs Adding and deleting single vertices and single lines Adding a depth first forest structure to the graph Chapter 3 Sets Functions to handle sets of vertices sets of lines and general sets i e sets of character strings Chapter 4 Graph Generating Functions Programs for generating subgraphs from
41. 127 Note Key values for insertion like SND are valid also for ntreeinsert Key values like SND or SNN usable for comparisons are valid also for rbtreepfind rbtreenext rbtreeprevious 120 CHAPTER 13 RED BLACK TREES 13 3 Functions 13 3 1 ntreeinsert Program Author G nther Stiege Universit t Oldenburg Syntax BOOLEAN ntreeinsert RB root RB elem int key Description root points to a general binary search tree elem is the record to be inserted TRUE is returned if a new record has been added to the tree If the key value already exists FALSE will be returned The type of the records and the search key used depend on the key class key see section 13 2 The insertion is done in a naive way i e the record is added at the place which its key value indicates No reordering of the tree is done Error Exits System error if NULL record is to be inserted System error if key class is not allowed Remarks None Examples See example 13 1 page 126 13 3 2 rbtreeinsert Program Author G nther Stiege Universit t Oldenburg Syntax BOOLEAN rbtreeinsert RB root RB elem int key Description root points to a red black tree elem is the record to be inserted TRUE is returned if a new record has been added to the tree If the key value already exists FALSE will be returned The type of the records and the search key used depend on the key class key see section 13 2 Error Exits System error if NULL record is t
42. 1BP 3CP 1HP END REDUCED STRUCTURE Table 6 3 Results of Program acomp01 c Part 6 4 EXAMPLES 73 BIBLOCK DECOMPOSITION PRINT OPTION VPA Undirected loops are counted twice GRAPH Ugraphi TYPE UGSLF No VERTICES 40 No EDGES 44 No ARCS 0 VERTICES do TDG 3 DG 3 0DG O IDG O Ugraph1 WCOMP1 Check Point NO_BIBLOCK_EDGES Ugraphi WCOMP1 SUB1 BLBO _d0 d1 _d0 d2 NO_INTERNAL_TREE_EDGES Ugraph1 WCOMP1 ITO c0 d0 TDG 3 DG 3 0DG O IDG O Ugraphi WCOMP1 Border Point NO_PERIPHERAL_TREE_EDGES Ugraphi WCOMP1 PT1 d2 g NO_BIBLOCK_EDGES Ugraphi WCOMP1 SUB1 BLBO _d0 d2 _d1 d2 TDG 3 DG 3 0DG O IDG O Ugraph1 WCOMP1 Check Point NO_BIBLOCK_EDGES Ugraphi WCOMP1 SUB2 BLBO _f0 f1 _f0 f2 NO_INTERNAL_TREE_EDGES Ugraphi WCOMP1 ITO cO fO0 TDG 4 DG 4 0DG O 1DG O Ugraphi WCOMP1 Hinge Point NO_BIBLOCK_EDGES Ugraph1 WCOMP1 SUBO BLBO _b0 b1 _b0 b2 NO_BIBLOCK_EDGES Ugraph1 WCOMP1 SUBO BLB2 _b0 a3 _b0 a5 TDG 7 DG 7 0DG O IDG O Ugraphi WCOMP1 Border Point Check Point Hinge Point NO PERIPHERAL TREE EDGES Ugraph1 WCOMP1 PTO 0 0 NO_BIBLOCK_EDGES Ugraph1 WCOMP1 SUBO BLB1 1 cO c3 NO_BIBLOCK_EDGES Ugraphi WCOMP1 SUBO BLB2 _ 0 12 _ 4 NO INTERNAL TREE EDGES Ugraphi WCOMP1 ITO _c0 d0 cO fO0 Table 6 4 Results of Program acom01 c Part III 74 CHAPTER 6 THE BIBLOCK DECOMPOSITION Example 6 2 Sometimes it is useful to aply the biblock
43. 5 rbtreefind Program Author G nther Stiege Universitat Oldenburg Syntax RB rbtreefind RB tree RB elem int key Description Searches a record in the red black tree given by tree The search value is given by elem The type of the record and how the search key is used depend on the key class key see section 13 2 The return value is the address of the found record It is NULL if no record is found Error Exits System error if search value is NULL System error if key class is not allowed Remarks None Examples See example 13 6 page 126 13 3 6 rbtreepfind Program Author G nther Stiege Universit t Oldenburg Syntax RB rbtreepfind RB tree RB elem int key 122 CHAPTER 13 RED BLACK TREES Description Searches a record in the binary search tree given by tree The search value is given by elem The type of the record and how the search key is used depend on the key class key see section 13 2 The return value is the address of the found record if it exists If a record with the given key does not exist and the provided key value is not greater than the largest existing key and not smaller than the smallest existing key the record with the next lower key value is returned Otherwise NULL is returned Error Exits System error if search value is NULL System error if key class is not allowed Remarks None Examples See example 13 6 page 126 13 3 7 rbtreesize Program Author G nther Stiege Universit t O
44. 7 1 Combined distance graphs point block point check point trees point 82 CHAPTER 7 DISTANCES NOT YET RELEASED Chapter 8 Edge and Vertex Partitions not yet released In this chapter only simple graphs 1 e graphs of type UGSLF are considered 8 1 Problem Description Strictly speaking a family of edge sets of a graph is an edge partition if the sets are pairwise disjoint and their union is the complete set of edges However it is more expedient to allow general sets of edges GHS knows two types of edge partitions 1 Strict partitions The edge sets are pairwise disjoint 2 General partitions The edge sets may have elements in common In no case the union of the edge sets is required to contain all edges of the graph We shall deal with non empty edge sets only The edge sets will be called classes Vertices edges common to two or more classes are attach ment points attachment edges The basic example is the partition generated by a set W of limiting vertices and by a set F of limiting edges W and F not both empty Two edges belong to the same class if the following holds There is a path through both edges with mot internal verter in W no edge in The path must start in a vertex in W or in an end point of an edge in F This partition is strict In a non connected graph the union of its classes may be a proper subset of the set of all edges however For more details see Stie1998 Function
45. 81 Stiege G nther Graphen und Graphalgorithmen Reihe Informatik Shaker Verlag 2006 51 53 61 94 99 Stiege Giinther General Graphs Berichte aus dem Department fiir Informatik 02 07 Universitat Oldenburg 2007 Available from http www bvs informatik uni oldenburg de Literatur Berichte oib07 02 html 51 58 61 94 99 Stiege G nther Einf hrung in die Informatik Reihe Informatik Shaker Verlag 2009 to appear 115 Tarjan Robert Endre Depth First Search and Linear Graph Algorithms SIAM Journal of Computing 1 2 215 225 1972 61 Volkmann Lutz Fundamente der Graphentheorie Springer Lehrbuch Mathematik Springer Verlag 1996 51 202 BIBLIOGRAPHY Index Symbols ARCS 12 DIRECTION 88 EDGES 12 END 12 31 33 36 88 GRAPH 12 GRAPH containing a a path 88 PATH 88 PATHLINES 88 POSITION 88 TYPE 12 VERTICES 12 A a acyclic 53 54 a circuit 53 55 63 a component 101 a cyclic 53 54 a cyclic weak component 63 a depth first search 54 a path 53 a period 55 a reachable 53 101 a tree 54 acyclic 53 acyclic component 66 102 add2class 85 add2edpart 85 add2edset 35 add2gset 36 add2vtset 33 addedset2edset 35 addline 16 addvertex 16 addvtset2vtset 33 AEDSRD 67 any 15 53 aprstd 68 aprstdvt 68 arc 12 53 arc name 12 astd 67 attachment point 54 65 AVTSTD 67 B b acyclic 53 b circuit 53 b cyclic 53 b depth first search 54
46. APPENDIX C GHS INTERNAL DATA STRUCTURES int phtype 1 no type assigned yet 0 a path 1 f path 2 b path PTHA phfirsted first line of path PTHA phlasted last line of path int phlength No of lines in path PTHA phspeced special line of path for various applications PTHA phspeced1 special line of path for various applications h struct pthastr PTHA line in path 1 PTHA pthaleft PTHA ptharight PTHA pthapar COLOR pthacolor void pthaauxiliary for future extensions EDGE pthaed line record VERTEX pthafirst first vertex in path direction VERTEX pthasecond second vertex in path direction PTHA pthanext next line in path PTHA pthaprevious previous line in path PHDR pthahdr pointer to path header C 12 Data Structures for Menger Structures k 3 ok sk ok sk ok sk ok sk ak ak ak ak ak ak ak ak ak ak kkk kk kk kk kkk kk kk kkk MGDESCR Menger descriptor SEPDESCR Separating aK aK 2K 3K 3K K aK aK 2K 3K 3K 3K aK aK 2K 3K 3K K aK K 3K 3K 3K K K K 3K 3K 3K K K K FK 3K KKK K K K struct mgdescrstr MGDESCR descriptor for Menger analysis t MGDESCR mgleft MGDESCR mgright MGDESCR mgpar COLOR mgcolor void mgaux
47. HUT color BLACK Leaf KNABE color BLACK Leaf LAGE color BLACK Leaf ROT color BLACK QUARK color BLACK PFAU color BLACK NOCH color BLACK NEIN color BLACK LUST color BLACK Leaf Leaf Leaf Leaf Leaf Leaf Leaf Leaf ZAHN color BLACK TANNE color BLACK Leaf Leaf ZANK color BLACK Leaf Leaf Parent ANTON Parent DER Parent RUHEN Parent HAT Parent HUT Parent KNABE Parent LAGE Parent ROT Parent QUARK Parent PFAU Parent NOCH Parent NEIN Parent SEHEN Parent ZAHN Parent ZAHN Table 13 3 Results of Program rbt01 c Part II 13 5 EXAMPLES 131 rbt02 Red black tree is correct ANTON BESUCH DER HAT HUT KNABE LAGE LUST NEIN NOCH PFAU QUARK ROT RUHEN SEHEN TANNE ZAHN ZANK Table 13 4 Results of Program rbt02 c Part I 132 CHAPTER 13 RED BLACK TREES HUT color BLACK Parent NULL BESUCH color BLACK Parent HUT ANTON color BLACK Parent BESUCH Leaf Leaf DER BLACK Parent BESUCH Leaf HAT RED Parent DER Leaf Leaf QUARK color RED Parent HUT LAGE color BLACK Parent QUARK KNABE color BLACK Parent LAGE Leaf Leaf NOCH RED Parent LAGE NEIN BLACK Parent NOCH LUST RED Parent NEIN Leaf Leaf Leaf PFAU BLACK Parent NOCH Leaf Leaf RUHEN color BLACK Parent ROT color BLACK Parent Leaf Leaf TANNE color RED Parent SEHEN color BLACK Parent Leaf Leaf ZAHN BLACK Parent
48. K08 Kil degree indegree outdegree Undirected edges _u K11 K13 Outgoing arcs _ d K11 K00 _d K11 K06 Incoming arcs _d K12 K11 K19 degree 1 indegree outdegree 2 Undirected edges u K19 K20 Outgoing arcs d K19 K07 d K19 K08 Incoming arcs _d KO7 K19 Table 2 6 Results of Program bas01 c 24 CHAPTER 2 BASIC GRAPH FUNCTIONS K00 degree indegree 2 outdegree 3 Outgoing arcs d KOO K01 d KOO K13 d KOO K21 Incoming arcs d K06 K00 d K11 K00 K15 degree indegree 3 outdegree 2 Outgoing arcs _d K15 K15a multiple _d K15 K15b multiple Incoming arcs _d K14 K15 _d X15 K15a multiple _d K15 K15b multiple K16 degree 2 indegree outdegree 3 Undirected edges _u X16 K17a multiple _u K16 K17b multiple Outgoing arcs d K16 K04 _d X16 K17a multiple _d K16 K17b multiple Incoming arcs _d K17 K16 K17 degree 2 indegree 3 outdegree Undirected edges _u X16 K17a multiple _u K16 K17b multiple Outgoing arcs _d K17 K16 Incoming arcs _d X16 K17a multiple _d K16 K17b multiple d K18 K17 K14 degree 4 indegree outdegree 2 Undirected edges _u X14 K14a multiple loop _u K14 K14b multiple loop Outgoing arcs _d K14 K14 loop _d K14 K15 Incoming arcs 4 14 14 loop Table 2 7 Results of Program bas01 c d 2 4 EXAMPLES 25 J Program ma
49. K12 K13 K11 is built To this end a new path header is explicitly created and the three lines individually added using function insertline2path The resulting subpath is output and again shown in table 9 3 The final step consists in again creating a new path header and inserting into this path the first and the second subpath using function insertpath2path The finally resulting path is shown in table 9 3 too 9 4 EXAMPLES 95 Kok sk okk sk ok ok Sk ok ak ae ak Pk ok ok ak ok R ak ak OR ak A I Program main Example for path functions DRO sk ok ok Sk ok ak ak ak ak ok ok a ok R ak ak ak ak aaa CFIA A A I IC I AK aK aK aK include lt stdio h gt include lt GHSstructure h gt int main int argc char argv t GRAPH graph PHDR phdr phdri phdr2 EDGE line graph readgraphlist argv 1 if graph NULL printf Incorrect graph input n exit 0 J phdri readpath graph NULL if graph NULL printf Error when reading paths exit 0 printpathlist phdri detailed NULL phdr2 newphdr graph A subpath2 line EDGE rbtreefind RB graph gt grdedlist RB d K12 K11 SEN insertline2path phdr2 line line gt edsec E line EDGE rbtreefind RB graph gt grdedlist RB d K12 K13 SEN insertline2path phdr2 line line gt edfirst E line EDGE rbtreefind RB graph gt gredlist
50. LV 1 wcompgraph WCOMP12 wcompgraph WCOMP12 SCOMP3 weak attachment point No_OUTGOING_EXTERNAL_TREE_ARCS 1 _dE12E13 No_INCOMING_EXTERNAL_TREE_ARCS 0 No_EDGES 1 _uE09E12 No OUTGOING STRONG COMPONENT ARCS 1 _dE12E11 No_INCOMING_STRONG_COMPONENT_ARCS 3 _dEO8E12 _dE10E12 _dE15E12 is to be read as follows Vertex E12 belongs to weak component No 12 of graph wcompgraph It has total degree 6 1 edge 2 outgoing arcs 3 incoming arcs The level number is 1 It is a vertex of return in strong component No 3 It is a weak attachment point A list of arcs and edges E12 is incident with follows stating for each arc whether it is an external dag arc or not For instance _dE12E13 is an outgoing arc of vertex E12 and belongs to the external dag _dE15E12 is an incoming arc und belongs to the strong component SCOMP3 38 CHAPTER 5 WEAK AND STRONG COMPONENTS Examples Example 5 2 page 58 5 3 4 condgraph Still to do 5 3 5 compgraph Still to do 5 4 Examples Example 5 1 This example corresponds to gcomp01 cmd and gcomp01 c in GHStests Function gcomponents is applied to the general graph wcompgraph shown in figure 5 1 In a second step the resulting structure is printed calling function gprstd Tables 5 1 and 5 2 show the output Examples gcomp02 cmd and gcomp02 c in GHStests show a condensed structure printing pa rameter STRCS and a complete structure printing parameter STR of the same graph The output is not included in t
51. STRONG COMPONENT wcompgraph WCOMP7 SCOMP2 uD10D12 3V 2E OA 3WAP EXTERNAL wcompgraph WCOMP7 EXD lt _dDO6DO7 gt 7V OE 6A 7WAP END REDUCED STRUCTURE Table 5 1 Weak and strong components of graph wcompgraph Part A 5 4 EXAMPLES 61 No A CYCLIC WEAK COMPONENTS WITH STRONG COMPONENTS 26V 14E 17A F CYCLIC STRONG COMPONENTS EXIST WEAK COMPONENT wcompgraph WCOMP8 lt _uE01E02 gt 2V 2E OA aper 1 MAXLV 0 rooted root wcompgraph WCOMP8 SCOMPO uEO1E02 strong component No STRONG COMPONENTS 1 No f ACYCLIC STRONG COMPONENTS 0 No CYCLIC STRONG COMPONENTS 1 STRONG COMPONENT wcompgraph WCOMP8 SCOMPO lt _0 01 02 gt 2V 2E OA lv EXTERNAL DAG wcompgraph WCOMP8 EXD lt gt OV OE OA WEAK COMPONENT wcompgraph WCOMP9 dEO4EO4 1V OE 14 aper 1 MAXLV 0 rooted root wcompgraph WCOMP9 SCOMPO dEOA4E04 strong component No STRONG COMPONENTS 1 No f ACYCLIC STRONG COMPONENTS 0 No CYCLIC STRONG COMPONENTS 1 STRONG COMPONENT wcompgraph WCOMP9 SCOMPO lt _dEO4E04 gt 1V OE 1 lv EXTERNAL DAG wcompgraph WCOMP9 EXD lt gt OV OE OA WEAK COMPONENT wcompgraph WCOMP10 lt _uEO3E03 gt 1V 1E 0 aper 1 MAXLV 0 rooted root wcompgraph WCOMP10 SCOMPO lt uEO3EO03 strong component No STRONG COMPONENTS 1 No f ACYCLIC STRONG COMPONENTS 0 No f CYCLIC STRONG COMPONENTS 1
52. Schematic pictures of the three kinds of paths are shown in figure 6 1 From this hierarchy of closed paths equivalence relations on lines are defined whose equivalence classes generate the decomposition subgraphs of the biblock decomposition T he result is shown in figure 6 2 The biblock decomposition proper starts with the a cyclic weak components Each Graph A Acyclic Weak Components A Cyclic Weak Components Improper Weak Components Peripheral Trees Border Points Stopfree Kernel Check Points Subcomponents Internal Trees Hinge Points Biblocks Figure 6 2 Biblock decomposition of a general graph contains exactly one equivalence class of lines generated from stopfree paths These lines generate the stopfree kernel The lines not contained in the stopfree kernel generate an a forest whose weak components are the peripheral trees In each stopfree kernel we find at least one equivalence class of lines generated by closed line simple a paths These classes generate the subcomponents In the stopfree kernel there may be lines not belonging to any subcomponent These again generate an a forest The corresponding weak components are the internal trees Finally each subomponent contains at least one equivalence class of lines generated by circuits These classes generate the biblocks biconnected blocks Structural units of the same level are line disjoint but in general not vertex disjoint The points
53. b path 53 b reachable 53 backward 15 53 basic graph data structures 166 basic graph functions 11 13 biblock 64 66 102 biblock decomposition 63 64 74 176 biblock graph 65 biblock tree 65 103 bipartite 55 BLB 67 102 blbgraph 69 block 63 block cutpoint graph 63 border point 65 breadth first 11 15 103 breadth first sequence 5 bridge 65 building block 44 102 C cdm suffix 4 CFR 102 check point 65 circuit 53 63 64 CLC 102 closed a path 63 closed line simple path 64 closed linesimple path 63 closed path 53 compgraph 58 component 53 101 condgraph 58 connected 101 connected component 53 63 cpchtp 45 cppartition 84 cut point 65 cyclic 53 cyclic component 102 103 204 cyclic ordering 55 D dag 54 data structures 11 13 31 44 55 67 102 119 139 166 data type 13 decomposition 101 decomposition element 44 47 48 55 degreedelete 46 delete see release deleted subgraph 47 deleteline 16 deletevertex 16 depth first 11 15 54 63 depth first search 182 dequeue 139 143 detailed print option 14 91 DFS 182 DG 12 DGS 12 DGSLF 12 difference of two sets 38 digraph 53 directed 53 directed acyclic graph 54 directed edge 12 directed graph 53 directed tree 54 disjoint UW paths 96 distance 79 distribution policy 3 dynamic memory 2 E EDGE 13 edge 12 53 edge name 12 edge partition 83 edge simple pat
54. by the calling program Examples See example qusta01 c in GHStests 14 3 9 fdequeue Program Author G nther Stiege Universit t Oldenburg Syntax void fdequeue QUSTA queue Description Returns a pointer to the top element of stack Error Exits None Remarks If the queue is empty NULL is returned Examples See example qusta01 c in GHStests 14 3 10 qfront Program Author G nther Stiege Universit t Oldenburg Syntax void qfront QUSTA queue Description Returns a pointer to the first element in queue Error Exits None Remarks If the queue is empty NULL is returned Examples See example qusta01 c in GHStests 14 3 11 Program Author G nther Stiege Universit t Oldenburg Syntax void qend QUSTA queue Description Returns a pointer to the last element in queue Error Exits None Remarks I the queue is empty NULL is returned Examples See example qusta01 c in GHStests 14 3 FUNCTIONS 145 14 3 12 qscreate Program Author G nther Stiege Universit t Oldenburg Syntax void qscreate RB rb Description Creates for each element of the red black tree a QS record which represents the original element in a queue and or a stack The auxiliary field of the original element points to the QS record The qsp field of the QS record points back to the original record Error Exits None Remarks None Examples See example qusta01 c in GHStests 14 3 13 qsremove Program Author G nthe
55. chapter with a section containing a set of examples Additional examples are contained in the GHS directory GHStests see section 1 2 The ex amples are intended to illustrate simple normal cases and not so much special applications Together with the introductory chapter 1 they may serve as a primer for GHScore Errors and system errors GHScore programs detect a variety of errors In the case of an error a explanatory message is written to standard output indicating the kind of error and the detecting routine Most errors are user errors inconsistent data and the like The routine returns If the routine yields a return value this will be an error value Some errors should never occur assuming the system programs correct If such a system error is detected the program exits with an appropriate error message Dynamic memory GHScore programs frequently allocate and deallocate dynamic memory An attempt is made to free dynamic memory as soon and as complete as possible The actual amount of dynamic memory allocated by GHScore programs is recorded in the global extern variable ghsmemsize of type long int See examples 2 3 page 16 and 3 1 page 38 Remark 1 1 Sometimes GHS functions detect an user error only after processing has started and some memory has been assigend For instance a graph structure is being constructed from an external description and an inicidence vertex name is missing in the vertex list In these cases GH
56. cyclic component is printed in breadth first sequence starting with a biblock The level of each vertex in the biblock tree is indicated as well as the father vertex Examples Example 6 1 page 70 11 4 Examples As an example let H be a 5 a linecomponent of general graph G From implication 11 1 follows that any 6 a linecomponent of G is either disjoint to H or a subgraph of H So H has no 6 a lineconnected subgraph or decomposes into 1 or more 6 a linecomponents and a set of edges arcs not belonging to any 6 a linecomponent If this set is not empty the subgraph it generates is called the 6 a of H From implication 11 2 follows than any 5 a component of G is either disjoint to H or a subgraph of H Every 5 a component in turn decomposes into 0 ore more 6 a components and possibly a 6 a cocomponent implication 11 1 Finally from implication 11 3 follows that any 5 f linecomponent of G is either disjoint to H or a subgraph of H Again the 5 f linecomponents may be decomposed further The decomposition follows the same arguments as for a decomposition Example 11 1 In this example program 5 1 table 11 1 is used It is applied to graph Ugraphl figure 6 3 The program reads the external description of the graph and constructs it using function readgraphlist Then function stddecomp is called to find and construct the biblock decomposition of the graph Afterwards function checkstr performs consistency checks Next function prstd is calle
57. format and output to file filename If filename is NULL it is output to standard output 6 4 Examples Example 6 1 In this example we consider the undirected graph Ugraph1 of figure 6 3 It consists of the improper weak component h the a acyclic weak component ig 15 and the a cyclic weak component ag a15 09 g We process the graph with the program shown in table 6 1 The program reads the external description of the graph and constructs it using function 7 Program main Reads a graph and constructs its biblock decomposition A condensed decomposition information weak and Strong components as well as biblock decomposition is printed The biblock decomposition is printed A list of vertices ordered by degree and vertex name is printed too It shows all relevant information of of each vertex and all edges incident with it include lt stdio h gt include lt GHSstructure h gt int main 1 GRAPH graph graph readgraphlist NULL astd graph gprstd graph STRCS NULL aprstd graph STRR NULL aprstd graph STRA NULL aprstd graph STR NULL aprstdvt graph VPA NU
58. is compared with char RWCOMP rbtcomp WCOMP compared to WCOMP by wcompnumber rbtreefind rbtreeinsert getname NWCOMP rbtcomp wcompnumber compared to int rbtreefind Note Do not use parameters of mode int RSCOMP rbtcomp SCOMP compared to SCOMP by scompnumber rbtreefind rbtreeinsert getname NSCOMP rbtcomp Scompnumber compared to int rbtreefind Note Do not use parameters of mode int REXD getname Name of wcomp with suffix EXD RGVTSTD rbtcomp Two GVSTD records are compared by rbtreefind a total deegree rbtreeinsert b vertex name getname kokok sk ak ak sk ok bk NOTE RGVTSTD must be used with the pointer gvtstdlist in a GSTDD record since that is the only list where an RB Tree of GVTSTD records is contructed To find a GVTSTD record given the name of its corresponding VERTEX record search the vertex directly and follow the pointer vtptgstd ak ak ak RGEDSTD rbtcomp Two GEDSTD records are compared by the rbtreefind names of the edges arcs they point to rbtreeinsert getname NGEDSTD rbtcomp Name of the vertex the GEDSTD record rbtreefind points to is compared with char 6 Biblock Decomposition 191
59. kkk R 1 Utilities f A General Services CRON rbtreeinsert Insertion in the order of appearance Valid for any record type Used to contruct linear linked lists PCLSIZE rbtcomp RELEM records representing sizes of rbtreefind partition classes The record s rbtreeinsert auxiliary field contains the size getname Comparison of the records according to size NOTE This sortkey may also be used with other RELEM records as long as an integer value in the auxiliary field is used as the primary RB key PECLSIZE rbtcomp As PCLSIZE 189 190 1 2 fh X28 LE ugs GRNM GRNC SND SNN RSND RSNN RSDND SED SEN RSED SED1 RSEN SIN rbtreefind Red Black Trees Stacks and Queues APPENDIX C GHS INTERNAL DATA STRUCTURES Records are compared to a value of type int These must be specified as pointers to an integer variable type int to avoid confusions between value 0 and NULL pointer Basic Graph Functions rbtcomp rbtreefind rbtreeinsert getname rbtcomp rbtreefind rbtcomp rbtreefind rbtreeinsert getname rbtcomp rbtreefind rbtcomp rbtreefind rbtreeinsert getname rbtcomp rbtreefind rbtcomp rbtreefind rbtree
60. of RVERTEX records see distance c QS qsqforward forward pointer in queue QS qsqbackward backward pointer in queue QS qssforward forward pointer in stack QS qssbackward backward pointer in stack void qsp pointer to original record int qshelpi application dependent int qshelp2 application dependent void qsphelp application dependent BOOLEAN qsinqueue record in queue BOOLEAN qsinstack record in stack C 5 Basic Graph Data Structures k k ok sk ok sk ok sk ok ak ak ak ak ak ak ak ak OR ak OR ak ak ak kk kk kk kk kkk kk kk kk kk kkk kk kk kkk GRAPH Structure of graphs C 2 1 GRAPHTYPE Indicator for type of graph Vertices C 2 2 RVERTEX Describes role of vertex C 2 3 EDGE Edges arcs C 2 4 REDGE Describes role of line C 2 5 Incidences C 2 6 oko sk ok ae ok 9k struct grphst GRAPH graph description t GRAPH grleft GRAPH grright GRAPH grpar COLOR grcolor void grauxiliary for future extensions char grname name of the graph int grtype graph type C 5 BASIC GRAPH DATA STRUCTURES int VERTEX int EDGE int EDGE GSTDD BOOLEAN BOO
61. output format is such that it can be read by readgset Error Exits Pointer NULL vertex set empty number of elements incorrect Remarks None Examples Example 3 2 page 38 3 5 3 releasegsetlist Program Author G nther Stiege Universit t Oldenburg Syntax void releasegsetlist VTSET vtset Description Deletes a list of general sets and frees completely the memory Error Exits None Remarks None Examples Example 3 1 3 5 4 add2gset Program Author G nther Stiege Universit t Oldenburg Syntax BOOLEAN add2gset GSET pvtset char name 3 5 FUNCTIONS FOR GENERAL SETS 37 Description Returns FALSE if the character string name is already an element of the general set Otherwise the string is added as a new element to the general set and TRUE is returned Creates new general set for first set element The string must be different from END Error Exits String pointer NULL String length 0 String equals END Remarks None Examples See example set03 c in GHS directory GHStests 3 5 5 gsetunion Program Author G nther Stiege Universit t Oldenburg Syntax GSET gsetunion RB lista int keya RB listb int keyb Description Creates a new general set as the set union of the two red black trees see chapter 13 given by lista and listb The elements of the general set are names of the records of the red black trees The key classes keya and keyb must be such that function getname is allowed see subsecti
62. paths join a vertex in vtsource not in vtsink to a vertex in vtsink not in vtsource and pass through at least one Menger vertex The starting point and the end points of Menger paths are admitted as Menger vertices too If parameter sep equals complete all Menger vertices of all paths are determined together with its minimal Menger separating sets see section 10 1 If parameter sep equals first only the first system of Menger sets in direction from vtsource to vtsink is determined 7 vertices common to vtsource vtsink separating elements The Menger paths found are line disjoint Their starting points in vtsource and their end points in vtsink are pairwise distinct Vertices from vtsource and or vertices from vtsink may be internal vertices of the path found All Menger paths join a vertex in vtsource not in vtsink to a vertex in vtsink not in vtsource and pass through at least one Menger line If parameter sep equals complete all Menger lines of all paths are determined together with its minimal Menger separating sets see section 10 1 If parameter sep equals first only the first system of Menger sets in direction from vtsource to vtsink is determined None 10 4 Examples Example 10 1 To be completed Graph pointer NULL Graph not of type UGSLF Vertex list and edge list both 10 4 EXAMPLES OOOO Figure 10 1 Menger line theorem graph Menglgraph1 99 100 CHAPTE
63. sk ok k 9k ae ak ae ok ae ok ok ak ak ak ara ae ak ak ak ak ak ak ak ak ak ak ak aka PR A o IRA ICA ROROR 4 2k 2k kkk Implicit functions in rbtree c 3 ak ak sk ok k ak ok ak ak ok ak ok ok ak ak ak A o IRA RA int rbtcomp RB 1s1 RB 1s2 int key char keyname int key C 3 3 Global Variables Global variables extern long int ghsmensize global counter of allocated memory extern BOOLEAN btesttest for test purposes extern char namebuffer 1001 common buffer for strings extern char typearrayl graph types as strings extern char stypearrayl graph subtypes as strings extern char vtclassarray vertex class extern char vtstatarrayl vertex processing status extern char edclassarray edge class extern char edstatarrayl edge processing status extern char poptionarray print option extern char edcolorarray line color extern char BLBstring pointer to BLN extern char ITstring pointer to IT extern char PTstring pointer to PT extern char ATTstring pointer to ATT 163 164 APPENDIX C GHS INTERNAL DATA STRUCTURES C 4 Data Structures for Utilities C 4 1 Data Structures for General Sevices k 3k ok sk ok sk ok sk ak sk ak ak ak ak ak oko OR ak OR ak ak oko ek ak ak kkk kk kk kk kk kkk kk kk kkk
64. we also may consider sets of vertices A vertex set of a general graph is called k a connected if every pair of different vertices is mutually k a reachable by internally disjoint a paths where the paths are allowed to traverse vertices not in the set k f connected vertex sets as well as lineconnected vertex sets are defined in an analogous manner Again such sets are uniquely determined if they are maximal For more details see Stiege Stie2006 or Stie2007a The algorithms used by GHS can be found there too Hierarchical Decomposition Hierarchical decomposition of a general graph is possible in four dimensions due to the following implications k connectedness k 1 connectedness 11 1 vertex connectedness gt lineconnectedness 11 2 f connectedness gt a connectedness 11 3 vertex set subgraph 11 4 The first three implications mean that every vertex set respectively every subgraph for which the left side holds also satisfies the right side The last implication says that the vertex set of a 102 CHAPTER 11 HIGHER DECOMPOSITIONS NOT YET RELEASED subgraph has at least the connectedness properties of the subgraph Decomposition for small k Every general graph is a 0 a linecomponent 0 a component 0 f linecomponent and a 0 f component The 1 a linecomponents and the 1 a components of a gen eral graph coincide They are called the weak components of the graph The 1 f linecomponents and the 1 f components als
65. 0 is a strong component then any of its vertices can be taken as root of the f tree 3 a cyclic weak component with no strong components This is again a dag but not an a tree If and only if there is only one vertex with level number 0 from this vertex all others are f reachable However at least one other vertex is f reachable by two different line simple paths Such weak components are called rooted 4 a cyclic weak component with strong components This is the general case In the external dag a circuits may be present The strong components of a weak component may be classified in the following manner e The strong component is f acyclic It then consists of edges only and is a free tree If all strong components have this property then there must be an a circuit containing arcs of the external dag e The strong component is f cyclic Edges and arcs may occur in any combination The following holds I Directed acyclic graph 5 2 FORMATS AND DATA STRUCTURES 55 If an arc is part of a strong component there is an f cycle through that arc and the strong component is f cyclic If a strong component contains an a circuit it is f cyclic and every edge on that a circuit lies on a an f circuit If and only if there is exactly one element with level number 0 there are vertices with root property i e vertices from which all other vertices are f reachable Again such weakly connected components are called rooted If the ele
66. 0E 2AP 1BP 1CP 2HP VERTICES a0 al a2 a3 a4 a5 a6 aT a8 a9 bo cO EDGES _a0 al _al a2 _al0 all _ 11 12 _ 12 13 _ 13 14 _ 14 15 _al5 a0 _a2 a3 _a3 a4 _a4 a5 _a5 a6 _a6 a7 af a8 a8 a9 a9 a10 _b0 a3 _b0 a5 _c0 a12 _c0 a4 Table 11 6 Results of Program 5 1 Part 11 4 EXAMPLES 111 ATTACHMENT POINTS bO cO BORDER POINTS cO CHECK POINTS cO HINGE POINTS bO cO No INTERNAL TREES 1 INTERNAL TREE cOx dO 3V 2E 1BP 3CP 1HP VERTICES cO dO fO EDGES _C0 d0 _C0 f0 ATTACHMENT_POINTS cO dO fO BORDER_POINTS cO CHECK POINTS cO dO fO HINGE_POINTS cO ND COMPLETE STRUCTURE Table 11 7 Results of Program 5 1 Part 112 CHAPTER 11 PRINT OPTION VPV GRAPH Graph2 TYPE UGSLF No VERTICES 40 No_EDGES 44 VERTICES NO PERIPHERAL TREE EDGES NO INTERNAL TREE EDGES NO_BIBLOCKS NO_BIBLOCK_EDGES _b0 b1 _b2 b0 NO_BIBLOCK_EDGES _b0 a3 _b0 a5 NO_PERIPHERAL_TREE_EDGES _c0 e0 NO_INTERNAL_TREE_EDGES 0 0 0 0 NO_BIBLOCKS NO_BIBLOCK_EDGES 0 1 3 0 NO_BIBLOCK_EDGES _ 0 12 _ 4 HIGHER DECOMPOSITIONS NOT YET RELEASED DEGREE CLASS RVDAP HINGEPOINT 0 0 2 2 bO bi CLASS EDBB CLASS EDBB 2 _a0 al CLASS EDBB CLASS EDBB DEGREE CLASS RVDAP HINGEPOINT CHECKPOINT BORDERPOINT 1 _c0 e0 CLASS EDPT 2 _ CLASS EDIT CLASS EDIT 2
67. 1 If such an element exists the subgraph it generates is returned as a new graph with name newname The type of the new graph is the same as that of the original graph with the following exception for the subgraph generated from the external dag of a weak component EXD GG DG DGS gt DGSLF Error Exits NULL returned if syntax of specified name wrong or decomposition element does not exist Remarks The hierarchical names of the elements of a decomposition are displayed by function gprstd page 56 and by function aprstd page 68 The name of a decomposition element given its address can also be obtained directly with function getname page 125 48 CHAPTER 4 GRAPH GENERATING FUNCTIONS Examples See example 5 2 page 58 4 3 6 generatefromchnm Program Author G nther Stiege Universit t Oldenburg Sont void generatefromchnm GRAPH graph char linename char comptype char newname Description linename specifies the name of a decomposition element as charname see sub section 4 1 2 To uniquely identify the element comptype must be specified as one of the following strings WCOMP weak component SCOMP strong component EXD external dag STP stopfree kernel PT peripheral tree internal tree SUB subcomponent BLB biblock If such an element exists the subgraph it generates is returned as a new graph with name newname The type of the new graph is the same as that of the original gr
68. 1 3 11 4 11 5 11 6 11 7 11 8 11 9 13 1 13 2 13 3 13 4 13 5 13 6 13 7 13 8 13 9 LIST OF TABLES Results of Program acomp02 c Part 1 76 Results of Program acomp02 c Part II 77 Results of Program acomp02 c Part 78 External File Format of GHS 88 Program pathol e 42 2 ho ed k Re d Retos 93 Input and output of program 1 01 94 Program DHL 2 2 iru oS e tin dotem OSA le HIE ie pe 105 Results of Program 6 1 Part D amp 5s asas ga can ee 106 Results of Program 5 1 Part 107 Results of Program 5 1 Part 108 Results of Program 5 1 Part He s i xcu E earned eng Pe ie 109 Results of Program 5 1 Part 110 Results of Program 5 1 Part Ie ne Ast qu etg x dete aX 111 Results of Program 5 1 Part 2 112 Results of Program 5 1 Part IV 113 Program EbbOl ce m kus Sot ain ete y uos EO aa ea 128 Results of Program rbt01 c 1 129 Results of Program rbt01 c Part II 130 Results of Program rbt02 c Part I arena eet ent 131 Results of Program rbt02 c Part II 132 Program rbtOf Gus dira eh RR op
69. 18 degree indegree outdegree Undirected edges _u K01 K02 Incoming arcs _d K00 K03 01 indegree outdegree Dutgoing arcs _d K03 K09 Incoming arcs _d K02 K04 K03 indegree outdegree Outgoing arcs _d K04 K05 Incoming arcs _d K16 K04 Table 2 4 Results of Program bas01 c 22 CHAPTER 2 BASIC GRAPH FUNCTIONS K05 indegree outdegree Undirected edges _u K05 K18 Incoming arcs d K04 K05 K06 indegree outdegree Outgoing arcs d K06 K00 Incoming arcs _d K11 K06 K12 degree indegree outdegree Outgoing arcs _d K12 K11 _d K12 K13 K20 indegree outdegree Undirected edges u K19 K20 Incoming arcs d K21 K20 K02 degree indegree outdegree Undirected edges u K01 K02 Outgoing arcs d K02 K03 Incoming arcs d K09 K02 indegree outdegree Dutgoing arcs _d KO7 K19 d KOT7 K21 Incoming arcs 4 19 07 K09 indegree outdegree Outgoing arcs d K09 K02 d K09 K08 Incoming arcs d K03 K09 Table 2 5 Results of Program 01 b 2 4 EXAMPLES 23 K13 degree indegree outdegree Undirected edges _u K11 K13 Incoming arcs d KOO K13 d K12 K13 K18 degree indegree outdegree Undirected edges u K05 K18 Outgoing arcs d K18 K17 Incoming arcs _d K10 K18 K21 degree indegree outdegree Outgoing arcs _d K21 K20 Incoming arcs d KOO K21 d KOT7 K21 K08 degree indegree outdegree Outgoing arcs 4 08 08 loop Incoming arcs 4 08 08 loop _d K09 K08 _d K19
70. 22 Edges Table 3 5 Program set02b c Chapter 4 Graph Generating Functions 4 1 Problem Description 4 1 1 General Remarks This chapter describes important GHS functions which generate new graphs from existing ones General graph generating functions The most important functions of this type are generatefromvt and generatefromed which construct the subgraph of a given graph generated by a set of vertices respectively edges arcs Another function is cpchtp which copies a graph while simultaneously changing its type Finally function degreedelete deletes recursively all vertices of degree n or lower from a graph and generates subgraphs from the remaining and from the deleted edges It also constructs a list of the vertices common to both subgraphs Functions for generating graphs from elementary graph decompositions Elemen tary general graph decompositions are the decomposition into weak and strong components chapter 5 at the one hand and the biblock decomposition chapter 6 at the other hand Func tion generatefromcomp builds the subgraph corresponding to a specific decomposition element given by its name For details on names and addresses see subsection 4 1 2 below Other graph generating functions Other graph generating functions are scattered through out the remaining chapters e Condensed graph and component graph of connected components See subsections 5 3 4 page 58 and 5 3 5 page 58 e Biblock graph of a bibloc
71. 3 5 Examples Example 13 1 For this example see rbt01 c and rbt01 cmd in directory GHStests Using ntreeinsert a binary search tree is constructed from the list of keys in file bookrnd klist in directory GHSgraphs After that the program tries to insert value HAT again and a warning occurs Then testtree is called to check wether the tree is a correct binary search tree which it is Afterwards testtree is called again to check wether we obtained a correct red black tree which we did not The tree is printed using printorder and printrbtree The program code is shown in table 13 1 the results are shown in tables 13 2 and 13 3 Example 13 2 For this example see rbt02 c and rbc02 cmd in directory GHStests Program rbt02 c is almost the same as rbtO1 c It uses rbtreeinsert instead of ntreeinsert The results are shown in tables 13 4 and 13 5 Table 13 5 shows clearly the better balancing of the tree as compared to table 13 3 Example 13 3 See rbt07 c and rbt07 cmd in directory GHStests Program rbt07 c is very similar to program rbt01 c and is partially shown in table 13 6 After constructing a red black tree from a file of key values this tree is completely removed by deleting all its records one by one The file used is GHSwords klist in directory GHSgraphs It consists of 5757 English 5 letter words and was extracted from Knuth s words dat see Knut1993 Table 13 7 shows the reults Example 13 4 See rbt09 c and r
72. 56 grstruct 102 GSET 31 gset2vtset 32 34 gsetdiff 38 gsetintersect 37 gsetunion 37 GSTDD 55 56 GVTSTD 55 H head 12 highcomponents 103 higher a decomposition 185 higher decomposition 101 hinge point 65 I improper weak component 53 INC 13 incidence structure 11 13 14 117 INCSQR 67 102 insertline2path 88 insertpath2path 89 internal data structures 13 internal tree 64 66 102 intersection of two sets 37 isimplifypath 91 IT 67 102 K key class 37 38 119 L level number 54 limiting edge 83 84 85 limiting vertex 83 84 85 line set 31 33 linecomponent 101 lineconnected 101 linereachable 101 list of arcs 12 list of edges 12 list of vertices 12 loop 12 53 M memory 2 205 memorysize 16 Menger 95 98 Menger line 95 Menger path 95 Menger separating set 95 Menger structure 184 Menger vertex 95 mengerstr 96 mengerstrvt 96 mgprstd 96 minimal Menger separating set 96 mnewqusta 139 145 multiple 12 53 N naive deletion 117 naive insertion 117 name of a building block 102 name of a component 56 67 68 name of a graph 12 name of a vertex 12 name of an arc 12 name of an edge 12 newphdr 88 normal print option 14 ntreedelete 117 120 ntreeinsert 117 120 number of a component 56 67 O open path 53 ordering 54 55 P paint2cpart 85 paint2part 84 partial ordering 54 partition 83 183 path 53 87 183 pathnam
73. BCH All vertices which are border points check points and hinge points Error Exits Graph pointer Null Biblock decomposition does not exist Wrong print option Remarks A list entry like cO TDG 7 DG 7 0DG 0 IDG O Ugraphi WCOMP1 Border Point Check Point Hinge Point NO PERIPHERAL TREE EDGES 1 Ugraphi WCOMP1 PTO _c0 e0 NO_BIBLOCK_EDGES 2 Ugraphi WCOMP1 SUBO BLB1 0 1 0 3 NO_BIBLOCK_EDGES 2 Ugraphi WCOMP1 SUBO BLB2 12 _ 4 NO_INTERNAL_TREE_EDGES 2 Ugraphi WCOMP1 ITO 0 0 cO f0 is to be read as follows Vertex cO has total degree 7 Tedges 0 outgoing arcs 0 incoming arcs The vertex belongs to weak component Ugraph1 WCOMP1 It is incident with peripheral tree edge _c0 e0 It is also incident with 4 edges which belong to biblocks Edges _co c1 and _co c3 are from biblock Ugraphi WCOMP1 SUBO BLB1 and edges _cO a12 and _c0 a4 are from biblock Ugraphi WCOMP1 SUBO BLB2 Finally cO is incident with 2 internal tree edges namely _c0 d0 and _co f0 Error Exits Graph pointer Null Biblock decomposition does not exist There is no cyclic weak componenent with name wkcomp File filename cannot be opened Examples Example 6 1 page 70 6 3 4 blbgraph Program Author G nther Stiege Universit t Oldenburg Syntax GRAPH blbgraph GRAPH graph char filename 70 CHAPTER 6 THE BIBLOCK DECOMPOSITION Description The biblock graph corresponding to graph is constructed in external GHS
74. COMPO SUB1 No_BIBLOCKS 1 3V 1E 14 2E OA 3V 1E 14 2V 1E OA 13V 6E 12 5CP 1HP 3V 1E 2A 2AP 1BP 1CP OHP 1V OE 1A 1AP OBP 1CP OHP BIBLOCK wcompgraph12 WCOMPO SUB1 BLBO 1V OE 1A 1AP OBP 1CP SUBCOMPONENT wcompgraphi2 WCOMPO SUB2 No BIBLOCKS 2 6V 1E 7A 4AP 2BP 2CP 1HP BIBLOCK wcompgraph12 WCOMPO SUB2 BLBO 3V OE 3A 3AP 2BP 1CP BIBLOCK wcompgraphi2 WCOMPO SUB2 BLB1 4V 1E 4A 2AP 1BP 1CP SUBCOMPONENT wcompgraphi2 WCOMPO SUB3 No_BIBLOCKS 1 OA 1AP OBP 1CP OHP BIBLOCK wcompgraph12 WCOMPO SUB3 BLBO 1V 1E OA 1AP OBP 1CP No INTERNAL TREES 2 INTERNAL TREE wcompgraphi2 WCOMPO ITO INTERNAL TREE wcompgraph12 WCOMPO IT1 END REDUCED STRUCTURE 1A 4AP 3CP OHP 2V OE 1A 2AP OBP 2CP OHP Table 6 7 Results of Program acomp02 c Part II 77 78 CHAPTER 6 THE BIBLOCK DECOMPOSITION BEGIN BIBLOCK DECOMPOSITION REDUCED STRUCTURE GRAPH wcompgraphi2 3 TYPE GG No VERTICES 14 No_EDGES 8 No_ARCS 9 No_ISOLATED_VERTICES 0 No_A ACYCLIC_WEAK_COMPONENTS 0 OV OE OA No_A CYCLIC_WEAK_COMPONENTS 1 14V 8E 9A A CYCLIC WEAK COMPONENT wcompgraphi2 3 WCOMPO 14V 8E 9A 5AP 2BP 2CP 1HP No PERIPHERAL TREES 2 PERIPHERAL TREE wcompgraphi2 3 WCOMPO PTO 3V 2E OA PERIPHERAL TREE wcompgraphi2 3 WCOMPO PT1 2V 1E OA STOPFREE KERNEL wcompgraphi2 3 WCOMPO STP 11V
75. DPART record and complementary records Error Exits Graph pointer NULL Graph not of type UGSLF Vertex list and edge list both empty Remarks None Examples 8 3 2 cppartition 8 3 3 paint2part Program Author G nther Stiege Universit t Oldenburg 8 4 EXAMPLES 85 Syntax EDPART paint2part GRAPH graph int pclrno Description Assumes a function int paintval EDGE ed yielding for every edge of the graph a valid color 0 lt perl lt pclrno or the color 1 meaning invisible Builds the strict edge partition generated from a list of limiting vertices vtlist and a list of limiting edges edlist Two edges belong to the same class if both lie on a path with no internal vertex from vtlist and no edge from edlist The path must start in a vertex from vtlist or in an ednpoint of an edge from edlist Creates an EDPART record and complementary records Error Exits Graph pointer NULL Graph not of type UGSLF Vertex list and edge list both empty Remarks None Examples 8 3 4 paint2cpart 8 3 5 add2edpart 8 3 6 add2class 8 3 7 releaseedpartlist 8 3 8 generatefromclass 8 3 9 prpartstr 8 3 10 prpartvted 8 4 Examples Example 8 1 To be completed 86 CHAPTER 8 EDGE AND VERTEX PARTITIONS NOT YET RELEASED Chapter 9 Paths not yet released 9 1 Problem Description Paths have been introduced in chapter 5 page 53 In the present chapter paths are GHS objects in their own right They are represented by
76. E _d2 g 2V 1E VERTICES d2 g EDGES _d2 g BORDER_POINT d2 PERIPHERAL TREE cO eO VERTICES cO 0 el e2 e3 EDGES 0 0 0 1 _ 1 2 _el e3 BORDER_POINT cO Table 11 3 Results of Program 5 1 Part Ila 108 CHAPTER 11 HIGHER DECOMPOSITIONS NOT YET RELEASED STOPFREE KERNEL _a0 a1 29V 35E No_SUBCOMPONENTS 3 SUBCOMPONENT fO f1 3V 1AP OBP 1CP OHP No_BIBLOCKS 1 BIBLOCK _f0 f1 3V 3E 1AP OBP 1CP OHP VERTICES fo f1 f2 EDGES fO f1 _f1 f2 f2 f0 ATTACHMENT POINTS fo CHECK_POINTS fo SUBCOMPONENT _dOx d1 3V 3E 2AP 1BP 1CP OHP No_BIBLOCKS 1 BIBLOCK 40 41 3V 3E 2AP 1BP 1CP OHP VERTICES do di d2 EDGES _d0 d1 _di d2 _ 2 ATTACHMENT_POINTS do d2 BORDER_POINTS d2 CHECK_POINTS do Table 11 4 Results of Program 5 1 Part IIb 11 4 EXAMPLES 109 SUBCOMPONENT cO ci 23V 27E 2AP 1BP 1CP 2HP No_BIBLOCKS 3 BIBLOCK _bOxb1 3V 3E 1AP OBP OCP 1HP VERTICES bo b1 b2 EDGES _b0 b1 _b1 b2 _b2 b0 ATTACHMENT_POINTS bo HINGE_POINTS bo BIBLOCK _c0 c1 AV 4E 1AP 1BP 1CP 1HP VERTICES cO c1 c2 c3 EDGES 0 1 _ 1 2 _c2 c3 3 0 POINTS 0 BORDER_POINTS cO POINTS cO HINGE POINTS cO Table 11 5 Results of Program 5 1 Part 110 CHAPTER 11 HIGHER DECOMPOSITIONS NOT YET RELEASED BIBLOCK _a0 a1 18V 2
77. ET pedset char name Description Adds a new line given by its name to an line set Creates new line set for first line Error Exits Edge arc with given name not in graph duplicate name to be included Remarks None Examples See example gen02 c in GHS directory GHStests The example is analogous to example 4 1 3 4 6 addedset2edset Program Author G nther Stiege Universit t Oldenburg Syntax void addedset2edset GRAPH graph EDSET pedset REDGE red Description Joins two line sets of the same graph Error Exits When calling add2edset Edge arc with given name not in graph Remarks None Examples See example gen02 c in GHS directory GHStests The example is analogous to example 4 1 3 5 Functions for General Sets 3 5 1 readgset Program Author G nther Stiege Universit t Oldenburg Syntax GSET readgset char filename 36 CHAPTER 3 SETS Description Reads a sequence of names from file filename to build a general set If filename equals NULL the names are read from standard input The end is indicated by EOF or END Returns a pointer to the set NULL if the set is empty Error Exits Set empty Remarks None Examples Example 3 2 page 38 3 5 2 savegset Program Author G nther Stiege Universit t Oldenburg Syntax void savegset GSET vtset char filename Description Writes the elements of a general set to file filename If filename equals NULL the output is written to standard output The
78. EY 119 stack 139 start point of an arc 12 STDGD 102 stopfree kernel 64 66 102 stopfree path 63 64 STR 56 68 STRA 56 68 STRCS 56 strong component 53 55 172 strongly connected component 53 STRR 56 68 struct 13 SUB 67 102 subcomponent 64 66 102 subgraph 43 system error 2 system of Menger paths 95 T tail 12 testtree 118 124 top 139 142 tree 54 65 type of graph see graph type U UG 12 UGS 12 UGSLF 12 83 undirected 53 undirected edge 12 undirected graph 12 union of two sets 37 user error 2 utility 164 UW paths 96 INDEX VERTEX 13 vertex 12 vertex name 12 vertex of no return 54 vertex set 31 vertex with root property 55 VPA 57 69 VPB 69 VPBC 69 VPBCH 69 VPBH 69 VPC 69 69 VPH 69 VPV 57 69 vtptgstd 56 VTSET 31 W WCOMP 55 weak attachment point 54 weak component 53 55 172 weakly connected component 53 words dat 4 207 208 INDEX
79. Error Exits None Remarks None Examples See example set03 c in GHS directory GHStests 3 6 Examples Example 3 1 Tables 3 1 and 3 2 show a program which builds a graph from an external descrip tion readgraphlist It then builds a general set joining the graph s vertex list with an empty set gsetunion From the general set the corrsponding vertex set is derived gset2vtset and then the general set is deleted releasegsetlist In the next step using function gsetunion again a new general set is created It contains all edges and all arcs of the graph From it the correponding line set is derived gset2edset Finally all sets are released releaseedsetlist releasegsetlist releasevtsetlist The amount of memory allocated is printed at different points of the program run Example 3 2 Table 3 4 shows in the upper part the command procedure set02 cmd This procedure compiles and starts program set02a c which is shown in the lower part of table 3 4 The program reads a graph and writes the list of vertex names as a general set to standard output savegset which by the command procedure is stored in the temporary file XYYX The command procedure then compiles and starts program set02b c Table 3 5 shows the program in the upper part It reads the graph again and then reads the general set from file XYYX readsgset From the general set the corresponding set of vertices gset2vtset is constructed which in turn is used to generat
80. G and b UG UGS When type conversion goes from an U type to a D type or vice versa the source type is considered GG and the above rules apply Warning Do not use edge arc names ending in _e2a With type conversions such names may cause a system error Duplicate key cannot be inserted Examples See example gen05 c in GHS directory GHStests It uses Graph1 of figure 2 1 page 18 and performs the following three conversions a GG UG b UG DG c DG UGSLF The results are printed with option normal 4 3 4 degreedelete Program Author G nther Stiege Universit t Oldenburg void degreedelete GRAPH oldgraph GRAPH delgraph char Syntax delname GRAPH remgraph char remname VTSET att int dg 4 3 FUNCTIONS 47 Description Recursively collects all vertices of total degree dg or less together with the edges arcs they are incident with The subgraphs generated by the deleted edges arcs and by the remaining edges are constructed and assigned to delgraph with name delname and remgraph with name remname respectively The original graph is not modified The list of vertices common to both subgraphs is constructed and assigned as a name list to att For an empty subgraph or an empty vertex list a NULL pointer is returned Error Exits graph delgraph remgraph or att equal NULL graphs have not pairwise distinct names zero or negative degree specified Remarks Isolated vertices of the origi
81. GHS programs other graph handling systems or other external sources Step 2 Table 1 2 shows a program in C called int01 c see also directory GHStests which solves the problem of our example In it the variable graph of type GRAPH is declared Then the function readgraphlist is called It reads the file representation of the graph from standard input builds the internal data structure of the graph and returns a pointer to the new graph record If the pointer is NULL an error has occurred The function savegraphlist is called next It writes the graph to standard output in the external graph format file format so that it can be read by readgraphlist After printing an intermediate heading line the function printbfs is called which prints the vertices of the graph in breadth first sequence starting at vertex D It also prints those edges which are used in the search and it prints the distance to the starting vertex The results of the program run are shown in table 1 3 A detailed description of the functions readgraphlist savegraphlist and printbfs is given in chapter 2 Basic Graph Functions Step 3 The program 01 is compiled with the command 6 CHAPTER 1 INTRODUCTION Program main Read a graph print it and print it in bfs sequence kokokekokeokokekekokelekelooke
82. GRAPHEN UND NETZWERKE UNIVERSIT T OLDENBURG DEPARTMENT F R INFORMATIK Fakult t 2 Informatik Wirtschafts und Rechtswissenschaften G nther Stiege GHS Graph Handling System User Manual GHScore Version 5 0 Oldenburg December 2009 Author s address Prof Dr G nther Stiege Universitat Oldenburg Department f r Informatik D 26111 Oldenburg Germany www bvs informatik uni oldenburg de Bibliographische Angaben Stiege G nther GHS Graph Handling System User Manual Version 5 0 Stiege G nther Oldenburg Universitat Oldenburg 2009 G nther Stiege Oldenburg 2009 Preface During the past years the Graph Handling System GHS has evolved from a program for finding the biblock decomposition of undirected graphs to a rather large and complex system for handling general graphs Its kernel is a library of C routines for a variety of graph functions termed GHScore In addition to GHScore a graphical user interface GHSgui which uses a library of java functions has been implemented by Sergej Alekseev and some external contributions have been added to GHS This manual describes GHScore version 4 0 In the manual the C routines are grouped together in chapters according to the kind of function they perform The chapters are subdivided in a uniform manner into four sections The first section gives some graph theoretic background of the functions It is followed by a short section on formats and data structur
83. HSwords and decomposes in weak and strong components Afterwords a list of all five classes of weak components is printed showing the charname and the hierarchical name for each component Since GHSwords is an undirected graph all but two of the classes are empty as they ought to be 128 CHAPTER 13 RED BLACK TREES K k k ak ak ak 3k 3k 3k aK ak ak 3K 3K 3K aK ak a 3K 3K 3K K aK aK 2K 3K 3K K aK aK 2K 3K 3K K aK ak 2K 3K 3K K aK aK 2K 3K 3K 3K aK K 3K 3K 3K aK K 2K 3K 3K 3K K K K 2K 3K 3K K K K 2K 2K 2K rbt01 Program for constructing binary search trees J gt K ok k sk sk sk ok ok ok ak ak ak ok ok ok 9k 3K aK ak ok ok 9k KT include lt stdio h gt include lt GHSstructure h gt int main int argc char argv RB root VERTEX vt FILE fdin int n char inbuffer 1012 BODLEAN b1 fdin fopen argv 1 r if fdin NULL printf rbt01 Input file s cannot be opened Wn argv 1 exit 0 root NULL Construction of a binary search tree using a list of key values n fscanf fdin As inbuffer while n EOF vt mnewvt newvt vt gt vtname mnewname inbuffer newname bl ntreeinsert amp root RB vt SND if 111 printf rbtO1 s exists already n vt gt vtname Continue without the multiple value n fscanf fdin As inbuffer Trying to insert a key value twice vt mnewvt newvti vt gt vtname mnewname HAT newnamei
84. Key classes are used for different purposes So care has to be taken when using them with the functions of this chapter This is best explained by an example In the definition of the enumeration type SORTKEY page 189 we find among others the following SND rbtcomp VERTEX compared to rbtreefind VERTEX by vtname rbtreeinsert getname SNN rbtcomp VERTEX gt vtname compared to char rbtreefind SED1 getname Uses EDGE record Provides edge name and names of end vertices 3 lines print format Key classes SND and SNN may be used to search rbtreefind within red black trees since they are supported by the central comparison routine rbtcomp which is of internal GHS use only SNN uses as search value a mere character string whereas with SND the search value is the name of a vertex whose record is given Therefore insertion rbtreeinsert is allowed with SND but is not with SNN For the same reason getname is allowed with SND but not with SNN On the other hand if a record is to be searched for in a red black tree of vertex records and the search criterion is the bare vertex name in contrast to a given vertex record key class SNN has to be used Key class SED1 is not supported by rbtcomp and must therefore not be used with red black trees It may be used with getname when an EDGE record is given to obtain the name of the edge and the names of its end points see example 13 10 page
85. L DER color BLACK Parent LAGE BESUCH color BLACK Parent DER Leaf Leaf HAT color BLACK Parent Leaf Leaf QUARK color RED Parent LAGE NOCH color BLACK Parent QUARK LUST color BLACK Parent NOCH Leaf NEIN color RED Parent LUST Leaf Leaf PFAU BLACK Parent NOCH Leaf Leaf TANNE color BLACK Parent QUARK RUHEN color BLACK Parent TANNE Leaf SEHEN color RED Parent Leaf Leaf ZAHN color BLACK Parent TANNE Leaf Leaf left left left right right left right right left left left right left right right left right right left left right left right right left right k k k k k k k k k k k k k k k k k k k k k k k k k k k S Ol Ol S WNP 000101 5450 N 00 N Table 13 8 Results of Program rbt08 c 136 CHAPTER 13 RED BLACK TREES string string string string string string string string string string string string string string string string string string string string string string a a a a a a a a a a a a a a a a a a a a a a Table 13 9 The vertices of Graph1 printed with printorder 13 5 EXAMPLES DACA GAA kkk kkk kkk kkk rbt10 Program showing an example for getname DAC GGG OAR kk kkk include lt stdio h gt include lt GHSstructure h gt int main int argc char argv GRAPH graph VERTEX
86. LEAN BOOLEAN BOOLEAN BOOLEAN BOOLEAN BOOLEAN BOOLEAN grvtno grvtlist gruedno gredlist grdedno grdedlist grgcomp grastd grsga grsgal grvsa grvsal grsgf grsgfl grvsf number of vertices list of vertices number of undirected edges list of edges number of directed edges arcs list of directed edges arcs pointer to weak strong decomposition TRUE Biblock decomposition exists The biblock decomposition if it exists starts with the weak com ponents of the weak and strong decomposition TRUE The higher decomposition into maximal a components exists This decomposition if it exists starts with the biblocks of the biblock decomposition TRUE The higher decomposition into maximal a linecomponents exists This decomposition if it exists starts with the subcomponents of the biblock decomposition TRUE The higher decomposition into maximal a connected vertex sets exists This decomposition if it exists starts with the biblocks of biblock decomposition TRUE The higher decomposition into maximal a lineconnected vertex sets exists This decomposition if it exists starts with the subcomponents of the biblock d
87. LL return 0 Table 6 1 Program 01 readgraphlist Then function astd is called to find and construct the biblock decomposition of the graph Next function gprstd is called with print option STRCS for condensed statistics The 3Here we specify subgraphs by their vertices 6 4 EXAMPLES 71 reduced listing of the biblock decomposition is then printed with function aprstd print option STRR Finally with function aprstdvt a list of attachment points option VPA is printed The results of these steps are shown in the following tables Table 6 2 shows the condensed results of the decomposition into weak and strong components which for undirected graphs are identical and the biblock decomposition Table 6 3 contains a listing of the biblock decomposition of Ugraphi printed with option STRR Table 6 4 shows a list of those vertices of Ugraph1 which are attachment points BEGIN CONDENSED STRUCTURE OF GENERAL DECOMPOSITION GRAPH Ugraphi TYPE UGSLF No_VERTICES No_EDGES No_ARCS No_ISOLATED_VERTICES No_WEAK_COMPONENTS_TYPE_1 No_WEAK_COMPONENTS_TYPE_2 No_WEAK_COMPONENTS_TYPE_3 No_WEAK_COMPONENTS_TYPE_4 No_WEAK_COMPONENTS_TYPE_5 No_WEAK_ATTACHMENT_POINTS No STRONG COMPONENTS f ACYCLIC No STRONG COMPONENTS f CYCLIC No_STOPFREE_KERNELS No_PERIPHERAL_TREES No_SUBCOMPONENTS No_BIBLOCKS No_INTERNAL_TREES No_HINGE_POINTS No_CHECK_POINTS 3 ND CONDENSED STRUCTURE OF GENERAL DECOMPOSITION
88. NULL printf rbt07 c Final tree is empty n else printf rbt07 c Final tree is not empty n Table 13 6 Program rbt07 c 134 rbt07 rbt07 rbt07 rbt07 rbt07 rbt07 rbt07 oo 0000009 C C C C C C CHAPTER 13 RED BLACK TREES Binary search tree is correct Correct Correct Correct Correct Correct Correct Correct Correct Correct Correct Correct Correct Correct Correct Correct Correct tree tree tree tree tree tree after deleting wasps after deleting infix after deleting toyon after deleting jihad after deleting teeth after deleting pores deleting bract deleting alert deleting cover deleting maned deleting peons deleting shire deleting vodka deleting zowie deleting teams deleting sacks Final tree is empty Table 13 7 Results of Program rbt07 c 13 5 EXAMPLES 135 stiege thinkpad gt rbt08 cmd rbt08 c The constructed red black tree is correct rbt08 c Dialog begins Input to terminate program Key to be deleted ROT rbt08 c Correct rb tree after deleting ROT Key to be deleted ANTON rbt08 c Correct rb tree after deleting ANTON Key to be deleted KNABE rbt08 c Correct rb tree after deleting KNABE Key to be deleted ZANK rbt08 c Correct rb tree after deleting ZANK Key to be deleted HUT rbt08 c Correct rb tree after deleting HUT Key to be deleted LAGE color BLACK Parent NUL
89. ONENTS PRINT OPTION VPA Undirected loops are counted twice GRAPH wcomp TYPE GG VERTICES 5 No EDGES 2 No_ARCS 2 VERTICES B04 DG 1 0DG O IDG 1 LV 2 wcomp WCOMPO wcomp WCOMPO SCOMP1 weak attachment point No OUTGOING EXTERNAL TREE ARCS 0 No INCOMING EXTERNAL TREE ARCS 1 _ 4 No_EDGES 1 _uB04B05 No OUTGOING STRONG COMPONENT ARCS 0 No INCOMING STRONG COMPONENT ARCS 0 B03 DG 1 0DG 1 IDG 1 LV 1 wcomp WCOMPO wcomp WCOMPO SCOMPO weak attachment point No OUTGOING EXTERNAL TREE ARCS 1 dBO3B04 No INCOMING EXTERNAL TREE ARCS 1 _dB02B03 No_EDGES 1 _uB01B03 No_OUTGOING_STRONG_COMPONENT_ARCS 0 No_INCOMING_STRONG_COMPONENT_ARCS 0 Table 5 3 List of attachment points of the third weak component of graph wcompgraph Chapter 6 The Biblock Decomposition 6 1 Problem Description Mutual a reachablity is used to define weak components in a general graph In the same way mutual f reachability is used to define strong components Higher components are defined by mutual k a reachability respectively mutual k f reachability Vertex v is k a reachable k f reachable from vertex v if there are at least k internally disjoint a paths f paths from u to v ie a paths which have only the endpoints in common Line disjoint paths i e the paths have no common lines lead to higher linecomponents For k 2 and a paths the decomposition is called biblock decompos
90. OT YET RELEASED PATH lt pathname gt Each path must have a name which is a string not starting with Or GRAPH lt graphname gt Each path must belong to a graph The name of the graph is recorded here The name of the graph is a string not starting with 7 DIRECTION lt dirvalue gt for for forward for backward POSITION lt posvalue gt 5 for start E for end PATHLINES lt plinelist gt List of path line entries May be empty A path line entry consists of the name of the line followed by the name of the first incidence vertex in path direction The name of a line is a string which must start with The name of a vertex is a string which must not start with or 7 Table 9 1 External File Format of GHS Graphs 9 3 Functions 9 3 1 newphdr Program Author G nther Stiege Universit t Oldenburg Syntax PHDR newphdr GRAPH graph char direction char name Description Creates a new path header for a path in graph Parameter direction specifies whether the path is an a paths f paths or b path A a a path arcs may be traversed in any direction F or f f path arcs must be traversed in forward direction only B or b b path arcs must be traversed in backward direction only In all cases edges may be traversed in any direction When lines are inserted into a path by GHS consistency with parameter direction is checked name is a user specifi
91. R 10 MENGER STRUCTURES NOT YET RELEASED 09292959 HY OO amp 058 g N S Figure 10 2 Menger line theorem graph Menglgraph2 Chapter 11 Higher Decompositions not yet released 11 1 Problem Description Loosely speaking a decomposition of a general graph is a family of subgraph whose union is the given graph and which have as few as possible vertices and lines in common We call a decomposition hierarchical if some of the decomposing subgraphs are decomposed themselves and this procedure is reiterated Graph decompositions are in general based on reachability properties Extending the definition of page 53 we say that vertex v is k a reachable from vertex u if there are at least k internally disjoint a paths from u to v We say that v is k a linereachable from u if there are at least k line disjoint a paths from u to v In an analogous manner k f reachability is defined A subgraph is k a connected k f connected if every pair of different vertices is mutually k a reachable k f reachable im the subgraph Maximal k a connected k f connected subgraphs are uniquely determined though not necessarily disjoint They are called k a components k f components of the graph In the same way lineconnectedness is defined Maximal k a lineconnected k f lineconnected subgraphs are uniquely determined and pairwise disjoint They are called k a linecomponents k f linecomponents Instead of subgraphs
92. R compared to PHDR by phname PHDR gt phname compared to char APPENDIX C GHS INTERNAL DATA STRUCTURES C 14 SORT KEYS FOR RED BLACK TREES 193 Not yet updated RSLND RSTAT RDMND RRVSTD RDRVSTD PPARTVT PRPARTVT PERPARTVT RSLED EEDSTD RREDSTD SSOINC rbtcomp rbtreefind rbtreeinsert rbtrcomp rbtreefind rbtcomp rbtreefind rbtreeinsert getname rbtcomp rbtreefind rbtreeinsert getname rbtcomp rbtreefind rbtreeinsert getname rbtcomp rbtreefind rbtreeinsert getname rbtrcomp rbtreefind rbtcomp rbtreefind rbtreeinsert getname rbtcomp rbtreefind rbtcomp rbtreefind rbtreeinsert rbtcomp rbtreefind rbtreeinsert getname rbtreecomp rbtcomp RVERTEX compared to RVERTEX by a distance to center in auxiliary field b vtname RVERTEX compared
93. RB u K11 K13 SEN insertline2path phdr2 line line gt edsec E printpathlist phdr2 detailed NULL phdr newphdr graph A mainpath insertpath2path phdr phdr1 insertpath2path phdr phdr2 printpathlist phdr detailed NULL return 0 Table 9 2 Program path01 c 94 CHAPTER 9 PATHS NOT YET RELEASED file pathO1 dat PATH subpathi GRAPH Graphi DIRECTION A POSITION E PATHLINES d KO0 K13 _u K11 K13 _d K11 K06 _ END results of program path01 BEGIN PATH LIST PATH subpathi PATH DIRECTION A any PATH LENGTH 4 _d K00 K13 1 11 13 _d K11 KO6 K11 _d K06 K00 06 END LIST detailed BEGIN PATH LIST PATH subpath2 PATH DIRECTION A any PATH LENGTH 3 _d K12 Ki1 K12 _d K12 K13 K12 K13 _u K11 K13 K13 11 END PATH LIST detailed BEGIN PATH LIST PATH mainpath PATH DIRECTION A any PATH LENGTH 4 _d K00 K13 u K11 K13 K13 _d K11 K06 11 _d K06 K00 KO6 END PATH LIST detailed Table 9 3 Input and output of program path01 Chapter 10 Menger Structures not yet released 10 1 Problem Description The name of Menger theorems is given to several similar graph theoretical results Let u and v be distinct and non adjacent vertices of a general graph Then 1 The maximum number of internally vertex disjoint a paths from u to v equals the mini mum number of vertices a separating u and v
94. S INTERNAL DATA STRUCTURES C 2 Literal Constants and Type Definitions Literal Constants and Type Definitions include lt stdio h gt include lt stdlib h gt include lt string h gt include lt math h gt ifndef _GHSSTRUCTURE_H_ define _GHSSTRUCTURE_H_ 1 Utilities 1 1 General Services define TRUE 1 define FALSE O typedef int BOOLEAN typedef struct relenstr RELEM Generic substructure 29 Red Black Trees define BLACK 1 define RED 0 typedef int COLOR typedef struct rbtree RB generic RB element 1 3 Stacks and Queues typedef struct ghsqusta QUSTA queue stack of arbitrary elements typedef struct ghsqs QS representative records in queues and stacks 2 Basic Graph Functions define 7 number of graph types typedef struct grphst GRAPH graphs and subgraphs typedef struct vtstr VERTEX vertices typedef struct rvtstr RVERTEX references to a vertex typedef struct edstr EDGE lines line or arc in the sequel edge is sometimes used for line and refers to both edges and arcs typedef struct redstr REDGE references to an line typedef struct incstr INC incidences 3 Sets typedef struct vtsetstr VTSET Vertex set typedef struct edsetstr EDSET Vertex set typedef struct gsetstr GSET General set typedef struct setelem SETELEM Element of general set
95. S returns an error code to the calling program but does not free the memory used up this point Note that the amount of memory allocated may depend on the computer architecture and the software systems used The examples of this manual correspond to an PC based Linux system and a GNU gcc compiler The amount of memory allocated depends also on the actual version of GHS since the data structures in GHS may change Therefore in an actual program run the numerical values of the examples cited above may differ from those given in this manual 1 2 HOW TO USE THE SYSTEM 1 2 How to Use the System The complete GHS system can freely be used The distribution policy of GHS is stated in table 1 1 page 3 dk HHH Gb dk HH HH HH dk HHH OF X OK Graph Handling System GHS Copyright c 2000 2003 Guenther Stiege and Sergej Alekseev Universitaet Oldenburg Germany All rights reserved Redistribution and use in source and binary forms with or without modification are permitted provided that 1 source code distributions retain the above copyright notice and this paragraph in its entirety 2 distributions including binary code include the above copyright notice and this paragraph in its entirety in the documentation or other materials provided with the distribution 3 all advertising materials mentioning featur
96. STRONG COMPONENTS 2 No f ACYCLIC STRONG COMPONENTS 2 5V 3E OA STRONG COMPONENT wcompgraph WCOMP3 SCOMPO uBO6BO8 3V 2E OA WAP STRONG COMPONENT wcompgraph WCOMP3 SCOMP1 uBO9B10 2V 1E OA WAP EXTERNAL wcompgraph WCOMP3 SCOMP1 dBO8BO9 2V OE 1A No A CYCLIC WEAK COMPONENTS WITHOUT STRONG COMPONENTS 2 8V OE 8A WEAK COMPONENT wcompgraph WCOMP4 lt dCO1CO3 AV OE 4A aper 2 MAXLV 2 WEAK COMPONENT wcompgraph WCOMP5 lt dCO5CO6 AV OE 4A aper 2 MAXLV 2 rooted root 05 vertex No A CYCLIC WEAK COMPONENTS WITH STRONG COMPONENTS 2 12V 6E 9A ALL STRONG COMPONENTS F ACYCLIC WEAK COMPONENT wcompgraph WCOMP6 dDO2DO3 5V 2E aper 2 MAXLV 2 rooted root D02 vertex No STRONG COMPONENTS 2 No f ACYCLIC STRONG COMPONENTS 2 4V 2E OA STRONG COMPONENT wcompgraph WCOMP6 SCOMPO lt uDO1DO3 2V 1E OA WAP STRONG COMPONENT wcompgraph WCOMP6 SCOMP1 lt uDO4DO5 2V 1E OA EXTERNAL_DAG wcompgraph WCOMP6 EXD lt dDO2DO3 AV OE 3WAP WEAK COMPONENT wcompgraph WCOMP7 dDO6DO7 7V 4E 6A aper 1 MAXLV 2 rooted root wcompgraph WCOMP7 SCOMPO lt _uDO6D08 gt strong component No STRONG COMPONENTS 3 No f ACYCLIC STRONG COMPONENTS 3 7V 4E OA STRONG COMPONENT wcompgraph WCOMP7 SCOMPO lt uDO6DO8 2V 1E OA STRONG COMPONENT wcompgraph WCOMP7 SCOMP1 lt uDO7DO9 2V 1E OA
97. TANNE Leaf ZANK RED Parent ZAHN Leaf Leaf k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k k 010145 Q S Q N 0100015 GQ S 50 N F 4400 GQ GQ N Hr Table 13 5 Results of Program rbt02 c Part II 13 5 EXAMPLES 133 K 3 2K 2K 3k ak ak ak 3k 3k 3K aK ak ak 3K 3K 3K aK aK a 3K 3K 3K 3K aK a 2K 3K 3K K aK a 2K 3K 3K K aK aK 2K 3K 3K 3K aK aK 2K 3K 3K 3K aK K 3K 3K 3K aK K K 3K 3K 3K K K K FK 3K 3K K K K 2K 2K 2K rbt07 Program showing deletions in binary search trees kokokekokokokekkokelekelookekekelelelelejoekekelelelelejolekekelelelelejokelekelelelelejeleelelelelejeleekelelelelejeleekelelelelelek include lt stdio h gt include lt GHSstructure h gt int main int argc char argv RB root rbroot VERTEX vt vtl FILE fdin int n char inbuffer 1012 BOOLEAN b1 Deleting records fdin fopen argv 1 r repositioning file n fscanf fdin As inbuffer while n EOF bl ntreedelete amp root RB inbuffer SNN if Ibl printf rbt07 Record s not in tree n inbuffer exit 0 bl testtree stdout root SND S Testing for correctness if bl printf rbt07 c Correct tree after deleting s n inbuffer else printf Incorrect search tree after deleting record s n inbuffer exit 0 n fscanf fdin As inbuffer if root
98. a graph list Prints the list in formats short and detailed include lt stdio h gt include lt GHSstructure h gt int main t GRAPH graphlist graphlist NULL graphlist readgraph NULL if graphlist NULL printf Incorrect graph input n exit 0 printgrlist graphlist short NULL printgrlist graphlist detailed NULL return 0 Table 2 3 Program bas01 c 2 4 EXAMPLES Graph0 Graphi Graphla Graphib 21 Results of calling printgrlist with option short Type UGSLF Vertices 6 Edges 7 Arcs Type GG Vertices 22 Edges 8 Arcs Type UG Vertices 22 Edges 37 Arcs Type DG Vertices 22 Edges Arcs Results of calling printgrlist with option detailed only Graphl Statistics of gr Vertices Edges Arcs Degree summary Mean total aph Graphi Type GG 22 8 Mult edges 4 Loops u 2 Mult loops u 29 Mult arcs 4 Loops d 4 Mult loops d undirected loops are counted twice degree 3 36 Standard deviation of total degree 1 55 Vertices Vertices Vertices Vertices Vertices Vertices Vertices Vertex list K10 of total degree 1 of total degree of total degree of total degree of total degree of total degree of total degree degree indegree outdegree Outgoing arcs _d K10 K01 K
99. ained in file bookrnd klist in directory GHSgraphs Then the key values KNABE BESUCH ANTON ZANK HAT HARZ are processed with rbtreenext and rbtreeprevious and give the following output 13 5 EXAMPLES 127 vertex preceeding vertex KNABE HUT vertex following vertex KNABE LAGE vertex preceeding vertex BESUCH ANTON vertex following vertex BESUCH DER vertex preceeding vertex ANTON NULL vertex following vertex ANTON BESUCH vertex preceeding vertex ZANK ZAHN vertex following vertex ZANK NULL vertex preceeding vertex HAT DER vertex following vertex HAT HUT rbt05 c HARZ is not element of the tree Example 13 8 See program rbt04 c and command rbt04 cmd in directory GHStests The maximum vertex name und the minimum vertex name of graph GHSwords are searched for and printed The output is Max zowie Min aargh Example 13 9 See Graphl of example 2 1 figure 2 1 page 18 If the graph is read with readgraphlist and then function printorder is called printorder fd RB graph gt grvtlist SND This is a test string the list of table 13 9 is printed For the complete program see rbt03 c in directory GHStests Example 13 10 Consider Graph0 figure 1 2 on page 5 rbt10 c reads and constructs Grapho It then finds edge _i and finally prints its name together with the names of it end points Table 13 10 Example 13 11 Example rbtcii cmd and rbtcii c in GHStest constructs graph G
100. aph with the following exception for the subgraph generated from the external dag of a weak component EXD GG gt DG DGS gt DGSLF Error Exits NULL returned if wrong parameter or decomposition element does not exist Remarks The charnames of the elements of a decomposition are displayed by function gprstd page 56 and by function aprstd page 68 The charname of a decomposition element given its address can also be obtained directly with function getcharname page 125 Examples See example 5 2 page 58 4 4 Examples Example 4 1 In this example we use Graphl figure 2 1 again Table 4 2 shows the program in the lower part Graphl is constructed using readgraphlist After that the vertex sets vtseti and vtset2 are filled using readvtset with the vertices shown in the upper part of table 4 2 For each vertex set its number of elements is printed and then the set itself using function savevtset Then vtset2 is joined to vtsei function addvtset2vtset and the single vertex KOO is added to vertexi function add2vtset Finally the subgraph of Graphl generated by vtseti is constructed function generatefromvt and written to standard output function printgrlist The results of the program run are shown in tables 4 3 and 4 4 44 EXAMPLES 49 K11 K06 END K15 14 K 3k k ak ak ak 3k 3k 3K ak ak ak 3K 3K 3K aK ak a 3K 3K 3K aK aK aK 3K 3K 3K K aK aK 2K 3K 3K K aK K 2K 3K 3K K aK aK K 3K 3K 3K K K 3K 3K 3K K
101. bt09 cmd in directory GHStests Program rbt09 c is the almost the same as program rbt07 c Insertion and deletion is done for a red bleck tree Example 13 5 See rbt08 c and rbt08 cmd in directory GHStests Program rbt08 c builds the red black tree shown in table 13 5 In the subsequent interactive phase records are deleted one by one Table 13 8 page 135 shows a run of the program where key ROT ANTON KNABE ZANK HUT are deleted in that order Example 13 6 See program rbt06 c and command rbt06 cmd in directory GHStests File GHSwords in directory GHSgraphs is used to construct the graph wordsgraph The list of ver tices wordsgraph gt grvtlist is organized as red black tree The key values aa aargh magma magmi flora flori zul are processed with rbtreefind and rbtreepfind and give the following output key value aa rbtreefind yields NULL rbtreepfind yields NULL key value aargh rbtreefind yields aargh rbtreepfind yields aargh key value magma rbtreefind yields magma rbtreepfind yields magma key value magmi rbtreefind yields NULL rbtreepfind yields magma key value flora rbtreefind yields flora rbtreepfind yields flora key value flori rbtreefind yields NULL rbtreepfind yields flora key value zul rbtreefind yields NULL rbtreepfind yields NULL Example 13 7 See program rbt05 c and command rbt05 cmd in directory GHStests The program builds a binary search tree from a list of key values cont
102. c name for the path If no name is provided GHS uses dummy Error Exits The function returns NULL if an error occurs Errors are Graph pointer NULL incorrect parameter value Remarks Additonal path properties like line simple open circuit and so on are neither recorded nor checked Examples 9 3 2 insertline2path Program Author G nther Stiege Universit t Oldenburg 9 3 FUNCTIONS 89 PTHA insertline2path PHDR phdr EDGE line VERTEX first tax Syntax char position Description Inserts the line given by line into the the path specified by phdr Vertex first is the first vertex of line in path direction The function checks whether the conditions of a correct path are fulfilled Parameter position controls where line is inserted start or S or s inserted as new first line of the path end or E or e inserted as last line of the path The PTHA record of the inserted line is returned NULL if an error occurred Error Exits Remarks Take care to not confound options start and end with path modes any forward and backward Examples 9 3 3 removelinefrompath Program Author G nther Stiege Universit t Oldenburg PTHA insertline2path PHDR phdr EDGE line VERTEX first tax Synta char position 9 3 4 insertpath2path Program Author G nther Stiege Universit t Oldenburg Syntax BOOLEAN insertpath2path PHDR phdr1 PHDR phdr2 Description Inserts the lines o
103. ccslist list of a cyclic weak components with all strong components f acyclic int wccsfno number of a cyclic weak components with at least one f cyclic strong C 7 DATA STRUCTURES FOR WEAK AND STRONG COMPONENTS WCOMP BOOLEAN Ts struct WCOMP WCOMP WCOMP COLOR void int int GSTDD int RVERTEX int REDGE int REDGE int RVERTEX int REDGE int RVERTEX int int SCOMP int SCOMP int component wccsflist list of a cyclic weak components with at least one f cyclic strong component gstdastd TRUE The biblock decomposition of the graph has been determined wcomp WCOMP weak component wcompleft wcompright wcomppar wcompcolor wcompauxiliary wcomptype type of weak component 1 not yet assigned 1 a acyclic no strong components 2 a acyclic strong components 3 a cyclic no strong components 4 a cyclic strong components all strong components f acyclic 5 a cyclic strong components at least one f cyclic strong component wcompnumber number of weak component wcompgstdd pointer to weak and strong decomposition wcompvtno number of vertices wcompvtlist list of vertices wcompedno number of edges wcompedlist list of edges wcompdedno number of arcs wcompdedlist list of arcs wcompexdvtno number of vertices of external dag wcompexdvtlist list of vertices of e
104. ces common to vtsource and vtsink are separating elements 2 lines joining directly a vertex of vtsource not in vtsink to a ver tex of vtsink not in vtsource are Menger paths see the problem description in section 10 1 page 95 and at the same time separating elements 3 All remaining Menger paths have length at least 2 and pass through one or more Menger vertices If parameter sep equals complete all Menger vertices of all these paths are determined together with its mini mal Menger separating sets see section 10 1 If parameter sep equals first only the first system of Menger sets in direction from vtsource to vtsink is determined b mode li 1 All vertices common to vtsource and vtsink are separating elements 2 Menger paths join a vertex in vtsource not in vtsink to a vertex in vtsink not in vtsource and pass through at least one Menger line If parameter sep equals complete for each path all its Menger lines together with their minimal Menger separating sets are determined see section 10 1 If parameter sep equals first only the first system of Menger sets in direction from vtsource to vtsink is determined 98 CHAPTER 10 MENGER STRUCTURES NOT YET RELEASED c mode evt 1 2 3 c mode el 1 2 Error Exits empty Remarks Examples All vertices common to vtsource and vtsink are separating elements The Menger paths found are vertex disjoint All Menger
105. ctions of chapter 3 For function generatefromcomp the data structures for weak and strong components chapter 5 and for the biblock decomposition chapter 6 are of concern too 4 3 Functions 4 3 1 generatefromvt Program Author G nther Stiege Universit t Oldenburg 4 3 FUNCTIONS 45 GRAPH generatefromvt GRAPH oldgraph char newname RVERTEX rvt Syntax Description Constructs the subgraph of a given graph generated by a set of vertices Error Exits Graph pointer NULL old and new graph have the same name vertex not in graph Remarks None Examples Example 4 1 page 48 See also example gen03 c in GHS directory GHStests 4 3 2 generatefromed Program Authors Dirk Ahlers and Tobe Toben Universit t Oldenburg GRAPH generatefromed GRAPH oldgraph char newname REDGE redge Syntax Description Constructs the subgraph of a given graph generated by a set of edges arcs Error Exits Graph pointer NULL old and new graph have the same name edge arc not in graph Remarks None Examples See example gen02 c in GHS directory GHStests The example is analogous to example 4 1 4 3 3 cpchtp Program Authors Dirk Ahlers and Tobe Toben Universit t Oldenburg Syntax GRAPH cpchtp GRAPH graph char newtype char newname Description Constructs a new graph by copying vertices and edges arcs from the old graph and simultaneously changing its type by modifying the copied edges arcs Error Exits
106. cture VERTEX grroot root optional void grattr pointer to user attribute structure int grattrtype type of user attribute structure 1 No attributes 0 Direct paths F enum grtp GRAPHTYPE 1 GG general graph all kinds of lines allowed DG general digraph DGS digraph single arcs DGSLF digraph single arcs loopfree UG general undirected graph UGS undirected graph single edges UGSLF undirected graph single edges loopfree b enum grsubtp GRAPHSUBTYPE 1 GSUBNA no subtype specified GSUBDIR graph representing direct path GSUBDIST1 distance graph centered in grroot GSUBDIST2 distance graph from the root to a second vertex GSUBDIST3 Global distance graph For each vertex the eccentricity and a list of most distant vertices are recorded in a QS record attached to the vertex C 5 BASIC GRAPH DATA STRUCTURES 3j struct vtstr VERTEX VERTEX VERTEX COLOR void char GRAPH int int int INC INC INC GVTSTD AVTSTD void DFSVT void int Fs struct rvtstr RVERTEX RVERTEX VERTEX vtleft vtright vtpar vtcolor vtauxiliary vtname vtgraph vtdg vtidg vtodg vtinclist vtiinclist vtoinclist vtptgstd vtptastd vtpthstd vtptdfs vtattr vtattrtype RVERTEX rvtleft rvtright Field grroot points to a li
107. d future enhancements The use of these fields in a function is also described under remarks In subsection C 5 page 166 the data structures pertaining to the basic graph functions of this chapter are defined To represent and manipulate graphs vertices and edges arcs the record types GRAPH VERTEX EDGE and INC for incidence records have been introduced yielding together a complete incidence list structure To represent vertices and edges in different additional roles the types RVERTEX and REDGE are used The enumeration type GRAPHTYPE is also used with the basic functions The basic data types are required for all other function classes too 2 3 Functions 2 3 1 readgraphlist Program Author G nther Stiege Universit t Oldenburg Syntax GRAPH readgraphlist char filename Description Reads a sequence of external graph descriptions from file filename If filename equals NULL the graph descriptions are read from standard input For each description an incidence structure is built GRAPH record VERTEX records EDGE records and INC records The records of each class are linked by a red black tree structure ordered by vertex name VERTEX or edge name EDGE INC The individual graph structures are linked in a list red black tree sorted by graph name Returns a pointer to list Error Exits Return value is NULL if an error has occurred Remarks None Examples Section 1 2 page 3 Example 2 1 page 16 2 3 2 savegraphlist P
108. d with print option STRCS for condensed statistics The results of these steps are shown in table 11 2 As the next step function prstd is called again this time with print option STR for a complete listing of the biblock decomposition The listing is shown in tables 11 4 11 5 11 6 and 11 7 104 CHAPTER 11 HIGHER DECOMPOSITIONS NOT YET RELEASED With function prstdvt a complete list of vertices option VPV is printed Only the output of the last two vertices of the list 0 and c0 is shown in table 11 8 Finally function biblocktrees is called to find the biblock graph of the biblock decomposition and to print it The result is shown in table 11 9 11 4 EXAMPLES 105 DEBRA aka ae af a ae aka KOR KOR KOR KOR KOR KOR KOR Program main Reads a graph and constructs its biblock decomposition The biblock decomposition is printed A list of vertices ordered by degree and vertex name is printed too It shows all relevant information of of each vertex and all edges incident with it Finally the biblock graph of the biblock decomposition is computed and printed aaa PKR ae aa ae a KOR KOR KOR KOR KOR KOR KOR KOR K include lt stdio h gt include lt GHSstructure h gt int main GRAPH graph graph readgraphlist stddecomp g
109. data type RELEM is used With data type RVSTD biblock decomposition properties of a vertex e g kind of attachment point are recorded In the same way records of type EDSTD are used for edges Edges a vertex is incident with may belong to more than one biblock hinge point Records of type INCSQR indicate the biblocks a vertex is element of Sev eral enumeration types RELEMCLASS RVSTDCLASS RVSTDSTAT EDCLASS EDSTAT POPTION STROPTION are used by the biblock decomposition functions mostly for internal purposes Remark 11 1 The proper building blocks of the biblock decomposition acyclic component cyclic component peripheral tree stopfree kernel internal tree subcomponent biblock are given unique and permanent names The name of a building block is not recored in a name field but is the name of one of its edges falsch identified by a specific procedure 11 3 FUNCTIONS 103 11 3 Functions 11 3 1 highcomponents Program Author G nther Stiege Universit t Oldenburg Examples Example 6 1 page 70 11 3 2 prbiblocktrees Program Author G nther Stiege Universit t Oldenburg Syntax void prbiblocktrees GRAPH graph Description Prints the biblock graph of a simple graph Only cyclic components are consid ered For each cyclic component the corresponding biblock tree is printed Error Exits Graph pointer Null Graph not of type UGSLF Biblock decomposition does not exist Remarks The biblock tree of a
110. decomposition to a subgraph found in a previous decomposition for instance to a strong component or to an external dag Program acom02 c see table 6 5 shows how this is done We consider graph wcompgraph figure 5 1 page 59 This graph is read using readgraphlist and then its weak and strong components are found gcomponents and printed gprstd This decomposition is not shown in this manual but we find from it that the last large weak component is WCOMP12 Using function generatefromcomp page 47 a new graph termed wcompgraph12 is generated from this weak component Its decomposition into weak and strong components and its biblock decomposition is calculated and printed tables 6 6 and 6 7 Of course these decompositions of wcompgrap12 are equivalent to the decompositions of WCOMP12 in the original graph Within wcompgraph12 the largest strong component is SCOMP3 From it again a new graph termed wcompgraph12 8 is generated Its biblock decomposition is found and printed table 6 8 The biblock decomposition of a strongly connected general graph is found considering exclusively a paths However it reveals also some f path properties For instance an edge lies on a f circuit if and only if it is element of some biblock 6 4 EXAMPLES 75 Program main Generates the subgraph corre
111. degree 2 2 Vertices of total degree 3 1 Vertices of total degree 5 1 Vertices of total degree 7 Table 4 3 Results of Program gen01 c 44 EXAMPLES 51 Vertex list K06 indegree outdegree Outgoing arcs d K06 K00 Incoming arcs _d K11 K06 K13 indegree outdegree Undirected edges _u K11 K13 Incoming arcs _d KO0 K13 KOO indegree outdegree Outgoing arcs d KOO K13 Incoming arcs d K06 K00 d K11 K00 K11 indegree outdegree Undirected edges _u K11 K13 Outgoing arcs _ d K11 K00 _d K11 K06 K15 degree indegree outdegree Outgoing arcs _d K15 K15a multiple _d K15 K15b multiple Incoming arcs d K14 K15 _d K15 K15a multiple _d K15 K15b multiple K14 degree 4 indegree outdegree 2 Undirected edges _u K14 Ki4a multiple _u K14 K14b multiple Outgoing arcs 4 14 14 loop d K14 K15 Incoming arcs _d K14 K14 loop Table 4 4 Results of Program gen01 c b 52 CHAPTER 4 GRAPH GENERATING FUNCTIONS Chapter 5 Weak and Strong Components 5 1_ Problem Description Connected components are the most obvious and the most important decomposition of undirected graphs For digraphs i e directed graphs the situation is more complex see Hara1969 CharL1996 or Volk1996 It gets still more complex if we allow for general graphs i e graphs of type GG In these graphs undirected edges and directed arcs may be present in any mixture In addition loops and multiple edges arcs are allowed In the f
112. der at least 3 h enum edclass EDCLASS classification 1 EDNY not yet classified EDPT peripheral tree line EDIT internal tree line EDBB biblock line struct incsqrstr INCSQR List of incidences t INCSQR incsqrleft INCSQR incsqrright C 8 DATA STRUCTURES FOR THE BIBLOCK DECOMPOSITION INCSQ COLOR void int REDGE int REDGE int REDGE BLB enum poption R t incsqrpar incsqrcolor incsqrauxiliary incsqredno incsqredlist incsqriedno incsqriedlist incsqroedno incsqroedlist incsqrblb POPTION VPV VPA VPB VPC VPH VPBC VPBH VPBCH VPCH enum stroption STROPTION t STR STRA STRR STRCS STAT STATCS for future extensions number of edges pointer to list of edges number of incoming arcs pointer to list of incoming arcs number of aoutgoing arcs pointer to list of aoutgoing arcs pointer to blb all all all all all all border points and check points but not hinge points all vertices which are border points and hinge points but not checkpoints all vertices which are border points check points and hinge points all vertices which are vertices attachment points border points check points hinge ponts vertices which are
113. directories e GHScore required Contains the source code of the GHScore C functions In addition it contains a Makefile and the header file GHSstructure h When the command make is executed using Makefile a library is created and stored in the directory GHScorelib GHScorelib is a directory with the same father directory as GHScore The name of the library is 1ibGHS so GHSgraphs optional In this directory a number of graphs including all graphs which are used as examples in this manual are collected The most important is the graph GHSwords which is the GHS version of Knuth s words dat Knut1993 GHStests optional Finally the directory GHStests is used to store all example programs of this manual To execute the programs each comes with a small command file having the same name and suffix cmd After installing the directories corresponding to GHScore we have a directory structure as shown in figure 1 1 GiScorelib GHSeraphs Figure 1 1 GHScore Directory Structure Before GHScore can be used some Unix variables have to be set export ghscore home xxx GHScore export ghsgraphs home xxx GHSgraphs export ghstests home xxxx GHStests export ghscorelib home xxx GHScorelib export LD LIBRARY PATH home xxx GHScoreliH There are two ways to use GHS The first way is the programmer s way It normally consists of the following four steps 1 Prepare the input file s 2 Pr
114. e 88 PDESCR 97 period 55 peripheral tree 64 66 102 PHDR 88 plinelist 88 pop 139 141 prbiblocktrees 103 printbfs 5 11 15 printdfs 11 15 printgrlist 11 14 printorder 118 124 printpathlist 91 printrbtree 118 124 proper weak component 53 prpartstr 85 206 prpartvted 85 PT 67 102 push 139 141 qend 139 144 qfront 139 144 QS 139 qscreate 139 145 qsremove 139 145 queue 139 QUSTA 139 RB 119 rbtcomp 119 rbtreedelete 117 rbtreefind 117 121 rbtreeidelete 121 rbtreeinsert 117 120 rbtreemax 118 123 rbtreemin 118 123 rbtreenext 118 122 rbtreepfind 118 121 rbtreeprevious 118 rbtreesize 118 122 rbtreesprevious 123 reachable 53 101 readedset 33 readgraphlist 5 11 13 readgset 35 readpath 90 readpathlist 90 readvtset 31 record type 13 red black tree 13 37 38 117 REDGE 13 releaseedpartlist 85 releaseedsetlist 34 releasegetlist 36 releasegraphlist 11 14 releasepathlist 91 releasequstalist 145 releasevtsetlist 32 RELEM 102 remaining subgraph 47 removelinefrompath 89 root 54 root property 55 rooted weak component 54 55 RVERTEX 13 RVSTD 102 saveedset 34 INDEX savegraphlist 5 11 13 savegset 36 savepathlist 91 savevtset 32 scanf 11 SCOMP 55 SEDI 119 set 31 set functions 31 SETELEM 31 short print option 14 91 shortest path 79 simple graph 83 simple path 53 SND 119 SNN 119 SORTK
115. e If filename equals NULL the names are read from standard input The end is indicated by EOF or END Builds the corre sponding set of vertices of the graph Returns a pointer to the set NULL if the set is empty or if an error has occurred 32 CHAPTER 3 SETS Error Exits Graph pointer NULL vertex set empty vertex name not from a vertex of the graph Remarks None Examples Example 4 1 page 48 3 3 2 gset2vtset Program Author G nther Stiege Universit t Oldenburg Syntax VTSET gset2vtset GSET gset GRAPH graph Description Constructs a vertex set from a general set Returns a pointer to the set NULL if an error has occurred Error Exits Graph pointer NULL pointer to general set NULL when calling add2vtset vertex with given name not in graph Remarks None Examples Example 3 1 See also program gen03 c in GHS directory GHStests 3 3 3 savevtset Program Author G nther Stiege Universit t Oldenburg Syntax void savevtset VTSET vtset char filename Description Writes the vertex names of a vertex set to file filename If filename equals NULL the output is written to standard output The output format is such that it can be read by readvtset Error Exits Pointer NULL vertex set empty number of elements incorrect Remarks None Examples Example 4 1 page 48 3 3 4 releasevtsetlist Program Author G nther Stiege Universit t Oldenburg Syntax void releasevtsetlist VTSET vtset Descriptio
116. e the graph again generatefromvt The names and the number of elements are printed for both the old and the new graph which are identical 3 6 EXAMPLES 39 Program main Reads a graph constructs a sequence of sets general set vertex set edge set and releases the sets Traces the amount of allocated memory kokokekokokokekekokelelelookekekelelelelejokekekelelelelejoleletelelelelejeleekelelelelejeleeleleleleleleetekelelelek include lt stdio h gt include lt GHSstructure h gt main GRAPH graph vtgra VTSET vtset EDSET edset GSET gset gsetl NULL char mgrname 100 graph readgraph if graph NULL printf Incorrect graph input n exit 0 strcpy mgraphname graph gt grname printf Memory after reading graph s Bytes n mgraphname ghsmemsize gset gsetunion RB graph gt grvtlist SND RB gseti SND printf Memory after reading first general set 46d Bytes n ghsmemsize vtset gset2vtset gset graph savevtset vtset printf Memory after building vertex set 46d Bytes n ghsmemsize releasegsetlist gset printf Memory after releasing first general set 46d Bytes n ghsmemsize gset gsetunion RB graph gt gredlist SED RB graph gt grdedlist SED
117. eak strong components decomposition of a general graph list of incidences Cyclic weak component Subcomponent Biblock Internal tree Peripheral tree Extension of VERTEX record Extension of EDGE record biblock of a vertex Vertex extension for additional dfs structure Edge extension for additional dfs structure Path header line on a path Descriptor for a Menger analysis Separating elements Main record for higher decomposition Element of a higher decompositions vertex record for higher decompositions line record for 157 158 APPENDIX C GHS INTERNAL DATA STRUCTURES 12 Distances higher decompositions C 3 Functions and Global Variables C 3 1 Explicit Functions k k ok sk ok sk ok sk ok sk ak ak Pk OR kk kkk kk kk kk kk kkk kk kk kkk Functions and global variables k k sk sk ok ok ok sk k ak ok ok ok 5k 3K aK ok ok 9k 3K 3K K aK Ok 9k 3K 3K K aK a 2K 3K 3K K aK OR 3K K aK ak 2K 3K 3K 3K aK aK 2K 3K 3K aK aK OR OR 3K 3K KOR OR K K A KOK OR K R R KOR K K k Explicit functions See user manual Basic Graph Functions GRAPH readgraphlist char filename basics c void savegraphlist GRAPH graph basics c char filename void
118. ecomposition TRUE The higher decomposition into maximal f components exists This decomposition if it exists starts with the strong components of the weak and strong decomposition TRUE The higher decomposition into maximal f linecomponents exists This decomposition if it exists starts with the strong components of the weak and strong decomposition TRUE The higher decomposition into maximal f connected vertex 167 168 APPENDIX C GHS INTERNAL DATA STRUCTURES sets exists This decomposition if it exists starts with the strong components of the weak and strong decomposition BOOLEAN grvsfl TRUE The higher decomposition into maximal f lineconnected vertex sets exists This decomposition if it exists starts with the strong components of the weak and strong decomposition int grdfs 0 there is no additional dfs tree structure 1 there is an additional f dfs tree structure 2 there is an additional b dfs tree structure 3 there is an additional a dfs tree structure VERTEX grdfsroot starting vertex for dfs structure int grsubtype graph subtype void grsysattr pointer to system attribute stru
119. edpartgen constructs such a partition The case where is the set of edges of a family of paths and W the set of end points of the path edges is important when determining Menger structures see chapter A second example is the edge partition which results from another edge partition when we delete from the first partition all 1 class edges where both vertices also belong to the same multi edge class and join the edge to all multi edge classes with this property The resulting partition may have non disjoint classes i e attachment edges It is a general partition Function cppartition among other options yields partitions of that type They are used for instance in determining the k components of a graph Non simple paths are allowed and there are cases where two edges of a class are joinable by non simple paths only 84 CHAPTER 8 EDGE AND VERTEX PARTITIONS NOT YET RELEASED Sometimes a strict edge partition is given by the application problem In such cases all edges of a class are painted with the same color If there is an external C function yielding the color of an edge GHS is able to construct the corresponding edge partition with function paint2part Function paint2cpart constructs the partition of the color connected classes of the original painting In addition to the normal colors of a painting the external function may yield the optional color invisible If this is the case the corresponding edge is n
120. ee chapter 9 Definitions and Properties of Connected Components A weakly connected component weak component for short of a general graph is a subgraph generated by a maximal set of mutually a reachable vertices We call isolates vertices improper weakly connected components In the following by weak components we always mean proper weakly connected components i e those which have at least one edge or arc A strongly connected component strong component 54 CHAPTER 5 WEAK AND STRONG COMPONENTS for short of a general graph is a subgraph of a proper weak component generated by a maximal set of mutually f reachable vertices We get the same strong components if we use mutual b reachability instead An edge and its end points always belong to a strong component In a weak component the subgraph generated by the arcs not belonging to any strong component is called the external dag of the weak component Vertices common to the external dag and to one of the strong components are called weak attachment points By z is f reachable from z but z is not f reachable from z a strict partial ordering z lt z is defined on the set of vertices of a weak component From the partial ordering a unique level number for each z is derived Level number 0 is assigned to the starting points of this partial ordering All vertices of a strong component have the same level number A vertex which is not element of a strong component is called vertex of no re
121. em errors if elem equals NULL or an illegal key has been specified Remarks None Examples See example 13 7 page 126 13 3 10 rbtreemax Program Author G nther Stiege Universit t Oldenburg Syntax RB rbtreemax RB tree Description Returns the record of the tree which has maximum ordering value i e the right most record Returns NULL if tree is empty Error Exits None Remarks None Examples See example 13 8 page 127 13 3 11 rbtreemin Program Author G nther Stiege Universit t Oldenburg Syntax RB rbtreemin RB tree Description Returns the record of the tree which has minimum ordering value i e the left most record Returns NULL if tree is empty Error Exits None Remarks None Examples See example 13 8 page 127 124 CHAPTER 13 RED BLACK TREES 13 3 12 printorder Program Author G nther Stiege Universit t Oldenburg Syntax void printorder FILE fd RB ndx int key char ftext Description Writes to the file given by file descriptor fd the names of the records of the red black tree pointed to by ndx in ascending order The type of the records depends on the key class key see section 13 2 A constant prefix printed with each record is specified by ftext Nothing is printed if ndx is NULL Error Exits File descriptor fd is NULL nothing is printed System error if key class is not allowed Examples See examples 13 1 page 126 13 2 page 126 and 13 9 page 127 Remarks The
122. emarks None Examples See example qusta01 c in GHStests 14 3 2 pop Program Author G nther Stiege Universit t Oldenburg Syntax void pop QUSTA stack Description The QS record on top of stack is removed and deleted A pointer to the qelem record it stands for is returned The qelem element is not touched Error Exits None Remarks If the stack is empty NULL is returned Examples See example qusta01 c in GHStests 14 3 3 fpush Program Author G nther Stiege Universit t Oldenburg Syntax void fpush QUSTA stack void qelem Description Puts element qelem on top of stack qelem may be an element of any type given by its address castes to void qelem is not linked directly into the stack list Instead a QS record which is pointed to from the auxiliary field of qelem is used The QS record must have been created and attached to the qelem element by the calling program Function qscreate may be used for this purpose Normally elements put in a stack with fpush should be removed from the stack with fpop and not pop Multiple membership is not allowed 142 CHAPTER 14 STACKS AND QUEUES Error Exits Error if NULL record is to be pushed onto stack Error if QS record missing If an attempt for multiple stack membership is detected an error message is printed no stack insertion is done and the function returns to the calling program Remarks The integer fields qshelpi and qshelp2 as well as the void pointer field qsp
123. en Gee ah ae RU ub ql 133 Results of Program 507 134 Results of Program 508 135 The vertices of Graph1 printed with 136 18 10 Ezample for getname sics 1 69 n Rr ow eo 137 Bibliography Pages where cited are in parentheses 1 1996 Chartrand Gary Lesniak Linda Graphs amp Digraphs Chapman amp Hall 3 edition 1996 51 CormLR1990 Cormen Thomas Leiserson Charles E Rivest Ronald L Introduction Hara1969 to Algorithms The MIT Electrical and Computer Science Series The MIT Press McGraw Hill Book Company 1990 115 119 1377 Harary Frank Graph Theory Addison Wesley Series in Mathematics Addison Wesley Publishing Company 1969 51 61 HopcT1973 Hopcroft John E Tarjan Robert Endre Efficient Algorithms for Graph Manip ulation Communications of the ACM 16 6 372 378 1973 61 Knut1993 Knuth Donald E The Stanford GraphBase Addison Wesley Publishing Company Stie1998 Stie2006 Stie2007a Stie2009 Tarj1972 Volk1996 1993 A Platform for Combinatorial Computing 4 124 Stiege Giinther Edge Partitions in Undirected Graphs Berichte aus dem Fachbereich Informatik 5 98 Universitat Oldenburg 1998 Available from http www bvs informatik uni oldenburg de Literatur Berichte oib98 05 html
124. entifiers The complete identification of a weak strong component is its name as specified in table 4 1 page 44 5 3 Functions 5 3 1 gcomponents Program Author Sergeij Alekseev Universit t Oldenburg Syntax void gcomponents GRAPH graph Description Finds the decomposition of a general graph of any type Weak components strong components external dag weak attachment points level numbers periods Creates a GSTDD record and complementary records After successful termination the field grgstruct of the graph s GRAPH record points to the GSTDD record Error Exits Graph pointer NULL General decomposition already exists pointer grgstruct is not NULL Remarks The field vtptgstd in the VERTEX records is used to point to the corresponding GVTSTD records The field edptgstd in the EDGE records is used to point to the corresponding GEDSTD records Examples Example 5 1 page 58 5 3 2 gprstd Program Author G nther Stiege Universit t Oldenburg Syntax void gprstd GRAPH graph int stroption char filname Description Writes the general decomposition weak components strong components and external dags of a general graph to file filename If filename equals NULL the output is written to standard oputput Has the following print options STR Prints complete decomposition structure STRA Prints weak attachment points but no other vertices and no edges STRR Prints reduced structure No vertices and no l
125. ernel REDGE wcompstpdedlist list of arcs of stopfree kernel int wcompsubno number of subcomponents SUB wcompsublist list of subcomponents int wcompblbno number of biblocks RELEM wcompblblist list of biblocks int wcompitno number of internal trees IT wcompitlist list of internal trees int wcompptno number of peripheral trees PT wcompptlist pointer to list of peripheral trees int wcompattno number of attachment points RVERTEX wcompattlist list of attachment points int wcompborno number of border points RVERTEX wcompborlist list of border points int wcompcheno number of check points RVERTEX wcompchelist list of check points int wcomphinno number of check points RVERTEX wcomphinlist list of hinge points h struct scomp C 3 3 SCOMP strong component 1 SCOMP scompleft SCOMP scompright SCOMP scomppar COLOR scompcolor void scompauxiliary int scomptype type of strong component 1 not yet assigned 1 f acyclic 2 f cyclic int scompnumber number of strong component 1 not yet assigned C 7 DATA STRUCTURES FOR WEAK AND STRONG COMPONENTS WCOMP int RVERTEX int REDGE int REDGE int RVERTEX int int struct gvtstd GVTSTD GVTSTD GVTSTD COLOR void VERTEX WCOMP int SCOMP int REDGE int REDGE int scompwcomp scompvtn
126. es The third section contains a detailed description of the individual functions A last section with examples completes each chapter I have programmed most of the GHScore functions myself Functions generatefromed and cpchtp were designed amd implemented by Dirk Ahlers and Tobe Toben Sergej Alekseev is responsible for the implementation of function gcomponents I gratefully acknowledge the patience Ingo Stierand and Sergej Alekseev have shown in long and intensive discussions and the many creative ideas they have contributed Oldenburg October 2004 G Stiege Preface to version 5 0 During the past years GHS has not progressed as much as originally planned This version 5 0 includes extensions and revisions of red black trees Paths Menger structures and higher decompositions are still lacking The work on the graphical user interface GHSgui has been suspended GHSqgui is not part of this version Again I have to thank Ingo Stierand and Sergej Alekseev for very valuable help Oldenburg December 2009 G Stiege il Contents 1 Introduction 1 1 General Remarks and Overview 1 2 How to Usethe System iu ueae des ea S RUE SEDES I GHS Functions 2 Basic Graph Functions 2 1 Problem Description 2 2 Formats and Data Structures 2 3 cPuncetiolsS 5 Za s sr x we OP aO Pu RUE q UR S RS EMO ER A are US BER 231 readeraphlist
127. es or use of this software display the following acknowledgement This product includes software developed by Guenther Stiege et al and Sergej Alekseev Universitaet Oldenburg Germany Neither the name of the University nor the names of its authors may be used to endorse or promote products derived from this software without Specific prior written permission 4 changes are permissible only if the changed files are given a new name different from the names of existing files of GHS and only if the changed files are clearly identified as not being part of GHS THE AUTHORS HAVE TRIED THEIR BEST TO PRODUCE A CORRECT AND USEFUL PROGRAM IN ORDER TO HELP PROMOTE COMPUTER SCIENCE RESEARCH BUT THIS SOFTWARE IS PROVIDED AS IS AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES INCLUDING WITHOUT LIMITATION THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X k Ck Ck Ck Ck KOK Ck k Ck Table 1 1 Distribution policy of GHS dk db Gb HF db db E HHH HH dk HHH CHAPTER 1 INTRODUCTION GHS comes as a package consisting of text files program sources and others and documentation From this package all what is needed can be installed to run GHS under a Unix system or a Windows system In a Unix system the package is decompressed using gzip and installed in a directory using tar GHScore uses the following
128. ex set vtsink Returns the corresponding Menger descriptor The kind of paths found depends on parameter mode mode equals vt or VT the paths are internally disjoint mode equals li or LI the paths are line disjoint mode equals evt or EVT the graph is temporarily enlarged see page 96 and vt is applied to the larger graph mode equals eli or ELI the graph is temporarily enlarged see page 96 and li is applied to the larger graph If direction equals A or a a paths are found whereas direction F or f indicates f paths name is a user specific name for the Menger structure Parameter bound delimits the number of paths bound lt 0 all paths are found bound gt 0 the function returns at most the specified number of paths In this case no Menger separating elements are determined even if they existed Parameter sep Values first or complete See the following description of paths and sepa rating elements Paths and separating elements Function mengertstr yields a complete description of the paths joining vtsource to vtsink as well as complete description of the elements separating these sets All paths found are simple They are also shortest in the sense that only the first vertex is element of vtsource and only the last vertex is element of vtsink The paths are described by a path descriptor PDESC a mode vt 1 All verti
129. f a queue qscreate and qsremove A QS record is created for removed from each element of an RB tree mnewqusta A new QUSTA record is created 14 2 Formats and Data Structures To handle stacks and queues the data types QUSTA and QS have been introduced Figure 14 1 shows these records and the links between them In the upper part a QUSTA record points to a queue left linked list and to a stack right linked list The uppermost QS record is the front of the queue respectively the top of the stack There is an additional pointer from the QUSTA 140 CHAPTER 14 STACKS AND QUEUES RECORD RECORD 4 5 Figure 14 1 Data structures QUSTA and QS record to the end of the queue The backward links in the list of QS records are not shown in the figure In the lower part of figure 14 1 the left side shows the use of QS records with simultaneous multiple membership push pop enqueue dequeue whereas the right side shows the use of QS records with membership attributes fpush fpop fenqueue fdequeue In the first case there is only a pointer from the QS record to the record it stands for The QS records are created by push and enqueue and deleted by pop and dequeue They are not visible for the calling program In the second case the QS record must be allocated and eventually released by the calling program The calling program is also responsible for putting a link from the original record to the QS record in the original
130. f biblocks containing maximal a connected vertex sets int hvsgalno number of maximal a lineconnectged vertex sets SUB hvsgallist list of subcomponents containing maximal a lineconnected vertex sets int hsggfno number of f components BLB hsggflist list of strong components containing f components int hsggflno number of f linecomponents SUB hsggfllist list of strong components containing f linecomponents int hvsgfno number of maximal f connected vertex sets BLB hvsgflist list of strong components containing maximal f connected vertex sets int hvsgflno number of maximal f lineconnectged vertex sets SUB xhvsgfllist list of strong components containing maximal f lineconnected vertex sets struct hdccomp HCOMP Higher decomposition element t HCOMP hcompleft HCOMP hcompright C 13 DATA STRUCTURES FOR THE HIGHER A DECOMPOSITION HCOMP hcomppar COLOR hcompcolor void hcompauxiliary int hcomptype int hcompdegree int hcompnumber void hcomplowerel HSTDD hcomphstdd int hcompvtno int hcompedno int hcompdedno int hcomcovtno int hcomcoedno int hcomcoeddno int hcompnextlvno HCOMP hcompnextlvli struct hvtstd
131. f the path given by phdr2 into the path given by phdr1 Path phdr1 is extended path phrd2 remains unchanged 1 If the last vertex of phdr1 and the first vertex of phdr2 are identical then the lines of phdr2 follow phdr1 in the resulting path 2 If the first vertex of phdr1 and the last vertex of phdr2 are identical then the lines of phdr2 precede phdr1 in the resulting path 3 If neither 1 nor 2 hold then phdr2 must be a closed path and its starting point must occur in phdr1 The lines of phdr2 are inserted into phdr1 following the first occurrence of that vertex The function returns TRUE if the insertion was correct It returns FALSE if an error occurred Error Exits 90 CHAPTER 9 PATHS NOT YET RELEASED Remarks 1 It may be that both conditions 1 and 2 above hold In that case the result is as described in condition 1 2 phdri and phdr2 must be valid header records and they must refer to the same graph However it is not necessary that these paths have positive lengths The following cases are possible length phdri length phdr2 0 0 no effect positive 0 no effect 0 positive second path is copied 9 3 5 readpath Examples Program Author G nther Stiege Universit t Oldenburg Syntax PHDR readpath GRAPH graph char filename Description Reads an external path description Table 9 1 from file filename If filename equals NULL the path description is read from standart input Using vertices and lines f
132. ferent from the names of existing files of GHS and only if the changed files are clearly identified as not being part of GHS THE AUTHORS HAVE TRIED THEIR BEST TO PRODUCE A CORRECT AND USEFUL dk HH HH HHH HHH HH dk OF 150 APPENDIX A GHS MAKEFILE PROGRAM IN ORDER TO HELP PROMOTE COMPUTER SCIENCE RESEARCH BUT THIS SOFTWARE IS PROVIDED AS IS AND WITHOUT ANY EXPRESS OR IMPLIED WARRANTIES INCLUDING WITHOUT LIMITATION THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE HOR k Gk Ck Ck Ck Ck Ck Ck Ck Ck ck H CC gcc Wall SDIR ODIR GHSobjects LIBDIR GHScorelib ghs createobjectdir ODIR basics o ODIR gsets o ODIR generate o ODIR cpchtp o ODIR util o ODIR rbtree o ODIR qusta o ODIR gcomponents o ODIR gstdutil o ODIR astd o ODIR astdutil o ODIR path o ODIR pathutil o ODIR menger o ODIR mengerutil o OO OO GP GO GLO GE GO GO all iO GO S ell ll gl NG GE tO dO il gh OO OO PO createlib createlib gcc g fPIC shared W1 o libGHS so DDIR o lc rm f r LIBDIR mkdir LIBDIR mv libGHS so LIBDIR rm r ODIR Directory for object files createobjectdir rm f r GHSobjects mkdir GHSobjects Basic Graph Functions ODIR basics o SDIR
133. file descriptor fd must have been set by fopen or alternately to stdout 13 3 13 printrbtree Program Author G nther Stiege Universit t Oldenburg Syntax void printrbtree FILE fd RB ndx int level int key Description Writes to the file given by file descriptor fd the actual structure of a red black tree in in order The type of the records depends on the key class key see section 13 2 The root of the tree is given by The root may be any node in the tree With level the level of this node is specified Remark level is for printing purposes only Any number can be used It is recommended to use 0 if the real level of the root is unknown Error Exits File descriptor fd is NULL nothing is printed System error if key class is not allowed Examples Examples 13 1 page 126 and 13 2 page 126 Remarks The file descriptor fd must have been set by fopen or alternately to stdout 13 3 14 testtree Program Author G nther Stiege Universit t Oldenburg Syntax BOOLEAN testtree FILE fd RB root int key char option Description Tests a binary tree given by its root If option equals S the tree is tested for correct binary search tree If option equals R the tree is tested in addition for correct red black tree TRUE is returned if no erros have been detected FALSE is returned otherwise If errors are detected they are output to fd Comparisons for greater less use key 13 3 FUNCTIONS 125 Error Exit
134. h 53 EDPART 84 85 edpartgen 84 edptgstd 56 EDSET 31 EDSTD 102 end point of an arc 12 end points of an edge 12 enqueue 139 142 EOF end of file 31 33 36 error 2 external dag 54 external file format 11 12 87 88 external graph format 5 external representation 11 87 INDEX F f acyclic 53 f circuit 53 55 74 f component 101 f cyclic 53 55 f depth first search 54 f path 53 f period 55 f reachable 53 101 f tree 54 fdequeue 139 144 fenqueue 139 143 field 13 file format 5 11 87 file representation of a graph 5 format 11 31 44 55 67 102 forward 15 53 fpop 139 142 fpush 139 141 free tree 54 G gcomponents 56 GEDSTD 55 general graph 12 53 general organizatio 155 general partition 183 general set 31 35 generate 43 generated subgraph 43 generatefromchnm 48 generatefromclass 85 generatefromcomp 47 67 68 generatefromed 45 generatefromvt 44 generategraphfrompath 91 generic data structure 164 getcharname 125 getname 118 125 GG 12 GHS 1 GHS format 11 12 87 88 GHScore 4 GHScorelib 4 GHSgraphs 4 GHSgui 5 ghsmemsize 2 16 GHSstructure 4 GHSstructure h 13 119 GHStests 4 GHSwords 4 47 127 gprstd 56 gprstdvt 57 GRAPH 13 INDEX graph functions 11 graph generating functions 43 44 graph handling system 1 graph type 5 12 46 graphical user interface 5 graphname 12 graphs see GHSgraphs grastd 67 grgstruct 55
135. he manual Example 5 2 Program gcomp03 c generates a subgraph from weak component WCOMP2 of graph wcompgraph applies gcomponents to this subgraph and prints a list of vertices using function gprstdvt with options VPV and VPA The results correponding to option VPA are shown in table 5 3 5 4 EXAMPLES ae 26 Figure 5 1 wcompgraph 60 CHAPTER 5 WEAK AND STRONG COMPONENTS BEGIN WEAK AND STRONG COMPONENTS REDUCED STRUCTURE GRAPH wcompgraph TYPE GG No VERTICES No_EDGES No_ARCS No_ISOLATED_VERTICES No_WEAK_COMPONENTS 13 No_A ACYCLIC_WEAK_COMPONENTS_WITHOUT_STRONG_COMPONENTS 2 9V OE 7A WEAK COMPONENT wcompgraph WCOMPO dA01403 4V OE 3A aper 2 MAXLV 2 WEAK COMPONENT wcompgraph WCOMP1 lt _dAO5A06 gt 5V OE 44 aper 2 MAXLV 2 f TREE root A05 vertex No A ACYCLIC WEAK COMPONENTS WITH STRONG COMPONENTS 2 10V 5E 3A WEAK COMPONENT wcompgraph WCOMP2 4 02 03 gt 5V 2E 2A aper 2 MAXLV 2 f TREE root B02 vertex No STRONG COMPONENTS 2 No f ACYCLIC STRONG COMPONENTS 2 4V 2E OA STRONG COMPONENT wcompgraph WCOMP2 SCOMPO lt uBO1BO3 2V 1E OA 1WAP STRONG COMPONENT wcompgraph WCOMP2 SCOMP1 lt _uBO4B05 gt 2V 1E OA WAP EXTERNAL wcompgraph WCOMP2 SCOMP1 dBO2BO3 3V OE 2A WEAK COMPONENT wcompgraph WCOMP3 dBO8BO9 5V 1A aper 2 MAXLV 1 f TREE root wcompgraph WCOMP3 SCOMPO lt _uB06B08 gt strong component No
136. help of the QS record may be used freely by the calling program Examples See example qusta01 c in GHStests 14 3 4 fpop Program Author G nther Stiege Universit t Oldenburg Syntax void fpop QUSTA stack Description The QS record on top of stack is removed but not deleted A pointer to the qelem element it stands for is returned The qelem is not touched Error Exits None Remarks If the stack is empty NULL is returned Examples See example qusta01 c in GHStests 14 8 5 top Program Author G nther Stiege Universit t Oldenburg Syntax void top QUSTA stack Description Returns a pointer to the top element of stack Error Exits None Remarks If the stack is empty NULL is returned Examples See example qusta01 c in GHStests 14 3 6 enqueue Program Author G nther Stiege Universit t Oldenburg Syntax void enqueue QUSTA queue void qelem 14 3 FUNCTIONS 143 Description Adds element qelem to the end of queue qelem may be an element of any type given by its address casted to void qelem is not linked directly into the queue Instead a new QS record is created which points to qelem The QS record remains invisible to the calling program Normally elements put in a queue with enqueue should be removed from the queue using dequeue and not fdequeue Multiple membership is allowed Error Exits Error if NULL record is to be added to queue Remarks None Examples See example qusta01 c in GHStes
137. here is also the function savegraphlist which transforms the internal representations of a list of graphs into their external representations and outputs these to a file or standard output Finally the function releasegraphlist releases a list of graphs A second group of functions printgrlist printdfs printbfs serve to print different aspects of a graph Some statistics the incidence lists of vertices list of vertices in depth first or breadth first sequence The functions addvertex and addline serve to enlarge an existing graph Functions deletevertex and deleteline can be used for diminishing an existing graph They have to be used with special care since adding or deleting a vertex or a line may change drastically graph properties and hence make inavlid secondary structures built upon those Finally there are functions dfsstructure and releasedfs which add a depth first forest struc ture to the graph respectively release it 2 2 Formats and Data Structures External file format Files which represent graphs in external GHS format are organized as shown in table 2 1 A graph file is a character file where relevant tokens are defined according to the C function scanf A formal syntax description in Backus Naur Form is given in the appendix page 153 12 GRAPH lt graphname gt TYPE lt graphtype gt VERTICES list of vertices EDGES list of edges ARCS list of arcs CHAPTER 2 BASIC GRAPH FUNCTIONS Each g
138. id releaseqstalist QUSTA qusta util c D 1 3 1 void releaseqslist QS qs util c D 1 3 2 void releasevtlist VERTEX vt util c D 2 2 void releaservtlist RVERTEX rvt util c D 2 3 void releaseedlist EDGE util c D 2 4 x void releaseredlist REDGE red util c D 2 5 x void releaseinclist INC inc util c D 2 6 void releasesellist SETELEM rel util c D 3 4 C 3 FUNCTIONS AND GLOBAL VARIABLES void releasegstddlist GSTDD gstdd util c D 4 1 void releasewcomplist WCOMP wcomp util c D A 2 void releasescomplist SCOMP scomp util c D 4 3 void releasegvtstdext VERTEX vt util c D 4 4 void releasegedstdext EDGE ed util c D 4 5 void releaseastd GRAPH graph util c D 5 1 void releasesublist SUB sub util c D 5 2 void releaseblblist BLB blb util c D 5 3 void releaseitlist IT xit util c D 5 4 void releaseptlist PT pt util c D 5 5 void releaseavtstdext VERTEX vt util c D 5 6 void releaseaedstdext EDGE ed util c D 5 7 void releaseincsqrlist INCSQR incsqr util c D 5 8 void releasedfsvtext VERTEX vt util c D 6 2 void releasedfsedext EDGE util c D 6 2 void releasepdhrlist PHDR phdr util c D 9 2 void releasephdrlist PHDR phdr void releasepthalist PTHA ptha util c D 9 3 void releasemgdescrlist MGDESCR mgdescr util c D 10 1 3 ak ak
139. iincforno no of incoming dfs forward arcs INC dfsiincforlist list of incoming dfs forward arcs int dfsiincbackno no of incoming dfs backward arcs INC dfsiincbacklist list of incoming dfs backward arcs int dfsiinccrossno no of incoming dfs cross arcs INC dfsiinccrosslist list of incoming dfs cross arcs int dfsoinctreeno no of outgoing dfs tree arcs INC dfsoinctreelist list of outgoing dfs forward arcs int dfsoincforno no of outgoing dfs forward arcs INC dfsoincforlist list of outgoing dfs forward arcs int dfsoincbackno no of outgoing dfs backward arcs INC dfsoincbacklist list of outgoing dfs backward arcs int dfsoinccrossno no of outgoing dfs cross arcs INC dfsoinccrosslist list of outgoing dfs cross arcs VERTEX dfsroot root of corrsponding dfs tree struct dfsedstr DFSED line extension for dfs structure 1 DFSED dfsedleft DFSED dfsedright DFSED dfsedpar COLOR dfsedcolor void dfsedauxiliary for future extensions EDGE dfsedp pointer to line DFSVT dfsedhead head of dfs arc DFSVT dfsedtail tail of dfs arc int dfsedtype type of dfs arc C 10 DATA STRUCTURES FOR GENERAL PARTITIONS F3 enum dfsedtype DFSEDTYPE 1 DFSNY not yet assigned DFSTREE dfs tree arc DFSFOR dfs forward arc DFSBACK dfs backward arc DFSCROSS dfs cross a
140. iliary for future extensions char mgname name of the Menger structure GRAPH mggraph pointer to graph int mgmode 1 No mode assigned yet 0 internally disjoint paths vt 1 line disjoint paths v1 C 13 DATA STRUCTURES FOR THE HIGHER A DECOMPOSITION 2 externally disjoint paths evt in the extended graph 3 line disjoint paths eli in the extended graph int mgdir 1 No direction assigned yet 0 a paths 1 f paths VTSET mgvtsource vertices of vtsource VTSET mgvtsink vertices of vtsink VTSET mgvtcommon vertices of vtcommon EDSET mgdiredges directly linking edges EDSET mgdirarcs directly linking arcs PDESCR mgpaths Menger paths void mgattr pointer to user attribute structure int mgattrtype type of user attribute structure 1 No attributes int mgbound lt 0 All Menger paths from vtsource to vtsink sre determined O lt At most this number of paths are determined BOOLEAN mgsep TRUE 11 Menger vertices lines on all pertinent paths together with its minimal Menger separating sets are recorded FALSE Only the first Menger separating set in direction from vtsource to vtsink is recorded SEPDESCR mgsepdescr Separating elements struct mgsepdescrstr SEPDESCR descriptor for separating elements t SEPDESCR sepleft SEPDESCR sepright SEPDESCR se
141. in Reads graph Prints all vertices reachable from a in depth first sequence forward direction b in depth first sequence any direction c in breadth first sequence backward direction kokokokokokokokekokelelekookekekelelelelejoekekelelelelejokeletelelelelejeleetelelelelejeleelelelelejeleekelelelelelek include lt stdio h gt include lt GHSstructure h gt int main t GRAPH graph graph readgraphlist NULL if graph NULL printf Incorrect graph input n exit 0 printdfs graph KOO forward NULL printdfs graph K00 any NULL printbfs graph KOO backward NULL return 0 Table 2 8 Program bas02 c 26 K00 _d K00 K01 K01 u K01 K02 K02 d K02 K03 K03 _d K03 K09 K09 d K09 K08 K08 _d K00 K21 K21 _d K21 K20 K20 _u K19 K20 K19 _d K19 K07 K07 _d K00 K13 K13 _u K11 K13 K11 _d K11 K06 K06 Part A CHAPTER 2 BASIC GRAPH FUNCTIONS _d K00 K01 K01 u K01 K02 K02 _d K02 K03 K03 _d K03 K09 K09 _d K09 K08 K08 _d K19 K08 K19 _u K19 K20 K20 _d K21 K20 K21 _d K07 K21 KO7 _ 1 K13 _u K11 K13 K11 d K11 K06 _d K12 K11 K12 Part B KOO _d K11 K00 K11 _d K06 K00 K06 _u K11 K13 K13 _d K12 K11 K12 Part C printdfs graph printdfs graph printbfs graph KOO forward NULL any NULL backward NULL Table 2 9 Res
142. ines are printed STRCS Prints condensed statistics only If available this statstistics also includes information about the biblock decomposition of the graph see chapter 6 Error Exits print option Graph pointer Null Decomposition into weak and strong components does not exist The numbering depends on the specific run of the decomposition algorithms 5 8 FUNCTIONS 97 Remarks A line like STRONG_COMPONENT wcompgraph WCOMP6 SCOMP1 lt _uE13E16 gt 2V 1E OA 2WAP lv 1 fper 2 is to be read Strong component No 1 of weak component No 6 of graph wcompgraph has charname _uE13E16 It consists of 2 vertices 1 edge and 0 arcs It has 2 weak attachment points level No 1 and f period 2 Examples Example 5 1 page 58 For option STRCS see example 6 1 page 70 5 3 3 gprstdvt Program Author G nther Stiege Universit t Oldenburg Syntax void gprstdvt GRAPH graph int poption char filename Description Writes a list of vertices ordered by total degree and vertex name to file filename If filename equals NULL the output is written to standard output For each vertex and the edges arcs incident with it graph decomposition information is written Has the following print options VPV All vertices VPA All weak attachment points Error Exits Graph pointer Null Decomposition into weak and strong components does not exist Wrong print option Remarks A list entry like E12 DG 1 0DG 2 IDG 3
143. ino 4 d ao e ifta 65 6 4 Biblock Graph Corresponding to Ugraphl 66 7 1 Combined distance graphs point block point check point trees point Unde i dette C8 ve ap olv Sr upa 81 91 as linked lists 5 2 Re Dane Rm RES PORE POS AUR 8T 10 1 Menger line theorem graph Menglgraph1 99 10 2 Menger line theorem graph Menglgraph2 100 14 1 Data structures QUSTA and 065 140 198 LIST OF FIGURES List of Tables 1 1 1 2 1 3 2 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 2 11 2 12 2 13 3 1 3 2 3 3 3 4 3 5 4 1 4 2 4 3 4 4 5 1 5 2 5 3 6 1 6 2 6 3 6 4 6 5 Distribution policy of 5 Program Intri th a ete Sc Xs Results of Program 1 01 External File Format of GHS Graphs 22e External File Description of Graphl Proor m basOTscus eis 2 asha xot B eleg UG Q NC EW RE Results of Program bas01 c Results of Program bas01 c Results of Program bas01 c Results of Program bas01 c 4 Program IE ETE E Rare TEE wd Results Program bas02 6 sway 5 BP
144. insert rbtcomp rbtreefind rbtreeinsert getname rbtcomp rbtreefind rbtcomp rbtreefind rbtreeinsert getname getname rbtcomp rbtreefind rbtcomp rbtreefind rbtreeinsert GRAPH compared to GRAPH by grname GRAPH gt grname compared to char VERTEX compared to VERTEX by vtname VERTEX gt vtname compared to char RVERTEX compared to RVERTEX by vtname RVERTEX gt rvtp gt vtname compared to char RVERTEX compared to RVERTEX by a total degree b vtname EDGE by edname EDGE gt edname compared to char REDGE compared to REDGE by line name Uses EDGE record Provides line name and names of end vertices in a 3 lines print format REDGE gt redp gt edname compared to char INC by linename C 14 SORT KEYS FOR RED BLACK TREES getname 3 Sets SSEL rbtcomp SETELEM compared to rbtreefind SETELEM by selname rbtreeinsert getname SSCEL rbtcomp SETELEM gt selname rbtreefind compared to char 4 Graph Generating Functions 5 Weak and Strong Components RGSTDD rbtcomp Two GSTDD records are compared by the rbtreefind names of the graphs they point to rbtreeinsert getname NGSTDD rbtcomp Name of the graph the GSTDD record rbtreefind points to
145. ition It is easy to obtain and very useful Its remarkable properties are due to the fact that two vertices which are mutually 2 a reachable lie on an a circuit They lie on a line simple closed a path if they are mutually 2 a linereachable This makes it possible to define the biblock decomposition using partitions of the set of lines of a general graph For details see Stie2006 or Stie2007a There the algorithms used in GHS can be found 2 a lineconnected subgraphs and therefore also 2 a connected subgraphs must contain a circuits Hence the biblock decomposition starts with the a cyclic weak components of a general graph In these a hierarchy of closed a path is considered Q QOO QOO Circuit Linesimple closed path Stopfree path Figure 6 1 Examples of closed paths circuits C closed line simple paths C stopfree paths Traditionally connected components of simple graphs are decomposed further by identifying the blocks i e maximal non separable subgraphs of each component and representing the blocks a well as the cutpoints which separate them by a block cutpoint graph see for instance Harary Hara1969 It is possible to construct the block cutpoint graph with a depth first search algorithm proposed by Hopcroft and Tarjan HopcT1973 Tarj1972 64 CHAPTER 6 THE BIBLOCK DECOMPOSITION A stopfree path is a closed a path where no line is immediately followed by itself and the first line is different from the last
146. k decomposition See subsection 6 3 4 page 69 e For subgraphs generated from elements of higher decompositions see chapter 11 4 1 2 Names and Adresses Weak and strong components together with the external dag lead to a hierarchial decomposition of a general graph The biblock decomposition of a general graph introduced in chapter 6 gives rise to the stopfree kernel peripheral trees subcomponents internal trees and biblocks another 44 CHAPTER 4 GRAPH GENERATING FUNCTIONS hierarchial decomposition Together we call these elements decomposition elements or building blocks Those which can occur multiply are described by structure records for instance BLB for biblocks or WCOMP for weak components Those which occur only once per weak component namely external dag and stoprfree kernel have their data stored in the corresponding WCOMP record The address of a decomposition element is the address of its describing record It is run dependent and in general will change from one construction of the graph to the next In additon hierarchical names based on the number of a decomposition element are provided too Table 4 1 shows how these name are built The number assigned to a decomposition element lt graphname gt WCOMP lt no gt weak component lt graphname gt WCOMP lt no gt SCOMP lt no gt strong component lt graphname gt WCOMP lt no gt EXD external dag lt graphname gt WCOMP lt no gt STP stopfree kernel lt graphname g
147. k sk ok sk ak ak ak ak ak ak sk oko OR ak OR ak ak ak OR kk kkk kk kk kk kkk kk kk kkk RB Generic for red black trees For SORTKEY type of sortig key see end of file ak ak ak aka KOR KIKI KOR I I A I aK aK aK KOR K struct rbtree RB RB left RB right RB par COLOR color void auxiliary F C 4 3 Data Structures for Stacks and Queues PREC ak sk ok sk ak sk ak ak ak ak ak ak ak ak ak ak ak kk kk kk kkk kk kk kk kk kkk kk kk kkk QUSTA Stacks an queues for arbitrary GHS elements C 1 3 1 QS Elements in queues and stacks C 1 3 2 Are not the records to be queued stacked but their representatives 3K 3K 3K K aK aK 2K 3K 3K K aK aK 2K 3K 3K K aK 3K 3K 3K 3K aK aK 2K 3K 3K K aK 2K 3K 3K 3K K aK 2K 3K 3K 3K K K K FK 3K KKK K K K struct ghsqusta QUSTA QUSTA qustaleft QUSTA qustaright QUSTA qustapar COLOR qustacolor void qustaauxiliary QS qustastart QS qustaend 05 qustatop struct ghsqs QS QS qsleft 165 166 APPENDIX C GHS INTERNAL DATA STRUCTURES QS qsright QS qspar COLOR qscolor void qsauxiliary may be used only as pointer to list
148. kekelelelelejoekekelelelelejolelekelelelelejeeletelelelelejeleelelelelejeleekelelelelek include lt stdio h gt include lt GHSstructure h gt int main t GRAPH graph graph readgraphlist NULL if graph NULL printf Incorrect graph input n exit 0 savegraphlist graph NULL printf nBreadth first search starting at D n printbfs graph D forward NULL return 0 Table 1 2 Program int01 c gcc I ghscore L ghscorelib int01 c IGHS Im o ghs After compiling the program we get the executable code in file ghs Step 4 Finally the program is run for instance with the Unix command cat ghsgraphs graphO ghs reading the graph description data from file graphO in the directory GHSgraphs and writing the results table 1 3 to standard output See also the command int01 cmd in the directory GHStests and start this command to see steps 3 and 4 being executed 1 2 HOW TO USE THE SYSTEM 7 GRAPH Graph0 TYPE UGSLF VERTICES END Breadth first search starting at D CHAPTER 1 INTRODUCTION Part I GHS Functions Chapter 2 Basic Graph Functions 2 1 Problem Description In this chapter the functions which are basic for all graph algorithms are described First of all there is the function readgraphlist which constructs the internal incidence structures of a sequence of graphs from their external representations read in from a file or standard input T
149. ks None Examples See example gen02 c in GHS directory GHStests The example is analogous to example 4 1 3 4 2 saveedset Program Authors Dirk Ahlers and Tobe Toben Universit t Oldenburg Syntax void saveedset EDSET edset char filename Description Writes the line names of a line set to file filename If filename equals NULL the output is written to standard output The output format is such that it can be read by readedset Error Exits Pointer NULL vertex set empty number of elements incorrect Remarks None Examples See example gen02 c in GHS directory GHStests The example is analogous to example 4 1 3 4 3 gset2edset Program Author G nther Stiege Universit t Oldenburg Syntax EDSET gset2edset GSET gset GRAPH graph Description Constructs an line set from a general set Returns a pointer to the set NULL if an error has occurred Error Exits Graph pointer NULL pointer to general set NULL when calling add2edset line with given name not in graph Remarks None Examples Example 3 1 3 4 4 releaseedsetlist Program Author G nther Stiege Universit t Oldenburg Syntax void releaseedsetlist VTSET vtset 3 5 FUNCTIONS FOR GENERAL SETS 35 Description Deletes a list of line sets and frees completely the memory Error Exits None Remarks None Examples Example 3 1 3 4 5 add2edset Program Author G nther Stiege Universit t Oldenburg Syntax void add2edset GRAPH graph EDS
150. ldenburg Syntax int rbtreesize RB tree Description Returns the number of records of the tree given by tree Error Exits None Remarks None Examples None 13 3 8 rbtreenext Program Author G nther Stiege Universit t Oldenburg Syntax RB rbtreenext RB tree RB elem BOOLEAN b int key Description If tree equals NULL b is set to TRUE und NULL is returned Otherwise the record given by elem and key is located in the search tree b is set to FALSE and NULL is returned if the record does not exist If it does exist b is set to TRUE and then the record with the next higher key value is searched for and its address is returned If no reord with higher key value exists NULL is returned Error Exits Indirect system errors if elem equals NULL or an illegal key has been specified Remarks None Examples See example 13 7 page 126 13 3 FUNCTIONS 123 13 3 9 rbtreeprevious Program Author G nther Stiege Universit t Oldenburg Syntax int rbtreeprevious RB tree RB elem BOOLEAN b int key Description If tree equals NULL b is set to TRUE and NULL is returned Otherwise the record given by elem and key is located in the search tree b is set to FALSE and NULL is returned if the record does not exist If it does exist b is set to TRUE and then the rocrd with the next lower key value is searched for and its address is returned If no record with lower key value exists NULL is returned Error Exits Indirect syst
151. lemented 2 3 10 deleteline not yet implemented 2 4 Examples Example 2 1 In this example graphs Graph0 figure 1 2 and Graph1 figure 2 1 are considered Graphl is a general graph showing undirected edges arcs multiple edges arcs and directed as well as undirected loops Its external file description is shown in table 2 2 In addition two modifications of Graphl are also considered Graphla results from Graphl by making all arcs undirected edges whereas Graphlb results from transforming all edges into arcs Program bas01 c table 2 3 shows a main program which reads the 4 graphs Graph0 Graphl Graphla and Graphlb building the internal graph structures and linking the graph structures in a list This is done with the function readgraphlist The graphs are then printed calling function printgrlist with option short Afterwards it is called again this time with option detailed The results are shown in tables 2 4 2 5 2 6 and 2 7 Example 2 2 In this example Graphl figure 2 1 and table 2 2 is constructed using readgraphlist and then all vertices reachable from vertex are written in depth first and breadth first se quence using the options forward and backward to specify the direction in which arcs are allowed to be followed Table 2 8 shows the main program used Table 2 9 contains the results Example 2 3 Program bas03 c in GHStests see also tables 2 10 2 11 and 2 12
152. ment is a vertex of no return then there is exactly one such vertex If it is a strong component all its vertices have root property In any case in general there is more than one simple f path from a vertex with root property to another vertex Condensed Graph and Component Graph STILL TO DO Periods of Components The a period p of a vertex v of a weak component is defined as the greatest common devisor of the lengths of all closed a paths which start and end in v The f period q of a vertex u of a strong component is defined as the greatest common devisor of the lengths of all closed f paths which start and end in u It is not difficult to prove that all vertices of a weak component have the same a period and that all vertices of a strong component have the same f period Therefore the a period of a weak component and the f period of a strong component can be defined based on the period of their vertices The a period of a weak component can only be 1 or 2 If it is 2 the weak component is called bipartite If a strong component contains an edge the f period of the strong component can only be 1 or 2 If it is a pure digraph any f period is possible If the a period f period of a weak strong component is p then the set of vertices of the weak strong component is partitioned into p classes with a cyclic ordering such that every step of an a path f path always passes from one class to the next in the cyclic ordering For more details on pe
153. mpared to char CFR sorted by a number of vertices b smallest line name WCFR sorted as CCFR SCFR sorted as CCFR Minimum line name of cfr CLC sorted by a number of vertices of CLC lines of CLC vertices of stopfree kernel line of stopfree kernel peripheral trees subcomponents internal trees b number of number of number of number of number of number of Pa aa name of largest biblock WCLC sorted as CCLC SCLC sortes as CCLC Internal tree sorted by C 14 SORT KEYS FOR RED BLACK TREES 195 rbtreefind a number of vertices rbtreeinsert b smallest line name getname IINCSQR rbtcomp Cronological order rbtreefind rbtreeinsert RREL rbtcomp List of substructures sorted by rbtreefind a ordering given in RELEMCLASS rbtreeinsert order of substructure not yet implemented for all substructures See also RPCLASS and RREDSTD PCLASS rbtcomp Partition classes ordered by class rbtreefind name The names are not ordered rbtreeinsert lexicographically but numerically getname PECLASS rbtcom EDCLASS by classname char rbreefind PRCLASS rbtcomp Partition classes ordered by class rbtreefind name The names are not ordered rbtreeinsert lexicographically but numerically getname PRECLASS rbtcom REDCLASS by classname char rbreefind RPCLASS rbtcomp Partition classes represented by rbt
154. n Deletes a list of vertex sets and frees completely the memory 3 4 FUNCTIONS FOR EDGE SETS 33 Error Exits None Remarks None Examples Example 3 1 3 3 5 add2vtset Program Author G nther Stiege Universit t Oldenburg Syntax void add2vtset GRAPH graph VTSET pvtset char name Description Adds a new vertex given by its name to a vertex set Creates new vertex set for first vertex Error Exits Vertex with given name not in graph duplicte vertex name to be added Remarks None Examples Example 4 1 page 48 3 3 6 addvtset2vtset Program Author G nther Stiege Universit t Oldenburg Syntax void addvtset2vtset GRAPH graph VTSET pvtset RVERTEX rvt Description Joins two vertex sets of the same graph Error Exits When calling add2vtset Vertex with given name not in graph Remarks None Examples Example 4 1 page 48 3 4 Functions for Edge Sets 3 4 1 readedset Program Authors Dirk Ahlers and Tobe Toben Universitat Oldenburg Syntax EDSET readedset GRAPH graph char filname Description Reads a sequence of names from file filename If filename equals NULL the input is read from standard input The end is indicated by EOF or END Builds the corre sponding set of lines of the graph Returns a pointer to the set NULL if the set is empty or if an error has occurred 34 CHAPTER 3 SETS Error Exits Graph pointer NULL vertex set empty vertex name not from a vertex of the graph Remar
155. nal graph are neither part of the remaining nor of the deleted subgraph With a fixed value of dg the set of edges arcs of the remaining subgraph and the deleted subgraph are a partition of the set of edges arcs of the original graph The subgraphs may have vertices in common a list of these is returned in att The total degree of a vertex of the remaining subgraph is at least dg 1 The total degree of a vertex of the deleted subgraph is bounded only by the maximal total degree of the original subgraph Examples See example gen04 c in GHS directory GHStests In this example the vertices of degree 1 are deleted from graph GHSwords The degree statistics of the original graph the deleted subgraph and the remaining subgraph are printed as well as the list of common vertices of the subgraphs If the lists are printed with option detailed instead of normal one can check that vertex chiff has degree 3 in the deleted subgraph and degree 2 in the remaining subgraph If graphs GHSwords biblock or tree u are used instead of GHSwords the deleted respectively the remaining subgraph is empty 4 3 5 generatefromcomp Program Author G nther Stiege Universit t Oldenburg Syn void generatefromcomp GRAPH graph char gstdname char newname Description gstdname specifies the hierachical name of a decomposition element For hier archical names see subsection 4 1 2 and table 4
156. nburg Syntax void printpathlist PHDR phdr char option char filename 9 3 8 printpathlist Program Author G nther Stiege Universit t Oldenburg Syntax void printpathlist PHDR phdr char option char filename Option must be one of the values short or detailed Description Writes a list of paths organized as red black tree to file filename If filename equals NULL the output is written to standard output For each path the name the mode the directon and the length are written With options detailed a complete list of all lines and vertices of the paths is written too Error Exits None Examples 9 3 9 releasepathlist Program Author G nther Stiege Universit t Oldenburg 9 3 10 simplifypath Program Author G nther Stiege Universit t Oldenburg 9 3 11 generategraphfrompath Program Author G nther Stiege Universit t Oldenburg 9 4 Examples Example 9 1 In this example we again consider Graphl from page 18 Program path01 c of table 9 2 shows how different GHS functions can be used to construct from Graphl an a path through vertices K00 K13 K11 K12 K13 K11 K06 K00 As a first step subpath K00 K13 K11 K06 K00 is built from its external representation using function readgraph The external representation is shown in the upper part of table 9 3 followed by the resulting subpath as output by the program 92 CHAPTER 9 PATHS NOT YET RELEASED In a second step the closed subpath K11
157. ng algorithms see Stiege Stie2006 and Stie2007a Survey of Functions The central function for Menger structures is mengerstr It finds a maximal set of simple paths of a specified mode and a specified direction joining a vertex in VTSOURCE to a vertex in VTSINK It also finds all Menger vertices Menger lines and the corresponding minimal Menger separating sets Function mgprstd is used to output a Menger structure 10 2 Formats and Data Structures For a general description and basic data types see section 2 2 page 11 The data structures specific for Menger structures are described in section C 12 page 184 A Menger descriptor type MGDESCR describes the sets VTSOURCE and VTSINK and the mode and the direction of the Menger structure found It points to a path descriptor type PDESCR where the Menger paths are recorded It also points to a separating descriptor type SEPDESCR where the details of the separating structure are recorded 10 3 Functions 10 3 1 mengerstr Program Author G nther Stiege Universit t Oldenburg MGDESCR mengerstr GRAPH graph VTSET vtsource VTSET vtsink Syntax char mode char direction char name int bound char sep 3To identify z by the index j we chose an arbitrary Menger paths system Po P Py with z on Po and x on Pj 10 3 FUNCTIONS 97 Description Finds a set of maximal cardinality of simple paths joining a vertex in vertex set vtsource to a vertex in vert
158. ns Examples Example 2 3 2 3 4 printgrlist Program Author G nther Stiege Universit t Oldenburg Syntax void printgrlist GRAPH graph char option char filename Option must be one of the values short normal or detailed Description Writes a list of graphs organized as red black tree to file filename If filename equals NULL the output is written to standard output For each graph the name the type and the numbers of vertices edges and arcs are written With options normal or detailed a degree summary is also written Option detailed causes the additional output of a list of vertices with their incident edges arcs 2 8 FUNCTIONS 15 Error Exits None Remarks The field edauxiliary in record type EDGE is used for detection of loops and multiple edges arcs Examples Example 2 1 page 16 2 3 5 printdfs Program Author G nther Stiege Universit t Oldenburg void printdfs GRAPH graph char vname char option char Syntax filename Option must be one of the values forward backward or any Description Writes to file filename in depth first sequence the vertices of graph graph which are reachable from vertex vname If filename equals NULL the output is written to standard output Edges if present are followed in any direction Arcs if present are followed in the direction specified by option The edges arcs followed are also printed as well as the depth level reached Error E
159. ns 6 3 1 astd Program Author G nther Stiege Universit t Oldenburg Syntax void astd GRAPH graph Description Finds the biblock decomposition of a general graph of any type Sets the values for the decomposition elements stopfree kernel peripheral tree internal trees subcomponents biblocks in the corresponding WCOMP records and creates complementary records After successful termination the field grastd of the graph s GRAPH record is set TRUE Error Exits Graph pointer NULL Biblock decomposition already exists Remarks To find the biblock decomposition of a general graph the weak components must be known If they are not function gcomponents page 56 is called implicitly before the a decomposition analysis is done The numbering depends on the specific run of the decomposition algorithms 68 CHAPTER 6 THE BIBLOCK DECOMPOSITION Examples Example 6 1 page 70 6 3 2 aprstd Program Author G nther Stiege Universit t Oldenburg Syntax void aprstd GRAPH graph int stroption char filename Description Writes the the biblock decomposition of a general graph of any type to file filename If filename equals NULL the output is written to standard output The function has the following print options STR Prints complete decomposition structure STRA Prints attachment points but no other vertices and no lines STRR Prints reduced structure No vertices and no lines Note Option STRCS for condensed output i
160. ntext and the subscript can be omitted It turns out that is a partial ordering on the set of Menger vertices Menger lines For given vertices u and v a given type and a given Menger vertex line z there exists a unique Menger set z 21 25 v amp 10 such that for every Menger set 21 72 2 1 it is true 1 paths have no inner vertices in common Note that a set of vertices set of lines f separating u and v need not be a set f separating v and u 96 CHAPTER 10 MENGER STRUCTURES NOT YET RELEASED that lt z for j 1 2 k 1 We call x z 79 22 1 the minimal Menger separating set corresponding to z Sets of Vertices as Sources and Sinks The Menger theorems still hold if instead of vertices u and v nonempty vertex sets U and W are considered This remains true even if elements in U are W are adjacent or if the sets have common elements In these cases mixed separating sets containing both vertices and lines have to be admitted Sometimes it is of interest to find all a paths f paths from U to W which start in U end in W and have no vertices at all in common i e disjoint UW paths This can be achieved by adding two additional vertices to the graph adding edges joining all vertices in U to the first new vertex and all vertices in W to the second new vertex and then applying the corresponding Menger algorithm to the new vertices For a detailed treatment of Menger structures includi
161. o scompvtlist scompedno scompedlist scompdedno scompdedlist scompwattno scompwattlist scomplevel scompperiod pointer to weak component number of vertices list of vertices number of edges list of edges number of arcs list of arcs number of weak attachment points list of weak attachment poits level number 1 not yet assigned level numbering starts with 0 f period of strong component 1 not yet assigned GVTSTD Vertex in a weak and strong decomposition of a general graph gvtstdleft gvtstdright gvtstdpar gvtstdcolor gvtstdauxiliary for future extension gvtstdp gvtstdwcomp gvtstdtype gvtstdscomp gvtstdexdino gvtstdexdilist gvtstdexdono gvtstdexdolist gvtstdlevel gt 5 pointer to vertex pointer to weak component NULL isolated vertex type of vertex 1 not yet assigned 0 isolated vertex 1 internal vertex of external dag no return 2 internal vertex of strong component 3 weak attachment point pointer to strong component NULL not applicable number of incoming external dag arcs list of incoming external dag arcs number of outgoing external dag arcs list of outgoing external dag arcs level number 1 Not yet assigned all vertices of a strong component have the level n
162. o be inserted System error if key class is not allowed Remarks Uses ntreeinsert internally Examples Example 13 2 page 126 13 3 3 ntreedelete Syntax BOOLEAN ntreedelete RB root RB elem int key Description root points to a binary search tree elem indicates the record to be deleted It may be the record itself given by its address or the name of the record Whatever is the case is determined by key see section 13 2 TRUE is returnend if the record has been deleted correctly If the record does not exist FALSE will be returned 13 3 FUNCTIONS 121 Error Exits System error if NULL record is to be deleted System error if key class is not allowed Remarks Deletion is done in the naive way See CormLR1990 Examples See example 13 3 page 1206 13 3 4 rbtreedelete Syntax BOOLEAN rbbreedelete RB root RB elem int key Description root points to a red black tree elem indicates the record to be deleted It may be the record itself given by its address or the name of the record Whatever is the case is determined by key see section 13 2 TRUE is returnend if the record has been deleted correctly If the record does not exist FALSE will be returned Error Exits System error if NULL record is to be deleted System error if key class is not allowed Remarks Deletion is done in such a way that afterwards a correct red black tree remains Examples See examples 13 4 page 126 and 13 5 page 126 13 3
163. o coincide They are called the strong components of the graph GHS functions for determining weak and strong components of a general graph are described in chapter 5 2 a linecomponents are different from 2 a components The former are called subcomponents and the latter biblocks See chapter 6 for details In general graphs 2 f linecomponents and 2 f components also differ Survey of Functions The central function for higher decompositions of a general graph is highcomponents For a given decomposition type internally disjoint paths line disjoint paths a paths f paths sub graphs vertex sets it finds the complete hierarchical decomposition according to equation 11 1 It uses heavily Menger paths see chapter 10 and applies a heuristics called RGB see the literature cited above Function highprst is used to output de decompostions found 11 2 Formats and Data Structures For a general description and basic data types see section 2 2 page 11 The data structures used with the biblock decomposition functions are described in subsection C 8 The main record to describe a biblock decomposition is of type STDGD It is pointed to from the grstruct field in the GRAPH record subsection C 5 The building blocks of a biblock decom position are represented by the data types CFR acyclic component CLC cyclic component and stopfree kernel SUB subcomponent BLB biblock IT internal tree and PT peripheral tree As a generic element
164. of vertices pointer to vertex list number of edges list of edges number of arcs list of arcs number of attachment points list of attachment points number of hinge pointer to list number of hinge pointer to list number of hinge pointer to list points of hinge points points of hinge points points of hinge points Tree for future extensions pointer to WCOMP identifying number IT number of vertices pointer to vertex list number of edges pointer to list of edges number of arcs pointer to list of arcs number of attachment points list of attachment points number of border points pointer to list of border points number of check points pointer to list of check points number of hinge points pointer to list of hinge points PT Peripheral Tree ptleft ptright ptpar ptcolor ptauxiliary ptwcomp for future extensions pointer to WCOMP C 8 DATA STRUCTURES FOR THE BIBLOCK DECOMPOSITION struct t int int RVERTEX int REDGE int REDGE VERTEX avtstd AVTSTD AVTSTD AVTSTD COLOR void VERTEX int BOOLEAN BOOLEAN BOOLEAN int REDGE int REDGE int REDGE PT int REDGE int REDGE int REDGE IT int ptnumber ptvtno ptvtlist ptedno ptedlist ptdedno ptdedlist ptbor
165. of vertices number of edges list of edges number of arcs list of arcs number of biblocks pointer to list of biblocks number of attachment points list of attachment points number of border points pointer to list of border points number of hinge points pointer to list of hinge points number of check points pointer to list of checkpoints for future extensions pointer to SUB identifying number BLB 177 178 int RVERTEX int REDGE int REDGE int RVERTEX int RVERTEX int RVERTEX int RVERTEX struct itstr t IT IT IT COLOR void WCOMP int int RVERTEX int REDGE int REDGE int RVERTEX int RVERTEX int RVERTEX int RVERTEX struct ptstr PT PT PT COLOR void WCOMP APPENDIX C GHS INTERNAL DATA STRUCTURES blbvtno blbvtlist blbedno blbedlist blbdedno blbdedlist blbattno blbattlist blbborno blbborlist blbcheno blbchelist blbhinno blbhinlist IT Internal itleft itright itpar itcolor itauxiliary itwcomp itnumber itvtno itvtlist itedno itedlist itdedno itdedlist itattno itattlist itborno itborlist itcheno itchelist ithinno ithinlist number
166. ogram a main program in C using the appropriate functions from the GHS library 3 Compile the program using the library in GHScorelib Using GHS under Windows is not described in this manual 1 2 HOW TO USE THE SYSTEM 5 4 Run the program and evaluate the results The second way is starting the Graphical User Interface for GHS GHSgui GHSgui is not described in this manual The programmer s way is best explained by an example Assume that we want to read the undirected graph Graph0 of figure 1 2 print it as raw graph and than print its vertices in GRAPH GraphO TYPE UGSLF VERTICES B A C E D F EDGES h A B C E f B C _e A C g C D C F i D F i END Figure 1 2 Graph0 breadth first sequence starting at vertex D Step 1 The graph must be available in a computer readable format in a file GHS assumes files in ASCII code with a simple structure At the right side of figure 1 2 a file representation of the Graph Graph0 is shown It consists of key words which start with a sign the name and the type of the graph the list of vertices and the list of lines divided in list of edges and list of arcs For each line the line name starting with _ and both its end points are listed A detailed description of the GHS graph file format is given in section 2 2 page 11 In the case of our example the graph file can easily be written manually In the case of larger and more complex graphs the files may come from
167. ollowing the definitions and properties of weakly connected components and strongly connected components are summarized For more details see Stiege Stie2007a and Stie2006 The algorithms used by GHS can be found there too Paths We consider three kinds of paths f paths b paths and a paths f stands for forward b for backward and a for any An f path is a sequence vo 1 01 l1 v2 AE Un_1 In Un with n gt 1 l is a an edge or an arc If l is an edge v _ is one of its end points and vj is the other end point If l is an arc vj_1 is its head and vj is its tail b paths and a paths are defined accordingly A path is closed if vg ux otherwise it is open path is simple if all v are pairwise distinct with the exception of the first and the last vertex of a closed path A path is edge simple if all 1 are pairwise distinct A closed simple and edge simple path is a circuit We distinguish f circuits b circuits and a circuits A sub graph with no f circuits is called f acyclic otherwise it is called f cyclic b acyclic b cyclic and a acyclic a cyclic graphs are defined accordingly Vertex v is f reachable b reachable a reachable from vertex u if there is an f path b path a path from u to v Note In this chapter paths are mere graph theoretic entities used to define weakly and strongly connected components and to establish their properties However paths exist in GHS also as objects in their own right For details s
168. omposition conceptually require numerous linked lists lists of vertices lists of edges incidence lists etc which frequently are processed in sequence On the other hand there is the need to rapidly find an element in these lists by its key value To cope with both requirements the decision has been made to consistently use red black trees and the experience with these trees has been completely satisfactory In former versions of GHS only a reduced set of functions for red black trees had been implented The actual version comprises a complete set of operations for red black trees It also includes naive inserting and naive deleting so that non balanced search trees can be buildt and ma nipulated The actual implementation of the algorithms follows closely Stie2009 which in turn is based largely on Cormen Leiserson Rivest CormLR1990 For the differences between older versions and the actual version see section 13 4 Note on Compatibility The following set of operations have been implemented ntreeinsert Naive insertion of a new record to a general binary search tree If there is already a record with the same key value in the tree the new record is not inserted and the calling program is notified rbtreeinsert A new record is inserted into a red black tree If there is already a record with the same key value in the tree the new record is not inserted and the calling program is notified ntreedelete Naive deleti
169. on C 4 2 page 165 in the appendix Error Exits None Remarks None Examples Example 3 1 3 5 6 gsetintersect Program Author G nther Stiege Universit t Oldenburg Syntax GSET gsetintersect RB lista int keya RB listb int keyb Description Creates a new general set as the set intersection of the two red black trees see chapter 13 given by lista and listb The elements of the general set are names of the records of the red black trees Key class keya must be such that function getname is possible with records of lista Key class keyb must be such that function rbtreefind must be possible in listb with a character string as compare value see subsection C 4 2 page 165 in the appendix Error Exits None Remarks None Examples See example gen03 c in GHS directory GHStests 38 CHAPTER 3 SETS 3 5 7 gsetdiff Program Author G nther Stiege Universit t Oldenburg Syntax GSET gsetdiff RB lista int keya RB listb int keyb Description Creates a new general set as the set difference between the red black tree see chapter 13 given by lista and the red black tree given by listb The elements of the general set are names of the records of the red black trees Key class keya must be such that function getname is possible with records of lista Key class keyb must be such that function rbtreefind must be possible in listb with a character string as compare value see subsection C 4 2 page 165 in the appendix
170. on of a record given by its key from a general binary seach tree rbtreedelete A record given by its key is removed from the red black tree A correct red black tree remains rbtreefind A record with a given key value is searched for in the tree If the record exists its address is the return value Otherwise NULL is returned 118 CHAPTER 13 RED BLACK TREES rbtreepfind A record with a given key value is searched for in the tree If the record exists its address is the return value If such a record does not exist and the provided key value is not greater then the largest existing key value and not smaller than the smallest existing key value the record with the next lower key value is returned Otherwise NULL is returned rbtreesize Returns the number of records in the tree rbtreenext For a given record finds the record with the next higher ordering value NULL if such a record does not exist rbtreeprevious For a given record finds the record with the next lower ordering value NULL if such a record does not exist rbtreemin Finds the record of the tree with minimum ordering value i e the left most record rbtreemax Finds the record of the tree with maximum ordering value i e the right most record In addition to the functions mentioned above there exist in GHS the following service functions related to trees printorder Prints the names of the records of a red black tree a general binary sarch tree in a
171. ot included in any class For more details see example 8 1 page 85 Function add2edpart which adds a new class to a general partition function add2class which adds a new edge to a class of a general partition function releaseedpartlist which deletes a list of partitions function generatefromclass which generates a new graph form an edge class and printing functions prpartstr and prpartvted complement the set of functions 8 2 Formats and Data Structures For a general description see section 2 2 page 11 The data structures used with general edge partition functions are listed in subsection C 10 page 183 Records of type EDPART describe partitions records of type EDCLASS describe edge classes The partition specific properties of a vertex are recorded in an instance of type PARTVT for edges type PARTED is used To represent records of these data types in different additional roles the data types REDCLASS RPARTV and RPARED are used 8 3 Functions 8 3 1 edpartgen Program Author G nther Stiege Universit t Oldenburg Syntax EDPART edpartgen GRAPH graph RVERTEX vtlist REDGE edlist Description Builds the strict edge partition generated from a list of limiting vertices vtlist and a list of limiting edges edlist Two edges belong to the same class if both lie on a path with no internal vertex from vtlist and no edge from edlist The path must start in a vertex from vtlist or in an endpoint of an edge from edlist Creates an E
172. pfind RB tree RB elem rbtree c int key int rbtreesize RB tree rbtree c RB rbtreemin RB tree rbtree c RB rbtreemax RB tree rbtree c RB rbtreenext RB tree RB elem rbtree c C 3 FUNCTIONS AND GLOBAL VARIABLES RB void void BOOLEAN void char void void void void void void void void void void void void void void int key rbtreeprevious RB tree RB elem int key printorder FILE fd RB ndx int key char ftext printrbtree FILE fd RB ndx int level int key testtree FILE fd RB root int key char option getname RB ndx int key getcharname RB ndx char comptype Queues and Stacks enqueue QUSTA qusta void qelem fenqueue QUSTA qusta void qelem push QUSTA qusta void qelem fpush QUSTA qusta void qelem dequeue QUSTA qusta fdequeue QUSTA qusta qfront QUSTA qusta qend QUSTA qusta pop QUSTA qusta fpop QUSTA qusta top QUSTA qusta qscreate RB list qsremove RB list releasequstalist QUSTA qusta C 3 2 Implicit Functions rbtree c rbtree c rbtree c rbtree c rbtree c rbtree c qusta qusta qusta qusta qusta qusta qusta qusta qusta qusta qusta qusta qusta util c oc co Gy 00000000090
173. ponding to a weak component and the one corresponding to one of its strong components The biblock decomposition is applied to that strong component PK RK k ak ak ak ak 3k 3k ak ak a 3K 3K 3K aK ak a 3K 3K 3K K aK aK 3K 3K 3K K aK aK 2K 3K 3K K aK K 2K 3K 3K K I aK K 3K include lt stdio h gt include lt GHSstructure h gt int main GRAPH ograph graph stronggraph ograph readgraphlist NULL gcomponents ograph gprstd ograph STRR NULL graph generatefromcomp ograph wcompgraph WCOMP12 wcompgraphi2 if graph NULL printf Connot generate subgraph Wn exit 0 astd graph gprstd graph STRR NULL aprstd graph STRR NULL stronggraph generatefromcomp graph wcompgraph12 WCOMPO SCOMP3 wcompgraph12 3 astd stronggraph aprstd stronggraph STRR NULL return 0 Table 6 5 Program acomp02 c 76 CHAPTER 6 THE BIBLOCK DECOMPOSITION GRAPH wcompgraphi2 TYPE GG No VERTICES No_EDGES No_ARCS No_ISOLATED_VERTICES No_WEAK_COMPONENTS No_A ACYCLIC_WEAK_COMPONENTS_WITHOUT_STRONG_COMPONENTS No_A ACYCLIC_WEAK_COMPONENTS_WITH_STRONG_COMPONENTS No_A CYCLIC_WEAK_COMPONENTS_WITHOUT_STRONG_COMPONENTS No_A CYCLIC_WEAK_COMPONENTS_WITH_STRONG_COMPONENTS ALL STRONG COMPONENTS F ACYCLIC No A CYCLIC WEAK COMPONENTS WITH STRONG COMPONENTS 20V 11E 144 F CYCLIC STRONG COMPONENTS EXIST WEAK COMPONENT wcompgraphi2 WCOMPO 20V 11E 14
174. ppar COLOR sepcolor void sepauxiliary for future extensions C 13 Data Structures for the Higher A Decomposition k 3k ok sk ok sk ok sk ok sk ak ak ak ak ak oko OR ak ak ak ak ak 2 kk kk kkk kk kk 2 HSTDD Weak and strong components C 11 1 185 186 APPENDIX C GHS INTERNAL DATA STRUCTURES Component vertex set C 11 2 higher decomposition TBP to be processed records KKR 2K 3K 3K K aK aK 2K 3K 3K 3K aK aK K 3K 3K K aK K 3K 3K 3K K K K 3K 3K 3K K K K FK 24 KKK K K struct hstdd GSTDD Weak and strong components HSTDD hstdleft HSTDD hstdright HSTDD hstdpar COLOR hstdcolor void hstdauxiliary for future extensions GRAPH hstdgraph pointer to graph HVTSTD hvtstdlist red black tree of HVTSTD records int hsggano number of a components BLB hsggalist list of biblocks containing a components int hsggalno number of a linecomponents SUB hsggallist list of subcomponents containing a linecomponents int hvsgano number of maximal a connected vertex sets BLB hvsgalist list o
175. r Stiege Universit t Oldenburg Syntax void qsremove RB rb Description Removes and deletes all QS records pointed to by the elements of red black tree rb Remarks None Error Exits None Examples See example qusta01 c in GHStests 14 3 14 mnewqusta Program Author G nther Stiege Universit t Oldenburg Syntax QUSTA mnewqusta char message Description Creates a new QUSTA record Remarks message is printed if there is not enough memory available Error Exits System error if there is not enough memory available Examples See example qusta01 c in GHStests 14 3 15 releasequstalist Program Author G nther Stiege Universit t Oldenburg 146 CHAPTER 14 STACKS AND QUEUES Syntax void releasequstalist QUSTA qusta Description Releases a red black tree of QUSTA records Each QUSTA record is deleted Note If there are QS records the QUSTA record points to see figure 14 1 these are not released Remarks To achieve a correct deallocation of memory one has to proceed the following way 1 Simultaneously multiple membership The user program must empty the stack queue com pletely using pop dequeue 2 Membership attributes The QS records must be deleted explicitly by calling qsremove Error Exits None Examples See example qusta01 c in GHStests 14 4 Examples See example qusta01 c in GHStests Part II Appendix to User Manual Appendix A GHS Makefile Hkk k k k k k ok ok
176. r reading graph s n graph gt grname Table 2 10 Program bas03 c Part I 28 CHAPTER 2 BASIC GRAPH FUNCTIONS strcpy buffer bl Graphla graph readgraphlist buffer if graph NULL printf Incorrect graph input n exit 0 h rbtreeinsert RB amp graphlist RB graph GRNM printf 81d int ghsmemsize printf Memory after reading graph s n graph gt grname strepy buffer bl GHSwords graph readgraphlist buffer if graph NULL printf Incorrect graph input n exit 0 h rbtreeinsert RB amp graphlist RB graph GRNM printf 81d int ghsmemsize printf Memory after reading graph s n graph gt grname strcpy buffer bl Graphib graph readgraphlist buffer if graph NULL printf Incorrect graph input n exit 0 h rbtreeinsert RB amp graphlist RB graph GRNM printf 81d int ghsmemsize printf Memory after reading graph s n graph gt grname graph GRAPH rbtreefind RB graphlist RB GraphO GRNC graphO cpchtp graph UGSLF Newgraph0 printf 81d int ghsmemsize printf Memory after copying graph GraphO to Newgraph0 n graph GRAPH rbtreefind RB graphlist RB Graphib GRNC graphib cpchtp graph DG Newgraphib printf 8ld int ghsmemsize printf Memory after copying graph Graphib to Newgraphib n graph GRAPH rbtreefind RB graphlist
177. ral tree stopfree kernel subcoponent internal tree biblock use the function generatefromcomp of chapter 4 page 47 6 2 Formats and Data Structures For a general description and basic data types see section 2 2 page 11 The data structures used with the biblock decomposition functions are described in subsection C 8 page 176 The main record for each stopfree kernel is of type WCOMP i e a record describing a weak component This record also describes the stopfree kernel and has pointers to lists of PT records peripheral trees SUB records subcomponents IT records internal trees and BLB records biblocks With data type AVTSTD biblock decomposition properties of a vertex e g kind of attachment point are recorded In the same way records of type AEDSTD are used for edges arcs Edges arcs a vertex is incident with may belong to more than one biblock hinge point Records of type INCSQR indicate the biblocks a vertex is element of Several enumeration types are used by the biblock decomposition functions mostly for internal purposes Remark 6 1 Peripheral trees within a weak component are numbered These numbers are used as identifiers The same applies to subcomponents and internal trees Within a subcomponent the biblocks are numbered These numbers are used as internal identifiers The complete identification of an element of the biblock composition is its name as specified in table 4 1 page 44 6 3 Functio
178. raph prstd graph STRCS prstd graph STR prstdvt graph VPV prbiblocktrees graph return 0 Table 11 1 Program 5 1 106 CHAPTER 11 HIGHER DECOMPOSITIONS NOT YET RELEASED Checking biblock decomposition of graph Graph2 TYPE UGSLF OK OK OK OK OK OK No VERTICES 40 No_EDGES 44 No isolated vertices correct Incidences from vertices to edges correct Numbers of vertices and edges in proper components correct Attachment points correct Edges correct SUB BLB correct End of checking biblock decomposition of graph Graph2 BEGIN CONDENSED STRUCTURE GRAPH Graph2 TYPE UGSLF 2 92 92 SF 2 No_VERTICES No_EDGES No_ISOLATED_VERTICES No_ACYCLIC_COMPONENTS No_CYCLIC_COMPONENTS No_PERIPHERAL_TREES No_STOPFREE_KERNELS No_SUBCOMPONENTS No_BIBLOCKS No_INTERNAL_TREES No_ATTACHMENT_POINTS No_BORDER_POINTS No_CHECK_POINTS No_HINGE_POINTS ND CONDENSED STRUCTURE P KO 5V 4E 34V 40E N OQ N Ol OI Q F N PF PB Table 11 2 Results of Program 5 1 Part I 11 4 EXAMPLES 107 BEGIN COMPLETE STRUCTURE GRAPH Graph2 TYPE UGSLF No VERTICES No_EDGES No_ISOLATED_VERTICES h No_ACYCLIC_COMPONENTS ACYCLIC_COMPONENT _10 11 VERTICES io il i2 i3 i4 EDGES _10 11 _11 11 _12 13 _13 14 No_CYCLIC_COMPONENTS 34V 40E CYCLIC_COMPONENT _ 0 1 34V 40E 5AP 2BP 3CP 2HP No_PERIPHERAL_TREES 2 PERIPHERAL_TRE
179. raph must have a name which is a string not starting with or Each graph must have a type which is one of the values GG DG DGS DGSLF UG UGS UGSLF GG general graph Mixtures of edges and arcs are allowed mul tiple edges and or arcs are allowed loops including multiple loops are allowed UG undirected graph Only undirected edges are allowed Multiple edges including multiple loops may occur UGS undirected graph single edges Only simple edges are al lowed Simple loops may occur UGSLF undirected graph single edges loop free Only simple edges are allowed Loops are forbidden DG DGS DGSLF Directed versions of UG UGS UGSLF Only arcs i e directed edges are allowed Vertices are specified by their names Vertex names are strings whose first character must not be or Vertex names must be unique within a graph A graph must have at least one vertex Edges are specified by their names Edge names are strings whose first character must be Each edge name must be fol lowed by two vertex names the names of its end points Edge names must be unique within a graph They must also be dif ferent from all arc names of the graph The number of edges of a graph may be 0 Arcs are specified by their names Arc names are strings whose first character must be Each arc name must be followed by two vertex names the first of which specifies the start point of the arc head whereas the
180. rc C 10 Data Structures for General Partitions k 3 ok sk ok sk ok sk ok sk ak ak PK ak ak ak ak OR ak OR R ak ak OF ok kkk kk kk 2k K K EDPART Line partition EDCLASS Line class of a partition REDCLASS Role of line class in a partition PARTVT Vertex in line partition RPARTVT Role of vertex in an line partition PARTED Edge in a an line partition RPARTED Role of line in a partition k 3k ok sk ok sk ok sk ok sk ak ak Pk ak ak ak ak OR ak ak ak ak oko ak ak ak ak 6 kk kk kk 2 C 11 Data Structures for Paths k 3k ok sk ok sk ok sk ak sk ak ak ak ak ak oko OR ak OR kk kkk kk kk kkk PHDR Path header PTHA Arc on a path DRC ok sk ok sk ak sk ak ak ak ak ak oko oR ak ak ak kk kkk kk kk 2k K K struct phdrstr PHDR header record of a path 1 PHDR phleft PHDR phright PHDR phpar COLOR phcolor void phauxiliary for future extensions char phname name of the path GRAPH phgraph pointer to graph 183 184
181. record s auxiliary field and a link from the QS record to the original record in the QS record s qsp field Each QS record provides two integer fields two Boolean fields and a void pointer in which the calling program may keep membership dependent information In figure 14 1 only the void pointer extension is shown Remark 14 1 On the one hand as figure 14 1 shows each QUSTA record is both header structure of a queue and header structure of a stack which can be operated on independently On the other hand each QS record has two forward links and two backward links not shown in the figure One pair is used in queues and the other pair is used in stacks Therefore the same QS record may appear in a queue and in a stack with identical or different QUSTA headers This case is not a multiple membership 14 3 FUNCTIONS 141 14 3 Functions 14 3 1 push Program Author G nther Stiege Universit t Oldenburg Syntax void push QUSTA stack void qelem Description Puts element qelem on top of stack qelem may be an element of any GHS type given by its address casted to void qelem is not linked directly into the the stack list Instead a new QS record is created which points to qelem The QS record remains invisible to the calling program Normally elements put on the stack with push should be removed from the stack using pop and not fpop Multiple membership is allowed Error Exits Error if NULL record is to be pushed onto stack R
182. reefind RELEM records ordered by rbtreeinsert class name getname SSTCS rbtcomp STCS compared to rbtreefind STCS rbtreeinsert getname SSCTCS rbtcomp STCS rbtreefind compared to char HHDC rbtcomp HCOMP compared to rbtreefind HCOMP by HCOMP rbtreeinsert name getname Note The name of a HCOMP record is a character string of a hierarchical structure It consists of two or more substrings separated by one or more blancs The first substring is the biblock name Then a possibly empty sequence of component candidate numbers In case of a candidate the number is inmediatly followed by the string CAND A cocomponent or cocandidate has no number but 196 APPENDIX C GHS INTERNAL DATA STRUCTURES the string C as name The component numbers are noted as strings but have numerical sort order E g nameofbiblock 1 3 12 is greater than nameofbiblock 1 3 4 TTBP getname for name purposes only NHDC rbtcomp HCOMP compared to char endif List of Figures 11 GHScore Directory 4 1 2 GYGDRhU X seeded rst eR dE NIE UNE ed REGUM sae 5 2k dee A Eee deed ct oo CR Eh v ND dog s eb duum 18 Dale Weompgraph y 3o DA e Mes 2 ku ba s Q uds 59 6 1 Examples of closed paths los ra SOR OE ne Rede 63 6 2 Biblock decomposition of a general graph 2l 64 6 35 Ugraplilo zs s at a otav oec att ais e a
183. releasegraphlist GRAPH graph util c void printgrlist GRAPH graph char option basics c char filename void printdfs GRAPH graph char vname basics c char option char filename void printbfs GRAPH graph char vname basics c char option char filename void dfsstructure GRAPH graph char vname basics c char option void releasedfs GRAPH graph util c Sets VTSET readvtset GRAPH graph char filename gsets c VTSET gset2vtset GSET gset GRAPH graph gsets c void savevtset VTSET vtset char filename gsets c void releasevtsetlist VTSET vtset util c void add2vtset GRAPH graph gsets c VTSET pvtset char name void addvtset2vtset GRAPH graph gsets c VTSET pvtset RVERTEX rvt EDSET readedset GRAPH graph char filename gsets c EDSET gset2edset GSET gset GRAPH graph gsets c void saveedset EDSET edset char filename gsets c void releaseedsetlist EDSET edset util c void add2edset GRAPH graph gsets c EDSET pedset char name void addedset2edset GRAPH graph gsets c EDSET pedset REDGE red C 3 FUNCTIONS AND GLOBAL VARIABLES GSET void void BOOLEAN GSET GSET GSET GRAPH GRAPH GRAPH void GRAPH GRAPH void void void void BOOLEAN void void readgset char filename savegset GSET g
184. riods in graphs see Stiege St1e2006 and Stie2007a 5 1 1 Survey of functions The main function of this chapter is gcomponents It finds the weakly connected and strongly connected components of a general graph Function gprstd is used to print the structure found by gcomponents A list of vertices is printed with gprstdvt To generate a subgraph from a decomposition element weak component strong component external dag function generatefromcomp page 47 of chapter 4 is used 5 2 Formats and Data Structures For a general description and basic data types see section 2 2 page 11 The data structures used with the decomposition into weak and strong components are described in subsection C 7 page 172 The main record to describe the decomposition into weak and strong components is of type GSTDD It is pointed to from the grgstruct field in the GRAPH record subsection C 5 The decomposition elements of a general graph are represented by the data types WCOMP weak component and SCOMP strong component With data type GVTSTD general vertex properties corresponding to weak and strong components e g weak attachment point are recorded In the same way records of type GEDSTD are used for edges arcs 56 CHAPTER 5 WEAK AND STRONG COMPONENTS Remark 5 1 Weak components of a general graph are numbered These numbers are used as identifiers Within a weak component the strong components are numbered These numbers are used as internal id
185. rogram Author G nther Stiege Universit t Oldenburg 14 CHAPTER 2 BASIC GRAPH FUNCTIONS Syntax void savegraphlist GRAPH graphlist char filename Description Writes a list of graphs organized as a red black tree to file filename If filename equals NULL the output is written to standard output For each graph of the list its incidence structure is output in GHS external graph format so that it can be read again by readgraphlist Error Exits List pointer NULL Graph has no vertices Remarks None Examples Section 1 2 especially table 1 3 page 7 2 3 3 releasegraphlist Program Author G nther Stiege Universit t Oldenburg Syntax void releasegraphlist GRAPH graphlist Description graphlist points to the root of the tree Releases a list of graphs organized as red black tree with all its vertices and edges freeing completely the memory Additional decomposition structures of the graph for instance the biblock decomposition see chapter 6 page 63 are also released without any warning Error Exits Graph pointer NULL Warning Remarks Releasing graphs must be done with care During processing a series of dependent structures like paths or Menger structures may have been created These point to the graph they have been derived from but there is no pointer from the graph to them So they cannot be deleted automatically together with the graph but must be released explicitly by the user program using the pertinent functio
186. rom graph graph an internal path description path header and path menbers is created A pointer to the path header is returnend by the function Returns NULL if an error ocurred Lines are added to the path being contructed at the start if POSITION indicates S They are added at the end if POSITION indicates E Error exits Remarks 1 The path maybe of length 0 i e plinelist see table 9 1 page 88 is empty 9 3 6 readpathlist Program Author G nther Stiege Universit t Oldenburg Syntax PHDR readpathlist GRAPH graph char filename Description Reads a sequence of external path descriptions Table 9 1 from file filename If filename equals NULL the path descriptions are read from standart input Using vertices and lines from graph graph for each path in external format an internal path description path header and path members is created The path header is inserted into a list The list is organized as red black tree sorted by path name A pointer to the list is returnend by the function Returns NULL if an error ocurred Lines are added to the actual path being contructed at the start if POSITION indicates S They are added at the end if POSITION indicates E Error exits 9 4 EXAMPLES 91 Remarks 1 All external paths descriptions must refer to the same graph 2 A path may be of length 0 i e plinelist see table 9 1 page 88 is empty 9 3 7 savepathlist Program Author G nther Stiege Universit t Olde
187. rting with and not starting with _ GG DG DGS DGSLF UG UGS UGSLF lt graphname gt lt edgename gt sep lt vertername gt sep lt vertername gt string starting with _ and not containing characters from lt sep gt 154 APPENDIX B GHS EXTERNAL DATA STRUCTURES Appendix C GHS Internal Data Structures k 3k k sk ok sk ok sk ok sk ak ak ak ak ak oko OR ak ak ak OR Ra FOR ak R OR kkk 2k 24 kk kk kk kkk kk kk kkk Data Structures for the Graph Handling System GHS Guenther Stiege Oldenburg 3a ka ak ak aka ak ae ak aa ak ak ara aka ak ak ara a ak aka ak ara ak ak ak ICI I III A GHSstructure h Common Data Structure for GHS Programs comments of type LaTeX for texing purposes only k sk ok sk ok sk ok sk ok sk ak ak Pk ak ak ak ak OR ak OR ak PK ak ak ak kkk kk kk kk kk kkk kk kkk K K C 1 General Organization Scheme General Partitions Paths Menger Structures Higher A Decomposition Distances 1 Utilities 1 1 General Services 1 Red Black Trees 1 3 Stacks and Queues 2 Basic Graph Functions 3 Sets 4 Graph Generating Functions 5i Weak and Strong Components 6 Biblock Decomposition T Additional DFS Structure 8 9 7 SS 156 APPENDIX C GH
188. s File descriptor fd is NULL nothing is printed Examples Examples 13 1 page 126 13 2 Remarks The file descriptor fd must have been set by fopen or alternately to stdout 13 3 15 getname Program Author G nther Stiege Universit t Oldenburg Syntax void getname RB ndx int key Description The name of the record pointed to by is provided The name is not the return value of the function but is available as a character string in the global array namebuffer Error Exits System error if ndx is NULL System error if key class is not allowed Remarks None Examples See example 13 10 page 127 and example 13 11 page 127 13 3 16 getcharname Program Author G nther Stiege Universitat Oldenburg Syntax void getcharname RB ndx char comptype Description The charname of the decomposition element pointed to by ndx and specified by comptype is provided as a pointer to the corresponding line name edname See also subsection 4 1 2 page 43 on names and addresses comptype must be specified as one of the following strings WCOMP weak component SCOMP strong component EXD external dag STP stopfree kernel PT peripheral tree LET internal tree SUB subcomponent BLB biblock Error Exits System error if ndx is NULL System error if comptype is NULL or has illegal value Remarks None Examples See example 13 11 page 127 126 CHAPTER 13 RED BLACK TREES 13 4 Note on Compatibility 1
189. s not provided with function aprstd See function gprst page 56 instead Error Exits Illegal print option Graph pointer Null Biblock decomposition does not exist Remarks A line like CYCLIC WEAK COMPONENT Ugraphi WCPOMP1 34V 40E OA 2BP 3CP 2HP is to be read The a cyclic weak component with name Ugraphi WCOMP1 consists of 34 vertices 40 edges and 0 arcs 5 of the vertices are attachment points of which 2 are border points 3 are check points and 2 are hinge points For name conventions see subsection 4 3 5 page 47 See also remark 5 1 page 56 and remark 6 1 page 67 Examples Example 6 1 page 70 6 3 3 aprstdvt Program Author G nther Stiege Universit t Oldenburg Syntax void aprstdvt GRAPH graph int poption char filename Description Writes to file filename a list of vertices ordered by degree and vertex name with biblock decomposition information about the vertex and the edges arcs incident with it If filename equals NULL the output is written to standard output Has the following print options 6 3 FUNCTIONS 69 VPV All vertices VPA All attachment points VPB All border points VPC All check points VPH All hinge points VPBC vertices which are border points and check points but not hinge points VPBH vertices which are border points and hinge points but not check points VPCH vertices which are check points and hinge points but not border points VP
190. scending order printrbtree Prints the actual structure of a red black tree a general binary sarch tree testtree Tests wether the tree given by its root is a correct binary search tree Optionally it is also tested wether it is a correct red black tree getname This function returns the name of an object when the address of the corresponding record is given The function does not use any tree structure and is included in the present chapter only because it uses the same definitions of key values and key classes see next section getcharname This function returns the charname of a decomposition element see subsection 4 1 2 page 43 on namesd and addresses This function uses neither tree structures nor key lasses It is included in the present chapter for its relationship to getname 13 2 FORMATS AND DATA STRUCTURES 119 13 2 Formats and Data Structures To handle red black trees in a uniform manner the generic date type RB has been introduced struct rbtree RB RB 1eft RB right RB par COLOR color void auxiliary F The definitions of almost all records in the GHS data structures start with these five fields and thus these records can be inserted and searched for in red black trees To handle the large number of different search criteria the enumeration type SORTKEY has been included into the file GHSstructure h see section C 14 page 189 The values of this data type indicate a key class
191. second specifies the end point tail Arc names must be unique within a graph They must also be different from all edge names of the graph The number of arcs of a graph may be 0 Table 2 1 External File Format of GHS Graphs 2 8 FUNCTIONS 13 Internal data structures The internal data structures used by GHS functions are specified in the file GHSstructure h which must be included in each GHS program Chapter C page 155 in the appendix contains a complete listing GHSstructure h is divided into subsections In the first subsection some constants and all com mon types are defined The second subsection contains C function definitions and the definition of global variables The remaining subsections describe data structures specific to a group of GHS functions In general these data structures are defined as records using the C statement struct For easier programming some enumeration types have been introduced too Most of the record types also called data types are suitable to be handled in a uniform manner as elements of red black trees see chapter 13 page 117 All fields of a record type have a fixed mode and a fixed semantic meaning Occasionally a different mode or a different meaning is used with a field If this is the case it is mentioned explicitly in the corresponding function description under remarks Most record types have an auxiliary field of mode void which is explicitly reserved for variable applications an
192. seti char filenema releasegsetlist GSET gset add2gset GSET pgset char name gsetunion RB lista int keya RB listb int keyb gsetintersect RB lista int keya RB listb int keyb gsetdiff RB lista int keya RB listb int keyb Graph Generating Functions generatefromvt GRAPH oldgraph char newname RVERTEX rvt generatefromed GRAPH oldgraph char newname REDGE red cpchtp GRAPH graph char newtype char newname degreedelete GRAPH oldgraph GRAPH delgraph char delname GRAPH remgraph char remname VTSET att int dg generatefromcomp GRAPH oldgraph char gstdname char newgraph generatefromchnm GRAPH oldgraph char gstdname char newgraph Weak and Strong Components gcomponents GRAPH graph gprstd GRAPH graph int stroption char filename gprstdvt GRAPH graph int poption char filename Bibloc Decomposition astd GRAPH graph generateblbgraph GRAPH graph char filename aprstd GRAPH graph int stroption char filename aprstdvt GRAPH graph int poption char filename Path Functions gsets c gsets c utilc gsets c gsets c gsets c gsets c generate c generate c cpcht c generate c generate c generate c gcomponents c gstdutil c gstdutil c astd c astd c astdutil c astdutil c
193. sets of vertices and sets of lines Functions to copy a graph and adapt it to a new type Functions to generate subgraphs where all vertices up to degree n have been deleted Chapter 5 Weak and Strong Components Programs for finding weakly and strongly connected components in gen eral graphs 2 CHAPTER 1 INTRODUCTION Chapter 6 The Biblock Decomposition A function which decomposes the cyclic weak connected components of a general graph of any type into a stopfree kernel the peripheral trees the subcomponents the internal trees and the biblocks In a general graph the direction of arcs is ignored and the a cyclic weak components are decomposed Print functions A Functions for generating the biblock graph Chapter 9 Paths not yet released Chapter 10 Menger Structures not yet released Chapter 11 Higher Decompositions not yet released Chapter 13 Red Black Trees Inserting a record into a red black tree Searching a record in a red black tree Printing red black trees Providing the name of an object given its record Though not graph functions in the strict sense a complete set of funtions on binary trees has been added Chapter 14 Stacks and Queues Push pop top enqueue dequeue Variants a Multiple simultaneous membership allowed and membership attributes not allowed b Mul tiple simultaneous membership not allowed and membership attributes allowed Care has been taken to complement each
194. specific data structures and may be manipulated by specific GHS functions Survey of Functions A path header for a new path is created by newphdr A line is added to a path with insert line2path It is removed by removelinefrompath Function insertpath2path inserts a path into another path A path is read from a file or standard input with readpath it is written to a file or standard output by savepath If several paths are to be read or written functions readpathlist respectively savepathlist are to be used The lists are organized as red black trees Function releasepathlist is used to release a list of paths Function printpath or printpathlist is used to print paths 9 2 Formats and Data Structures For a general description and basic data types see section 2 2 page 11 The special data structures corresponding to paths are described in subsection C 11 page 183 A path header type PHDR describes a path a member record type PTHA stands for each occurrence of a line in the path As shown in figure 9 1 the member records are organized as a PHDR PTHA PTHA S PTHA Figure 9 1 Paths as linked lists doubly linked list The list indicates the path direction The field pddir in the header indicates the allowed direction of lines in the paths i e whether we have a paths f paths or b paths External file format Files which represent paths in external GHS format are organized as shown in table 9 1 88 CHAPTER 9 PATHS N
195. st of RVERTEX records ordered by 1 2 by vertex name For future extensions name of vertex graph vertex belongs to degree of vertex no of undirected edges Undirected loops counted only once Kok k sk kok okk k k kok k k k k kk k k k K KRK K K K K KK K k indegree of vertex outdegree of vertex pointer to incindence list undirected edges pointer to incindence list incoming arcs pointer to incindence list outgoing arcs decomposition extension of record weak and strong components decomposition extension of record biblock decomposition decomposition extension of record higher decompositions extension record for additional dfs structure pointer to attribute structure type of attribute structure 1 No attribute structure 0 User specific attributes not supported by GHS Attributes supported by GHS none at the time 169 170 RVERTEX COLOR void VERTEX 33 struct 1 edstr EDGE EDGE EDGE COLOR void char char VERTEX VERTEX GEDSTD AEDSTD DFSED void int 35 struct redstr REDGE REDGE REDGE COLOR void
196. t WCOMP lt no gt PT lt no gt peripheral tree lt graphname gt WCOMP lt no gt IT lt no gt internal tree lt graphname gt WCOMP lt no gt SUB lt no gt subcomponent lt graphname gt WCOMP lt no gt SUB lt no gt BLB lt no gt biblock lt no gt is the identifying number of the decomposition element Table 4 1 Decomposition hierarchies and names depends also of the construction run of the graph and may vary from one run to the next However it is useful and desirable to identify the decomposition elements by names which are run independent Therefore connected components and biblock decomposition elements get a second name a charname A such the smallest line name whitin the lines of a decomposition element is chosen Remark 4 1 1 Weak and strong components could have been characterized by vertex names since they are vertex disjoint Elements of the biblock decomposition are in general not vertex disjoint However they have no common lines For consistency reasons line names have also been chosen for connected components In general higher components as introduced in chapter 11 have lines in common Therefore no charnames but only hierarchical names based on component numbers are used 4 2 Formats and Data Structures For a general description and basic data types see section 2 2 page 11 The data structures used with the graph generating functions are the same as the ones used with the set handling fun
197. tex 179 180 APPENDIX C GHS INTERNAL DATA STRUCTURES INCSQR avtstdblblist pointer to list of biblock edge lists BOOLEAN avtstdgreen TRUE vertex is incident with an edge arc of an internal tree enum rvstdclass RVSTDCLASS Classification 1 RVDNY not yet classified RVDPV vertex in peripheral tree not attachement point RVDIV vertex in internal tree not attachment point RVDBV vertex in biblock not attachment point RVDAP attachment point struct aedstd AEDSTD line in a biblock decomposition t AEDSTD aedstdleft AEDSTD aedstdright AEDSTD aedstdpar COLOR aedstdcolor void aedstdauxiliary for future extensions EDGE aedstdp pointer to edge int aedstdedcolor coloring for classifying int aedstdclass class of edge arc void aedstdelcmp pointer to elementary component edge arc belongs to int edstdcompno Number of higher connected components status FINAL or OPEN or cocomponents the edge is element of RELEM edstdcomplist List of higher connected components status FINAL or OPEN or cocomponents the edge is element of The connected component is of or
198. the problem Example Figure 6 3 shows a simple graph which consists of 3 weak components specified by Figure 6 3 Ugraph1 their vertices 1 h Improper connected component 2 lio i1 i2 i3 i4 Proper a acyclic weak component No stopfree kernel 66 CHAPTER 6 THE BIBLOCK DECOMPOSITION 3 a0 a15 bo b1 b2 Co do d da eo 1 2 es fo fi Proper a cyclic weak component The stopfree kernel consists of the biblocks ao 2 015 bo co bo bi ba co C1 C2 do di d I fo fo and the internal tree co do fo In addition there are the peripheral trees 42 9 and co eo 1 2 10 41 22 13 14 Co 2 3 co do fo Attachment vertex Isol Vertex peripheral tree or acyclic component O Internal tree C Biblock rece Stopfree kernel Subcomponent Figure 6 4 The Biblock Graph Corresponding to Ugraph1 Figure 6 4 shows the corresponding biblock graph 6 2 FORMATS AND DATA STRUCTURES 67 Survey of Functions The main function of this chapter is astd It constructs the biblock decomposition of a general graph Function aprstd is used to write the biblock decomposition of a general graph Func tion aprstdvt writes a list of vertices The biblock graph corresponding to a general graph is constructed by function generateblbgraph To generate a subgraph from an a decomposition element periphe
199. to RVERTEX by a eccentricity in the rvtauxiliary field of the RVERTEX record b vtname RVERTEX compared to RVERTEX by oldname pointed to by auxiliary field RVSTD by total degree and vertex name DRVSTD vertex by total degree and name PARTVT vertex compared to PARTVT by name PARTVT RPARTVT compared to RPARTVT by vtname compared to char RPARTVT comparted to char REDGE compared to REDGE by a level number in auxiliary field b edname EDSTD by line name EDSTD by a edstdcompno b line name SOINC compared to SOINC by PPARTED PEPARTED PRPARTED PERPARTED CCFR WCCFR SCCFR MCFR DOO WCCLC SCCLC IIT rbtreeinsert rbtcomp rbtreefind rbtreeinsert getname rbtcomp rbtreefind rbtcomp rbtreefind rbtreeinsert getname rbtcomp rbtreefind rbtcomp rbtreefind rbtreeinsert getname rbtcomp rbtreefind rbtreeinsert getname rbtcomp rbtreefind rbtreeinsert getname getname rbtcomp rbtreefind rbtreeinsert getname rbtrcomp rbtreefind rbtreeinsert getname rbtrcomp rbtreefind rbtreeinsert getname rbtcomp APPENDIX C GHS INTERNAL DATA STRUCTURES depth of subtree breadth of subtree weight of subtree vtno edno outdegree of end vertex of arc d name of line PARTED compared to PARTED e o op PARTED compared to char RPARTED compared to RPARTED RPARTED co
200. tructure of the giant biblock are analyzed As usual the distance between two vertices a and b of the same component is the minimum length of the paths from a to b The length of a path is its number of edges length 0 is allowed In general there is more than one shortest path between two vertices The vertices and edges of the shortest paths form a subgraph the distance graph with respect to a and b Figure 7 1 shows the distance graphs point block point check point trees and point hinge combined in a single drawing In principle the distance graph with respect to a and b is independent of the order of these vertices It is convenient however to impose a direction on the distance graph by fixing one of the two vertices as starting point of all shortest paths For reasons which shortly will become clear we call it the center of the distance graph whereas the other vertex is called goal The direction of the distance graph assigns a unique level number to each of its vertices The center has level 0 the goal has level d where d is the distance from a vertex of level i 0 lt i lt d 1 to a vertex of level 1 7 2 Formats and Data Structures For a general description and basic data types see section 2 2 page 11 Knuth uses the names start and goal 80 7 3 Functions e shortpath e distances e fdistances 7 4 Examples CHAPTER 7 DISTANCES NOT YET RELEASED 7 4 EXAMPLES 81 Figure
201. tructures 12 3 Functions 12 4 Examples 13 Red Black Trees Problem Description Formats and Data Structures rbtreeprevious 13 3 10 rbtreemax 13 3 11 rbtreemin 13 3 12 printorder 13 3 13 printrbtree 13 3 14 testtree 13 3 15 getname 13 3 16 getcharname 13 4 Note on Compatibility 13 5 Examples 14 Stacks and Queues 14 1 Problem Description 14 2 Formats and Data Structures 14 3 Functions CONTENTS CONTENTS vii 14 3 8 fenque ue 6 RR RI EROR PG EL b AS quA Aa 143 14 3 9 fdequeue sama ei eh a Ros RS OE YS Roe dh wO A d UR EL 144 TALS LOGON 4 25252 en Aene ob oie eur ud de 144 vivas n CN a an de Ad epe Cir er fe de 144 TAO T2igsereate s o bakar mc SS breed erts wu 145 14 3 13 qSEetoVe oe vr evecta 2 ERE NE ISP uii odes 145 14 314 mnewqust amp net Wu e ome epe wu 145 14 3 15 releasequstalisti els done rds ed Ree 145 1434 Examples y 2 28 EX REUS S L asa EM WEE NE 146 H Appendix to User Manual 147 A GHS Makefile 149 B GHS External Data Structures 153 BI File Format a 2 e a BS Br hembras 153 C GHS Internal Data Structures 155 C 1 General Organization Scheme 155 C 2 Literal Constants and Type 156 Functions and Global Variables 158 C3 Explicit Functions eu
202. ts 14 3 7 dequeue Program Author G nther Stiege Universit t Oldenburg Syntax void dequeue QUSTA queue Description The QS record at the front of queue is removed and deleted A pointer to the qelem record it stands for is returned The qelem element is not touched Error Exits None Remarks If the queue is empty NULL is returned Examples See example qusta01 c in GHStests 14 3 8 fenqueue Program Author G nther Stiege Universit t Oldenburg Syntax void fenqueue QUSTA queue void qelem Description Adds element qelem to the end of queue qelem may be an element of any type given by its address casted to void qelem is not linked directly into the queue Instead a QS record which is pointed to from the auxiliary field qelem is used The QS record must have been created and attached to the qelem by the calling program Function qscreate may be used for this purpose Normally elements put in a queue with fenqueue should be removed from the queue with fdequeue and not dequeue Multiple membership is not allowed Error Exits Error if NULL record is to be added to queue Error if QS record missing If an attempt for multiple queue membership is detected an error message is printed no queue insertion is made and the function returns to the calling program 144 CHAPTER 14 STACKS AND QUEUES Remarks The integer fields qshelpi and qshe1p2 as well as the void pointer field qsphelp of the QS record may be used freely
203. turn If in a weak component there is only one element of level 0 vertex of no return or strong component the weak component is called rooted Weak connected components can easily be found with a depth first search i e a depth first search where arcs may be passed through in any direction The same algorithm tests whether the weak component is a acyclic or not Within a weak component the strong components are found by a combination of f depth first search and b depth first search The same algorithms find the level numbers of the strong components as well as those of the vertices of no return Finally the algorithms also test whether a strong component found is f acyclic or not We thus get the following classification of weak and strong components A weak component is of one of the following types 1 a acyclic weak component with no strong components It is a dag It is an a tree i e there is exactly one simple a path joining any pair of distinct vertices If and only if there is only one vertex with level number 0 the weak component is an f tree directed tree too and the vertex is its root 2 a acyclic weak component with strong components The strong components consist of edges only As subgraphs they are free trees The weak component is an a tree It is also an f tree if and only if there is only one element with level number 0 If this element is a vertex of no return this vertex is the root If the element with level number
204. ud eee Regn Program bas0S e Part T aee g a ri te ds Program basg e PartI tala maaa au rn o S e tote Program Ste anda aa hos ah hs dede sua Results of Program 03 Program setot c Part p ea RS Program septo Eoo Part sos raa sore ge s xS Results of Prograyncset01 6_ sss eee a u e ag Ba E Rega Command Procedure set02 cmd and Program set02a c Program 86t02b 6 kann a ee du e bos Oy Te e ERU Decomposition hierarchies and Program 1 vk X aed ro Dee Ped Sh o e ead os ere orig Results of Program gen01 c Results of Program gen01 c b amp ee Exe er ie Weak and strong components of graph wcompgraph Part Weak and strong components of graph wcompgraph Part List of attachment points of the third weak component of graph wcompgraph TProgram acompOlic 1 23 be Tk Arh aoe a a b SUE ce oe Results of Program acomp01 c Part 1 Results of Program acomp01 c Part Results of Program acom01 c Part II Program acomp02 6 dese RV a A RUE s L Gue 2 12 19 20 21 22 28 24 25 26 27 28 29 29 200 6 6 6 7 6 8 9 1 9 2 9 3 11 1 11 2 1
205. ults of Program bas02 c 2 4 EXAMPLES 27 Program main Reads 5 graphs sequence building a graph list Then copies 3 of them without changing the graph type Finally the list and the 3 copies are released The amount of memory used is printed after each graph creation and each graph releasing include lt stdio h gt include lt GHSstructure h gt int main char buffer GRAPH graph graphlist graphwords graphib int i bl graphlist NULL buffer getenv ghsgraphs bl strlen buffer strcpy buffer bl Graph0 printf n n 8ld int ghsmemsize printf Memory before reading the graphs n graph readgraphlist buffer if graph NULL printf Incorrect graph input n exit 0 I rbtreeinsert RB amp graphlist RB graph GRNM printf 81d int ghsmemsize printf Memory after reading graph s n graph gt grname strcpy buffer bl Graphi graph readgraphlist buffer if graph NULL printf Incorrect graph input n exit 0 rbtreeinsert RB amp graphlist RB graph GRNM printf 81d int ghsmemsize printf Memory afte
206. umber 175 176 APPENDIX C GHS INTERNAL DATA STRUCTURES of that component BOOLEAN gvtstdmarked General mark indicator struct gedstd GEDSTD line in a weak and strong decomposition 1 GEDSTD gedstdleft GEDSTD gedstdright GEDSTD gedstdpar COLOR gedstdcolor void gedstdauxiliary EDGE gedstdp pointer to arc int gedstdtype type of line 1 not yet assigned 1 edge gedstdelcmp points to strong component 2 arc of a strong component gedstdelcmp points to strong component 3 arc of an external dag gedstdelcmp points to weak component void gedstdelcmp pointer to elementary component edge arc belongs to BOOLEAN gedstdmarked general mark indicator C 8 Data Structures for the Biblock Decomposition J k bk sk sk sk ok sk ak sk ok sk oR ak ak ak ak ak ak kkk kk kk kk kkk OR K SUB Subcomponent BLB Biblock IT Internal tree PT Peripheral tree AVTSTD Vertex in a biblock decomposition RVSTDCLASS Vertex classification RVSTDSTAT Vertex processing status
207. vt1 EDGE ed graph readgraphlist argv 1 if graph NULL printf Incorrect graph input n exit 0 ed EDGE rbtreefind RB graph gt gredlist RB i SEN getname RB ed SED1 printf s n namebuffer Program output Table 13 10 Example for getname 137 138 CHAPTER 13 RED BLACK TREES Chapter 14 Stacks and Queues 14 1 Problem Description Stacks and queues are useful and important basic data structures see for instance Cormen Leiserson Rivest CormLR1990 In GHS the decision has been made to implement them as doubly linked lists When using stacks and queues in the implementation of graph algorithms two problems arise At the one hand it is sometimes useful to have a given record simultaneously as a member in different stacks or different queues or more than once in the same stack or in the same queue At the other hand it is often necessary to give the membership of a record in a stack queue an attribute valid for the duration of the membership push and pop respectively enqueue and dequeue are to be used when there are no membership attributes required Allow simultaneous multiple membership fpush and fpop respectively fenqueue and fdequeue are to be used when membership attributes are required Simultaneous multiple member ship is not allowed top returns a pointer to the uppermost record of a stack qfront and qend return a pointer to the first last record o
208. xits Error message if vertex vname is not vertex of graph graph Remarks The field vtauxiliary in record type VERTEX is used for the depth level reached Examples Example 2 2 page 16 2 3 6 printbfs Program Author G nther Stiege Universit t Oldenburg void printbfs GRAPH graph char vname char option char Syntax filename Option must be one of the values forward backward or any Description Writes to file filename in breadth first sequence the vertices of graph graph which are reachable from vertex vname If filename equals NULL the output is written to standard output Edges if present are followed in any direction Arcs if present are followed in the direction specified by option The edges arcs followed are also printed as well as the distance from the actual vertex to the start vertex Error Exits Error message if vertex vname is not vertex of graph 16 CHAPTER 2 BASIC GRAPH FUNCTIONS Remarks The field vtauxiliary in record type VERTEX is used as a pointer to a RVERTEX record which in turn is used for queuing Examples Example 2 2 page 16 2 3 7 addvertex not yet released Program Author G nther Stiege Universit t Oldenburg Syntax void addvertex GRAPH graph char vtname Description A new vertex with name vtname is added to graph graph The graph must be of type GG general graph Error exits Examples 2 3 8 addline not yet implemented 2 3 9 deletevertex not yet imp
209. xternal dag wcompexddedno number of arcs of external dag wcompexddedlist list of arcs of external dag wcompwattno number of weak attachment points wcompwattlist list of weak attachment points wcompstrongno number of strong components wcompsno number of f acyclic strong components wcompslist list of f acyclic strong components wcompsfno number of f cyclic strong components wcompsflist list of f cyclic strong components wcompperiod a period of weak component 1 not yet assigned 173 174 APPENDIX C GHS INTERNAL DATA STRUCTURES int wcomproot root type of weak component 1 not yet assigned 0 component is not rooted 1 there is a vertex of no return with root property 2 there is a strong component with root property void wcomprootp NULL Not applicable NULL pointer to vertex if wcomproot 1 pointer to strong component if wcomproot 2 int wcompstpvtno number of vertices of stopfree kernel RVERTEX wcompstpvtlist list of vertices of stopfree kernel int wcompstpedno number of lines of stopfree kernel REDGE wcompstpedlist list of lines of stopfree kernel int wcompstpdedno number of arcs of stopfree k

Download Pdf Manuals

Related Search

Related Contents

文字サンプル - DreamSky  Manuel Utilisateur Français  N8120-004 US100 ユーザーズ・ガイド  Ultra Start 4500 Automobile Alarm User Manual  Axis M5013-V  Epson Z8150NL  MANUAL DEL USUARIO - Primo Water Store  D - Hobart  M A N U E L  信州大学繊維学部安全の手引き  

Copyright © All rights reserved. Failed to retrieve file