Package COM.INFORMATIMAGO.TOOLS.DEPENDENCY-CYCLES


Find cycles in a dependency graph.

The graph is defined by a list of nodes and two methods:

 (ADJACENCY-LIST node) -> list-of-nodes

 (REACHABLE-LIST node) -> list-of-nodes

             which is the recursive closure of ADJACENCY-LIST,
             but provided for efficiency.


The function FIND-CYCLES returns a list of cycles in the graph defined
by the given list of nodes and the previous methods.

 (FIND-CYCLES nodes) -> list-of-cycles

The function REPORT-PROBLEMS prints a report of the found cycles.

 (REPORT-PROBLEMS nodes)


License:

    AGPL3

    Copyright Pascal J. Bourguignon 2012 - 2018

    This program is free software: you can redistribute it and/or modify
    it under the terms of the GNU Affero General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU Affero General Public License for more details.

    You should have received a copy of the GNU Affero General Public License
    along with this program.  If not, see <http://www.gnu.org/licenses/>.

(adjacency-list object)

generic-function

Return the list of vertices connected to vertex thru a single edge.

(dependencies-graph objects)

function

RETURN:  a graph as defined by the nodes in the OBJECTS sequence and
         the ADJACENCY-LIST an REACHABLE-LIST methods.

FIND-CYCLES

(find-shortest-path from to successors)

function

RETURN: The shortest path of length>0 from FROM to TO if it exists, or NIL.

(generate-dependencies-graph objects output-dotfile-path)

function

DO:     Generates a GraphViz dot file to draw the dependency-graph defined
        by the nodes in the OBJECTS sequence and the ADJACENCY-LIST an
        REACHABLE-LIST methods.

PRINT-CYCLE

(reachable-list vertex)

generic-function

Return the list of vertices rechable from vertex.

(report-problems objects &key report)

function

DO:     Find cycles in the graph defined by the nodes in the OBJECTS
        sequence and the ADJACENCY-LIST and REACHABLE-LIST methods.