forked from cfrasinaru/Graph4J
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathchanges.txt
59 lines (51 loc) · 3.39 KB
/
changes.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
1.0.8
-Generator for random Hamiltonian graphs and digraphs
-Generator for random graphs that have Ore's property: RandomOreGraphGenerator
-Palmer's algorithm for finding a Hamiltonian cycle in a graph that satisfies Ore's condition: PalmerHamiltonianCycle
-Graphs class has a new method: hasOreProperty
1.0.7 2024-03-10
-Algorithm for tree isomorphism
-Graphs class has a new method: isTree
1.0.6 2023-10-11
-Removed all implementations that require external dependencies
-VertexConnectivityAlgorithm: maximum vertex disjoint paths, minimum vertex cutset, vertex connectivity number
-EdgeConnectivityAlgorithm: maximum edge disjoint paths, minimum edge cutset, edge connectivity number
-Johnson's algorithm for determining all pairs shortes paths: JohnsonShortestPath
-A* algorithm for determining the shortest path using a distance heursitic: AStarAlgorithm
-Iterators over all cliques, with min and max size, DFS or BFS: DFSCliqueIterator, BFSCliqueIterator
1.0.5 2023-07-07
-Sequential and parallel implementations of Boruvka algorithm for MST: BoruvkaMinimumSpanningTreeDefault/Parallel
-Generator for Barabasi-Albert networks: BarabasiALbertGenerator
-Generator for Watts-Strogatz networks: WattsStrogatzGenerator
-Greedy coloring algorithms for bandwith and equitable coloring
-Exact backtracking coloring algoritms for bandwith and equitable coloring
-Generator for grid graphs and digraphs: GridGenerator
1.0.4 2023-04-27
-Parallel implementation of Filter-Kruskal algorithm for MST: ParallelFilterKruskal
-Improved algorithms for computing graph metrics (center, radius, etc): GraphMetrics
-Algorithm for counting the number of triangles in a graph: TriangleCounter
-Simple greedy heuristic for the vertex separator problem: GreedyVertexSeparator
-Parallel implementation of backtrack vertex coloring: ParallelBacktrackColoring
1.0.3 2023-04-29
- Exact algorithm for vertex coloring: BacktrackColoring
- Simple heuristic for determining a single maximal clique: MaximalCliqueFinder
- New heuristic algorithm for vertex coloring: RecursiveLargestFirst (RLF)
- New greedy coloring algorithms: Random, LargestDegreeFirst, SmallestDegreeLast, DSatur
- All graph generators run with safeMode(false)
- VertexSet uses a IntHashMap for improving the performance of vertex removal
1.0.2 2023-04-09
- Improved algorithm for enumerating maximal cliques: BronKerboschCliqueIterator
- Examples of using Graph4J API: org.graph4j.examples
- Support for tournament graphs: org.graph4j.support.Tournament
(determining if a digraph is tournament, obtaining a hamiltonian path in a tournament)
1.0.1 2023-03-19
- Algorithm for single pair shortest path: org.graph4j.alg.sp.BidirectionalDijkstra
- Algorithm for bridge detection: org.graph4j.alg.connectivity.BridgeDetectionAlgorithm
- Bug: Graph.maxVertexNumber() was not correct (should return -1 in case of an empty graph)
- Bug: Graph.addVertex() was not correct (due to maxVertexNumber being incorrect)
Moved to Graph4JExt
-ILP (Gurobi) implementation for the vertex separator problem: GurobiVertexSeparator
-ILP (Gurobi) implementation of the stable set model for equitable coloring: GurobiStableModelEquitableColoring
-CSP (Choco) implementation for vertex coloring: ChocoColoring
-Exact ILP coloring algoritms for bandwith and equitable coloring (using Gurobi)
-ILP (Gurobi) implementation of the assignment model for vertex coloring: GurobiAssignmentColoring