Terminology: A Graph has Nodes connected by Links (directed from one node to another);
Cycle free - application: project tasks. The Links have no attributes.
If a Node has no links it is independent of the others; same applies to sets of Nodes.
When storing a graph, I reference the other nodes like this
class Graph {
public nodes: GraphNode[];
}
class GraphNode {
public id: string; // key
public label: string;
public prerequisiteId: string; // pointer - the id of the previous node
public dependentId: string; // pointer - the id of the following node
}
(why: ease of entry and retrieval, no need for storing a list; links have no attributes and can be derived on the fly)
With this, I can draw most graphs found in project plans with their tasks.
e.g.
b
a< > d
c
a=starting point
b=parallel, starts after a is complete (prerequisite: a, dependent:d)
c=parallel, starts after a is complete (prerequisite: a, dependent:d)
d=finish, starts after b+c is complete
Question A:
What graph constructs can I not represent with this model?
(please provide images or so)
When drawing the graph, I convert the structure to
class PaintNode {
public id: string;
public label: string;
public prerequisiteIds: string[]; // pointer list - the id of the previous nodes
}
The conversion from GraphNodes to PaintNodes is pretty easy.
Question B:
What is a good algorithm to convert PaintNodes to GraphNodes?
(pseudo code is fine in Java or Typescript style)
Question C:
How can I recognize that the PaintNodes cannot be converted to GraphNodes due to the restriction of the data model?
(pseudo code is fine in Java or Typescript style)
Follow up project: automatic layout