scala.collection.Graph – Call for Comments

Where's the code, so we can play with it?
Here's some simple graph implementation that I used as a template engine for the scala workflows: https://github.com/razie/razbase/blob/master/base/src/main/scala/razie/g/Graphs.scalaTests here https://github.com/razie/razbase/blob/master/base/src/test/scala/razie/g/GraphTest.scala
It allows building graphs like this x --> List(x,x,y) --| y which builds a branch and join. 
And you can do stuff like this

//------------------- begin / end subgraph
/** sub-graph root, control node: create new control node linking to all others */class WfStart(a: WfActivity*) extends WfSimple { a map (this --> _) }
/** sub-graph end, control node: find all ends of subgraph and point to this end */class WfEnd(a: WfActivity*) extends WfSimple {  // find all distinct leafs and connect them to me distint because 1->2->4 and 1->3->4  (a flatMap (x => razie.g.Graphs.entire[WfActivity, WfLink](x).dag filterNodes { z => z.glinks.isEmpty })).distinct foreach (i => i +-> this)}

Limiting traversal depth - I found that to be an invaluable help when debugging inevitable screw ups...
Anyways, maybe you can find some reusables in there. 

Cheers,Razvan
On 2010-11-14, at 7:34 AM, Peter Empen <scala-graph@arcor.de> wrote:

Hi Everyone with special interest in Scala collections and / or graphs:

I’ve been working on a graph collection, fitting ideally into the 2.8
collection package of the Scala Library. Aiming a contribution, I’d like to
evaluate with you

a) whether Graph should become part of the Scala Library,
b) what you think about my design from the users perspective and
c) what features should be provided as a minimum.

Notational note: Writing "Graph" (G in capital) I’m pinpointing the targeted
Scala type while "graph" (lower case) should refer to the mathematical term.

A) Why Graph?
-------------
Most of you will have dealt with problem domains including elements with graph-
like structures. But how to proceed in Scala? Everybody has to start out on
his own because the Scala Library does not support graphs directly, yet.
There are some well-featured Java frameworks for graphs but they don’t really
fit into Scala. Those, for instance, who set up http://code.google.com/p/scala-
graphs/wiki/Requirements in 2009 have realized this lack, too, but their
undertaking seems to have come to a halt.

So, a few months ago, I also decided to start programming graphs in Scala on
my own. Doing so, I’ve  focused on integration with the 2.8 collections
framework. In spite of the promise of easy creation of custom collections, I
ran into several problems. This was mainly because Graph needs two type
parameters and if you look at the implementation details of Map, the other
collection with two type parameters, you’ll understand, why this task was non-
trivial. I think my work could be valuable for the Scala Community.

A?
Do you feel it makes sense for graphs to become part of the Scala Library?

B) Design Principles
--------------------
Let me outline some design principles of Graph from the users perspective:

(1) Mutable, immutable

In-line with general scala.collection principles, Graph has its immutable and
mutable variants defaulting to immutable.

(2) Type parameters

Graph has two type parameters: one for the contained nodes (vertices) and one
for the contained relations (they usually speak of edges).

(3) Upper bounds of the type parameters

Graph doesn’t impose any restrictions on the type of nodes meaning that the
upper bound of the nodes type parameter is Any. In contrast, the type
parameter for relations has a specific upper bound: Relation.

trait Graph[N, R <: Relation[N]]

Why Relation? As needed in case of hypergraphs, relations contain 2 to n
nodes. Therefore, relations are the most general kind of edges. Edges can be
thought of as special relations connecting 2 vertices meaning that Edge should
be derived from Relation. The point is that we want Graph to encompass
hypergraphs, as well.

(4) Factories

You can instantiate a Graph as easily as you are accustomed when using List,
Set etc. If you pass the factory arguments of the type Relation they will be
wrapped by Rel, otherwise by Node – see (6) for what is wrapping good for.

(4.1) One node
scala> val g = Graph(1)
g: scala.collection.Graph[Int,Nothing] = Graph(Node(1))
scala> g.nodes
res0: g.Nodes = Set(1)
scala> g.relations
res1: g.Relations = Set()

(4.2) Nodes and relations
scala> val h = Graph("A", Relation("A","B"))
h: scala.collection.Graph[java.lang.String,scala.collection.Relation
[java.lang.String]] = Graph(Node(B), Node(A), Rel(Relation(Nodes(A, B))))
scala> h.nodes
res2: h.Nodes = Set(B, A)
scala> h.relations
res3: h.Relations = Set(Relation(Nodes(A, B)))

(4.3) Nodes and edges
scala> val i = Graph(1, Edge(1,3))
i: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
Graph(Node(3), Node(1), Rel(Edge(Nodes (1, 3))))

(4.4) Explicit type parameters
If you don’t pass at least one node and one Relation, the missing type
parameter will be inferred to Nothing, what is at the moment language- /
compiler-inherent, so better you define them explicitly:

val j = Graph[Int, Edge[Int]] (Edge(1,3))
j: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
Graph(Node(3), Node(1), Rel(Edge(Nodes(1, 3))))

(4.5) Specific graphs
Common graph types have their own specific factories:
SimpleGraph, MultiGraph, DirectedGraph, UndirectedGraph
At the moment, Graph is the most common graph namely hypegraph, but I’m afraid
this is not the best suitable naming.

(5) Consistency

Graph seamlessly maintains a consistent state of the nodes and relations sets.
This basically includes the following:

(5a) Nodes of a relation being added will also be added to the nodes set if
not yet included.

(5b) By default, nodes participating in any relation of the relation set
cannot be removed. However, you can force node removal in which case all
relations with a back reference to the node to be removed will also be removed.

(5c) More constraints on specific graphs…

(6) SetLike

Graph is SetLike allowing you to use the same operators whether adding (+, +=)
or subtracting (-, -=) nodes or relations. Utilizing the SetLike-interface,
you no more need to verbose the nodes or relations set. This is simply
achieved by letting right-hand operands being an instance of Relation
implicitly map to the relations set while all other operands to the nodes set.
Also, traversing through Graph you’ll get both nodes and relations. Certainly
it’s up to you to traverse the nodes or relations set directly.

To handle passing arguments to Graph through SetLike it was necessary to wrap
them to Node respectively Rel. This wrapping only takes place when passing
parameters or traversing Graph through the SetLike interface,  so for any
internal algorithm there is no performance penalty.

Just a few examples for how SetLike can make code more compact:

(6.1) Add a node
scala> Graph[Any,Edge[Any]]("A") + 1
res1: scala.collection.Graph[Any,scala.collection.Edge[Any]] =
Graph(Node(A), Node(1))

(6.2) Remove an edge
scala> Graph[Int,Edge[Int]](Edge(1,1), Edge(1,2)) - Edge(1,1)
res2: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
Graph(Node(1), Node(2), Rel(Edge(Nodes (1, 2))))

(6.3) As a main benefit, all other SetLike-methods work, too. For instance,
let’s try filter:
scala> val g = Graph(1, Edge(2,3))
g: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
Graph(Node(3), Node(1), Node(2), Rel(Edge(Nodes(2, 3))))
scala> g.filter (nodePredicate((i:Int) => i>1))
res7: scala.collection.Graph[Int,scala.collection.Relation[Int]] =
Graph(Node(3), Node(2), Rel(Relation(Nodes(2, 3))))

(6.4) shorthand for 6.3
scala> g.filter ((i:Int) => i>1)

(7) Properties

It may be of great value to be able to define behavior such as (5b) or
optimization properties for a Graph instance. An example for the letter is
whether for each node a set of its connectors should be maintained
additionally for speed optimisation.

Properties can be set at instantiation time like
Graph( WITH_CONNECTORS_SETS )( node1, node2, rel1, rel2 )
or anytime later.

