Graph Representation

Simple graphs are commonly represented using adjacency lists, in which each vertex contains a pointer to a list of its neighbors. There is typically no explicit representation of edges; <#13423#>vi<#13423#> is said to be adjacent to <#13425#>vj<#13425#> if <#13427#>vj<#13427#> is in the adjacency list of <#13429#>vi<#13429#>. In LINK, however, this representation is not sufficient. A hypergraph <#13431#>G<#13431#> is a pair <#13433#>(V,E)<#13433#>, where <#13435#>#tex2html_wrap_inline13435#<#13435#> is a set of vertices and <#13437#>#tex2html_wrap_inline13437#<#13437#> is a collection of finite subsets of <#13439#>V<#13439#>. Since edges may have cardinalities not equal to 2, adjacency list membership is not sufficient to determine the neighbors of a vertex. In LINK, hypergraphs are represented by a <#13383#>SortedArray<#13383#> of <#13384#>Vertex<#13384#> pointers and an <#13385#>MSet<#13385#> of <#13386#>Edge<#13386#> pointers. The <#13387#>Container<#13387#> object <#13388#>SortedArray<#13388#> is used instead of <#13350#>Set<#13441#>;SPMlt;<#13441#>Vertex*, SortedArray<#13443#>;SPMlt;<#13443#>Vertex*<#13445#>;SPMgt;<#13445#> <#13447#>;SPMgt;<#13447#><#13350#> in order to allow the programmer to circumvent the <#13389#>Iterator<#13389#> mechanism and iteration through the <#13390#>Vertex<#13390#> set using fast pointer arithmetic. Membership checks prevent duplicate <#13391#>Vertices<#13391#> from occurring. Each <#13392#>Edge<#13392#> object contains a <#13393#>Collection<#13393#> pointer which locates the set or sequence storing the <#13394#>Vertices<#13394#> in that <#13395#>Edge<#13395#>. The virtual functions of the <#13396#>Collection<#13396#> class can allow a single algorithm code to work on many different classes of <#13397#>Graph<#13397#> objects with no modification. The bottleneck in accomplishing this in general is being able to define an algorithm's performance on various classes of <#13398#>Graph<#13398#> rather than language or system limitations.