New major version proposal

[JesusTheHun]

New major version proposal

Breaking changes :

• Graph is now a class, so it is instantiated with new Graph() instead of Graph().
• Graph.adjacent() now returns a Set<Node> or undefined if the node is not found.
• Graph.nodes() is no longer available. A property nodes: Set<Node> is now exposed.
• Graph.serialize() is no longer available. A standalone function serializeGraph is available instead.
• Graph.deserialize() is no longer available. A standalone function deserializeGraph is available instead.
• Graph.hasCycle() is no longer available. A standalone function hasCycle is available instead.
• All algorithm methods (i.e. graph.topologicalSort() are no longer available. A standalone function is available for each of them.
• The shortestPath algorithm now returns an object { nodes: Node[], weight: number } instead of an augmented array.

Internal changes :

• The project now uses a composition pattern. Closes #18
• Native data structure Map and Set are used instead of records and arrays. Closes #27
• Nodes are now references by their instance instead of their id property.
• The tests have been migrated to vitest in order to be able to write tests in TypeScript without troubles.
• Additional tests for types input and output have been written.
• The library is now bundled using rollup. The current solution does not support the export of types coming from type-only files. In addition, both .d.cts and .d.mts declaration files are now distributed.

Features :

• Nodes can now be anything, not just string. Closes #51, closes #38
• New functions getNode, getFirstNode, findNodes to help you retrieve node references when they are objects.
• Edge can now have properties. Closes #80
• Algorithm depthFirstSearch now accepts a function shouldFollow as an option, to conditionally follow an edge.
• Graph now accept 2 generics to define the type of the nodes and edge properties.
• The graph types are inferred from deserializeGraph() and the serialization type carries the types with it.

const g = new Graph<{ id: string }, { type: string }>();

// Good ✅
g.addNode({ id: "abcdef" });
g.setEdgeProperties(source, target, { type: 'foo' });

// Bad ❌ TS Error
g.addNode({ id: 1 });
g.setEdgeProperties(source, target, { label: 'foo' });

const node = g.nodes();
//     ^? { id: string }[]

const props = g.getEdgeProperties(source, target);
//     ^? { type: string }

## Migration

### Serialization
```diff
-const serialized = Graph().serialize();
+const serialized = serializeGraph(graph);

-const graph = Graph().deserialize(serialized);
+const graph = deserializeGraph(serialized);

Algorithms

-const sorted = graph.topologicalSort();
+const sorted = topologicalSort(graph);

-const path = graph.shortestPath();
-const nodes = path;
-const weight = path.weight;
+const { nodes, weight } = shortestPath(graph);

[curran]

Wow, this is a very invasive change! There are so many changes here, it will take me some time to review it all and consider the consequences of each one. I would prefer smaller isolated PRs that make individual changes so that each one can be considered and evaluated individually.

For example, each of the following could be done as separate PRs:

• Adding the edge attributes #80
• migration to classes
• migration from Mocha to Vitest

One thing that also comes to mind is that if we go ahead with such invasive changes that require a major version bump, let's tackle https://github.com/datavis-tech/graph-data-structure/issues/18! Ideally the graph functions would not be all in one monolithic import, but rather separate modules that could be imported and used. The migration to a class-based approach is a huge step in that direction.

Perhaps we could adopt a pattern where users of the library can import functions and then bind them to the class somehow? Or maybe they could be functions where the Graph is passed in and the functions access their internals.

In summary, I may ultimately merge in this PR, but I first need to do a thorough review of all the changes, which will take some time. I'm heading out on a trip now and will be back in July. If you'd like to get changes in sooner, please make smaller PRs.

Thanks so much for your contribution!

[JesusTheHun]

There are so many changes here, it will take me some time to review

hi @curran I didn't expect you to merge this right away 😄 but those are the changes I'm going to need to go forward in one of my project, so I thought I would share them.

Note that the breaking changes are clearly identified and contained. It will be easy for users to migrate.

1. The migration to vitest is pretty straight forward, the tests have been migrated to perform the exact same assertions.
2. The migration to a class comes with all the TypeScript sugars, that itself is tied to the possibility to reference nodes as objects instead of just string.

I would prefer smaller isolated PRs that make individual changes so that each one can be considered and evaluated individually.

I could have done separate PRs, but that would have induced substantially more work, especially for the TypeScript side of it.

One thing that also comes to mind is that if we go ahead with such invasive changes that require a major version bump, let's tackle https://github.com/datavis-tech/graph-data-structure/issues/18

This PR does not go in the right direction for #18 . Tree-shaking is not possible when using classes. The way to go would be composition :

We would have GraphData, a class that holds the data and allows to manipulate it (addNode, addEdge, etc...). Then functions that take a GraphData as first argument.

import { GraphData, topologicalSort } from 'graph-data-structure';

const graphData = GraphData.deserialize(data);
const sortedNodes = topologicalSort(graphData);

This structure would allow tree-shaking, only the imported classes and functions would be included in the app's bundle. As it is right now, I would say we avoid premature optimizations : the ESM bundle is currently 5kb, which is completely fine.

[JesusTheHun]

@curran Now you have composition ;)