B?
=> => => Any suggestions on how to improve Graph’s design?

C) Feature Planning
-------------------
I’d say the above foundations are in a usable state.

At the moment, Graph is not intended to cover graph theory. It just aims to be
a suitable basement to build upon. More aspects of the graph theory including
vector spaces or algorithms, could be appended successively.

Graph is designed for direct usage but also for easy extensibility in mind.
Its documentation also serves as a cookbook for how to deal with custom graphs
such as attributed graphs.

C?
=> => => Which features, in your opinion, are essential for a potential first
release of Graph?

Cheers
Peter

Hi,

Peter Empen wrote:
(snip)
> A?
> Do you feel it makes sense for graphs to become part of the Scala Library?

I think so, yes, absolutely. It is a very common data structure and a ton of algorithms "off the bookshelf" operate on graphs.

(snip)
> B?
> => => => Any suggestions on how to improve Graph’s design?
If you could point me/us to the code to play around with, I am sure there'll be some ideas incoming.

(snip)
> C?
> => => => Which features, in your opinion, are essential for a potential first
> release of Graph?

It seems like what you've already got is a pretty solid foundation. Although some weak spots might be best discovered by playing around with the thing.

Cheers for your work and for taking the time to write about it thoroughly.

Kind regards
Andreas

In my experience, it is not that important to have a set of base graph
types with various variants (directed, undirected, etc..). It is more
important to have the ability to map a custom structure into a graph and
then perform graph related operations (wide visiting, deep visiting,
etc..) on it, while inserting your own code into key parts of those
operations.

So basically it would be nice to have some kind of Graph. The some kind
of GraphView extends Graph that can be mapped to custom structures. And
a bunch of graph related algorithms operating on Graph and extensible at
key points.

Linas.

On Sun, 2010-11-14 at 12:34 +0000, Peter Empen wrote:
> Hi Everyone with special interest in Scala collections and / or graphs:
>
> I’ve been working on a graph collection, fitting ideally into the 2.8
> collection package of the Scala Library. Aiming a contribution, I’d like to
> evaluate with you
>
> a) whether Graph should become part of the Scala Library,
> b) what you think about my design from the users perspective and
> c) what features should be provided as a minimum.
>
> Notational note: Writing "Graph" (G in capital) I’m pinpointing the targeted
> Scala type while "graph" (lower case) should refer to the mathematical term.
>
> A) Why Graph?
> -------------
> Most of you will have dealt with problem domains including elements with graph-
> like structures. But how to proceed in Scala? Everybody has to start out on
> his own because the Scala Library does not support graphs directly, yet.
> There are some well-featured Java frameworks for graphs but they don’t really
> fit into Scala. Those, for instance, who set up http://code.google.com/p/scala-
> graphs/wiki/Requirements in 2009 have realized this lack, too, but their
> undertaking seems to have come to a halt.
>
> So, a few months ago, I also decided to start programming graphs in Scala on
> my own. Doing so, I’ve focused on integration with the 2.8 collections
> framework. In spite of the promise of easy creation of custom collections, I
> ran into several problems. This was mainly because Graph needs two type
> parameters and if you look at the implementation details of Map, the other
> collection with two type parameters, you’ll understand, why this task was non-
> trivial. I think my work could be valuable for the Scala Community.
>
> A?
> Do you feel it makes sense for graphs to become part of the Scala Library?
>
> B) Design Principles
> --------------------
> Let me outline some design principles of Graph from the users perspective:
>
> (1) Mutable, immutable
>
> In-line with general scala.collection principles, Graph has its immutable and
> mutable variants defaulting to immutable.
>
> (2) Type parameters
>
> Graph has two type parameters: one for the contained nodes (vertices) and one
> for the contained relations (they usually speak of edges).
>
> (3) Upper bounds of the type parameters
>
> Graph doesn’t impose any restrictions on the type of nodes meaning that the
> upper bound of the nodes type parameter is Any. In contrast, the type
> parameter for relations has a specific upper bound: Relation.
>
> trait Graph[N, R <: Relation[N]]
>
> Why Relation? As needed in case of hypergraphs, relations contain 2 to n
> nodes. Therefore, relations are the most general kind of edges. Edges can be
> thought of as special relations connecting 2 vertices meaning that Edge should
> be derived from Relation. The point is that we want Graph to encompass
> hypergraphs, as well.
>
> (4) Factories
>
> You can instantiate a Graph as easily as you are accustomed when using List,
> Set etc. If you pass the factory arguments of the type Relation they will be
> wrapped by Rel, otherwise by Node – see (6) for what is wrapping good for.
>
> (4.1) One node
> scala> val g = Graph(1)
> g: scala.collection.Graph[Int,Nothing] = Graph(Node(1))
> scala> g.nodes
> res0: g.Nodes = Set(1)
> scala> g.relations
> res1: g.Relations = Set()
>
> (4.2) Nodes and relations
> scala> val h = Graph("A", Relation("A","B"))
> h: scala.collection.Graph[java.lang.String,scala.collection.Relation
> [java.lang.String]] = Graph(Node(B), Node(A), Rel(Relation(Nodes(A, B))))
> scala> h.nodes
> res2: h.Nodes = Set(B, A)
> scala> h.relations
> res3: h.Relations = Set(Relation(Nodes(A, B)))
>
> (4.3) Nodes and edges
> scala> val i = Graph(1, Edge(1,3))
> i: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
> Graph(Node(3), Node(1), Rel(Edge(Nodes (1, 3))))
>
> (4.4) Explicit type parameters
> If you don’t pass at least one node and one Relation, the missing type
> parameter will be inferred to Nothing, what is at the moment language- /
> compiler-inherent, so better you define them explicitly:
>
> val j = Graph[Int, Edge[Int]] (Edge(1,3))
> j: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
> Graph(Node(3), Node(1), Rel(Edge(Nodes(1, 3))))
>
> (4.5) Specific graphs
> Common graph types have their own specific factories:
> SimpleGraph, MultiGraph, DirectedGraph, UndirectedGraph
> At the moment, Graph is the most common graph namely hypegraph, but I’m afraid
> this is not the best suitable naming.
>
> (5) Consistency
>
> Graph seamlessly maintains a consistent state of the nodes and relations sets.
> This basically includes the following:
>
> (5a) Nodes of a relation being added will also be added to the nodes set if
> not yet included.
>
> (5b) By default, nodes participating in any relation of the relation set
> cannot be removed. However, you can force node removal in which case all
> relations with a back reference to the node to be removed will also be removed.
>
> (5c) More constraints on specific graphs…
>
> (6) SetLike
>
> Graph is SetLike allowing you to use the same operators whether adding (+, +=)
> or subtracting (-, -=) nodes or relations. Utilizing the SetLike-interface,
> you no more need to verbose the nodes or relations set. This is simply
> achieved by letting right-hand operands being an instance of Relation
> implicitly map to the relations set while all other operands to the nodes set.
> Also, traversing through Graph you’ll get both nodes and relations. Certainly
> it’s up to you to traverse the nodes or relations set directly.
>
> To handle passing arguments to Graph through SetLike it was necessary to wrap
> them to Node respectively Rel. This wrapping only takes place when passing
> parameters or traversing Graph through the SetLike interface, so for any
> internal algorithm there is no performance penalty.
>
> Just a few examples for how SetLike can make code more compact:
>
> (6.1) Add a node
> scala> Graph[Any,Edge[Any]]("A") + 1
> res1: scala.collection.Graph[Any,scala.collection.Edge[Any]] =
> Graph(Node(A), Node(1))
>
> (6.2) Remove an edge
> scala> Graph[Int,Edge[Int]](Edge(1,1), Edge(1,2)) - Edge(1,1)
> res2: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
> Graph(Node(1), Node(2), Rel(Edge(Nodes (1, 2))))
>
> (6.3) As a main benefit, all other SetLike-methods work, too. For instance,
> let’s try filter:
> scala> val g = Graph(1, Edge(2,3))
> g: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
> Graph(Node(3), Node(1), Node(2), Rel(Edge(Nodes(2, 3))))
> scala> g.filter (nodePredicate((i:Int) => i>1))
> res7: scala.collection.Graph[Int,scala.collection.Relation[Int]] =
> Graph(Node(3), Node(2), Rel(Relation(Nodes(2, 3))))
>
> (6.4) shorthand for 6.3
> scala> g.filter ((i:Int) => i>1)
>
> (7) Properties
>
> It may be of great value to be able to define behavior such as (5b) or
> optimization properties for a Graph instance. An example for the letter is
> whether for each node a set of its connectors should be maintained
> additionally for speed optimisation.
>
> Properties can be set at instantiation time like
> Graph( WITH_CONNECTORS_SETS )( node1, node2, rel1, rel2 )
> or anytime later.
>
> B?
> => => => Any suggestions on how to improve Graph’s design?
>
> C) Feature Planning
> -------------------
> I’d say the above foundations are in a usable state.
>
> At the moment, Graph is not intended to cover graph theory. It just aims to be
> a suitable basement to build upon. More aspects of the graph theory including
> vector spaces or algorithms, could be appended successively.
>
> Graph is designed for direct usage but also for easy extensibility in mind.
> Its documentation also serves as a cookbook for how to deal with custom graphs
> such as attributed graphs.
>
> C?
> => => => Which features, in your opinion, are essential for a potential first
> release of Graph?
>
> Cheers
> Peter
>

