Hyperedge segments

> > > > >

An IlvSegmentedHyperEdge object has a shape that consists of line segments. The line segments form branches that connect all hyperedge ends. Therefore, the segments can be connected to other segments and can be connected to hyperedge ends at a node. We call a segment incident to a node an end segment, and the other segments the inner segments. The segments of a hyperedge form an unrooted, undirected segment tree.

A segmented hyperedge with its segment tree

In the figures above:

The dashed lines indicate the segments that are incident.
The red lines indicate which segments are connected to end nodes.
The segments a, b, d, and g are end segments; the segments c, e, and f are inner segments.

You may be surprised that the segment tree is undirected, even though the hyperedge may be directed. The direction of the hyperedge comes from the fact that arrow heads are drawn at certain end points. This direction is irrelevant for the segment tree; that is, there is no root of the segment tree, but each segment has several (or 0) incident segments. By starting at an arbitrary segment, an algorithm can traverse all incident segments recursively without running into a cycle. Therefore it is an unrooted, undirected segment tree.

A segment is implemented by the inner class IlvSegmentedHyperEdge.Segment. To retrieve all segments of a hyperedge, make the call shown in the following code example.

Retrieving all segments of a hyperedge

IlvSegmentedHyperEdge seghyperedge = ...
Iterator iterator = seghyperedge.getSegments();
while (iterator.hasNext()) {
  IlvSegmentedHyperEdge.Segment segment =
    (IlvSegmentedHyperEdge.Segment)iterator.next();
  ...
}

The API of IlvSegmentedHyperEdge.Segment includes the methods listed in the following table.

Methods of IlvSegmentedHyperEdge.Segment

Method	Description
getHyperEdge	Returns the hyperedge that owns the segment.
getEnds	Returns the hyperedge ends of the segment if it is an end segment. If it returns an empty array, the segment is an inner segment.
getIncidentSegmentsCount	Returns the number of incident segments.
getIncidentSegment	Returns the incident segment with index i. The index of incident segments starts at 0.
isIncident	Tests whether two segments are incident.

If two segments A and B are connected, then A will have B as incident segment and B will have A as incident segment. This allows traversal of the incident segments in any direction. To avoid running into a loop, you only have to make sure that you do not visit the segment again where you immediately came from. The method in the following code example illustrates this concept.

Method for traversal of incident segments in any direction

public void visit(IlvSegmentedHyperEdge.Segment segment,
                  IlvSegmentedHyperEdge.Segment cameFrom)
{
  ...
  int n = segment.getIncidentSegmentsCount();
  for (int i = 0; i < n; i++) {
    IlvSegmentedHyperEdge.Segment childSegment =
          segment.getIncidentSegment(i);
    if (childSegment != cameFrom)
      visit(childSegment, segment);
  }
}
...
// visit all segments reachable from startSegment
 visit(startSegment, null);

Current section

Segmented hyperedges