class GBN_GEN_DGRAPH
	-- directed graph, possibly with
	-- multiple edges and self-loops
	-- Note.  Array nodes etc range should always
	-- be 1 to node_count.  Array edges etc range should
	-- always be 1 to at least edge_count, or 2*edge_count
	-- in the undirected case.  The idea is that the nodes
	-- can be specified merely by counting them, but the
	-- edges must be added piecemeal.  To be consistent with
	-- this, node_count and edge_count should be used
	-- and not the lower (always 1) and upper bounds on
	-- the various arrays (which are mostly private, anyway).
	-- In an undirected graph, there are 2*edge_count directed
	-- edges, stored in adjacent inverse pairs.
inherit
  GBN_PROTECTED

creation
  make, make_in, make_inout, make_undirected
  

feature
  node_count, edge_count : INTEGER
  is_undirected : BOOLEAN 

  has_outlists : BOOLEAN is
    do
      Result := outlists /= Void
    end

  has_inlists : BOOLEAN is
    do
      Result := inlists /= Void
    ensure
      Result implies not is_undirected
    end

  valid_ranges : BOOLEAN is
    do
      Result :=
      nodes.lower = 1 and then
      nodes.upper = node_count and then
      (inlists /= Void implies 
        (inlists.lower = 1 and inlists.upper = node_count)) and then
      (outlists /= Void implies
        (outlists.lower = 1 and outlists.upper = node_count)) and then
      (inlists /= Void implies 
        (inlist_place/=Void and then
	(inlist_place.lower = 1 and inlist_place.upper = node_count )))
	and then
      (outlists /= Void implies 
        (outlist_place/=Void and then
	(outlist_place.lower = 1 and outlist_place.upper = node_count )))

      if Result and not is_undirected then
	Result :=
        edges /= Void and then (edges.lower=1 and edges.upper >= edge_count)
      end

      if Result and is_undirected then
	Result :=
        edges /= Void and then (edges.lower=1 and edges.upper >= 2*edge_count)
      end
    end

  has_node ( n : GBN_NODE ) : BOOLEAN is
    local
      i : INTEGER
    do
      if n /= Void then
        i := n.index
        if i.in_range ( 1, node_count ) and then
            nodes.item (i).index = i
        then
          Result := true
        end
      end
    end

  has_edge ( n : GBN_EDGE ) : BOOLEAN is
    local
      i : INTEGER
    do
      if n /= Void then
        i := n.index
        if i.in_range ( 1, edge_count ) and then
            edges.item (i).index = i
        then
          Result := true
        end
      end
    end

  node (i: INTEGER) : GBN_NODE is
    require
      in_range : i.in_range ( 1, node_count )
    do
      Result := nodes.item (i)
    ensure
      has_node : has_node (Result)
      node_index: node_index (Result) = i
    end

  node_index ( nd: GBN_NODE ) : INTEGER is
    require
      has_node : has_node ( nd )
    do
      Result := nd.index
    ensure
      node ( Result ) = nd
    end

  all_nodes_iterator : GBN_GNODE_ITERATOR is
    do
      !! Result.make ( Current )
    end

  all_edges_iterator : GBN_GEDGE_ITERATOR is
	-- In a directed graph, only produces
	-- one edge from each pair of directed
	-- edges.
    do
      !! Result.make ( Current )
    end

feature {GBN_GNODE_ITERATOR}
  nodes : ARRAY [ GBN_NODE ]

feature {GBN_GEDGE_ITERATOR}
  edges : ARRAY [ GBN_EDGE ]

feature {NONE}
  inlists : ARRAY [ GBN_DLIST [ GBN_EDGE ] ]
  outlists : ARRAY [ GBN_DLIST [ GBN_EDGE ] ]
  inlist_place : ARRAY [ GBN_DLIST_PLACE [ GBN_EDGE ] ]
  outlist_place : ARRAY [ GBN_DLIST_PLACE [ GBN_EDGE ] ]

  make ( nc, ec : INTEGER ) is
  	-- Make with out-lists, most usual kind.
	-- node_count becomes nc.  Not so edge_count,
	-- but edges array has initial size ec.
    require
      nonnegative : nc >= 0 and ec >= 0
    local
      i : INTEGER
      temp : GBN_DLIST [ GBN_EDGE ]
    do
      !! edges.make (1, ec)
      !! outlist_place.make (1, ec)
      node_count := nc
      !! nodes.make (1, node_count)
      !! outlists.make (1, node_count)
      from
        i := 1
      until
      	i > node_count
      loop
	!! temp.make_protecting ( Current )
	outlists.put ( temp , i )
	i := i+1
      end
    end

  make_in ( nc, ec : INTEGER ) is
  	-- Make with in-lists, rather unusual.
	-- Otherwise like make.
    require
      nonnegative : nc >= 0 and ec >= 0
    local
      i : INTEGER
      temp : GBN_DLIST [ GBN_EDGE ]
    do
      !! edges.make (1, ec)
      !! inlist_place.make (1, ec)
      node_count := nc
      !! nodes.make (1, node_count)
      !! inlists.make (1, node_count)
      from
        i := 1
      until
      	i > node_count
      loop
	!! temp.make_protecting ( Current )
	inlists.put ( temp , i )
	i := i+1
      end
    end

  make_inout ( nc, ec : INTEGER ) is
  	-- Make with in-lists and out-lists, rather unusual.
    require
      nonnegative : nc >= 0 and ec >= 0
    local
      i : INTEGER
      temp : GBN_DLIST [ GBN_EDGE ]
    do
      !! edges.make (1, ec)
      !! inlist_place.make (1, ec)
      !! outlist_place.make (1, ec)
      node_count := nc
      !! nodes.make (1, node_count)
      !! inlists.make (1, node_count)
      !! outlists.make (1, node_count)
      from
        i := 1
      until
      	i > node_count
      loop
        !! temp.make_protecting ( Current )
	inlists.put ( temp, i )
        !! temp.make_protecting ( Current )
	outlists.put ( temp, i )
	i := i+1
      end
      is_undirected := true
    end

  make_undirected ( nc, ec: INTEGER ) is
      -- Actually bidirected.  In lists are
      -- not created since they are the same as
      -- outlists in a bidirected graph, but
      -- the inverse of edges must be stored,
      -- and every undirected edge corresponds
      -- to an inverse pair of directed edges
      -- in the graph. Hence 2*ec...
      -- Graph operations differ considerably
      -- between ordinary and undirected graphs.
    require
      nonnegative : nc >= 0 and ec >= 0
    local
      i : INTEGER
      temp : GBN_DLIST [ GBN_EDGE ]
    do
      !! edges.make (1, 2*ec)
      !! inlist_place.make (1, 2*ec)
      !! outlist_place.make (1, 2*ec)
      node_count := nc
      !! nodes.make (1, node_count)
      !! outlists.make (1, node_count)
      from
        i := 1
      until
      	i > node_count
      loop
        !! temp.make_protecting ( Current )
	outlists.put ( temp, i )
	i := i+1
      end
      is_undirected := true
      !! node_maps.make
      !! edge_maps.make
    end

feature {GBN_NODE_MAP}
  node_maps : GBN_DLIST [ GBN_NODE_MAP [ ANY ] ]

feature {GBN_EDGE_MAP}
  edge_maps : GBN_DLIST [ GBN_EDGE_MAP [ ANY ] ]

invariant
  valid_ranges : valid_ranges
  node_maps : node_maps /= Void
  edge_maps : edge_maps /= Void
end -- class GBN_GEN_DGRAPH