Skip to content

Aorta3698/catalan_toolbox

Repository files navigation

Goals

These are the goals that I'd like to achieve:

  • Conversion between tree to other well-known (generalized) Catalan structures in linear time.

  • Support for common operations such as triangulation flip for each type of Catalan structures.

  • A visualizer tool that produces publication level of svg.

  • Enumeration of well-known Catalan structures (including $k$-ary trees and $r$-dyck paths).

  • Enumeration of pattarn avoiding Catalan structures.

See Milestones for sub items break down.


Conversion Flow


Galleries

Here shows the visualization for catalan(4) in each Catalan structure. There are 14 of them for each.

For catalan(5), please click here (42 of them for each Catalan structure).

For MacOS users

You will likely encounter this error below when attempting to do triangulation flip:

nextEventMatchingMask should only be called from the Main Thread!

It is because that the visualizer is not started on the main thread and apparently Apple does not allow that - read more about it here.


Milestones

Generalized Catalan Tree generator

  • A verifiably random generator for full k-ary tree

Tree

  • Visualizer for full k-ary trees
  • Gallery for $C_4$ and $C_5$

Dyck Path

  • Convert between r-dyck path mirrored pre-order bit string and tree in O(n)
  • Convert between r-dyck path pre-order bit string and tree in O(nlog(n/r))
  • Visualizer for r-dyck path
  • Verify a given path is a valid r-dyck path or not
  • Flip mountain
  • Gallery for $C_4$ and $C_5$

Triangulation

  • Convert between polygon triangulation and binary tree in O(n)
  • Visualizer for polygon triangulation
  • Triangulation flip in O(1) with O(n) pre-processing and visualize the result
  • Verify a given polygon triangulation is a valid polygon triangulation or not
  • Gallery for $C_4$ and $C_5$

Non-intersecting Chord Graph

  • Convert between non-intersecting chord graph and binary tree in O(n)
  • Visualizer for non-intersecting chord graph
  • Exchange a chord and visualize the result
  • Verify a given chord graph is a valid non-intersecting chord graph or not
  • Gallery for $C_4$ and $C_5$

Non-crossing Arcs

  • Convert between non-crossing arcs and binary tree in O(n)
  • Visualizer for non-crossing arcs
  • Exchange an arc and visualize the result
  • Verify a given arcs is a valid non-crossing arcs or not
  • Gallery for $C_4$ and $C_5$

Coin Stack

  • Visualizer for coin stack
  • Gallery for $C_4$ and $C_5$

Enumeration

  • Package Mutze codes into a C++ library.
  • Use the above to enumerate pattern avoiding binary trees.
  • Generalize the above to all Catalan structures.
  • Plot the patterns and ask users to comfirm the patterns.
  • Plot pattern avoiding Calatan structures.
  • Save all of the above as svg files onto the disk.
  • Able to enumerate generalized Catalan structures lexicographically via an interator.

Other

  • Output full k-ary tree as a file and read from it to recreate it
  • A website that hosts all visualization for well-known Catalan structures for n >= 3 to n < ?.

Organization

  • Documentation
  • Code base rewrite to follow OOP
  • Code base rewrite to follow modern C++
  • Refactor Project structure to follow include/, obj/, src/, lib/ format.
  • Refactor Makefile to follow modern standard.
  • Compile related work

Compile Instruction

C++23

The Makefile uses -std=c++23, so make sure your g++ compiler version supports it.

Additionally, make sure that GNU GMP library is installed (bignum lib).

MacOS

Install GNU GMP and g++-14 from Homebrew.

Steps To Follow

  • Run ./install.sh

This will create a python virtual environment, install all dependencies, and then run Makefile.

It also attempts to silence the warning described below.

The provided script has been tested on:

  • Arch Linux (Distrobox within Fedora Silverblue)
  • Macbook M1 first gen

RuntimeWarning: invalid value encountered in divide

Netgraph lib currently has this warning as discussed by the library creator here; to suppress this harming warning, put

np.seterr(divide='ignore', invalid='ignore')

where the warning occurrs.

credit to this post.


Related Work

Tree

Height of Tree

Tree Generation

Tree Enumeration

Pattern Avoiding Trees Enumeration

Edge Flip Tree Graph has a Hamiltonian path and cycle


Dyck Paths


Triangulation


Catalan Structures


Counting


Super Catalan


Mixing Time


Other

About

No description, website, or topics provided.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published