|##########|
|#MAGIC   #|CLABLMFI
|#PROJECT #|"ImportHelp"
|#PATHS   #|"StdProject"
|#FLAGS   #|xx---x--x-----x-----------------
|#USERSW  #|--------------------------------
|#USERMASK#|--------------------------------
|#SWITCHES#|xx---xxxxx------
|##########|
DEFINITION MODULE Graphs;

IMPORT Lists;

EXCEPTION
  CircleFound : "Circle in graph detected";


  DEFINITION MODULE DirectedGraphs(NodePtr : POINTER TO Node;
                                   EdgePtr : POINTER TO Edge);

    DEFINITION MODULE NodeLists = Lists.BiLists(NodePtr);

    TYPE
      Edge     = RECORD
                   from,
                   to    : RECORD
                             prev,
                             next  : EdgePtr;
                             with  : NodePtr
                           END;
                 END;
      Node     = RECORD OF NodeLists.BiNode;
                   from,
                   to    : RECORD
                             first,
                             last   : EdgePtr;
                           END;
                   mark  : BOOLEAN;
                 END;
      Graph    = RECORD
                   nodes : NodeLists.BiList;
                 END;

      ApplyN   = PROCEDURE(n : NodePtr);
      ApplyE   = PROCEDURE(e : EdgePtr);
      DestructN= PROCEDURE(n : NodePtr);
      DestructE= PROCEDURE(e : EdgePtr);

    PROCEDURE Init(VAR graph : Graph);

    PROCEDURE RemoveAll(VAR graph : Graph);

    PROCEDURE DeleteAll(VAR graph : Graph);

    PROCEDURE DestructAll(VAR graph : Graph;
                              desN  : DestructN;
                              desE  : DestructE);


    PROCEDURE AddNode(VAR graph : Graph;node : NodePtr);

    PROCEDURE RemoveNode(VAR graph : Graph;
                             node  : NodePtr;
                             des   : DestructE);

    PROCEDURE DeleteNode(VAR graph : Graph;
                             node  : NodePtr);


    PROCEDURE AddEdge(VAR graph : Graph;
                          src,
                          dst   : NodePtr;
                          edge  : EdgePtr);

    PROCEDURE RemoveEdge(VAR graph : Graph;
                             edge  : EdgePtr);

    PROCEDURE DeleteEdge(VAR graph : Graph;
                             edge  : EdgePtr);

    PROCEDURE FindEdge(VAR graph : Graph;
                           src,
                           dst   : NodePtr):EdgePtr;


    PROCEDURE SortTopological(VAR graph : Graph);


    PROCEDURE ApplyNodes(VAR graph : Graph;
                             apply : ApplyN);

    PROCEDURE ApplyToEdges(VAR graph : Graph;
                               node  : NodePtr;
                               apply : ApplyE);

    PROCEDURE ApplyFromEdges(VAR graph : Graph;
                                 node  : NodePtr;
                                 apply : ApplyE);

    PROCEDURE ApplyAllEdges(VAR graph : Graph;
                                apply : ApplyE);


    PROCEDURE ApplyDepthFirst(VAR graph  : Graph;
                                  root   : NodePtr;
                                  applyN : ApplyN;
                                  applyE : ApplyE);

    PROCEDURE ApplyBreathFirst(VAR graph  : Graph;
                                   root   : NodePtr;
                                   applyN : ApplyN;
                                   applyE : ApplyE);

    PROCEDURE MarkNodes(VAR graph : Graph);

    PROCEDURE ApplyMarked(VAR graph : Graph;
                              apply : ApplyN);

  END DirectedGraphs;

END Graphs.