On Sunday November 14 2010, Peter Empen wrote:
> Hi Everyone with special interest in Scala collections and / or
> graphs:
>
> I’ve been working on a graph collection, fitting ideally into the 2.8
> collection package of the Scala Library. Aiming a contribution, I’d
> like to evaluate with you

I'm curious which graph libraries you've worked with and which serve as
models or anti-models for your design? I have worked only with JGraphT,
but find it quite good.

> a) whether Graph should become part of the Scala Library,

I'd say it's not immediately obvious that a graph should be a
collection. Is it a collection of vertices? Vertex labels? Edges? Edge
labels?

> b) what you think about my design from the users perspective and
> c) what features should be provided as a minimum.
>
> Notational note: Writing "Graph" (G in capital) I’m pinpointing the
> targeted Scala type while "graph" (lower case) should refer to the
> mathematical term.
>
> A) Why Graph?

The need for a graphing library surely needs no explanation or
justification!

> ...
>
> A?
> Do you feel it makes sense for graphs to become part of the Scala
> Library?

Yes.

> B) Design Principles
> --------------------
> Let me outline some design principles of Graph from the users
> perspective:
>
> (1) Mutable, immutable
>
> In-line with general scala.collection principles, Graph has its
> immutable and mutable variants defaulting to immutable.
>
> (2) Type parameters
>
> Graph has two type parameters: one for the contained nodes (vertices)
> and one for the contained relations (they usually speak of edges).

I would use the terms vertex and edge uniformly (not "relation").

> (3) Upper bounds of the type parameters
>
> Graph doesn’t impose any restrictions on the type of nodes meaning
> that the upper bound of the nodes type parameter is Any. In contrast,
> the type parameter for relations has a specific upper bound:
> Relation.
>
> trait Graph[N, R <: Relation[N]]
>
> Why Relation? As needed in case of hypergraphs, relations contain 2
> to n nodes. Therefore, relations are the most general kind of edges.
> Edges can be thought of as special relations connecting 2 vertices
> meaning that Edge should be derived from Relation. The point is that
> we want Graph to encompass hypergraphs, as well.

Why isn't the graph structure entirely up to the graph library and the
user's vertex and edge labels attached by the library to the graph?
Forcing the edges to be subtypes of a library class seems less than
optimal. If Relation is a trait, it's probably manageable, but if it's
a class (abstract or not) it's a problem. I do not immediately see how
the hypergraph case changes the analysis. In JGraphT you can (for
certain graph sub-types) have multiple edges between two given
vertices. Does your design allow that (I see MultiGraph below, so I'm
guessing the answer is "yes")?

But please, do not call them "Relation!"

> (4) Factories
>
> You can instantiate a Graph as easily as you are accustomed when
> using List, Set etc. If you pass the factory arguments of the type
> Relation they will be wrapped by Rel, otherwise by Node – see (6) for
> what is wrapping good for.
>
> ...
>
> (4.5) Specific graphs
> Common graph types have their own specific factories:
> SimpleGraph, MultiGraph, DirectedGraph, UndirectedGraph
> At the moment, Graph is the most common graph namely hypegraph, but
> I’m afraid this is not the best suitable naming.

Acyclic graph types (both directed and undirected) is probably
necessary, including verification that no cycles exist and none are
allowed to be created, of course.

Are disconnected graphs allowed? Can they be prohibited? Detected?

> (5) Consistency
>
> ...
>
> (6) SetLike
>
> ...
>
> (7) Properties
>
> It may be of great value to be able to define behavior such as (5b)
> or optimization properties for a Graph instance. An example for the
> letter is whether for each node a set of its connectors should be
> maintained additionally for speed optimisation.

By "connectors" do you mean immediate neighbors? Vertices at distance
one from the node in question? Or do you mean the edges that terminate
upon that node? It's not terminology I've encountered, I don't think.

> Properties can be set at instantiation time like
> Graph( WITH_CONNECTORS_SETS )( node1, node2, rel1, rel2 )
> or anytime later.

I believe you should use Scala naming conventions, which exclude all
upper-case + underscore (C- / Java-style) constant names.

Are these properties open-ended / extensible? Can we define methods or
functions that supply such property tests?

> B?
> => => => Any suggestions on how to improve Graph’s design?
>
> C) Feature Planning
> -------------------
> I’d say the above foundations are in a usable state.

If the code is complete, to what extent are it (and you) amenable to any
changes we might suggest?

> At the moment, Graph is not intended to cover graph theory. It just
> aims to be a suitable basement to build upon. More aspects of the
> graph theory including vector spaces or algorithms, could be appended
> successively.

Algorithms are where graphs become useful. Just representing them is
only 20% of the job.

Given a node or a relation, can I discover its immediate neighbors? Are
there at least basic traversals (depth- and breadth-first)? Cycle
detection?

> ...
>
> C?
> => => => Which features, in your opinion, are essential for a
> potential first release of Graph?

While I don't want to "play" with the code, I'd like to see the API docs
(Scaladoc HTML, i.e.). Presumably you're working with Scala 2.8. Is it
self-contained or does it use 3rd-party libraries (i.e., those other
than the Scala standard library)?

Uniform terminology (that excludes "relation") and, preferably uses
formal terms (vertex and edge, e.g.), not casual ones (node, e.g.).

> Cheers
> Peter

Sorry I had so much terminological feedback. I know it's the least
important aspect, but I'm of the school that holds that names matter,
even if they are irrelevant to function.

Randall Schulz

On Sunday November 14 2010, Linas wrote:
> In my experience, it is not that important to have a set of base
> graph types with various variants (directed, undirected, etc..). It
> is more important to have the ability to map a custom structure into
> a graph and then perform graph related operations (wide visiting,
> deep visiting, etc..) on it, while inserting your own code into key
> parts of those operations.

What you're looking for is something to create a dynamically accessible
reflection of run-time object networks. I don't think that's the
principle use case for a graph library, though I suppose a decent graph
library would admit such a use without too much trouble.

(By the way, if you don't have a directed graph, you cannot properly
model a network or lined object instances, so the underlying graph
types _do_ matter.)

I suggest you analyze Mr. Empen's design from the standpoint of its
ability to support your use case.

