An implementation of directed graph with powerful graph matching functionality.
Anything could change in the next releases.
This library is experimental and NOT production-ready by any means.
In this library, a graph has two main components: Node and DEdge. Node[N] contains id:Int and a value of type N .DEdge[E] has from:Int and to:Int and value of type E.
Using:
resolvers += Resolver.sonatypeRepo("snapshots")
libraryDependencies += "com.github.omidb" %%% "dgraph" % "0.1.0-SNAPSHOT"##Create Graph
There are two main ways you can create a graph:
Using Nodes and Edges
val nodes = Map(0 -> Node("n0", 0), 1 -> Node("n1", 1), 2 -> Node("n2", 2))
val edges = TreeMap((0,1) -> DEdge("e0",0,1), (1,0) -> DEdge("e1",1,0), (1,2) -> DEdge("e2",1,2))
val g:Dgraph[String,String] = DGraph.from(nodes,edges)###Using a recursive representation
Using QNodeLike and HalfEdgeLike you can represent different recursive graphs, but it will get converted to Dgraph.
Following all are QNodeLike :
QNode is a simple node
QNodeMarker is a node with a mark for future references
QNodeRef is a references to a marker node
Following are all HalfEdgeLike :
HalfEdge is an edge to a node
EmprtHalfEdge is an empty node and edge
Here is an example:
val g:Dgraph[String,String] = DGraph.from(QNode("n0", HalfEdge("e0", QNode("n1", EmptyHalfEdge))))For all these we provide a DSL to make things easier:
import DGraphDSL._
val g = DGraph.from[String,String](
Nd("n0",
--("e0")->Nd("n1"),
--("e1")->Nd("n2"),
--("e2")->Nd("n3"))
)
val g2 = DGraph.from[String,String](
Nd("n0",
--("e0")->NdMark("n1","mrk1"),
--("e1")->Nd("n2"),
--("e2")->Nd("n3",
--("e3")->(Ref("mrk1"))))
)##Graph Pattern
This library provides algorithms for graph matching. A pattern for matching on graphs is a graph of DGraph[NodeMatchLike[N],EdgeMatchLike[E]] which both NodeMatchLike[N] and EdgeMatchLike[E] contains an eval function of T=> Boolean
The following are all NodeMatchLike[N]:
NodeMatchAND[N] all the output edge-nodes should be true <&()
NodeMatchANDCons[N] all the output edge-nodes should be true (order is important) <&()
NodeMatchOR[N] one of the output edge-nodes is enough to be true <|()
We can use our DSL to define the pattern graph:
val q = query[String,String](
<&(_ == "n0",
-?>(_ == "e0", <&(_ == "n1"))
)
)-?> is a simple EdgeMatch ...
##Graph Operations:
let's assume we have a graph:
import DGraphDSL._
val g = DGraph.from[String,String](
Nd("n0",
--("e0")->NdMark("n1","mrk1"),
--("e1")->Nd("n2"),
--("e2")->Nd("n3",
--("e3")->(Ref("mrk1"))))
)and a pattern:
val q = query[String,String](
<&(_ == "n0",
-?>(_ == "e0", <&(_ == "n1"))
)
)We can perform many operations on it like Scala collections:
g.containsNode("n0") //check if it contains a node
g.containsEdge("e0") //check if it contains an edge
g.contains(q) //check if it contains a subgraph that matches the q query
g.mapByNodes(_.toInt) //convert the graph by mapping nodes
g.mapByEdges(e => e.toInt + 1) //convert the graph by mapping edges
g.map(_.toInt, _.toInt + 1) //convert the graph by two different map functions
g.filterNodes(_.startWith("n0")) //filtering nodes
g.filterEdges(_.startWith("e0")) //filtering edges
g.filter(q) // return List[DGraph[String,String]] of sub-graphs that match the queryAll the functions above use GraphMatch.mtch(g, q) that returns all possible matches between graph g and query q.
If you want to extract some information from graph and convert it to a record (case class) you can do the following:
Let's say you have the following graph and you want to extract some specific items from it.
import DGraphDSL._
case class SimpleExtract(n0:String, n3:String, e3:String)
val g = DGraph.from[String,String](
Nd("n0",
--("e0")->Nd("n1"),
--("e1")->Nd("n2"),
--("e2")->Nd("n3",
--("e3")->Nd("n4")))
)We can use queryAndExtract that will give us two graphs: A query graph and an Extractor graph
val res = queryAndExtract[String, String, SimpleExtract](
<-&(n => n == "n0", (n, p) => p.copy(n0 = n),
--?>(_ == "e2", (e,p) => p,
<-&(_ == "n3", (n, p) => p.copy(n3 = n),
--?>(_ == "e3", (e,p) => p.copy(e3 = e), <-&(_ == "n4",(n,p) => p))))
),
g, SimpleExtract("", "", "")
)
println(res.head._2)
assert(res.head._2 == SimpleExtract("n0", "n3", "e3"))As you can see, it will extract the information and updates the SimpleExtract("", "", "").
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent