.\" ident	@(#)Graph_alg:man/cycle_list.3	3.2
.\"
.\" C++ Standard Components, Release 3.0.
.\"
.\" Copyright (c) 1991, 1992 AT&T and UNIX System Laboratories, Inc.
.\" Copyright (c) 1988, 1989, 1990 AT&T.  All Rights Reserved.
.\"
.\" THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T and UNIX System
.\" Laboratories, Inc.  The copyright notice above does not evidence
.\" any actual or intended publication of such source code.
.\" 
.TH \f3cycle_list\fP \f3Graph_alg(3C++)\fP " "
.SH NAME
cycle_list, cycle_list_u \- find cycles in a Graph
.SH SYNOPSIS OF Graph_alg.h
.Bf

#include <List.h>

#define Graph_algdeclare(\f2G\fP,\f2V\fP,\f2E\fP)...
#define Graph_algimplement(\f2G\fP,\f2V\fP,\f2E\fP)...

\f2Expanding Graph_algdeclare(G,V,E) produces the following text:\fP

    List_of_p<\f2E\fP> cycle_list(const \f2G\fP& g,const \f2V\fP* v);
    List_of_p<\f2E\fP> cycle_list(const \f2G\fP& g,const \f2E\fP* e);

    List_of_p<\f2E\fP> cycle_list_u(const \f2G\fP& g,const \f2V\fP* v);
    List_of_p<\f2E\fP> cycle_list_u(const \f2G\fP& g,const \f2E\fP* e);

.Be
.SH DESCRIPTION
A cycle is a sequence of Edges starting at 
a Vertex and returning to that Vertex (no Edge can
appear twice in the sequence).
For an undirected Graph, the sequence must include at least
three Edges; for a directed Graph, at least one.
These functions return an arbitrary cycle 
in \f4g\fP involving a given Edge or Vertex.
As usual, functions whose names end in \f4_u\f1
treat Graphs as undirected, while functions without
the suffix treat Graphs as directed.
A cycle in an undirected Graph must include at least
three Edges; a cycle in a directed Graph must include
at least one.
.PP
The sequence of Edges constituting the cycle is returned
as a list of Edge pointers (see \f3List(3C++)\f1).
.SH COMPLEXITY
Worst case \f2O(max(v,e))\f1, where \f2v\f1
is the number of Vertices and \f2e\f1
is the number of Edges in the Graph.  
Average performance seems much better.
.NOTES
If you merely need to know whether a given Edge or
Vertex is involved in a cycle, use \f3cycle(.)\f1.
.SH SEE ALSO
.Bf
\f3intro(.)\f1
\f3cycle(.)\f1
\f3List(3C++)\f1
.Be