> So basically it would be nice to have some kind of Graph. The some
> kind of GraphView extends Graph that can be mapped to custom
> structures. And a bunch of graph related algorithms operating on
> Graph and extensible at key points.
>
> Linas.

Randall Schulz

On Sunday November 14 2010, Randall R Schulz wrote:
> On Sunday November 14 2010, Linas wrote:
> > ...
>
> What you're looking for is something to create a dynamically
> accessible reflection of run-time object networks. I don't think
> that's the principle use case for a graph library, though I suppose a
> decent graph library would admit such a use without too much trouble.
>
> (By the way, if you don't have a directed graph, you cannot properly
> model a network or lined object instances, so the underlying graph

...network of linked object instances...

> types _do_ matter.)

> I suggest you analyze Mr. Empen's design from the standpoint of its
> ability to support your use case.
>
> ...
>
>
> Randall Schulz

Good to hear about this, graphs are certainly worthy of going in the
core of Scala.

What I'd like to be able to do is use such Graphs as interfaces to RDF
models/stores [1] and apply (possibly 3rd party) graph algorithms to
them. Right now I'm using Jena [2], which is in Java (which as it
happens has a Graph interface, but it's rather distant from a generic
graph) which works nicely through Scala, but doesn't exactly encourage
Scala idioms.

Not sure how this might pan out - I suppose the key characteristics of
the RDF model are that it's a labelled digraph (with URIs as labels
for nodes and arcs, usually) and you often spend time viewing the
stuff as a set of triples (subject=node, property=relation,
object=node).

Cheers,

Danny.

[1] http://www.w3.org/TR/2004/REC-rdf-concepts-20040210/#section-Graph-syntax
[2] http://jena.sourceforge.net/

On 14 November 2010 13:34, Peter Empen wrote:
> Hi Everyone with special interest in Scala collections and / or graphs:
>
> I’ve been working on a graph collection, fitting ideally into the 2.8
> collection package of the Scala Library. Aiming a contribution, I’d like to
> evaluate with you
>
> a) whether Graph should become part of the Scala Library,
> b) what you think about my design from the users perspective and
> c) what features should be provided as a minimum.
>
> Notational note: Writing "Graph" (G in capital) I’m pinpointing the targeted
> Scala type while "graph" (lower case) should refer to the mathematical term.
>
> A) Why Graph?
> -------------
> Most of you will have dealt with problem domains including elements with graph-
> like structures. But how to proceed in Scala? Everybody has to start out on
> his own because the Scala Library does not support graphs directly, yet.
> There are some well-featured Java frameworks for graphs but they don’t really
> fit into Scala. Those, for instance, who set up http://code.google.com/p/scala-
> graphs/wiki/Requirements in 2009 have realized this lack, too, but their
> undertaking seems to have come to a halt.
>
> So, a few months ago, I also decided to start programming graphs in Scala on
> my own. Doing so, I’ve  focused on integration with the 2.8 collections
> framework. In spite of the promise of easy creation of custom collections, I
> ran into several problems. This was mainly because Graph needs two type
> parameters and if you look at the implementation details of Map, the other
> collection with two type parameters, you’ll understand, why this task was non-
> trivial. I think my work could be valuable for the Scala Community.
>
> A?
> Do you feel it makes sense for graphs to become part of the Scala Library?
>
> B) Design Principles
> --------------------
> Let me outline some design principles of Graph from the users perspective:
>
> (1) Mutable, immutable
>
> In-line with general scala.collection principles, Graph has its immutable and
> mutable variants defaulting to immutable.
>
> (2) Type parameters
>
> Graph has two type parameters: one for the contained nodes (vertices) and one
> for the contained relations (they usually speak of edges).
>
> (3) Upper bounds of the type parameters
>
> Graph doesn’t impose any restrictions on the type of nodes meaning that the
> upper bound of the nodes type parameter is Any. In contrast, the type
> parameter for relations has a specific upper bound: Relation.
>
> trait Graph[N, R <: Relation[N]]
>
> Why Relation? As needed in case of hypergraphs, relations contain 2 to n
> nodes. Therefore, relations are the most general kind of edges. Edges can be
> thought of as special relations connecting 2 vertices meaning that Edge should
> be derived from Relation. The point is that we want Graph to encompass
> hypergraphs, as well.
>
> (4) Factories
>
> You can instantiate a Graph as easily as you are accustomed when using List,
> Set etc. If you pass the factory arguments of the type Relation they will be
> wrapped by Rel, otherwise by Node – see (6) for what is wrapping good for.
>
> (4.1) One node
> scala> val g = Graph(1)
> g: scala.collection.Graph[Int,Nothing] = Graph(Node(1))
> scala> g.nodes
> res0: g.Nodes = Set(1)
> scala> g.relations
> res1: g.Relations = Set()
>
> (4.2) Nodes and relations
> scala> val h = Graph("A", Relation("A","B"))
> h: scala.collection.Graph[java.lang.String,scala.collection.Relation
> [java.lang.String]] = Graph(Node(B), Node(A), Rel(Relation(Nodes(A, B))))
> scala> h.nodes
> res2: h.Nodes = Set(B, A)
> scala> h.relations
> res3: h.Relations = Set(Relation(Nodes(A, B)))
>
> (4.3) Nodes and edges
> scala> val i = Graph(1, Edge(1,3))
> i: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
> Graph(Node(3), Node(1), Rel(Edge(Nodes (1, 3))))
>
> (4.4) Explicit type parameters
> If you don’t pass at least one node and one Relation, the missing type
> parameter will be inferred to Nothing, what is at the moment language- /
> compiler-inherent, so better you define them explicitly:
>
> val j = Graph[Int, Edge[Int]] (Edge(1,3))
> j: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
> Graph(Node(3), Node(1), Rel(Edge(Nodes(1, 3))))
>
> (4.5) Specific graphs
> Common graph types have their own specific factories:
> SimpleGraph, MultiGraph, DirectedGraph, UndirectedGraph
> At the moment, Graph is the most common graph namely hypegraph, but I’m afraid
> this is not the best suitable naming.
>
> (5) Consistency
>
> Graph seamlessly maintains a consistent state of the nodes and relations sets.
> This basically includes the following:
>
> (5a) Nodes of a relation being added will also be added to the nodes set if
> not yet included.
>
> (5b) By default, nodes participating in any relation of the relation set
> cannot be removed. However, you can force node removal in which case all
> relations with a back reference to the node to be removed will also be removed.
>
> (5c) More constraints on specific graphs…
>
> (6) SetLike
>
> Graph is SetLike allowing you to use the same operators whether adding (+, +=)
> or subtracting (-, -=) nodes or relations. Utilizing the SetLike-interface,
> you no more need to verbose the nodes or relations set. This is simply
> achieved by letting right-hand operands being an instance of Relation
> implicitly map to the relations set while all other operands to the nodes set.
> Also, traversing through Graph you’ll get both nodes and relations. Certainly
> it’s up to you to traverse the nodes or relations set directly.
>
> To handle passing arguments to Graph through SetLike it was necessary to wrap
> them to Node respectively Rel. This wrapping only takes place when passing
> parameters or traversing Graph through the SetLike interface,  so for any
> internal algorithm there is no performance penalty.
>
> Just a few examples for how SetLike can make code more compact:
>
> (6.1) Add a node
> scala> Graph[Any,Edge[Any]]("A") + 1
> res1: scala.collection.Graph[Any,scala.collection.Edge[Any]] =
> Graph(Node(A), Node(1))
>
> (6.2) Remove an edge
> scala> Graph[Int,Edge[Int]](Edge(1,1), Edge(1,2)) - Edge(1,1)
> res2: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
> Graph(Node(1), Node(2), Rel(Edge(Nodes (1, 2))))
>
> (6.3) As a main benefit, all other SetLike-methods work, too. For instance,
> let’s try filter:
> scala> val g = Graph(1, Edge(2,3))
> g: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
> Graph(Node(3), Node(1), Node(2), Rel(Edge(Nodes(2, 3))))
> scala> g.filter (nodePredicate((i:Int) => i>1))
> res7: scala.collection.Graph[Int,scala.collection.Relation[Int]] =
> Graph(Node(3), Node(2), Rel(Relation(Nodes(2, 3))))
>
> (6.4) shorthand for 6.3
> scala> g.filter ((i:Int) => i>1)
>
> (7) Properties
>
> It may be of great value to be able to define behavior such as (5b) or
> optimization properties for a Graph instance. An example for the letter is
> whether for each node a set of its connectors should be maintained
> additionally for speed optimisation.
>
> Properties can be set at instantiation time like
> Graph( WITH_CONNECTORS_SETS )( node1, node2, rel1, rel2 )
> or anytime later.
>
> B?
> => => => Any suggestions on how to improve Graph’s design?
>
> C) Feature Planning
> -------------------
> I’d say the above foundations are in a usable state.
>
> At the moment, Graph is not intended to cover graph theory. It just aims to be
> a suitable basement to build upon. More aspects of the graph theory including
> vector spaces or algorithms, could be appended successively.
>
> Graph is designed for direct usage but also for easy extensibility in mind.
> Its documentation also serves as a cookbook for how to deal with custom graphs
> such as attributed graphs.
>
> C?
> => => => Which features, in your opinion, are essential for a potential first
> release of Graph?
>
> Cheers
> Peter
>
>

