I am trying to write a graph library in typescript for my application and I try to make it as generic as possible. However, I encounter this problem of type unrecognition in my code and I am not sure why it is happening. In short, BasicVertex is a concrete child class of the abstract class GraphVertex; BasicEdge is a concrete child class of the abstract class GraphEdge. CoupleGraph implements interface IGraph.
In my plan, CoupleGraph requires a concrete child class of GraphVertex (something that extends GraphVertex and instantiable) and a concrete child class of GraphEdge (something that extends GraphEdge and instantiable). Here is my code:
export abstract class GraphVertex<KT, VT> {
public abstract getKey(): KT;
public abstract getValue():VT;
}
export abstract class GraphEdge<KT, VT, EKT, EVT>{
edgeDirectional: boolean = false;
edgeWeighted: boolean = false;
// node1: GraphNode<KT, VT>;
// node2: GraphNode<KT, VT>;
weight?: number;
abstract getKey(): EKT;
abstract getNodeKeyLeadTo(nodeKey:KT):KT;
}
export interface IGraph<KT, VT, EKT, EVT> {
getNodes(): GraphVertex<KT, VT>[];
getNodeKeys(): KT[];
getNeighborVertices(node: KT): GraphVertex<KT,VT>[];
getNeighborVerticeKeys(node: KT): KT[];
getEdges(): GraphEdge<KT,VT, EKT, EVT>[];
getIncidentEdges(node:KT): GraphEdge<KT,VT, EKT, EVT>[];
getIncidentEdgeKeys(node:KT): EKT[];
areAdjacent(node1: KT, node2: KT): boolean;
insertNode(key:KT, value:VT):void;
removeNode(key:KT):void;
insertEdge(key1:KT, key2:KT, weight?:number): void;
removeEdge(key1:KT, key2: KT):void;
getNodeByKey(nodeKey:KT):GraphVertex<KT,VT>;
getEdgeByKey(edgeKey:EKT):GraphEdge<KT,VT,EKT,EVT>;
}
export type InitableKeyValueVertexClass<KT,VT> = GraphVertex<KT,VT> & (new(key:KT, value:VT)=>GraphVertex<KT,VT>);
export type InitableValueDefinedEdgeClass<VKT,VVT,EKT,EVT> = GraphEdge<VKT,VVT,EKT,EVT> & (new(fromNodeKey:VKT,toNodeKey:VKT,value:EVT)=>InitableValueDefinedEdgeClass<VKT,VVT,EKT,EVT>);
export class CoupleGraph<VKT,VVT,EKT,EVT,VertexClass extends InitableKeyValueVertexClass<VKT,VVT>,EdgeClass extends InitableValueDefinedEdgeClass<VKT,VVT,EKT,EVT>> implements IGraph<VKT,VVT,EKT,EVT> {
nodesMap:Map<VKT, VertexClass>;
edgesMap:Map<EKT, EdgeClass>;
nodeEdgesMap:Map<VKT,EKT[]>;
VertexObject:new(key:VKT, value:VVT)=> VertexClass;
EdgeObject:new(fromNodeKey:VKT,toNodeKey:VKT,value:EVT)=>EdgeClass
constructor(VertexObject:new(key:VKT, value:VVT)=> VertexClass, EdgeObject:new(fromNodeKey:VKT,toNodeKey:VKT,value:EVT)=>EdgeClass) {
// super();
this.nodesMap = new Map<VKT,VertexClass>();
this.edgesMap = new Map<EKT,EdgeClass>();
this.nodeEdgesMap = new Map<VKT,EKT[]>();
this.VertexObject = VertexObject;
this.EdgeObject = EdgeObject;
}
public getNodes(): VertexClass[] {
const nodes:VertexClass[] = [];
for (const [nodeKey, node] of this.nodesMap) {
nodes.push(node);
}
return nodes;
}
public getNodeKeys(): VKT[] {
const nodes:VKT[] = [];
for (const [nodeKey, node] of this.nodesMap) {
nodes.push(nodeKey);
}
return nodes;
}
public getNeighborVertices(nodeKey: VKT): VertexClass[] {
const nodes:VertexClass[] = [];
const edgeKeys = this.getIncidentEdgeKeys(nodeKey);
for (const edgeKey of edgeKeys) {
const edge = this.getEdgeByKey(edgeKey);
const otherNodeKey = edge.getNodeKeyLeadTo(nodeKey);
nodes.push(this.getNodeByKey(otherNodeKey));
}
return nodes;
}
public getNodeByKey(nodeKey:VKT) {
const node = this.nodesMap.get(nodeKey);
if (!node) throw new Error(`Node with key [${nodeKey}] not exist`);
return node;
}
public getEdgeByKey(edgeKey:EKT) {
const edge = this.edgesMap.get(edgeKey);
if (!edge) throw new Error(`Edge with key ${edgeKey} not exist`);
return edge;
}
public getNeighborVerticeKeys(nodeKey: VKT): VKT[] {
const nodeKeys:VKT[] = [];
const edgeKeys = this.getIncidentEdgeKeys(nodeKey);
for (const edgeKey of edgeKeys) {
const edge = this.getEdgeByKey(edgeKey);
const otherNodeKey = edge.getNodeKeyLeadTo(nodeKey);
nodeKeys.push(otherNodeKey);
}
return nodeKeys;
}
public getEdges(): EdgeClass[] {
const edges:EdgeClass[] = [];
for (const [edgeKey, edge] of this.edgesMap) {
edges.push(edge);
}
return edges;
}
public getIncidentEdges(nodeKey: VKT): EdgeClass[] {
const edges:EdgeClass[] = [];
for (const edgeKey of this.getIncidentEdgeKeys(nodeKey)) {
edges.push(this.getEdgeByKey(edgeKey));
}
return edges;
}
public getIncidentEdgeKeys(node: VKT): EKT[] {
const edgeKeys = this.nodeEdgesMap.get(node);
if (!edgeKeys) throw new Error(`Node with key ${node} not exist`);
return edgeKeys;
}
public areAdjacent(node1: VKT, node2: VKT): boolean {
const edges = this.getIncidentEdges(node1);
for (const edge of edges) {
const otherNodeKey = edge.getNodeKeyLeadTo(node1);
if (otherNodeKey === node2) return true;
}
return false;
}
public insertNode(key: VKT, value: VVT): void {
const existNode = this.nodesMap.get(key);
if (existNode) throw new Error(`Fail to get Vertex: vertex with key ${key} already exists.`);
const node = new this.VertexObject(key,value);
}
public removeNode(key: VKT): void {
throw new Error("Method not implemented.");
}
public insertEdge(key1: VKT, key2: VKT, weight?: number | undefined): void {
throw new Error("Method not implemented.");
}
public removeEdge(key1: VKT, key2: VKT): void {
throw new Error("Method not implemented.");
}
}
class BasicVertex<VKT,VVT> extends GraphVertex<VKT,VVT> {
key:VKT;
value:VVT
constructor(key:VKT,value:VVT) {
super();
this.key = key;
this.value = value;
}
getValue(): VVT {
throw new Error("Method not implemented.");
}
public getKey(): VKT {
throw new Error("Method not implemented.");
}
}
class BasicEdge<VKT,VVT,EKT,EVT> extends GraphEdge<VKT,VVT,EKT,EVT> {
fromNodeKey:VKT;
constructor(fromNodeKey:VKT,toNodeKey:VKT,value:EVT) {
super();
this.fromNodeKey = fromNodeKey;
}
getKey(): EKT {
throw new Error("Method not implemented.");
}
getNodeKeyLeadTo(nodeKey: VKT): VKT {
throw new Error("Method not implemented.");
}
}
My above implementation is compilable and syntax-correct. But when I try to instantiate a CoupleGraph that takes BasicVertex and BasicEdge:
const g = new CoupleGraph<string,string,string,string,
BasicVertex<string,string>,
BasicEdge<string, string, string, string>>(BasicVertex, BasicEdge);
I got error
Type 'BasicVertex<string, string>' does not satisfy the constraint 'GraphVertex<string, string> & (new (key: string, value: string) => GraphVertex<string, string>)'.
Type 'BasicVertex<string, string>' is not assignable to type 'new (key: string, value: string) =>
GraphVertex<string, string>'.
Type 'BasicVertex<string, string>' provides no match for the signature 'new (key: string, value: string): GraphVertex<string, string>'.
I don't understand why I am getting this error cuz BasicVertex<string, string> has constructor (key:string,value:string)=>BasicVertex<string,string> which should satisfy the signature.
And the following code also has no error in syntax or in compiling.
const v: new(key:string, value:string)=>GraphVertex<string,string>&GraphVertex<string,string> = BasicVertex<string,string>;
which means BasicVertex satisfies the type constraint right? So why is the error occurring?
const v: new(key:string, value:string)=>GraphVertex<string,string>&GraphVertex<string,string> = ...
likely doesn't mean what you think it means; parentheses will help you be explicit. You seem to meanconst v: (new(key:string, value:string)=>GraphVertex<string,string>)&GraphVertex<string,string>
but the compiler interprets it asconst v: new(key:string, value:string)=>(GraphVertex<string,string>&GraphVertex<string,string>)
. Please consider using parentheses and editing if your assumptions are wrong.GraphVertex<KT,VT> & (new(key:KT, value:VT)=>GraphVertex<KT,VT>);
to be? On the face of it that is the type of an instance ofGraphVertex
which is also a constructor ofGraphVertex
. It's very rare for an object in JavaScript to be both an instance and a constructor of the same type, so it's unlikely to be what you want. The actual use case probably calls for either an instance or a constructor, but it's not clear to me which you want. Hopefully you'll pare this down to a minimal reproducible example from which it will be more obvious.