Gryphon is a library for representing and traversing graphs.
The core concepts are in the package com.phasmidsoftware.gryphon.core. As always, consult the spec files (under test directory) to learn how to use the library.
Attributed is a trait which supports an attribute of some type. Attributed types are Graph, Edge, Vertex.
Graphs come in two basic types (represented by traits): DirectedGraph and UndirectedGraph. Only directed edges can be added to a directed graph and similarly for undirected graphs. A Graph has an attribute which is its description.
There are three kinds of edges:
- undirected edge
- directed edge
- vertex pair
A vertex pair has no representation of its connection, see VertexPair. Otherwise, undirected and directed edges are as you might expect.
The attribute type pertaining to an Edge is whatever you want it to be. If, for example, you want to work with a Minimum Spanning Tree, or the Shortest Paths Tree, then you would want your edge attribute to be orderable. In this case, you would want either a UndirectedOrderedEdge or a DirectedOrderedEdge. For edges which do not have an intrinsic ordering, use UndirectedEdge and DirectedEdge. The mechanism for providing the ordering for an edge is through the Ordering type class (part of Scala's implicits).
From the perspective of application code, vertices are represented only by their attribute. Again, you choose the appropriate attribute type. Note, however, that if you are working with undirected edges, the attribute type for a vertex must have an intrinsic ordering similarly defined to that of edges (see above).
There is a Vertex type, but it is generally only referenced internally by library methods.
Depth-first and breadth-first search are supported. In each case, a visitor of type Visitor is passed to dfs or bfs.
The visitor type provides a generic visitor which can be used by dfs or bfs. Please note that, like everything else in the Gryphon library, Visitor is immutable. It's best to see how it is used by looking at, for example, GraphSpec.
At present, there is only one application: the minimum spanning tree (MST).
Why is there no GitHub history for version 0.1.0? Was the code stolen from somewhere? No. When I created the repository, GitHub placed it in a different organization from my normal organization (rchillyard). I forked that repository and continued working on developing version 0.1.0 without paying attention to the location of the repository. The fact that the repo was forked was not very satisfactory, however, and I decided to create a brand-new repository. The history is still (currently) available as Gryphon-forked (https://github.com/rchillyard/Gryphon-forked). The first commit took place 2023/04/11 and the last commit to the forked repo was pushed on 2023/04/19.
The current version is 0.1.1
Version 0.1.0 supports the Prim application, and provides dfs and bfs graph traversal.