On Sun, 2010-11-14 at 08:16 -0800, Randall R Schulz wrote:
> On Sunday November 14 2010, Linas wrote:
> > In my experience, it is not that important to have a set of base
> > graph types with various variants (directed, undirected, etc..). It
> > is more important to have the ability to map a custom structure into
> > a graph and then perform graph related operations (wide visiting,
> > deep visiting, etc..) on it, while inserting your own code into key
> > parts of those operations.
>
> What you're looking for is something to create a dynamically accessible
> reflection of run-time object networks. I don't think that's the
> principle use case for a graph library, though I suppose a decent graph
> library would admit such a use without too much trouble.

Not really. What I was trying to say, that in my experience you often do
not explicitly build a graph by adding vertices and edges to some Graph
class but you have a set of linked data structures that you must process
by applying graph related algorithms. One way is to explicitly build a
graph from them, but this involves extensive copying. Another way is to
map those data structures to a graph by defining mapping functions for
vertices, edges and edge-vertex relations.

Since Mr. Empen is building a graph library from a scratch, he may want
to consider planning for such capability.

> (By the way, if you don't have a directed graph, you cannot properly
> model a network or lined object instances, so the underlying graph
> types _do_ matter.)

True. I have oversimplified the case.

> I suggest you analyze Mr. Empen's design from the standpoint of its
> ability to support your use case.
>
>
> > So basically it would be nice to have some kind of Graph. The some
> > kind of GraphView extends Graph that can be mapped to custom
> > structures. And a bunch of graph related algorithms operating on
> > Graph and extensible at key points.
> >
> > Linas.
>
>
>
>
> Randall Schulz

Linas.

On Sunday November 14 2010, Linas wrote:
> On Sun, 2010-11-14 at 08:16 -0800, Randall R Schulz wrote:
> > On Sunday November 14 2010, Linas wrote:
> > > ...
> >
> > What you're looking for is something to create a dynamically
> > accessible reflection of run-time object networks. I don't think
> > that's the principle use case for a graph library, though I suppose
> > a decent graph library would admit such a use without too much
> > trouble.
>
> Not really. What I was trying to say, that in my experience you often
> do not explicitly build a graph by adding vertices and edges to some
> Graph class but you have a set of linked data structures that you
> must process by applying graph related algorithms.

I do. That's what graphs are. That's what general-purpose graph
libraries are for.

What you want is not a general-purpose graph library, it's a dynamic
object graph library, which is properly seen as a special case.

> ...
>
> Since Mr. Empen is building a graph library from a scratch, he may
> want to consider planning for such capability.

You want that. But as I say, a good graph library will admit what you
want and you should be looking at it from the perspective of how much
work you'd have to do to create what you want using it by comparison to
doing so from scratch.

> > ...
> >
> >
> > Randall Schulz
>
> Linas.

Randall Schulz

Not really. What I was trying to say, that in my experience you often do
not explicitly build a graph by adding vertices and edges to some Graph
class but you have a set of linked data structures that you must process
by applying graph related algorithms. One way is to explicitly build a
graph from them, but this involves extensive copying. Another way is to
map those data structures to a graph by defining mapping functions for
vertices, edges and edge-vertex relations.

A agree that this is a common use case, i.e. the need to run some graph algorithms
on a custom structure that is graph like, it would be nice if a graph library to be
"pimpable" by implicit a few implicit conversions :

  implicit def city2Edge(c: City): Edge[City]
  implicit def road2Vertice(r: Road): Vertice[City]

Max

On Sun, Nov 14, 2010 at 1:24 PM, Maxime Lévesque <maxime.levesque@gmail.com> wrote:

Not really. What I was trying to say, that in my experience you often do
not explicitly build a graph by adding vertices and edges to some Graph
class but you have a set of linked data structures that you must process
by applying graph related algorithms. One way is to explicitly build a
graph from them, but this involves extensive copying. Another way is to
map those data structures to a graph by defining mapping functions for
vertices, edges and edge-vertex relations.

A agree that this is a common use case, i.e. the need to run some graph algorithms
on a custom structure that is graph like, it would be nice if a graph library to be
"pimpable" by implicit a few implicit conversions :

Oops, i really meant :
 

  implicit def city2Edge(c: City): Edge[City]
  implicit def road2Vertice(r: Road): Vertice[Road]

and then :

    shortestPath(rome, beijing) : Traversable[Vertice[Road]]
 
Max

Maxime,

(please see below:)

> On Sun, Nov 14, 2010 at 1:24 PM, Maxime Lévesque wrote:
>
> Not really. What I was trying to say, that in my experience you often do
> not explicitly build a graph by adding vertices and edges to some Graph
> class but you have a set of linked data structures that you must process
> by applying graph related algorithms. One way is to explicitly build a
> graph from them, but this involves extensive copying.

In my design you can path a vertices and edges set to the Graph-constructor in
which case copying is not really necessary. What is still necessary is
consistence-checking.

> ...
>   implicit def city2Edge(c: City): Edge[City]  implicit def road2Vertice(r:
Road): Vertice[Road]
>
> and then :    shortestPath(rome, beijing) : Traversable[Vertice[Road]] 

How do you ensure the consistency of your graph sets in your example? Maybe
your shortestPath method must cope with possible inconsistency?

Peter

Dear Randall,

I do hate inaccurate terminology, too. Sorry if it's not obvious, but I was
thinking a lot about it.

Vertices / nodes:
Vertices may really be the better choice, allthough I've seen several
publications using nodes synonymously. Maybe node is more or less an European
term?

Edge / Relation:
I tend to associate an edge with a line connecting just two vertices. Do you
think we should speak of an edge even if more than two vertices are connected -
as in case of hypergraphs? That was my only reason to switch to relation. All
in all you're right, most people would dislike the term relation because they
deal with "normal" graphs.

I value your design suggestions very much - more anweres will follow. My code
is not complete in that sense so I'm fully amenable to positive changes or
enhancements.

Regards
Peter

2010/11/14 Peter Empen <scala-graph@arcor.de>

Edge / Relation:
I tend to associate an edge with a line connecting just two vertices. Do you
think we should speak of an edge even if more than two vertices are connected -
 as in case of hypergraphs? That was my only reason to switch to relation. All
