Data.Graph transitive closure

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
19 messages Options
Reply | Threaded
Open this post in threaded view
|

Data.Graph transitive closure

David Feuer
I just noticed that Data.Graph doesn't offer a transitive closure operation. Looking into implementing one, I discovered that doing so efficiently has been the subject of non-trivial research [*]. So if there's any demand, we should try to implement a reasonably efficient version in containers. Anybody want one?


_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.Graph transitive closure

Elliot Cameron-2
It's hard to imagine reaching for a graph without some thought that you'd want to compute a closure. I've wanted this in the past, but I've never thought seriously about using Data.Graph for it. Perhaps this is why?

On Wed, Jun 19, 2019 at 6:20 PM David Feuer <[hidden email]> wrote:
I just noticed that Data.Graph doesn't offer a transitive closure operation. Looking into implementing one, I discovered that doing so efficiently has been the subject of non-trivial research [*]. So if there's any demand, we should try to implement a reasonably efficient version in containers. Anybody want one?

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.Graph transitive closure

chessai .
I want one, because, why not? It might be useful to those who use that API. I'm always excited to see APIs become more complete.

On Wed, Jun 19, 2019, 6:39 PM Elliot Cameron <[hidden email]> wrote:
It's hard to imagine reaching for a graph without some thought that you'd want to compute a closure. I've wanted this in the past, but I've never thought seriously about using Data.Graph for it. Perhaps this is why?

On Wed, Jun 19, 2019 at 6:20 PM David Feuer <[hidden email]> wrote:
I just noticed that Data.Graph doesn't offer a transitive closure operation. Looking into implementing one, I discovered that doing so efficiently has been the subject of non-trivial research [*]. So if there's any demand, we should try to implement a reasonably efficient version in containers. Anybody want one?

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.Graph transitive closure

Andreas Abel
In reply to this post by Elliot Cameron-2
Since there was nothing standard out there we (Agda) rolled our own.

 
https://github.com/agda/agda/blob/f3f82fa0510335087653ba715cef06a5702deb18/src/full/Agda/Utils/Graph/AdjacencyMap/Unidirectional.hs#L719-L877

There are even two versions (complete (Abel) and
gaussJordanFloydWarshallMcNaughtonYamada (Danielsson)) which behave
differently wrt. runtime, so we use both, for different purposes.

Algorithms might look different for different graph representations, we
use a version of adjacency lists which works also well for sparse graphs.

On 2019-06-20 00:38, Elliot Cameron wrote:

> It's hard to imagine reaching for a graph without some thought that
> you'd want to compute a closure. I've wanted this in the past, but I've
> never thought seriously about using Data.Graph for it. Perhaps this is why?
>
> On Wed, Jun 19, 2019 at 6:20 PM David Feuer <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     I just noticed that Data.Graph doesn't offer a transitive closure
>     operation. Looking into implementing one, I discovered that doing so
>     efficiently has been the subject of non-trivial research [*]. So if
>     there's any demand, we should try to implement a reasonably
>     efficient version in containers. Anybody want one?
>
>     [*] http://www.cs.hut.fi/~enu/thesis.html
>     _______________________________________________
>     Libraries mailing list
>     [hidden email] <mailto:[hidden email]>
>     http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.Graph transitive closure

Johannes Waldmann-2
In reply to this post by David Feuer
> ... reasonably efficient transitive closure for Data.Graph ...

well, since we have

  type Graph = Array Vertex [Vertex]

efficiency is already questionable?
We cannot quickly check whether an edge is present,
we cannot quickly get all predecessors of a vertex.
But perhaps we don't need to. The underlying assumptions
(cost of elementary operations)
of http://www.cs.hut.fi/~enu/thesis.html
are not immediately clear.


The cited Agda library has

   newtype Graph n e = Graph (Map n (Map n e))


Another option is to store back edges as well, as in
https://github.com/haskell-works/relation/blob/master/src/Data/Relation/Internal.hs


FGL fuses these two maps

