Structures_Graph
[ class tree: Structures_Graph ] [ index: Structures_Graph ] [ all elements ]

Class: Structures_Graph_Manipulator_AcyclicTest

Source Location: /Structures_Graph-1.1.1/Structures/Graph/Manipulator/AcyclicTest.php

Class Overview


The Structures_Graph_Manipulator_AcyclicTest is a graph manipulator which tests whether a graph contains a cycle.


Author(s):

Copyright:

  • (c) 2004 by SÚrgio Carvalho

Methods


Inherited Variables

Inherited Methods


Class Details

[line 55]
The Structures_Graph_Manipulator_AcyclicTest is a graph manipulator which tests whether a graph contains a cycle.

The definition of an acyclic graph used in this manipulator is that of a DAG. The graph must be directed, or else it is considered cyclic, even when there are no arcs.



[ Top ]


Method Detail

isAcyclic   [line 124]

boolean isAcyclic( &$graph)

isAcyclic returns true if a graph contains no cycles, false otherwise.
  • Return: true iff graph is acyclic
  • Access: public

Parameters:

   &$graph   — 

[ Top ]

_isAcyclic   [line 79]

void _isAcyclic( &$graph)

Check if the graph is acyclic
  • Access: protected

Parameters:

   &$graph   — 

[ Top ]

_nonVisitedInDegree   [line 64]

integer _nonVisitedInDegree( &$node)

This is a variant of Structures_Graph::inDegree which does not count nodes marked as visited.
  • Return: Number of non-visited nodes that link to this one
  • Access: protected

Parameters:

   &$node   — 

[ Top ]


Documentation generated on Mon, 20 Jul 2015 21:30:02 +0000 by phpDocumentor 1.4.4. PEAR Logo Copyright © PHP Group 2004.