in all you're right, most people would dislike the term relation because they
deal with "normal" graphs.

Maybe I'm talking nonsense here, but why not some 'HyperEdge' implementation of Edge ?
 

Regards
Peter

Hello Andreas,

my highest priority is to process all incomming design suggestions. Then, I
should prepare a thorough Scaladoc. Because Graph is just my spare-time work,
it'll take some time before you can start playing around with it - hope you
don't mind.

Peter

I never encountered the term "relation" to describe an edge...it's always edges and vertices. I personally use node and edge or link.

Thanks,
Razvan

On 2010-11-14, at 3:09 PM, Peter Empen wrote:

> Dear Randall,
>
> I do hate inaccurate terminology, too. Sorry if it's not obvious, but I was
> thinking a lot about it.
>
> Vertices / nodes:
> Vertices may really be the better choice, allthough I've seen several
> publications using nodes synonymously. Maybe node is more or less an European
> term?
>
> Edge / Relation:
> I tend to associate an edge with a line connecting just two vertices. Do you
> think we should speak of an edge even if more than two vertices are connected -
> as in case of hypergraphs? That was my only reason to switch to relation. All
> in all you're right, most people would dislike the term relation because they
> deal with "normal" graphs.
>
> I value your design suggestions very much - more anweres will follow. My code
> is not complete in that sense so I'm fully amenable to positive changes or
> enhancements.
>
> Regards
> Peter
>
>

If it's work in early progress why talk about it? If it is in some rather advanced stages, why not share the location of said code?

Why not just put a scala wrapper on top of jgraph and inherit all the functionality there?

Thanks,
Razvan

On 2010-11-14, at 3:41 PM, Peter Empen wrote:

> Hello Andreas,
>
> my highest priority is to process all incomming design suggestions. Then, I
> should prepare a thorough Scaladoc. Because Graph is just my spare-time work,
> it'll take some time before you can start playing around with it - hope you
> don't mind.
>
> Peter
>
>

A graph is a set of vertices, and an incidence relation on those vertices (v1 is incident to v2 if (v1,v2) is in the incidence relation). Hence the terminology.graham
On Nov 14, 2010, at 1:03 PM, Razvan Cojocaru wrote:

I never encountered the term "relation" to describe an edge...it's always edges and vertices. I personally use node and edge or link.

Thanks,
Razvan

On 2010-11-14, at 3:09 PM, Peter Empen <scala-graph@arcor.de> wrote:

Dear Randall,

I do hate inaccurate terminology, too. Sorry if it's not obvious, but I was

thinking a lot about it.

Vertices / nodes:

Vertices may really be the better choice, allthough I've seen several

publications using nodes synonymously. Maybe node is more or less an European

term?

Edge / Relation:

I tend to associate an edge with a line connecting just two vertices. Do you

think we should speak of an edge even if more than two vertices are connected -

as in case of hypergraphs? That was my only reason to switch to relation. All

in all you're right, most people would dislike the term relation because they

deal with "normal" graphs.

I value your design suggestions very much - more anweres will follow. My code

is not complete in that sense so I'm fully amenable to positive changes or

enhancements.

Regards

Peter

I checked terminology on wikipediA and still didn't find "relation".
They do mention hyperedge
http://en.m.wikipedia.org/wiki/Glossary_of_graph_theory?wasRedirected=true

Cheers,
Razie

On Sunday, November 14, 2010, Graham Matthews
wrote:
> A graph is a set of vertices, and an incidence relation on those vertices (v1 is incident to v2 if (v1,v2) is in the incidence relation). Hence the terminology.graham
> On Nov 14, 2010, at 1:03 PM, Razvan Cojocaru wrote:
> I never encountered the term "relation" to describe an edge...it's always edges and vertices. I personally use node and edge or link.
>
> Thanks,
> Razvan
>
> On 2010-11-14, at 3:09 PM, Peter Empen wrote:
>
> Dear Randall,
>
> I do hate inaccurate terminology, too. Sorry if it's not obvious, but I was
> thinking a lot about it.
>
> Vertices / nodes:
> Vertices may really be the better choice, allthough I've seen several
> publications using nodes synonymously. Maybe node is more or less an European
> term?
>
> Edge / Relation:
> I tend to associate an edge with a line connecting just two vertices. Do you
> think we should speak of an edge even if more than two vertices are connected -
> as in case of hypergraphs? That was my only reason to switch to relation. All
> in all you're right, most people would dislike the term relation because they
> deal with "normal" graphs.
>
> I value your design suggestions very much - more anweres will follow. My code
> is not complete in that sense so I'm fully amenable to positive changes or
> enhancements.
>
> Regards
> Peter
>
>
>
>

Can we see Relation class? Could not figure out how it could be used to define graphs.

And besides... your directed graphs, I hope they include "directed multigraphs", right?

Subclassing from Relation, I guess, with the purpose of including hypergraphs, will have an unpleasant result that you won't be able to limit the relationship arity to 2 (this is not Agda).

Probably since almost everybody has an implementations... it make sense not to listen to anybody at all. :)

-Vlad

2010/11/14 Peter Empen <scala-graph@arcor.de>

Hi Everyone with special interest in Scala collections and / or graphs:

I’ve been working on a graph collection, fitting ideally into the 2.8
collection package of the Scala Library. Aiming a contribution, I’d like to
evaluate with you

a) whether Graph should become part of the Scala Library,
b) what you think about my design from the users perspective and
c) what features should be provided as a minimum.

Notational note: Writing "Graph" (G in capital) I’m pinpointing the targeted
Scala type while "graph" (lower case) should refer to the mathematical term.

A) Why Graph?
-------------
Most of you will have dealt with problem domains including elements with graph-
like structures. But how to proceed in Scala? Everybody has to start out on
his own because the Scala Library does not support graphs directly, yet.
There are some well-featured Java frameworks for graphs but they don’t really
fit into Scala. Those, for instance, who set up http://code.google.com/p/scala-
graphs/wiki/Requirements in 2009 have realized this lack, too, but their
undertaking seems to have come to a halt.

So, a few months ago, I also decided to start programming graphs in Scala on
my own. Doing so, I’ve  focused on integration with the 2.8 collections
framework. In spite of the promise of easy creation of custom collections, I
ran into several problems. This was mainly because Graph needs two type
parameters and if you look at the implementation details of Map, the other
collection with two type parameters, you’ll understand, why this task was non-
trivial. I think my work could be valuable for the Scala Community.

A?
Do you feel it makes sense for graphs to become part of the Scala Library?

B) Design Principles
--------------------
Let me outline some design principles of Graph from the users perspective:

(1) Mutable, immutable

In-line with general scala.collection principles, Graph has its immutable and
mutable variants defaulting to immutable.

(2) Type parameters

Graph has two type parameters: one for the contained nodes (vertices) and one
for the contained relations (they usually speak of edges).

(3) Upper bounds of the type parameters

Graph doesn’t impose any restrictions on the type of nodes meaning that the
upper bound of the nodes type parameter is Any. In contrast, the type
parameter for relations has a specific upper bound: Relation.

trait Graph[N, R <: Relation[N]]

Why Relation? As needed in case of hypergraphs, relations contain 2 to n
nodes. Therefore, relations are the most general kind of edges. Edges can be
thought of as special relations connecting 2 vertices meaning that Edge should
be derived from Relation. The point is that we want Graph to encompass
hypergraphs, as well.

(4) Factories

You can instantiate a Graph as easily as you are accustomed when using List,
Set etc. If you pass the factory arguments of the type Relation they will be
wrapped by Rel, otherwise by Node – see (6) for what is wrapping good for.

(4.1) One node
scala> val g = Graph(1)
g: scala.collection.Graph[Int,Nothing] = Graph(Node(1))
scala> g.nodes
res0: g.Nodes = Set(1)
scala> g.relations
res1: g.Relations = Set()

