Computing even cycles in directed graphs
This interface, written by
Petr Hlineny,
will let you run an algorithm designed
by N. Robertson, P.D. Seymour and
R. Thomas
[
Permanents, Pfaffian orientations, and even directed circuits,
Ann. Math. 150 (1999), 166-183]. The interface calls a program written in C by
Christopher Carl Heckman.
Best viewed with Netscape!
See the guide below for how to input a digraph. Given a digraph, the
algorithm either finds an even directed cycle, or answers that none exists.
A short guide
Use your mouse to draw the digraph you want to test in the above window.
The left button creates new vertices,
or new edges starting in existing vertices.
An edge can have arbitrarily many bends.
While drawing an edge, a single click on the left button creates
a bend; a double click creates a new vertex which will become the
head of the current edge; Esc cancels the drawing of the current edge.
Use the middle button (or shift + left button)
to select an existing vertex or edge.
When selected, a vertex or an edge can be dragged, bends may be
introduced to edges as described above, and vertices and edges
may be deleted using the Del key. To remove a bend select it using
the middle button (or shift + left button) and press Esc.
Press the Clear button to clear the drawing window, and
use the top buttons to move or scale the picture.
Press the CYCLE button to call the algorithm
(through CGI),
then see the line immediately below the picture
(and the picture itself) for results.