Playing with Algebraic Graphs (port from Swift Sandbox)

algebraic-graphs.swift

// Paper located: https://github.com/snowleopard/alga-paper
infix operator <>: AdditionPrecedence
protocol Semigroup {
	static func <>(lhs: Self, rhs: Self) -> Self
}
protocol Monoid: Semigroup {
	static var empty: Self { get }
}
protocol CommutativeMonoid: Monoid { }
protocol BoundedSemilattice: CommutativeMonoid { }


/*protocol Graphish {
	associatedtype Vertex
	static func vertex(_ v: Vertex) -> Self
	static var empty: Self { get }
	
	associatedtype Overlay: BoundedSemilattice
	// actually a monoid we want a unified empty
	associatedtype Connect: Semigroup
}
extension Graphish {
	static var empty: Self {
		return Overlay.empty
	}
	static func overlay(_ g1: Self, _ g2: Self) -> Self {
		return Overlay.<>(g1, g2)
	}
	static func connect(_ g1: Self, _ g2: Self) -> Self {
		return Connect.<>(g1, g2)
	}
}*/

/// Algebraic graphs are characterised by the following 8 axioms:
/// • + is commutative and associative, i.e. x + y = y + x and
/// x + (y + z) = (x + y) + z. (idempotence implied by decomposition)
/// • (G, →,ε) is a monoid, i.e. ε → x = x, x → ε = x and
/// x → (y → z) = (x → y) → z.
/// • → distributes over +: x → (y + z) = x → y + x → z and
/// (x + y) → z = x → z + y → z.
/// • Decomposition: x → y → z = x → y + x → z + y → z
protocol Graphish {
	associatedtype Vertex
	
	static var empty: Self { get }
	static func vertex(_ v: Vertex) -> Self
	static func overlay(_ g1: Self, _ g2: Self) -> Self
	static func connect(_ g1: Self, _ g2: Self) -> Self
}
/// • → is commutative
protocol UndirectedGraphish: Graphish {}

/// • vertex x = vertices [x] and edge x y = clique [x,y].
/// • vertices xs ⊆ clique xs, where x ⊆ y means x is a
///   subgraph of y, i.e. Vx ⊆ Vy and Ex ⊆ Ey hold.
/// • clique (xs + ys) = connect (clique xs) (clique ys).
extension Graphish {
	static func edge(_ x: Self.Vertex, _ y: Self.Vertex) -> Self {
		return Self.connect(Self.vertex(x), Self.vertex(y))
	}
	
	static func edges<S: Sequence>(_ vs: S) -> Self where S.Element == (Self.Vertex, Self.Vertex) {
		return vs.map{ (x, y) in Self.edge(x, y) }.reduce(Self.empty) { Self.overlay($0, $1) }
	}
	
	static func vertices<S: Sequence>(_ vs: S) -> Self where S.Element == Self.Vertex {
		return vs.map{ Self.vertex($0) }.reduce(Self.empty) { Self.overlay($0, $1) }
	}
	
	static func clique<S: Sequence>(_ vs: S) -> Self where S.Element == Self.Vertex {
		return vs.map{ Self.vertex($0) }.reduce(Self.empty) { Self.connect($0, $1) }
	}
	
	/*static func path<S: Sequence>(_ vs: S) -> Self where S.Element == Self.Vertex {
		if let f = vs.first {
			
		} else { // count == 0
			
		}
		// return vs.map{ Self.vertex($0) }.reduce(Self.empty) { Self.}
	}*/
}

/*struct AnyGraph<V>: Graphish {
	associatedtype Vertex = V
	
	private var _empty: AnyGraph<V>
	private var _vertex: (V) -> AnyGraph<V>
	private var _overlay: (AnyGraph<V>, AnyGraph<V>) -> AnyGraph<V>
	private var _connect: (AnyGraph<V>, AnyGraph<V>) -> AnyGraph<V>
	
	init<G: Graphish>(g: G) where G.Vertex == V {
		_empty = G.empty
		_vertext = G.vertex
		_overlay = G.overlay
		_connect = G.connect
	}
	
	static var empty: Self {
		return _empty
	}
	static func vertex(_ v: Vertex) -> Self {
		return _vertex(v)
	}
	static func overlay(_ g1: Self, _ g2: Self) -> Self {
		return _overlay(g1, g2)
	}
	static func connect(_ g1: Self, _ g2: Self) -> Self {
		return _connect(g1, g2)
	}
}*/


struct TupleOf<A: Equatable & Hashable> {
	var t: (A, A)
}
extension TupleOf: Equatable {
	static func ==(lhs: TupleOf, rhs: TupleOf) -> Bool {
		return lhs.t.0 == rhs.t.0 && lhs.t.1 == rhs.t.1
	}
}
extension TupleOf: Hashable {
	var hashValue: Int {
		return t.0.hashValue ^ t.1.hashValue
	}
}
struct Relation<A: Equatable & Hashable> {
	var domain: Set<A>
	var relation: Set<TupleOf<A>>
}
extension Relation: Graphish {
	typealias Vertex = A
	
	static var empty: Relation<A> { return Relation<A>(domain: Set(), relation: Set()) }
	static func vertex(_ v: Vertex) -> Relation<A> {
		return Relation(domain: [v], relation: Set())
	}
	static func overlay(_ g1: Relation, _ g2: Relation) -> Relation {
		return Relation(domain: g1.domain.union(g2.domain), relation: g1.relation.union(g2.relation))
	}
	static func connect(_ g1: Relation, _ g2: Relation) -> Relation {
		return Relation(domain: g1.domain.union(g2.domain), relation: 
			g1.relation.union(g2.relation).union(
				Set(g1.domain.flatMap { a in
					g2.domain.map{ b in TupleOf(t: (a, b)) }
				})
			)			   
		)
	}
}

// Deep embedding
/*indirect enum Graph<A> {
	case _empty
	case _vertex(A)
	case _overlay(Graph<A>, Graph<A>)
	case _connect(Graph<A>, Graph<A>)
}
extension Graph: Graphish {
	typealias Vertex = A
	
	var empty: Graph<A> {
		return ._empty
	}
	static func vertex(_ v: Vertex) -> Graph<A> {
		return ._vertex(v)
	}
	static func overlay(_ g1: Graph<A>, _ g2: Graph<A>) -> Graph<A> {
		return ._overlay(g1, g2)
	}
	static func connect(_ g1: Graph<A>, _ g2: Graph<A>) -> Graph<A> {
		return ._connect(g1, g2)
	}

}*/

print(Relation.clique([1,2,3,4]))