note
	description: "[
		Descendant of GRAPH[V] where V is now COMPARABLE.
		Mathematical model for a Directed Graph = (vertices, edges)
		where vertices is a set of comparable vertices in generic parameter V,
		and edges is a relation in vertices:
			vertices: SET [V]
			edges: REL [V, V]
		Inherits immutable queries and commands
		to add and remove vertices and edges.
		Also derived queries for outgoing and incoming edges:
			outgoing (v: V): REL[V, V]
			incoming (v: V): REL[V, V]
			adjacent (v: V): SEQ [V]
		adjacent is redefined as sorted sequence of (comprable) vertices 
		to uniquely define shortest paths etc.
		Derived queries such as:
			reachable (src: V): SEQ[V]
			shortest_path(v1, v2: V): detachable SEQ[V]
		where reachable uses breadth-first search starting with vertex src,
		to return the set of all nodes reachable from src.
		shortest_path returns the shortest path between v1 and v2 if it exists.
		Also has queries for cycles and topological sort.
	]"
	author: "JSO and JW"
	date: "$Date$"
	revision: "$Revision$"

class interface
	COMPARABLE_GRAPH [V -> COMPARABLE]

create 
	make_empty,
	make_from_tuple_array

convert
	make_from_tuple_array ({attached ARRAY [TUPLE [V, V]]})

feature -- Sorted outgoing edges

	adjacent (v: V): SEQ [V]
			-- Sorted list of outgoing edges from v
		ensure then
			sorted: across
					1 |..| (Result.count - 1) as i
				all
					Result [i.item] < Result [i.item + 1]
				end
	
end -- class COMPARABLE_GRAPH

Generated by ISE EiffelStudio