# Yargraph

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_connected?`

,`three_edge_connections`

, algorithm runs in O(n^2))

Contributions are most welcome.

## Copyright

Copyright (c) 2014 Ben J. Woodcroft. See LICENSE.txt for further details.