Monday, July 2, 2012

Implementation of a directed graph in ParaSail

Below is an implementation of a (pointer-free) directed graph in ParaSail, as promised in the EETimes.com article ParaSail : Less is More with Multicore.
  [ see http://www.eetimes.com/design/embedded/4375616/ParaSail--Less-is-more-with-multicore ]

// Example ParaSail program -- Directed Graph module

// Copyright (C) 2011-2012, AdaCore, New York, NY
// To be used only for Personal, Academic, or Evaluation Purposes;
// Not for Commercial Production Use.
// Report errors at http://groups.google.com/group/parasail-programming-language

interface DGraph<Element is Assignable<>> is
  // Interface to a Directed-Graph module

    type Node_Id is new Integer<1..10**6>;
      // A unique id for each node in the graph

    type Node_Set is Countable_Set<Node_Id>;
      // A set of nodes

    func Create() -> DGraph;
      // Create an empty graph

    func Add_Node(var DGraph; Element) -> Node_Id;
      // Add a node to a graph, and return its node id

    op "indexing"(ref DGraph; Node_Id) 
      {Node_Id in DGraph.All_Nodes()}
      -> ref Element;
      // Return a reference to an element of the graph

    func Add_Edge(var DGraph; From, To : Node_Id)
      {From in DGraph.All_Nodes(); To in DGraph.All_Nodes()};
      // Add an edge in the graph

    func Successors(ref const DGraph; Node_Id) -> ref const Node_Set
      {Node_Id in DGraph.All_Nodes()};
      // The set of successors of a given node

    func Predecessors(ref const DGraph; Node_Id) -> ref const Node_Set
      {Node_Id in DGraph.All_Nodes()};
      // The set of predecessors of a given node

    func All_Nodes(DGraph) -> Node_Set;
      // The set of all nodes

    func Roots(DGraph) -> Node_Set;
      // The set of all nodes with no predecessor

    func Leaves(DGraph) -> Node_Set;
      // The set of all nodes with no successor
end interface DGraph;

class DGraph is
  // Class defining the Directed-Graph module

    interface Node<> is
      // Local definition of Node structure
        var Elem : Element;
        var Succs : Node_Set;
        var Preds : Node_Set;
    end interface Node;

    var G : Vector<Node>;
      // The vector of nodes, indexed by Node_Id

    const Debug : Boolean := #false;

    func Boundary_Set(DGraph; Nodes : Countable_Range<Node_Id>;
      Want_Roots : Boolean) -> Node_Set is
      // Recursive helper for exported Roots and Leaves functions
        if Debug then
            Println("Boundary_Set for " | Nodes.First | ".." | Nodes.Last);
        end if;
        const Len := Length(Nodes);
        case Len of
          [0] =>
            return [];
          [1] =>
            if Want_Roots?
                Is_Empty(Predecessors(DGraph, Nodes.First)):
                Is_Empty(Successors(DGraph, Nodes.First))
            then
                // This is on the desired boundary
                return [Nodes.First];
            else
                // This is not on the desired boundary
                return [];
            end if;
          [..] =>
            // Divide and conquer
            const Half_Way := Nodes.First + Len / 2;
            return 
              Boundary_Set(DGraph, 
                Nodes.First ..< Half_Way, Want_Roots) |
              Boundary_Set(DGraph,
                Half_Way .. Nodes.Last, Want_Roots);
        end case;
    end func Boundary_Set;

  exports

    func Create() -> DGraph is
      // Create an empty graph
        return (G => []);
    end func Create;

    func Add_Node(var DGraph; Element) -> Node_Id is
      // Add a node to a graph, and return its node id
        DGraph.G |= (Elem => Element, Succs => [], Preds => []);
        return Length(DGraph.G);
    end func Add_Node;

    op "indexing"(ref DGraph; Node_Id) -> ref Element is
      // Return a reference to an element of the graph
        return DGraph.G[ [[Node_Id]] ].Elem;
    end op "indexing";

    func Add_Edge(var DGraph; From, To : Node_Id) is
      // Add an edge in the graph
        DGraph.G[ [[From]] ].Succs |= To;
        DGraph.G[ [[To]] ].Preds |= From;
    end func Add_Edge;

    func Successors(ref const DGraph; Node_Id) -> ref const Node_Set is
      // The set of successors of a given node
        return DGraph.G[ [[Node_Id]] ].Succs;
    end func Successors;

    func Predecessors(ref const DGraph; Node_Id) -> ref const Node_Set is
      // The set of predecessors of a given node
        return DGraph.G[ [[Node_Id]] ].Preds;
    end func Predecessors;

    func All_Nodes(DGraph) -> Node_Set is
      // The set of all nodes
        return 1 .. Length(DGraph.G);
    end func All_Nodes;

    func Roots(DGraph) -> Node_Set is
      // The set of all nodes with no predecessor
        return Boundary_Set
          (DGraph, 1 .. Length(DGraph.G), Want_Roots => #true);
    end func Roots;

    func Leaves(DGraph) -> Node_Set is
      // The set of all nodes with no successor
        return Boundary_Set
          (DGraph, 1 .. Length(DGraph.G), Want_Roots => #false);
    end func Leaves;
end class DGraph;

func Test_Graph() is
  // A test program that manipulates a directed graph of univ-enums

    type DGE is DGraph<Univ_Enumeration>;

    func Build_Graph() -> New_G : DGE is
      // A function that builds up a graph of Univ_Enumerations
        New_G := Create();  // Create the empty graph

        const Hello := New_G.Add_Node(#hello);
        const There := New_G.Add_Node(#there);
        const Stranger := New_G.Add_Node(#stranger);

        New_G.Add_Edge(Hello, There);
        New_G.Add_Edge(There, Stranger);
        New_G.Add_Edge(Hello, Stranger);

    end func Build_Graph;
       
    func Print_Nodes(DGE; Nodes : DGE::Node_Set; Indent : Univ_String := " ")
      // Display the elements of a node set, with the given indent
    is
        for S in Nodes loop
            Println(Indent | DGE[S]);
        end loop;
    end func Print_Nodes;

    func Print_Succs(DGE; N : DGE::Node_Id) is
      // Display the successors of a given node
        Println("Successors of " | DGE[N] | " (node " | N | ")");
        Print_Nodes(DGE, DGE.Successors(N));
    end func Print_Succs;

    // Now build the graph and display some info on the graph

    var Gr : DGE := Build_Graph();

    Println("Roots of graph:");
    Gr.Print_Nodes(Gr.Roots());

    Println("Leaves of graph:");
    Gr.Print_Nodes(Gr.Leaves());
    
    Println("All nodes, and their successors:");
    for N in All_Nodes(Gr) forward loop
        Gr.Print_Succs(N);
    end loop;
end func Test_Graph;

No comments:

Post a Comment