ideal • runtime • graphs • base

class base graph[readonly data vertice type, readonly data edge type]

extends debuggable

implements graph[vertice type, edge type]

private class edge[readonly data vertice type, readonly data edge type]

implements immutable data

vertice type from

vertice type to

edge type the source

edge(vertice type from, vertice type to, edge type the source)

this • from = from

this • to = to

this • the source = the source

protected equivalence relation[vertice type] equivalence

private dictionary[vertice type, set[edge[vertice type, edge type]]] all edges

overload base graph(equivalence relation[vertice type] equivalence)

this • equivalence = equivalence

this • all edges = hash dictionary[vertice type, set[edge[vertice type, edge type]]] • new()

overload base graph()

this(runtime util • default equivalence !> readonly value !> equivalence relation[vertice type])

override readonly set[vertice type] vertices()

return all edges • keys()

override void add edge(vertice type from, vertice type to, edge type the source)

new edge : edge[vertice type, edge type] • new(from, to, the source)

outgoing edges : all edges • get(from)

if outgoing edges is_not null

outgoing edges • add(new edge)

else

new outgoing edges : hash set[edge[vertice type, edge type]] • new()

new outgoing edges • add(new edge)

all edges • put(from, new outgoing edges)

override immutable set[vertice type] adjacent(vertice type from) pure

edge set : all edges • get(from)

if edge set is null

return empty[vertice type] • new()

adjacent vertices : hash set[vertice type] • new()

for (edge : edge set • elements)

adjacent vertices • add(edge • to)

return adjacent vertices • frozen copy()

override boolean introduces cycle(vertice type from, vertice type to) pure

if equivalence(from, to)

return true

list[vertice type] considered : base list[vertice type] • new(from, to)

visited : hash set[vertice type] • new()

visited • add(from)

visited • add(to)

for (considered vertice : considered)

for (target vertice : adjacent(considered vertice) • elements)

if visited • contains(target vertice)

if equivalence(target vertice, from)

return true

else

considered • append(target vertice)

visited • add(target vertice)

return false