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] inherit GRAPH [V] redefine adjacent, vertices_list, pq, vertex_distance_pair end 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 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 then sorted: across 1 |..| (Result.count - 1) as i all Result [i.item] < Result [i.item + 1] end 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} -- 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 end -- class COMPARABLE_GRAPH
Generated by ISE EiffelStudio