Sunday, July 24, 2005

A data structural approach to detect cycles

Refer to the previous post about the construction of the hypergraph with ordinary nodes and hypernodes.

The ordinary nodes correspond to the number of times an edge has been selected in the PRDG. A hyperedge is from a subset of (ordinary) nodes to a subset of nodes. Either the head of the edge, or the tail of the edge can be a zero size subset.

Now define the arity of a hyperedge as the sum of its indegrees and outdegrees.
Some simple observations:
for a hypernode v with an edge S to T, if indegree(v) = outdegree(v) = 1 (or card(S)=card(T)=1), then we can "club" the two singleton sets to make another singletonset. The hyperedges which begin or end at the vertices of the sets S and T can be made to correspondingly begin or end at the new vertex, which can be called its own singleton set.

The hypernodes can be stored in a priority queue, which supports the following operations:
  • deletion of the hypernode with the minimal arity

    Also, a hypernode v such that indegree(v) = 0 or (outdegree(v) =0) can be removed from the queue. This would lead us to a pruning of the graph:
    removal of the hypernode from the priority queue: This hypernode may not be at the top of the priority queue.
    pruning the hyperedges which begin or end at these vertices
    TO DO: try to see some examples of the particular linear programs of unitary form.
    solve the dual linear programs
    look at the original and dual graphs