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.