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 
	COMPARABLE_GRAPH [V -> COMPARABLE]

create 
	make_empty,
	make_from_tuple_array

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

feature {NONE} -- Initialization

	default_create
			-- Process instances of classes with no creation clause.
			-- (Default: do nothing.)
			-- (from ANY)
		do
		end
	
feature -- Access

	generating_type: TYPE [detachable COMPARABLE_GRAPH [V]]
			-- Type of current object
			-- (type of which it is a direct instance)
			-- (from ANY)
		external
			"built_in"
		ensure -- from ANY
			generating_type_not_void: Result /= Void
		end

	generator: STRING_8
			-- Name of current object's generating class
			-- (base class of the type of which it is a direct instance)
			-- (from ANY)
		external
			"built_in"
		ensure -- from ANY
			generator_not_void: Result /= Void
			generator_not_empty: not Result.is_empty
		end
	
feature -- Comparison

	frozen deep_equal (a: detachable ANY; b: like arg #1): BOOLEAN
			-- Are a and b either both void
			-- or attached to isomorphic object structures?
			-- (from ANY)
		do
			if a = Void then
				Result := b = Void
			else
				Result := b /= Void and then a.is_deep_equal (b)
			end
		ensure -- from ANY
			instance_free: class
			shallow_implies_deep: standard_equal (a, b) implies Result
			both_or_none_void: (a = Void) implies (Result = (b = Void))
			same_type: (Result and (a /= Void)) implies (b /= Void and then a.same_type (b))
			symmetric: Result implies deep_equal (b, a)
		end

	frozen equal (a: detachable ANY; b: like arg #1): BOOLEAN
			-- Are a and b either both void or attached
			-- to objects considered equal?
			-- (from ANY)
		do
			if a = Void then
				Result := b = Void
			else
				Result := b /= Void and then a.is_equal (b)
			end
		ensure -- from ANY
			instance_free: class
			definition: Result = (a = Void and b = Void) or else ((a /= Void and b /= Void) and then a.is_equal (b))
		end

	frozen is_deep_equal (other: COMPARABLE_GRAPH [V]): BOOLEAN
			-- Are Current and other attached to isomorphic object structures?
			-- (from ANY)
		require -- from ANY
			other_not_void: other /= Void
		external
			"built_in"
		ensure -- from ANY
			shallow_implies_deep: standard_is_equal (other) implies Result
			same_type: Result implies same_type (other)
			symmetric: Result implies other.is_deep_equal (Current)
		end

	frozen standard_equal (a: detachable ANY; b: like arg #1): BOOLEAN
			-- Are a and b either both void or attached to
			-- field-by-field identical objects of the same type?
			-- Always uses default object comparison criterion.
			-- (from ANY)
		do
			if a = Void then
				Result := b = Void
			else
				Result := b /= Void and then a.standard_is_equal (b)
			end
		ensure -- from ANY
			instance_free: class
			definition: Result = (a = Void and b = Void) or else ((a /= Void and b /= Void) and then a.standard_is_equal (b))
		end

	frozen standard_is_equal (other: COMPARABLE_GRAPH [V]): BOOLEAN
			-- Is other attached to an object of the same type
			-- as current object, and field-by-field identical to it?
			-- (from ANY)
		require -- from ANY
			other_not_void: other /= Void
		external
			"built_in"
		ensure -- from ANY
			same_type: Result implies same_type (other)
			symmetric: Result implies other.standard_is_equal (Current)
		end
	
feature -- Status report

	conforms_to (other: ANY): BOOLEAN
			-- Does type of current object conform to type
			-- of other (as per Eiffel: The Language, chapter 13)?
			-- (from ANY)
		require -- from ANY
			other_not_void: other /= Void
		external
			"built_in"
		end

	same_type (other: ANY): BOOLEAN
			-- Is type of current object identical to type of other?
			-- (from ANY)
		require -- from ANY
			other_not_void: other /= Void
		external
			"built_in"
		ensure -- from ANY
			definition: Result = (conforms_to (other) and other.conforms_to (Current))
		end
	
feature -- Duplication

	frozen clone (other: detachable ANY): like other
		obsolete "Use `twin' instead. [2017-05-31]"
			-- Void if other is void; otherwise new object
			-- equal to other
			--
			-- For non-void other, clone calls copy;
			-- to change copying/cloning semantics, redefine copy.
			-- (from ANY)
		do
			if other /= Void then
				Result := other.twin
			end
		ensure -- from ANY
			instance_free: class
			equal: Result ~ other
		end

	copy (other: COMPARABLE_GRAPH [V])
			-- Update current object using fields of object attached
			-- to other, so as to yield equal objects.
			-- (from ANY)
		require -- from ANY
			other_not_void: other /= Void
			type_identity: same_type (other)
		external
			"built_in"
		ensure -- from ANY
			is_equal: Current ~ other
		end

	frozen deep_clone (other: detachable ANY): like other
		obsolete "Use `deep_twin' instead. [2017-05-31]"
			-- Void if other is void: otherwise, new object structure
			-- recursively duplicated from the one attached to other
			-- (from ANY)
		do
			if other /= Void then
				Result := other.deep_twin
			end
		ensure -- from ANY
			instance_free: class
			deep_equal: deep_equal (other, Result)
		end

	frozen deep_copy (other: COMPARABLE_GRAPH [V])
			-- Effect equivalent to that of:
			--		copy (other . deep_twin)
			-- (from ANY)
		require -- from ANY
			other_not_void: other /= Void
		do
			copy (other.deep_twin)
		ensure -- from ANY
			deep_equal: deep_equal (Current, other)
		end

	frozen deep_twin: COMPARABLE_GRAPH [V]
			-- New object structure recursively duplicated from Current.
			-- (from ANY)
		external
			"built_in"
		ensure -- from ANY
			deep_twin_not_void: Result /= Void
			deep_equal: deep_equal (Current, Result)
		end

	frozen standard_clone (other: detachable ANY): like other
		obsolete "Use `standard_twin' instead. [2017-05-31]"
			-- Void if other is void; otherwise new object
			-- field-by-field identical to other.
			-- Always uses default copying semantics.
			-- (from ANY)
		do
			if other /= Void then
				Result := other.standard_twin
			end
		ensure -- from ANY
			instance_free: class
			equal: standard_equal (Result, other)
		end

	frozen standard_copy (other: COMPARABLE_GRAPH [V])
			-- Copy every field of other onto corresponding field
			-- of current object.
			-- (from ANY)
		require -- from ANY
			other_not_void: other /= Void
			type_identity: same_type (other)
		external
			"built_in"
		ensure -- from ANY
			is_standard_equal: standard_is_equal (other)
		end

	frozen standard_twin: COMPARABLE_GRAPH [V]
			-- New object field-by-field identical to other.
			-- Always uses default copying semantics.
			-- (from ANY)
		external
			"built_in"
		ensure -- from ANY
			standard_twin_not_void: Result /= Void
			equal: standard_equal (Result, Current)
		end

	frozen twin: COMPARABLE_GRAPH [V]
			-- New object equal to Current
			-- twin calls copy; to change copying/twinning semantics, redefine copy.
			-- (from ANY)
		external
			"built_in"
		ensure -- from ANY
			twin_not_void: Result /= Void
			is_equal: Result ~ Current
		end
	
feature -- Basic operations

	frozen as_attached: attached COMPARABLE_GRAPH [V]
		obsolete "Remove calls to this feature. [2017-05-31]"
			-- Attached version of Current.
			-- (Can be used during transitional period to convert
			-- non-void-safe classes to void-safe ones.)
			-- (from ANY)
		do
			Result := Current
		end

	frozen default: detachable COMPARABLE_GRAPH [V]
			-- Default value of object's type
			-- (from ANY)
		do
		end

	frozen default_pointer: POINTER
			-- Default value of type POINTER
			-- (Avoid the need to write p.default for
			-- some p of type POINTER.)
			-- (from ANY)
		do
		ensure -- from ANY
			instance_free: class
		end

	default_rescue
			-- Process exception for routines with no Rescue clause.
			-- (Default: do nothing.)
			-- (from ANY)
		do
		end

	frozen do_nothing
			-- Execute a null action.
			-- (from ANY)
		do
		ensure -- from ANY
			instance_free: class
		end
	
feature {NONE} 

	vertices_list: LIST [V]
		local
			l_a: SORTED_TWO_WAY_LIST [V]
		do
			Result := Precursor
			create l_a.make_from_iterable (Result)
			Result := l_a
		end
	
feature {NONE} -- Constructor

	make_empty
			-- (from GRAPH)
		do
			create edges.make_empty
			create vertices.make_empty
		end

	make_from_tuple_array (a: ARRAY [TUPLE [V, V]])
			-- (from GRAPH)
		local
			l_pair: PAIR [V, V]
		do
			create vertices.make_empty
			create edges.make_empty
			across
				a as pair
			loop
				l_pair := create {attached PAIR [V, V]}.make_from_tuple (pair.item)
				edges.extend (l_pair)
				vertices.extend (l_pair.first)
				vertices.extend (l_pair.second)
			end
		end
	
feature -- Conversion to array.

	array_compare (a, b: ARRAY [TUPLE [V, V]]): BOOLEAN
			-- compare two arrays of tuple
			-- (from GRAPH)
		local
			l_a, l_b: PAIR [V, V]
			i: INTEGER_32
		do
			if a.count = b.count and a.lower = b.lower then
				from
					i := a.lower
					Result := True
				until
					i > a.count or not Result
				loop
					l_a := create {attached PAIR [V, V]}.make_from_tuple (a [i])
					l_b := create {attached PAIR [V, V]}.make_from_tuple (a [i])
					Result := Result and l_a ~ l_b
					i := i + 1
				end
			end
		end

	as_array: ARRAY [TUPLE [V, V]]
			-- Return edges as an array of tuples
			-- (from GRAPH)
		do
			create Result.make_from_array (edges.as_array)
			Result.compare_objects
		end
	
feature -- Iterable

	new_cursor: ITERATION_CURSOR [V]
			-- Fresh cursor associated with current structure
			-- (from GRAPH)
		do
			Result := vertices.new_cursor
		ensure -- from ITERABLE
			result_attached: Result /= Void
		end
	
feature -- Output

	Io: STD_FILES
			-- Handle to standard file setup
			-- (from ANY)
		once
			create Result
			Result.set_output_default
		ensure -- from ANY
			instance_free: class
			io_not_void: Result /= Void
		end

	print (o: detachable ANY)
			-- Write terse external representation of o
			-- on standard output.
			-- (from ANY)
		do
			if o /= Void then
				Io.put_string (o.out)
			end
		ensure -- from ANY
			instance_free: class
		end

	frozen tagged_out: STRING_8
			-- New string containing terse printable representation
			-- of current object
			-- (from ANY)
		external
			"built_in"
		ensure -- from ANY
			tagged_out_not_void: Result /= Void
		end
	
feature -- Platform

	Operating_environment: OPERATING_ENVIRONMENT
			-- Objects available from the operating system
			-- (from ANY)
		once
			create Result
		ensure -- from ANY
			instance_free: class
			operating_environment_not_void: Result /= Void
		end
	
feature {NONE} -- Retrieval

	frozen internal_correct_mismatch
			-- Called from runtime to perform a proper dynamic dispatch on correct_mismatch
			-- from MISMATCH_CORRECTOR.
			-- (from ANY)
		local
			l_msg: STRING_8
			l_exc: EXCEPTIONS
		do
			if attached {MISMATCH_CORRECTOR} Current as l_corrector then
				l_corrector.correct_mismatch
			else
				create l_msg.make_from_string ("Mismatch: ")
				create l_exc
				l_msg.append (generating_type.name)
				l_exc.raise_retrieval_exception (l_msg)
			end
		end
	
feature -- Sorted outgoing edges

	adjacent (v: V): SEQ [V]
			-- Sorted list of outgoing edges from v
		require -- from  GRAPH
			True
		local
			sorted: SORTED_TWO_WAY_LIST [V]
		do
			create sorted.make
			across
				outgoing (v) as e
			loop
				sorted.extend (e.item.second)
			end
			create Result.make_empty
			across
				sorted as x
			loop
				Result.append (x.item)
			end
		ensure -- from GRAPH
			consistent_counts: Result.count = outgoing (v).count
			source_is_v: across
					Result as x
				all
					outgoing (v).has (create {PAIR [V, V]}.make_from_tuple ([v, x.item]))
				end
		ensure then
			sorted: across
					1 |..| (Result.count - 1) as i
				all
					Result [i.item] < Result [i.item + 1]
				end
		end
	
feature -- advanced queries

	cycle (v: V): detachable SEQ [V]
			-- Return a cycle starting from v if any.
			-- (from GRAPH)
		do
			Result := dfs_for_cycle (v)
		end

	is_a_shortest_path (v1, v2: V; seq: SEQ [V]): BOOLEAN
			-- does seq denote a shortest path between v1 and v2?
			-- When there are multiple shortest paths between v1 and v2,
			-- return TRUE if seq is any one of them.
			-- (from GRAPH)
		do
			Result := is_valid_path (seq) and then seq.first ~ v1 and then seq.last ~ v2 and then across
				paths (v1, v2) as path
			all
				seq.count <= path.item.count
			end
		end

	is_acyclic: BOOLEAN
			-- Does the graph contain no cycles?
			-- (from GRAPH)
		local
			it: ITERATION_CURSOR [V]
		do
			from
				Result := True
				it := vertices.new_cursor
			until
				not Result or else it.after
			loop
				Result := not attached cycle (it.item)
				it.forth
			end
		ensure -- from GRAPH
				Result = across
					vertices is l_v
				all
					not attached cycle (l_v)
				end
		end

	is_equal (other: COMPARABLE_GRAPH [V]): BOOLEAN
			-- Is other attached to an object considered
			-- equal to current object?
			-- (from GRAPH)
		require -- from ANY
			other_not_void: other /= Void
		do
			Result := Current |<: other and other |<: Current
		ensure -- from ANY
			symmetric: Result implies other ~ Current
			consistent: standard_is_equal (other) implies Result
		end

	is_reachable (v1, v2: V): BOOLEAN
			-- (from GRAPH)
		require -- from GRAPH
				has_vertex (v1) and has_vertex (v2)
		do
			Result := attached shortest_path (v1, v2)
		ensure -- from GRAPH
				Result = attached shortest_path (v1, v2)
		end

	is_subgraph alias "|<:" (other: COMPARABLE_GRAPH [V]): BOOLEAN
			-- (from GRAPH)
		do
			Result := vertices |<: other.vertices and edges |<: other.edges
		end

	is_topologically_sorted (seq: like topologically_sorted): BOOLEAN
			-- (from GRAPH)
		do
			Result := seq.count = vertices.count and then across
				seq as v
			all
				vertices.has (v.item)
			end and then across
				1 |..| seq.count as i
			all
				across
					1 |..| seq.count as j
				all
					i.item = j.item or else (edges.has (create {PAIR [V, V]}.make_from_tuple ([seq [i.item], seq [j.item]])) implies i.item < j.item)
				end
			end
		end

	is_valid_path (seq: SEQ [V]): BOOLEAN
			-- Does seq denote a valid path in graph?
			-- (from GRAPH)
		require -- from GRAPH
			at_least_one_vertex: not seq.is_empty
		local
			l_i: INTEGER_32
		do
			from
				l_i := 2
				Result := vertices.has (seq [1])
			until
				not Result or else l_i > seq.count
			loop
				Result := edges.has (create {PAIR [V, V]}.make_from_tuple ([seq [l_i - 1], seq [l_i]]))
				l_i := l_i + 1
			end
		ensure -- from GRAPH
			singleton_path: seq.count = 1 implies (vertices.has (seq [1]) = Result)
			longer_path: seq.count > 1 implies (Result = across
					2 |..| seq.count as i
				all
					edges.has (create {PAIR [V, V]}.make_from_tuple ([seq [i.item - 1], seq [i.item]]))
				end)
		end

	paths (v1, v2: V): SET [SEQ [V]]
			-- Return the set of all acyclic paths (ones not containing cycles) between v1 and v2.
			-- (from GRAPH)
		local
			parents: REL [V, V]
			init_suffixes: SET [SEQ [V]]
			init_visited: SET [V]
		do
			parents := bfs_for_paths (v1)
			create Result.make_empty
			if parents.domain.has (v2) then
				create init_visited.make_empty
				create init_suffixes.make_empty
				init_suffixes.extend (create {SEQ [V]}.make_empty)
				Result := paths_helper (v1, v2, init_visited, parents, init_suffixes)
			end
		ensure -- from GRAPH
			all_paths_are_valid: across
					Result as path
				all
					is_valid_path (path.item) and then path.item.first ~ v1 and then path.item.last ~ v2
				end
		end

	reachable (src: V): SEQ [V]
			-- Breadth-First Search
			-- Starting with vertex src,
			-- return the set of all nodes reachable from src.
			-- Uses adjacent (a sorted list in COMPARABLE_GRAPH) rather than outgoing (always unsorted REL)
			-- (from GRAPH)
		require -- from GRAPH
				has_vertex (src)
		local
			visited: SET [V]
			q: ARRAYED_QUEUE [V]
			l_front, l_adjacent: V
		do
			create Result.make_empty
			create visited.make_empty
			create q.make (vertices.count)
			q.compare_objects
			from
				q.extend (src)
			until
				q.is_empty
			loop
				l_front := q.item
				if not visited.has (l_front) then
					visited.extend (l_front)
					Result.append (l_front)
					across
						adjacent (l_front) as x
					loop
						l_adjacent := x.item
						if visited.has (l_adjacent) then
						else
							q.extend (l_adjacent)
						end
					end
				end
				q.remove
			end
		ensure -- from GRAPH
			every_vertex_in_result_is_reachable_from_src: across
					Result as v
				all
					is_reachable (src, v.item)
				end
			every_vertex_reachable_from_src_is_in_result: across
					vertices as v
				all
					is_reachable (src, v.item) implies Result.has (v.item)
				end
		end

	shortest_path (v1, v2: V): detachable SEQ [V]
			-- Return the shortest path between v1 and v2 if it exists.
			-- Bredth-First Search is used without assuming that there are no self-loops.
			-- (from GRAPH)
		local
			parent: FUN [V, V]
			complete: BOOLEAN
			current_vertex: V
		do
			parent := bfs_for_shortest_path (v1)
			if parent.domain.has (v2) then
				from
					current_vertex := v2
					create Result.make_empty
				until
					complete
				loop
					Result.prepend (current_vertex)
					if current_vertex ~ v1 then
						complete := True
					else
						check
								parent.domain.has (current_vertex)
						end
						current_vertex := parent [current_vertex]
					end
				end
			elseif v1 ~ v2 then
				create Result.make_empty
				Result.prepend (v1)
			end
		ensure -- from GRAPH
			void_result: not attached Result implies not (has_vertex (v1) and then has_vertex (v2) and then is_reachable (v1, v2))
			result_is_valid: attached Result implies is_valid_path (Result) and then Result.first ~ v1 and then Result.last ~ v2
			result_is_the_shortest: attached Result implies across
					paths (v1, v2) as path
				all
					Result.count <= path.item.count
				end
		end

	shortest_path_via_dijkstra (v1, v2: V): detachable SEQ [V]
			-- Return the shortest path between v1 and v2 if it exists.
			-- Dijkstra's algorithm is used without assuming that there are no self-loops.
			-- Cost of path: Result.count - 1
			-- (from GRAPH)
		local
			parent: FUN [V, V]
			complete: BOOLEAN
			current_vertex: V
		do
			parent := dijkstra (v1)
			if parent.domain.has (v2) then
				from
					current_vertex := v2
					create Result.make_empty
				until
					complete
				loop
					Result.prepend (current_vertex)
					if current_vertex ~ v1 then
						complete := True
					else
						check
								parent.domain.has (current_vertex)
						end
						current_vertex := parent [current_vertex]
					end
				end
			elseif v1 ~ v2 then
				create Result.make_empty
				Result.prepend (v1)
			end
		ensure -- from GRAPH
			void_result: not attached Result implies not (has_vertex (v1) and then has_vertex (v2) and then is_reachable (v1, v2))
			result_is_valid: attached Result implies is_valid_path (Result) and then Result.first ~ v1 and then Result.last ~ v2
			result_is_the_shortest: attached Result implies across
					paths (v1, v2) as path
				all
					Result.count <= path.item.count
				end
		end

	topologically_sorted: SEQ [V]
			-- Return a sequence <<..., vi, ..., vj, ...>> such that
			-- (vi, vj) in edges => i < j
			-- A topological sort is performed.
			-- (from GRAPH)
		require -- from GRAPH
				is_acyclic
		local
			in_degree: FUN [V, INTEGER_32]
			q: ARRAYED_QUEUE [V]
			front, x: V
		do
			create in_degree.make_empty
			across
				vertices as v
			loop
				in_degree.extend (create {PAIR [V, INTEGER_32]}.make_from_tuple ([v.item, incoming (v.item).count]))
			end
			create q.make (vertices.count)
			across
				in_degree as pair
			loop
				if pair.item.second = 0 then
					q.extend (pair.item.first)
				end
			end
			from
				create Result.make_empty
			until
				q.is_empty
			loop
				front := q.item
				q.remove
				Result.append (front)
				across
					adjacent (front) as adj
				loop
					x := adj.item
					in_degree.override_by ([x, in_degree [x] - 1])
					if in_degree [x] = 0 then
						q.extend (x)
					end
				end
			end
		ensure -- from GRAPH
				is_topologically_sorted (Result)
		end
	
feature -- agent functions

	vertices_edge_count: INTEGER_32
			-- total number of incoming and outgoing edges of all vertices in vertices
			-- Result = (Σv ∈ vertices : outgoing(v).count + incoming(v).count)
			-- (from GRAPH)
		do
			Result := {NUMERIC_ITERABLE [V]}.sumf (vertices, agent (a_vertex: V): INTEGER_32
					do
						Result := outgoing (a_vertex).count + incoming (a_vertex).count
					end)
		end

	vertices_incoming_edge_count: INTEGER_32
			-- total number of incoming edges of all vertices in vertices
			-- Result = (Σv ∈ vertices : incoming(v).count)
			-- (from GRAPH)
		do
			Result := {NUMERIC_ITERABLE [V]}.sumf (vertices, agent (a_vertex: V): INTEGER_32
					do
						Result := incoming (a_vertex).count
					end)
		end

	vertices_outgoing_edge_count: INTEGER_32
			-- total number of outgoing edges of all vertices in vertices
			-- Result = (Σv ∈ vertices : outgoing(v).count)
			-- (from GRAPH)
		do
			Result := {NUMERIC_ITERABLE [V]}.sumf (vertices, agent (a_vertex: V): INTEGER_32
					do
						Result := outgoing (a_vertex).count
					end)
		end
	
feature -- basic queries

	edge_count: INTEGER_32
			-- number of outgoing edges
			-- (from GRAPH)
		do
			Result := edges.count
		end

	edge_extended alias "|\/|" (e: PAIR [V, V]): COMPARABLE_GRAPH [V]
			-- extend if not already in
			-- (from GRAPH)
		require -- from GRAPH
			valid_vertices: has_vertex (e.first) and has_vertex (e.second)
		do
			Result := Current.deep_twin
			Result.edge_extend (e.deep_twin)
		end

	edge_removed alias "|\" (e: PAIR [V, V]): COMPARABLE_GRAPH [V]
			-- (from GRAPH)
		do
			Result := Current.deep_twin
			Result.edge_remove (e)
		end

	has_edge (p: PAIR [V, V]): BOOLEAN
			-- does graph have pair p
			-- can use p as tuple
			-- (from GRAPH)
		do
			Result := edges.has (p)
		end

	has_vertex (v: V): BOOLEAN
			-- (from GRAPH)
		do
			Result := vertices.has (v)
		end

	in_degree_count (v: V): INTEGER_32
			-- number of incoming edges of vertex v
			-- (from GRAPH)
		require -- from GRAPH
				has_vertex (v)
		do
			Result := incoming (v).count
		end

	incoming (v: V): REL [V, V]
			-- The set of incoming edges to v
			-- (from GRAPH)
		do
			create Result.make_empty
			across
				edges as e
			loop
				if e.item.second ~ v then
					Result.extend (e.item)
				end
			end
		ensure -- from GRAPH
			consistent_counts: Result.count = (edges @> v).count
			destination_is_v: across
					Result as e
				all
					e.item.second ~ v
				end
		end

	is_empty: BOOLEAN
			-- is the graph empty?
			-- (from GRAPH)
		do
			Result := vertex_count = 0 and edge_count = 0
		end

	out_degree_count (v: V): INTEGER_32
			-- number of outgoing edges of vertex v
			-- (from GRAPH)
		require -- from GRAPH
				has_vertex (v)
		do
			Result := outgoing (v).count
		end

	outgoing (v: V): REL [V, V]
			-- The set of outgoing edges from v
			-- (from GRAPH)
		do
			create Result.make_empty
			across
				edges as e
			loop
				if e.item.first ~ v then
					Result.extend (e.item)
				end
			end
		ensure -- from GRAPH
			consistent_counts: Result.count = (edges @< v).count
			source_is_v: across
					Result as e
				all
					e.item.first ~ v
				end
		end

	vertex_count: INTEGER_32
			-- (from GRAPH)
		do
			Result := vertices.count
		end

	vertex_extended alias "+" (v: V): COMPARABLE_GRAPH [V]
			-- extend if not already in
			-- (from GRAPH)
		do
			Result := Current.deep_twin
			Result.vertex_extend (v.deep_twin)
		end

	vertex_removed alias "-" (v: V): COMPARABLE_GRAPH [V]
			-- (from GRAPH)
		do
			Result := Current.deep_twin
			Result.vertex_remove (v)
		end
	
feature -- commands

	edge_extend (e: PAIR [V, V])
			-- connect vertex e.first to e.second
			-- if not already in
			-- (from GRAPH)
		require -- from GRAPH
			valid_vertices: has_vertex (e.first) and has_vertex (e.second)
		do
			edges.extend (e)
		ensure -- from GRAPH
				edges ~ old edges.deep_twin + create {PAIR [V, V]}.make_from_tuple ([e.first, e.second])
				vertices ~ old vertices.deep_twin
		end

	edge_remove (e: PAIR [V, V])
			-- (from GRAPH)
		do
			edges.subtract (e)
		end

	vertex_extend (v: V)
			-- insert vertex v into graph
			-- if not already in
			-- (from GRAPH)
		do
			vertices.extend (v)
		ensure -- from GRAPH
				vertices ~ old vertices.deep_twin + v
				edges ~ old edges.deep_twin
		end

	vertex_remove (v: V)
			-- Remove vertex v and all relevant edges
			-- (from GRAPH)
		local
			new_edges: like edges
		do
			vertices.subtract (v)
			create new_edges.make_empty
			across
				edges as pair
			loop
				if pair.item.first /~ v and pair.item.second /~ v then
					new_edges.extend (pair.item)
				end
			end
			edges := new_edges
		ensure -- from GRAPH
				vertices ~ old vertices.deep_twin - v
				edges ~ (old edges.deep_twin @>> v) @<< v
		end
	
feature -- infinity

	Infinity: INTEGER_64
			-- (from GRAPH)
		once
			Result := {INTEGER_64}.max_value
		end

	Zero: INTEGER_64
			-- (from GRAPH)
		once
			Result := Result.zero
		end
	
feature -- model

	edges: REL [V, V]
			-- (from GRAPH)

	vertices: SET [V]
			-- (from GRAPH)
	
feature -- out

	debug_output: STRING_8
			-- String that should be displayed in debugger to represent Current.
			-- (from GRAPH)
		local
			adjacent_list: SEQ [V]
		do
			Result := ""
			across
				vertices_list is l_vertex
			loop
				Result.append ("[" + l_vertex.out)
				adjacent_list := adjacent (l_vertex)
				if not adjacent_list.is_empty then
					Result.append (":")
				end
				across
					1 |..| adjacent_list.count is l_i
				loop
					Result.append (adjacent_list [l_i].out)
					if l_i < adjacent_list.count then
						Result.append (",")
					end
				end
				Result.append ("]")
			end
		ensure -- from DEBUG_OUTPUT
			result_not_void: Result /= Void
		end

	out: STRING_8
			-- New string containing terse printable representation
			-- of current object
			-- (from GRAPH)
		do
			Result := debug_output
		ensure -- from ANY
			out_not_void: Result /= Void
		end
	
feature {NONE} -- traversals

	bfs_for_paths (src: V): REL [V, V]
			-- Breadth-First Search
			-- Starting with vertex src,
			-- return the parentS of each reachable vertex on ALL paths back to src.
			-- (from GRAPH)
		local
			visited: SET [V]
			q: ARRAYED_QUEUE [V]
			l_front, l_adjacent: V
		do
			create Result.make_empty
			create visited.make_empty
			create q.make (vertices.count)
			from
				q.extend (src)
			until
				q.is_empty
			loop
				l_front := q.item
				if not visited.has (l_front) then
					visited.extend (l_front)
					across
						adjacent (l_front) as v
					loop
						l_adjacent := v.item
						if not visited.has (l_adjacent) then
							q.extend (l_adjacent)
						end
						Result.extend (create {PAIR [V, V]}.make_from_tuple ([l_adjacent, l_front]))
					end
				end
				q.remove
			end
		end

	bfs_for_shortest_path (src: V): FUN [V, V]
			-- Breadth-First Search
			-- Starting with vertex src,
			-- return the parent of each reachable vertex on their shortest path back to src.
			-- (from GRAPH)
		local
			visited: SET [V]
			q: ARRAYED_QUEUE [V]
			l_front, l_adjacent: V
		do
			create Result.make_empty
			create visited.make_empty
			create q.make (vertices.count)
			from
				q.extend (src)
			until
				q.is_empty
			loop
				l_front := q.item
				if not visited.has (l_front) then
					visited.extend (l_front)
					across
						adjacent (l_front) as v
					loop
						l_adjacent := v.item
						if visited.has (l_adjacent) then
						else
							q.extend (l_adjacent)
							if not Result.domain.has (l_adjacent) then
								Result.extend (create {PAIR [V, V]}.make_from_tuple ([l_adjacent, l_front]))
							end
						end
					end
				end
				q.remove
			end
		end

	dfs_for_cycle (src: V): detachable SEQ [V]
			-- Depth-First Search
			-- Starting with vertex src,
			-- return the first cycle detected if any.
			-- (from GRAPH)
		local
			visited: SET [V]
			s: ARRAYED_STACK [V]
			top, x: V
			found_a_cycle, found_an_unvisited_node: BOOLEAN
			it: ITERATION_CURSOR [V]
		do
			from
				create Result.make_empty
				create visited.make_empty
				create s.make (vertices.count)
				s.extend (src)
			until
				found_a_cycle or else s.is_empty
			loop
				top := s.item
				if visited.has (top) then
					if adjacent (top).has (top) then
						Result.append (top)
						found_a_cycle := True
					else
						s.remove
						Result.remove (Result.count)
					end
				else
					visited.extend (top)
					Result.append (top)
					from
						it := adjacent (top).new_cursor
						found_an_unvisited_node := False
					until
						found_a_cycle or else found_an_unvisited_node or else it.after
					loop
						x := it.item
						if visited.has (x) then
							Result.append (x)
							found_a_cycle := True
						else
							s.extend (x)
							found_an_unvisited_node := True
						end
						it.forth
					end
				end
			end
			if not found_a_cycle then
				check
						Result.is_empty
				end
				Result := Void
			end
		end

	dijkstra (src: V): FUN [V, V]
			-- Using Dijkstra's shortest-path algorithm to traverse the graph.
			-- Starting with vertex src,
			-- return the parent of each reachable vertex on their shortest path back to src.
			-- (from GRAPH)
		local
			q: MY_PRIORITY_QUEUE [VERTEX_DISTANCE_PAIR [V]]
			init_dist: INTEGER_64
			distance: FUN [V, INTEGER_64]
			parent: FUN [V, V]
			l_min: V
			x: V
			alt_distance: INTEGER_64
		do
			create parent.make_empty
			create distance.make_empty
			q := pq
			across
				vertices as v
			loop
				if v.item ~ src then
					init_dist := Zero
				else
					init_dist := Infinity
				end
				distance.extend (create {PAIR [V, INTEGER_64]}.make_from_tuple ([v.item, init_dist]))
				q.enqueue (vertex_distance_pair ([v.item, init_dist]))
			end
			from
			until
				q.is_empty
			loop
				l_min := q.first.vertex
				q.dequeue
				across
					adjacent (l_min) as l_x
				loop
					x := l_x.item
					if distance [l_min] = Infinity then
						alt_distance := Infinity
					else
						alt_distance := distance [l_min] + 1
					end
					if alt_distance < distance [x] then
						distance [x] := alt_distance
						q.prune (vertex_distance_pair ([x, distance [x]]))
						q.enqueue (vertex_distance_pair ([x, alt_distance]))
						parent.override_by ([x, l_min])
					end
				end
			end
			Result := parent
		end

	paths_helper (v1, v2: V; visited: SET [V]; parents: REL [V, V]; suffixes: SET [SEQ [V]]): SET [SEQ [V]]
			-- (from GRAPH)
		local
			ps: SET [V]
			new_suffixes: SET [SEQ [V]]
			new_visited: SET [V]
		do
			create new_suffixes.make_empty
			across
				suffixes as suffix
			loop
				new_suffixes.extend (suffix.item |<- v2)
			end
			if v1 ~ v2 then
				Result := new_suffixes
			else
				create Result.make_empty
				ps := (parents @< v2).range
				new_visited := visited + v2
				across
					ps as parent
				loop
					if not new_visited.has (parent.item) then
						Result.union (paths_helper (v1, parent.item, new_visited, parents, new_suffixes))
					end
				end
			end
		end
	
feature {NONE} -- traversals queries for Dijkstra's algorithm

	pq: MY_PRIORITY_QUEUE [VERTEX_DISTANCE_PAIR [V]]
		do
			create {MY_PRIORITY_QUEUE [COMPARABLE_VERTEX_DISTANCE_PAIR [V]]} Result.make_empty
		end

	vertex_distance_pair (t: TUPLE [v: V; d: INTEGER_64]): VERTEX_DISTANCE_PAIR [V]
		do
			create {COMPARABLE_VERTEX_DISTANCE_PAIR [V]} Result.make (t)
		end
	
invariant
		-- from GRAPH
	empty_consistency: vertex_count = 0 implies edge_count = 0
	valid_edge_ends: edges.domain |\/| edges.range |<: vertices
		vertex_count = vertices.count
	consistency_incoming_outgoing: across
			vertices is l_vertex
		all
			across
				outgoing (l_vertex) is l_edge
			all
				incoming (l_edge.second).has (l_edge)
			end and across
				incoming (l_vertex) is l_edge
			all
				outgoing (l_edge.first).has (l_edge)
			end
		end
	consistency_incoming_outgoing2: across
			edges is l_edge
		all
			outgoing (l_edge.first).has (l_edge) and incoming (l_edge.second).has (l_edge)
		end
	count_property_symmetry_1: vertices_edge_count = 2 * edge_count
	count_property_symmetry_2: vertices_outgoing_edge_count = vertices_incoming_edge_count
	self_loops_are_incomng_and_outgoing: across
			vertices is l_vertex
		all
			across
				incoming (l_vertex) is l_edge
			some
				l_edge.first ~ l_edge.second
			end = across
				outgoing (l_vertex) is l_edge
			some
				l_edge.first ~ l_edge.second
			end
		end

		-- from ANY
	reflexive_equality: standard_is_equal (Current)
	reflexive_conformance: conforms_to (Current)

end -- class COMPARABLE_GRAPH

Generated by ISE EiffelStudio