(4.2) Nodes and relations
scala> val h = Graph("A", Relation("A","B"))
h: scala.collection.Graph[java.lang.String,scala.collection.Relation
[java.lang.String]] = Graph(Node(B), Node(A), Rel(Relation(Nodes(A, B))))
scala> h.nodes
res2: h.Nodes = Set(B, A)
scala> h.relations
res3: h.Relations = Set(Relation(Nodes(A, B)))

(4.3) Nodes and edges
scala> val i = Graph(1, Edge(1,3))
i: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
Graph(Node(3), Node(1), Rel(Edge(Nodes (1, 3))))

(4.4) Explicit type parameters
If you don’t pass at least one node and one Relation, the missing type
parameter will be inferred to Nothing, what is at the moment language- /
compiler-inherent, so better you define them explicitly:

val j = Graph[Int, Edge[Int]] (Edge(1,3))
j: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
Graph(Node(3), Node(1), Rel(Edge(Nodes(1, 3))))

(4.5) Specific graphs
Common graph types have their own specific factories:
SimpleGraph, MultiGraph, DirectedGraph, UndirectedGraph
At the moment, Graph is the most common graph namely hypegraph, but I’m afraid
this is not the best suitable naming.

(5) Consistency

Graph seamlessly maintains a consistent state of the nodes and relations sets.
This basically includes the following:

(5a) Nodes of a relation being added will also be added to the nodes set if
not yet included.

(5b) By default, nodes participating in any relation of the relation set
cannot be removed. However, you can force node removal in which case all
relations with a back reference to the node to be removed will also be removed.

(5c) More constraints on specific graphs…

(6) SetLike

Graph is SetLike allowing you to use the same operators whether adding (+, +=)
or subtracting (-, -=) nodes or relations. Utilizing the SetLike-interface,
you no more need to verbose the nodes or relations set. This is simply
achieved by letting right-hand operands being an instance of Relation
implicitly map to the relations set while all other operands to the nodes set.
Also, traversing through Graph you’ll get both nodes and relations. Certainly
it’s up to you to traverse the nodes or relations set directly.

To handle passing arguments to Graph through SetLike it was necessary to wrap
them to Node respectively Rel. This wrapping only takes place when passing
parameters or traversing Graph through the SetLike interface,  so for any
internal algorithm there is no performance penalty.

Just a few examples for how SetLike can make code more compact:

(6.1) Add a node
scala> Graph[Any,Edge[Any]]("A") + 1
res1: scala.collection.Graph[Any,scala.collection.Edge[Any]] =
Graph(Node(A), Node(1))

(6.2) Remove an edge
scala> Graph[Int,Edge[Int]](Edge(1,1), Edge(1,2)) - Edge(1,1)
res2: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
Graph(Node(1), Node(2), Rel(Edge(Nodes (1, 2))))

(6.3) As a main benefit, all other SetLike-methods work, too. For instance,
let’s try filter:
scala> val g = Graph(1, Edge(2,3))
g: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
Graph(Node(3), Node(1), Node(2), Rel(Edge(Nodes(2, 3))))
scala> g.filter (nodePredicate((i:Int) => i>1))
res7: scala.collection.Graph[Int,scala.collection.Relation[Int]] =
Graph(Node(3), Node(2), Rel(Relation(Nodes(2, 3))))

(6.4) shorthand for 6.3
scala> g.filter ((i:Int) => i>1)

(7) Properties

It may be of great value to be able to define behavior such as (5b) or
optimization properties for a Graph instance. An example for the letter is
whether for each node a set of its connectors should be maintained
additionally for speed optimisation.

Properties can be set at instantiation time like
Graph( WITH_CONNECTORS_SETS )( node1, node2, rel1, rel2 )
or anytime later.

B?
=> => => Any suggestions on how to improve Graph’s design?

C) Feature Planning
-------------------
I’d say the above foundations are in a usable state.

At the moment, Graph is not intended to cover graph theory. It just aims to be
a suitable basement to build upon. More aspects of the graph theory including
vector spaces or algorithms, could be appended successively.

Graph is designed for direct usage but also for easy extensibility in mind.
Its documentation also serves as a cookbook for how to deal with custom graphs
such as attributed graphs.

C?
=> => => Which features, in your opinion, are essential for a potential first
release of Graph?

Cheers
Peter

--
Thanks,
-Vlad

Linas wrote:
> In my experience, it is not that important to have a set of base graph
> types with various variants (directed, undirected, etc..). It is more
> important to have the ability to map a custom structure into a graph and
> then perform graph related operations (wide visiting, deep visiting,
> etc..) on it, while inserting your own code into key parts of those
> operations.
+1

The emphasis is then to create generic algorithms on graphs that instead of using concrete Node and Edge classes, use a view of the underlying object graph that implements the operations they require (mostly iteration I believe).

