New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Please publish Graph-misc #74

Closed
NicolasRouquette opened this Issue Jun 5, 2017 · 16 comments

Comments

Projects
None yet
2 participants
@NicolasRouquette
Copy link
Contributor

NicolasRouquette commented Jun 5, 2017

Instead of copying source code from Graph-misc, it would be nice if we could instead use a source dependency in a build.sbt like this:

scalaVersion := "2.11.8"

lazy val graph_misc =
 ProjectRef(uri("file:/opt/local/imce/users/nfr/github.scala/scala-graph#cb7a8c1"), "Graph-misc")

lazy val root = Project("scala-graph-dependency", file(".")) dependsOn graph_misc

Unfortunately, this doesn't work because graph-misc hasn't been published so there is no POM for it.

Note that one can do something similar with the other published modules (e.g., Graph-json).
Not sure why it is necessary to publish the module though but at this time.

@NicolasRouquette

This comment has been minimized.

Copy link
Contributor Author

NicolasRouquette commented Jun 5, 2017

Actually, the problem is due to this: sbt/sbt#2901
The workaround suggested in the PR works; I created a scala_211 branch with:

  scalaVersion := Version.compiler_2_11,
  crossScalaVersions := Seq(scalaVersion.value, Version.compiler_2_12),

Now, the above build.sbt works.

NicolasRouquette added a commit to NicolasRouquette/scala-graph that referenced this issue Jun 5, 2017

@peter-empen

This comment has been minimized.

Copy link
Contributor

peter-empen commented Jun 10, 2017

Nicolas, is it graph-misc connectivity you are interested in? I'm just thinking about moving it to graph-core...

@NicolasRouquette

This comment has been minimized.

Copy link
Contributor Author

NicolasRouquette commented Jun 10, 2017

Yes, the hierarchical topological sort algorithm is useful.
Moving it to graph-core & publishing a new version would be super helpful!

@peter-empen

This comment has been minimized.

Copy link
Contributor

peter-empen commented Jun 11, 2017

What exactly do you mean by "hierarchical topo sort"? How does it relate to the connectivity algorithms in graph-misc?
Based on this new term I am not sure we are done by publishing graph-misc or adding connectivity to graph-core.

@NicolasRouquette

This comment has been minimized.

Copy link
Contributor Author

NicolasRouquette commented Jun 12, 2017

Sorry, I was confusing the algo in graph-misc with how I use it for computing a hierarchical topo sort of a directed graph in my application where I use a topo sort on the DAG and and within each connected component, use the list of nodes as an arbitrary topo sort.

@NicolasRouquette

This comment has been minimized.

Copy link
Contributor Author

NicolasRouquette commented Jun 22, 2017

@peter-empen Is there anything beyond my confusion that prevents adding connectivity to graph-core?

@peter-empen

This comment has been minimized.

Copy link
Contributor

peter-empen commented Jun 24, 2017

Apart from time, no. To add Tarjan's algorithm to graph-core s more a new implementation than just moving it from graph-misc since Graph for Scala always cares about visitors, mixed, multi and even hypergraphs. So please bear with me if it takes some more days.

@peter-empen peter-empen added enhancement and removed publishing labels Jul 9, 2017

@peter-empen

This comment has been minimized.

Copy link
Contributor

peter-empen commented Jul 9, 2017

FYI: I've added scc support to core. It still needs to be made tail-recursive and, certainly, documented. Publishing is going after that.

@NicolasRouquette

This comment has been minimized.

Copy link
Contributor Author

NicolasRouquette commented Jul 10, 2017

Thanks @peter-empen; can you clarify which algos need to be made tail-recursive & documented?

For tail-recursive conversion, I presume you're referring to the new functionality in misc, i.e.:

in scalax.collection.connectivity.GraphComponents

in scalax.collection.connectivity.GraphTrees

in scalax.collection.connectivity.GraphTrees

@peter-empen

This comment has been minimized.

Copy link
Contributor

peter-empen commented Jul 11, 2017

I was referring to the new commit 009f4bf, more specifically TraverserImpl.scala#L499.
Would you want to devote time to make Tarjan's algorithm tail-recursive there? Then your starting point could be TConnectivity.scala. Otherwise I'll get down to it in a few days.
Then the new functionality must be described on http://www.scala-graph.org/guides/core-traversing.html.

@NicolasRouquette

This comment has been minimized.

Copy link
Contributor Author

NicolasRouquette commented Jul 11, 2017

Ah, thanks for the clarification. I'll take a look at refactoring this algorithm first.

@peter-empen

This comment has been minimized.

Copy link
Contributor

peter-empen commented Jul 26, 2017

Nicolas, do you manage to work on this? Tell me if I should take over.

@NicolasRouquette

This comment has been minimized.

Copy link
Contributor Author

NicolasRouquette commented Aug 9, 2017

Sorry, I have been swamped and haven't had time to look at this refactoring.
Go ahead and take over.

@peter-empen

This comment has been minimized.

Copy link
Contributor

peter-empen commented Aug 11, 2017

Ok I'll see to it after vacations.

@peter-empen

This comment has been minimized.

Copy link
Contributor

peter-empen commented Sep 11, 2017

With 1.12.0, finding strongly connected components is included in core.

@NicolasRouquette

This comment has been minimized.

Copy link
Contributor Author

NicolasRouquette commented Sep 13, 2017

Thanks @peter-empen!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment