|
Action:
|
Determines whether or not a graph has a cycle.
|
|
|
Filename:
|
kern/kern_scm/graph_scm.cxx
|
|
|
Syntax:
|
(graph:cycle? in-graph)
|
|
|
Arg Types:
|
in-graph
|
graph
|
|
|
Returns:
|
boolean
|
|
|
Description:
|
A cycle is defined as a connected group of vertices whose individual removal from the graph results in a linear graph and the same number of components. In other words, none of the vertices of the cycle are cut vertices and none have edges to more than one vertex.
|
|
|
in-graph specifies a graph.
|
|
|
Example:
|
; graph:cycle?
|
|
; Create a simple example
|
|
(define g1 (graph "me-you you-us us-them
|
|
|
them-they me-they
|
|
|
FIDO-SPOT SPOT-KING SPOT-PETEY"))
|
|
;; g1
|
|
; CAREFUL: The order of the graph output may
|
|
; not be the same each time.
|
|
(graph:cycle? g1)
|
|
;; #f
|
|
(define g2 (graph:component g1 "FIDO"))
|
|
;; g2
|
|
(graph:cycle? g2)
|
|
;; #f
|
|
(define g3 (graph:component g1 "me"))
|
|
;; g3
|
|
(graph:cycle? g3)
|
|
;; #t
|