class GBN_DGRAPH [G,H]
	-- directed graph, possibly with
	-- multiple edges and self-loops.
	-- Undirected graph is encoded as bidirected.
	-- List of nodes is exported as GBN_ROTUPLE [ GBN_NODE ]
	-- List of edges as GBN_ROTUPLE [ GBN_EDGE ].
	-- Inverse of edges only available in undirected graphs.
	-- List of all edges only gives one of each inverse pair.
	-- Data may be stored with nodes and edges.  For
	-- undirected graphs data may be duplicated on edge
	-- inverses, but need not be.  For example, in Voronoi
	-- diagrams, or planar graphs, one will want to associate
	-- with each edge the face to its left, or the Voronoi
	-- vertex on that face (Delaunay triangulation).
	-- G is node-data type, H edge-data type.
	-- This kind of graph is suitable for computational
	-- geometry, principally allowing a merge operation.
	-- The merge operation is `absorb_suffix,' similar
	-- to the GBN_TUPLE operation.  The other's list of nodes is
	-- absorbed as a suffix of the current's list.
	-- This is appropriate for divide-and-conquer
	-- geometry algorithms when left-to-right order matters.
	-- Also it is permissible for an edge to have only
	-- one incident vertex --- the other at infinity.
	-- This is indicated by a frn = Void or ton = Void

inherit
  GBN_PROTECTED

creation
  make, make_in, make_inout, make_undirected
  

feature
  node_count : INTEGER is
    Result := nodes.count
  end
  
  edge_count : INTEGER is
  	-- In an undirected graph, the inverse
	-- of edges in the edges list is not stored.
	-- Hence this gives the number of undirected edges.
    Result := edges.count
  end

  is_undirected : BOOLEAN 

  has_outlists : BOOLEAN
  has_inlists : BOOLEAN

  has_node ( n : GBN_NODE ) : BOOLEAN is
    local
      i : INTEGER
    do
      Result := n /= Void and then
        uf_marker . find = n . uf_marker . find
    end

  has_edge ( n : GBN_EDGE ) : BOOLEAN is
    local
      i : INTEGER
    do
      Result := n /= Void and then
        uf_marker . find = n . uf_marker . find
    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_DLIST_ITERATOR [ GBN_NODE ] is
    do
      Result := nodes.iterator
    end

  all_edges_iterator : GBN_DLIST_ITERATOR [ GBN_EDGE ] is
    do
      Result := edges.iterator
    end

feature {NONE}

  nodes : DLIST [ GBN_NODE [G]]
  edges : DLIST [ GBN_EDGE [H]]
  uf_marker : GBN_UF_ELEMENT

  make is
  	-- Make with out-lists, most usual kind.
	-- node_count becomes nc.  Not so edge_count,
	-- but edges array has initial size ec.
    local
      i : INTEGER
      temp : GBN_DLIST [ GBN_EDGE ]
    do
    end


invariant
  node_maps : node_maps /= Void
  edge_maps : edge_maps /= Void
end -- class GBN_DGRAPH