Hi,
I want to let you know that I have released my library (PATG) for
graph patterns under BSD license.
Right now it is SBCL only... (I will fix this, but unfortunately I am
busy moving to UK now).
In case you ask what are graph patterns.. it is a description of
subgraph with various properties of nodes and edges. Some example,
imagine you want to find a subgraph which looks like this in some
graph *g*:
(gmatch-idxs ((0 |.| -> 1 2 3)
(1 |+| -> 1 (4 |~|))
(2 |+| -> (2 |-|) (3 |~-|))
(3 -> 1 4)
(4)
(5 |-| -> 1))
*g* :proxies #(1))
which finds graph where node 0 is fixated to node 1 in graph *g*
(proxies)
nodes 1 and 2 are "sticky" (once they find a successful match in graph
*g*, they don't change)
nodes 3 and 4 are regular nodes
and node 5 must not exist (there should be no node with edge to 1),
because it has negative flag -
edge 1 -> 4 matches edge from 1 -> 4 or 4 -> 1 because it has
bidirectional flag ~
edge 2 -> 3 with flag ~- forbids any edge 2 -> 3 and 3 -> 2, because
it has negative bidirectional flag
edge 2 -> 2 (cyclic edge) must not exist because it has negative flag
-
there is also a way to alter graphs with alterant patterns like this
one:
(gpush ((0 |0| -> (1 xxx edge again))
(1 |1|)
(2 c -> 0)
(3 d -> 1)
(4 e -> 1 2 3))
*g* :proxies #(0 1))
normal tutorial which gets you quite far in on http://common-lisp.net/project/patg/
there is no systematic documentation, because of lack of time now, but
the domain specific language consists only from 2 primitives: defmatch
and defpush (and their wrappers gmatch and gpush), so I believe that
anybody who reads the tutorial will have no problem to start using it
in case he finds this library beneficial.
The library is designed for solving user specified problems so all
important functionality like testing whether 2 nodes & edges are
equivalent, building nodes & edges from s-exp description,
visualization using graphviz and others are made using CLOS, you just
specialize the right methods. Unfortunately, using library on user
specified graphs are not in tutorial right now, but if you check how
this is accomplished for default-graph class in sources, you will have
no problem I think.
About maturity, this is basically a project which started 3 years ago,
and I have learnt CL on it to the stage where I am now (heh, still
long road to take ;-) ... It was rewritten several times from scratch,
and now I think it's stable and fast. I am using it in other project
to express AI in multi-player strategic game as a graph language which
compile the AI behavior patterns to fast CL code. Of course there are
things to improve, but the library can be quite useful as it is now.
Other areas, where this lib can be useful are internal compiler
representation (graph rewriting engine), crazy prototype object system
(where objects are graphs, with slots like nodes connected with
various properties on edges), generation engine (where data graph
describes structure you want to evolve, and patterns represent graph
constraints you want the data graph to have (or forbids)...) and many
others...
Have fun,
Karol Skocik
On Aug 23, 4:23 am, Karol Skocik <············@gmail.com> wrote:
> Hi,
> I want to let you know that I have released my library (PATG) for
> graph patterns under BSD license.
Looks interesting! Thanks for releasing it!
I don't think I have a use for it right now, but might in the future.
-- Scott