Ittay
> So basically it would be nice to have some kind of Graph. The some kind
> of GraphView extends Graph that can be mapped to custom structures. And
> a bunch of graph related algorithms operating on Graph and extensible at
> key points.
>
> Linas.
>
> On Sun, 2010-11-14 at 12:34 +0000, Peter Empen wrote:
>> Hi Everyone with special interest in Scala collections and / or graphs:
>>
>> I’ve been working on a graph collection, fitting ideally into the 2.8
>> collection package of the Scala Library. Aiming a contribution, I’d like to
>> evaluate with you
>>
>> a) whether Graph should become part of the Scala Library,
>> b) what you think about my design from the users perspective and
>> c) what features should be provided as a minimum.
>>
>> Notational note: Writing "Graph" (G in capital) I’m pinpointing the targeted
>> Scala type while "graph" (lower case) should refer to the mathematical term.
>>
>> A) Why Graph?
>> -------------
>> Most of you will have dealt with problem domains including elements with graph-
>> like structures. But how to proceed in Scala? Everybody has to start out on
>> his own because the Scala Library does not support graphs directly, yet.
>> There are some well-featured Java frameworks for graphs but they don’t really
>> fit into Scala. Those, for instance, who set up http://code.google.com/p/scala-
>> graphs/wiki/Requirements in 2009 have realized this lack, too, but their
>> undertaking seems to have come to a halt.
>>
>> So, a few months ago, I also decided to start programming graphs in Scala on
>> my own. Doing so, I’ve focused on integration with the 2.8 collections
>> framework. In spite of the promise of easy creation of custom collections, I
>> ran into several problems. This was mainly because Graph needs two type
>> parameters and if you look at the implementation details of Map, the other
>> collection with two type parameters, you’ll understand, why this task was non-
>> trivial. I think my work could be valuable for the Scala Community.
>>
>> A?
>> Do you feel it makes sense for graphs to become part of the Scala Library?
>>
>> B) Design Principles
>> --------------------
>> Let me outline some design principles of Graph from the users perspective:
>>
>> (1) Mutable, immutable
>>
>> In-line with general scala.collection principles, Graph has its immutable and
>> mutable variants defaulting to immutable.
>>
>> (2) Type parameters
>>
>> Graph has two type parameters: one for the contained nodes (vertices) and one
>> for the contained relations (they usually speak of edges).
>>
>> (3) Upper bounds of the type parameters
>>
>> Graph doesn’t impose any restrictions on the type of nodes meaning that the
>> upper bound of the nodes type parameter is Any. In contrast, the type
>> parameter for relations has a specific upper bound: Relation.
>>
>> trait Graph[N, R<: Relation[N]]
>>
>> Why Relation? As needed in case of hypergraphs, relations contain 2 to n
>> nodes. Therefore, relations are the most general kind of edges. Edges can be
>> thought of as special relations connecting 2 vertices meaning that Edge should
>> be derived from Relation. The point is that we want Graph to encompass
>> hypergraphs, as well.
>>
>> (4) Factories
>>
>> You can instantiate a Graph as easily as you are accustomed when using List,
>> Set etc. If you pass the factory arguments of the type Relation they will be
>> wrapped by Rel, otherwise by Node – see (6) for what is wrapping good for.
>>
>> (4.1) One node
>> scala> val g = Graph(1)
>> g: scala.collection.Graph[Int,Nothing] = Graph(Node(1))
>> scala> g.nodes
>> res0: g.Nodes = Set(1)
>> scala> g.relations
>> res1: g.Relations = Set()
>>
>> (4.2) Nodes and relations
>> scala> val h = Graph("A", Relation("A","B"))
>> h: scala.collection.Graph[java.lang.String,scala.collection.Relation
>> [java.lang.String]] = Graph(Node(B), Node(A), Rel(Relation(Nodes(A, B))))
>> scala> h.nodes
>> res2: h.Nodes = Set(B, A)
>> scala> h.relations
>> res3: h.Relations = Set(Relation(Nodes(A, B)))
>>
>> (4.3) Nodes and edges
>> scala> val i = Graph(1, Edge(1,3))
>> i: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
>> Graph(Node(3), Node(1), Rel(Edge(Nodes (1, 3))))
>>
>> (4.4) Explicit type parameters
>> If you don’t pass at least one node and one Relation, the missing type
>> parameter will be inferred to Nothing, what is at the moment language- /
>> compiler-inherent, so better you define them explicitly:
>>
>> val j = Graph[Int, Edge[Int]] (Edge(1,3))
>> j: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
>> Graph(Node(3), Node(1), Rel(Edge(Nodes(1, 3))))
>>
>> (4.5) Specific graphs
>> Common graph types have their own specific factories:
>> SimpleGraph, MultiGraph, DirectedGraph, UndirectedGraph
>> At the moment, Graph is the most common graph namely hypegraph, but I’m afraid
>> this is not the best suitable naming.
>>
>> (5) Consistency
>>
>> Graph seamlessly maintains a consistent state of the nodes and relations sets.
>> This basically includes the following:
>>
>> (5a) Nodes of a relation being added will also be added to the nodes set if
>> not yet included.
>>
>> (5b) By default, nodes participating in any relation of the relation set
>> cannot be removed. However, you can force node removal in which case all
>> relations with a back reference to the node to be removed will also be removed.
>>
>> (5c) More constraints on specific graphs…
>>
>> (6) SetLike
>>
>> Graph is SetLike allowing you to use the same operators whether adding (+, +=)
>> or subtracting (-, -=) nodes or relations. Utilizing the SetLike-interface,
>> you no more need to verbose the nodes or relations set. This is simply
>> achieved by letting right-hand operands being an instance of Relation
>> implicitly map to the relations set while all other operands to the nodes set.
>> Also, traversing through Graph you’ll get both nodes and relations. Certainly
>> it’s up to you to traverse the nodes or relations set directly.
>>
>> To handle passing arguments to Graph through SetLike it was necessary to wrap
>> them to Node respectively Rel. This wrapping only takes place when passing
>> parameters or traversing Graph through the SetLike interface, so for any
>> internal algorithm there is no performance penalty.
>>
>> Just a few examples for how SetLike can make code more compact:
>>
>> (6.1) Add a node
>> scala> Graph[Any,Edge[Any]]("A") + 1
>> res1: scala.collection.Graph[Any,scala.collection.Edge[Any]] =
>> Graph(Node(A), Node(1))
>>
>> (6.2) Remove an edge
>> scala> Graph[Int,Edge[Int]](Edge(1,1), Edge(1,2)) - Edge(1,1)
>> res2: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
>> Graph(Node(1), Node(2), Rel(Edge(Nodes (1, 2))))
>>
>> (6.3) As a main benefit, all other SetLike-methods work, too. For instance,
>> let’s try filter:
>> scala> val g = Graph(1, Edge(2,3))
>> g: scala.collection.Graph[Int,scala.collection.Edge[Int]] =
>> Graph(Node(3), Node(1), Node(2), Rel(Edge(Nodes(2, 3))))
>> scala> g.filter (nodePredicate((i:Int) => i>1))
>> res7: scala.collection.Graph[Int,scala.collection.Relation[Int]] =
>> Graph(Node(3), Node(2), Rel(Relation(Nodes(2, 3))))
>>
>> (6.4) shorthand for 6.3
>> scala> g.filter ((i:Int) => i>1)
>>
>> (7) Properties
>>
>> It may be of great value to be able to define behavior such as (5b) or
>> optimization properties for a Graph instance. An example for the letter is
>> whether for each node a set of its connectors should be maintained
>> additionally for speed optimisation.
>>
>> Properties can be set at instantiation time like
>> Graph( WITH_CONNECTORS_SETS )( node1, node2, rel1, rel2 )
>> or anytime later.
>>
>> B?
>> => => => Any suggestions on how to improve Graph’s design?
>>
>> C) Feature Planning
>> -------------------
>> I’d say the above foundations are in a usable state.
>>
>> At the moment, Graph is not intended to cover graph theory. It just aims to be
>> a suitable basement to build upon. More aspects of the graph theory including
>> vector spaces or algorithms, could be appended successively.
>>
>> Graph is designed for direct usage but also for easy extensibility in mind.
>> Its documentation also serves as a cookbook for how to deal with custom graphs
>> such as attributed graphs.
>>
>> C?
>> => => => Which features, in your opinion, are essential for a potential first
>> release of Graph?
>>
>> Cheers
>> Peter
>>
>

On Sun, Nov 14, 2010 at 1:04 PM, Randall R Schulz <rschulz@sonic.net> wrote:

On Sunday November 14 2010, Linas wrote:
> On Sun, 2010-11-14 at 08:16 -0800, Randall R Schulz wrote:
> > On Sunday November 14 2010, Linas wrote:
> > > ...
> >
> > What you're looking for is something to create a dynamically
> > accessible reflection of run-time object networks. I don't think
> > that's the principle use case for a graph library, though I suppose
> > a decent graph library would admit such a use without too much
> > trouble.
>
> Not really. What I was trying to say, that in my experience you often
> do not explicitly build a graph by adding vertices and edges to some
> Graph class but you have a set of linked data structures that you
> must process by applying graph related algorithms.

I do. That's what graphs are. That's what general-purpose graph
libraries are for.

What you want is not a general-purpose graph library, it's a dynamic
object graph library, which is properly seen as a special case.

I'm not so sure I buy this.   What I'd love to see is a type trait (or traits) as the fundamental basis of the library:  GraphLike[T]  (and perhaps DirectedGraphLike[T])
This trait would provide a mechanism to traverse vertices and edges in the graph.   The library would then consist of a whole bunch of algorithms which take  a (graph : T : GraphLike) as an argument.
Finally, when users want their objects to be treated as graphs, they can do so in a companion object.
trait MyFoo {  val left : myFoo  val right : myFoo }object MyFoo {  implicit lazy val graphAdapter = new GraphLike[MyFoo] {     ...  }}
Now, anytime you pass a MyFoo instance into a method that takes a (graph : T : GraphLike) the implicit resolution mechanism will kick in and provide the desired GraphLike type trait.

Finally, you can provide optimised graph structures (a.l.a. what you have now) that can be used to construct graphs in the situation where you do not need/want to provide the type trait adapter.
*and* all of this is not runtime reflection, but static.
I guess which piece builds on the other isn't as important as the ability to adapt my existing object tree to the Graph libraries interfaces via type trait.   Make for a great elegant framework.  See scala-arm for an example of this design.
- Josh

 > Which features, in your opinion, are essential for a potential first release of Graph?

 

Possibly not essential for a first release, but I'd like to see transitive reduction and transitive closure. Topological sorts (particular to DAGs) also ++.