type GraphRep a b = IntMap (Context' a b)
type Context' a b = (IntMap [b], a, IntMap [b])

https://hackage.haskell.org/package/fgl-5.7.0.1/docs/src/Data.Graph.Inductive.PatriciaTree.html#Gr


this saves some look-ups (if you need successors and
predecessors of the very same node)
but this can't be used for relations,
where start and end of an edge have different types.
But for transitive closure, these types would agree anyway.


What to make of this?

Perhaps Data.Graph should be moved out of containers.
The design space is just too large to single out one specific point?
If we keep it, it would be very nice to document the complexity
of algorithms. Section 7 of the King/Launchbury paper
(cited in the API docs) claims "DFS in O(V+E)", backed up by
experiments. This seems to be the main motivation for this library
(DFS, with application: SCC). It's not clear whether the underlying
design should be recommended for a general graph library.


- Johannes




_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.Graph transitive closure

Elliot Cameron-2
I've actually wondered why Data.Graph existed since it is obviously not written for serious/heavy usage. So I do see an argument for deprecating it instead of polishing it.

On Fri, Jun 21, 2019 at 10:10 AM Johannes Waldmann <[hidden email]> wrote:
> ... reasonably efficient transitive closure for Data.Graph ...

well, since we have

  type Graph = Array Vertex [Vertex]

efficiency is already questionable?
We cannot quickly check whether an edge is present,
we cannot quickly get all predecessors of a vertex.
But perhaps we don't need to. The underlying assumptions
(cost of elementary operations)
of http://www.cs.hut.fi/~enu/thesis.html
are not immediately clear.


The cited Agda library has

   newtype Graph n e = Graph (Map n (Map n e))


Another option is to store back edges as well, as in
https://github.com/haskell-works/relation/blob/master/src/Data/Relation/Internal.hs


FGL fuses these two maps

type GraphRep a b = IntMap (Context' a b)
type Context' a b = (IntMap [b], a, IntMap [b])

https://hackage.haskell.org/package/fgl-5.7.0.1/docs/src/Data.Graph.Inductive.PatriciaTree.html#Gr


this saves some look-ups (if you need successors and
predecessors of the very same node)
but this can't be used for relations,
where start and end of an edge have different types.
But for transitive closure, these types would agree anyway.


What to make of this?

Perhaps Data.Graph should be moved out of containers.
The design space is just too large to single out one specific point?
If we keep it, it would be very nice to document the complexity
of algorithms. Section 7 of the King/Launchbury paper
(cited in the API docs) claims "DFS in O(V+E)", backed up by
experiments. This seems to be the main motivation for this library
(DFS, with application: SCC). It's not clear whether the underlying
design should be recommended for a general graph library.


- Johannes




_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.Graph transitive closure

David Feuer
Yes, Data.Graph is a weird, difficult-to-polish corner of containers. I'm all for removing it, but there's one sticky point: it's managed to accumulate some extremely important reverse dependencies. In particular, GHC, Cabal, and Agda all use it. So if we want to deprecate it, we need a really good plan for what happens next.

On Fri, Jun 21, 2019, 12:37 PM Elliot Cameron <[hidden email]> wrote:
I've actually wondered why Data.Graph existed since it is obviously not written for serious/heavy usage. So I do see an argument for deprecating it instead of polishing it.

On Fri, Jun 21, 2019 at 10:10 AM Johannes Waldmann <[hidden email]> wrote:
> ... reasonably efficient transitive closure for Data.Graph ...

well, since we have

  type Graph = Array Vertex [Vertex]

efficiency is already questionable?
We cannot quickly check whether an edge is present,
we cannot quickly get all predecessors of a vertex.
But perhaps we don't need to. The underlying assumptions
(cost of elementary operations)
of http://www.cs.hut.fi/~enu/thesis.html
are not immediately clear.


The cited Agda library has

   newtype Graph n e = Graph (Map n (Map n e))


Another option is to store back edges as well, as in
https://github.com/haskell-works/relation/blob/master/src/Data/Relation/Internal.hs


FGL fuses these two maps

type GraphRep a b = IntMap (Context' a b)
type Context' a b = (IntMap [b], a, IntMap [b])

https://hackage.haskell.org/package/fgl-5.7.0.1/docs/src/Data.Graph.Inductive.PatriciaTree.html#Gr


this saves some look-ups (if you need successors and
predecessors of the very same node)
but this can't be used for relations,
where start and end of an edge have different types.
But for transitive closure, these types would agree anyway.


What to make of this?

Perhaps Data.Graph should be moved out of containers.
The design space is just too large to single out one specific point?
If we keep it, it would be very nice to document the complexity
of algorithms. Section 7 of the King/Launchbury paper
(cited in the API docs) claims "DFS in O(V+E)", backed up by
experiments. This seems to be the main motivation for this library
(DFS, with application: SCC). It's not clear whether the underlying
design should be recommended for a general graph library.


- Johannes




_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.Graph transitive closure

Johannes Waldmann-2
In reply to this post by Elliot Cameron-2

> I've actually wondered why Data.Graph existed since it is obviously not
> written for serious/heavy usage.

But it was!

As I understand, it was originally part of GHC
(ghc-0.29/ghc/compiler/utils/Digraph.lhs)
for computing SCCs (in the graph of dependencies of declarations).

So we can assume that it does this well.

And I guess it's used for the very same purpose in Cabal and Agda.

- J.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.Graph transitive closure

David Feuer
The big problem is that when it was broken off into containers, there was no attempt to add appropriate abstraction barriers. So it's ... awkward.

On Fri, Jun 21, 2019, 2:10 PM Johannes Waldmann <[hidden email]> wrote:

> I've actually wondered why Data.Graph existed since it is obviously not
> written for serious/heavy usage.

But it was!

As I understand, it was originally part of GHC
(ghc-0.29/ghc/compiler/utils/Digraph.lhs)
for computing SCCs (in the graph of dependencies of declarations).

So we can assume that it does this well.

And I guess it's used for the very same purpose in Cabal and Agda.

- J.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.Graph transitive closure

Carter Schonwald
i've definitely used the efficient SCC bits of Data.Graph in the past.

graphs are just such a rich area that it seems doubtful that there'll ever be a one true library 

On Fri, Jun 21, 2019 at 2:21 PM David Feuer <[hidden email]> wrote:
The big problem is that when it was broken off into containers, there was no attempt to add appropriate abstraction barriers. So it's ... awkward.

On Fri, Jun 21, 2019, 2:10 PM Johannes Waldmann <[hidden email]> wrote:

> I've actually wondered why Data.Graph existed since it is obviously not
> written for serious/heavy usage.

But it was!

As I understand, it was originally part of GHC
(ghc-0.29/ghc/compiler/utils/Digraph.lhs)
for computing SCCs (in the graph of dependencies of declarations).

So we can assume that it does this well.

And I guess it's used for the very same purpose in Cabal and Agda.

- J.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.Graph transitive closure

Johannes Waldmann-2
On 21.06.19 20:44, Carter Schonwald wrote:

>  ... it seems doubtful that there'll
> ever be a one true [graph] library

Yes. My point was that Data.Graph isn't a "graph library"
(it was never meant to be) - it's a "DFS/SCC library".

- J.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.Graph transitive closure

Alan Isaac
In reply to this post by David Feuer
Feedback from an occasional Haskell user:
I would use it.

I've noticed that computational implementations of "transitive closure"
often deviate from my (user-level) understanding of the standard
mathematical definition.  Specifically, self loops are often discarded.
I assume/hope the math def will be used in haskell.

A prominent example is Mathematica's TransitiveClosureGraph command.
E.g., `TransitiveClosureGraph[{a -> b, b -> c, c -> a}]` has no self loops,
even though `a` is clearly reachable from `a`, and
TransitiveClosureGraph[{a -> a, b -> b, c -> c}]` is empty!)
In the past networkx also had this flaw (although they indicated a plan
to fix this; I'd have to recheck the current status).

Cheers, Alan Isaac

PS My apologies if I misread your post; I understood it to request
user feedback, not just developer assessment.


On 6/20/2019 8:00 AM, David wrote:
> I just noticed that Data.Graph doesn't offer a transitive closure
> operation. Looking into implementing one, I discovered that doing so
> efficiently has been the subject of non-trivial research [*]. So if there's
> any demand, we should try to implement a reasonably efficient version in
> containers. Anybody want one?

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.Graph transitive closure

Johannes Waldmann-2
In reply to this post by David Feuer
> .. I would use it.

what is your use case?
Can you extract test cases that could be used
to validate correctness and complexity of an implementation?

Specific question: assume the implementation gives you
S =  transitive-closure-of(R).
Then what do you do with  S  (in your application)?
Does  Data.Graph  (i.e., array of lists of successors)
have the right structure? E.g., it is inefficient
to test for membership in these lists. But lists are fine
if you need to handle all successors anyway.


Evaluation of (recursive) Datalog queries is another
application area of transitive closure algorithms.
(e.g., https://doi.org/10.1007/BF01264013 )


- J.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.Graph transitive closure

Andrew Butterfield-2
In reply to this post by Johannes Waldmann-2
Dear Johannes, Carter, David, libraries,

  As a formal methodist who likes and uses functional languages a lot, I looked at doing this
in a "principled" way a long time ago.

The idea was to formally specify an abstract graph datatype and various graph operations
(create, query, modify, transitive closure, etc, etc...) and then show correctness of of simple
but possibly inefficient implementations.
Then the plan was to develop efficient operations, including use of appropriate graph representation
types, and show formally that they were refinements of the inefficient ones.

It rapidly became *very* clear that the best/only? way to do something efficiently was to decide
which operations were important, and specialise for those. Woe betide you if you left out an operator
that later would be important, because its efficient implementation could well force you
to do  complete re-design.

Basically, it is not feasible to design a large/general-purpose graph library that  does everything efficiently.

I then got distracted by something else.....

Regards, Andrew


> On 21 Jun 2019, at 19:48, Johannes Waldmann <[hidden email]> wrote:
>
> On 21.06.19 20:44, Carter Schonwald wrote:
>
>> ... it seems doubtful that there'll
>> ever be a one true [graph] library
>
> Yes. My point was that Data.Graph isn't a "graph library"
> (it was never meant to be) - it's a "DFS/SCC library".
>
> - J.
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

--------------------------------------------------------------------
Andrew Butterfield     Tel: +353-1-896-2517     Fax: +353-1-677-2204
Lero@TCD, Head of Foundations & Methods Research Group
School of Computer Science and Statistics,
Room G.39, O'Reilly Institute, Trinity College, University of Dublin
                         http://www.scss.tcd.ie/Andrew.Butterfield/
--------------------------------------------------------------------

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.Graph transitive closure

Johannes Waldmann-2
Hi,

> I looked at doing this in a "principled" way a long time ago.
> I then got distracted by something else.....

You don't say :-)

Well, short-term suggestion (for containers:Data.Graph)
don't change existing code,
but improve documentation and do some benchmarking
https://github.com/haskell/containers/issues/648
https://github.com/haskell/containers/issues/649

@David: perhaps you can label these issues as "nice to have"
so it does not look like "bugs that need fixing".
Benchmarking would make for a nice student project?
In fact, I will pitch this to my current class.

- Johannes
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.Graph transitive closure

Evan Laforge
I have been bit before by Data.Graph... I think it's that since it's a
type synonym, it inherits Eq from Array, but it doesn't have a
normalized form, so Eq is misleading in that topologically equal
graphs are not Eq... something like that.  And it can't be fixed
because it's just a type synonym over Array.  That's probably the "no
attempt to add abstraction barriers" alluded to above.  But the reason
I used it in the first place was I wanted a graph, and behold there is
Data.Graph already installed.  So it's presence in containers gives it
the impression of authority, but it's definitely not as well developed
as the other types in containers.

Since it seems like it can't be moved or made into a proper type
without breaking things, we could at least have some caveats in the
documentation, saying what it's appropriate for and what it's not.
And maybe warning about that Eq thing.  So I guess I'm seconding the
"just add documentation" suggestion.

Also while I'm here it's weird and confusing how it silently
re-exports Data.Tree...

On Mon, Jun 24, 2019 at 4:02 AM Johannes Waldmann
<[hidden email]> wrote:

>
> Hi,
>
> > I looked at doing this in a "principled" way a long time ago.
> > I then got distracted by something else.....
>
> You don't say :-)
>
> Well, short-term suggestion (for containers:Data.Graph)
> don't change existing code,
> but improve documentation and do some benchmarking
> https://github.com/haskell/containers/issues/648
> https://github.com/haskell/containers/issues/649
>
> @David: perhaps you can label these issues as "nice to have"
> so it does not look like "bugs that need fixing".
> Benchmarking would make for a nice student project?
> In fact, I will pitch this to my current class.
>
> - Johannes
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.Graph transitive closure

David Feuer
If we could boot it out of containers and into its own package, that would make me happier; then I wouldn't have such a weird, special-purpose structure sitting around in an otherwise general-purpose library.

On Mon, Jun 24, 2019, 1:38 PM Evan Laforge <[hidden email]> wrote:
I have been bit before by Data.Graph... I think it's that since it's a
type synonym, it inherits Eq from Array, but it doesn't have a
normalized form, so Eq is misleading in that topologically equal
graphs are not Eq... something like that.  And it can't be fixed
because it's just a type synonym over Array.  That's probably the "no
attempt to add abstraction barriers" alluded to above.  But the reason
I used it in the first place was I wanted a graph, and behold there is
Data.Graph already installed.  So it's presence in containers gives it
the impression of authority, but it's definitely not as well developed
as the other types in containers.

Since it seems like it can't be moved or made into a proper type
without breaking things, we could at least have some caveats in the
documentation, saying what it's appropriate for and what it's not.
And maybe warning about that Eq thing.  So I guess I'm seconding the
"just add documentation" suggestion.

Also while I'm here it's weird and confusing how it silently
re-exports Data.Tree...

On Mon, Jun 24, 2019 at 4:02 AM Johannes Waldmann
<[hidden email]> wrote:
>
> Hi,
>
> > I looked at doing this in a "principled" way a long time ago.
> > I then got distracted by something else.....
>
> You don't say :-)
>
> Well, short-term suggestion (for containers:Data.Graph)
> don't change existing code,
> but improve documentation and do some benchmarking
> https://github.com/haskell/containers/issues/648
> https://github.com/haskell/containers/issues/649
>
> @David: perhaps you can label these issues as "nice to have"
> so it does not look like "bugs that need fixing".
> Benchmarking would make for a nice student project?
> In fact, I will pitch this to my current class.
>
> - Johannes
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.Graph transitive closure

Johannes Waldmann-2
On 24.06.19 20:22, David Feuer wrote:

> If we could boot it out of containers and into its own package,

https://hackage.haskell.org/package/GraphSCC-1.0.4/docs/Data-Graph-SCC.html
 ?
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: Data.Graph transitive closure

David Feuer
If Iavor wants to adopt Data.Graph into his package, I'm fine with that. I'm not exactly clear on what his package adds to the mix, but if it's not my problem it's not my problem. GHC HQ needs to sign off on adding it as a boot package, but its dependencies (base, array, containers) should make that acceptable.

On Mon, Jun 24, 2019, 2:25 PM Johannes Waldmann <[hidden email]> wrote:
On 24.06.19 20:22, David Feuer wrote:

> If we could boot it out of containers and into its own package,

https://hackage.haskell.org/package/GraphSCC-1.0.4/docs/Data-Graph-SCC.html
 ?

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries