Yet another Ruby graphing library. Implements some graph/vertex/edge related algorithms. Currently operates only on undirected graphs.
- find all Hamiltonian cycles in a graph using an exponential time algorithm (
hamiltonian_cycles, dynamic programming method of Bellman, Held, and Karp).
- find edges that are a part of all Hamiltonian cycles (
edges_in_all_hamiltonian_cycles, requires exponential time so may be very slow)
- find only some edges that are a part of all Hamiltonian cycles (
some_edges_in_all_hamiltonian_cycles, faster but may not find all edges)
Soon to be implemented:
- finding bridges (
bridges, requires linear time using Schmidt's chain decompositions method)
- determining 3-edge-connectivity and if 3-edge-connected (but not 4- or more), determine pairs of edges whose removal disconnects the graph (
three_edge_connections, algorithm runs in O(n^2))
Contributions are most welcome.
Copyright (c) 2014 Ben J. Woodcroft. See LICENSE.txt for further details.