Comments (9)
No problem :) I'll keep the issue open, to remember to add a few methods to ToGraph
class. I guess, we'll need to add not just isAcyclic
but also topSort
, dfs
, etc.
from alga.
Holy crap that's fantastic. I'm going to try that out right away.
from alga.
@fosskers Great! I'll keep this issue open -- isAcyclic
seems like a useful function to add to the API.
from alga.
@fosskers Thanks! I agree, this is a useful function to add. If you don't necessarily need a polymorphic function, the implementation is quite simple:
isDag :: Ord a => AdjacencyMap a -> Bool
isDag = isJust . topSort
You'll just need to convert your graph data type to AdjacencyMap
.
With the new ToGraph
type class (coming soon in algebraic-graphs-0.2
), I believe we could even add it as a separate method, giving you isAcyclic :: (ToGraph g, Ord (ToVertex g)) => g -> Bool
.
from alga.
Ah ha! So it was just a simple thing. And luckily for me, I'm already using AdjacencyMap
.
From the Haddocks:
Compute the topological sort of a graph or return Nothing if the graph is cyclic.
Perhaps I should have used my eyes to read 😢
from alga.
So isJust . topSort
tells us if there's a cycle, which by itself is still very useful. Would it be hard to report the values of the vertices that are causing the cycle?
from alga.
@fosskers To find the cycle, you can use the scc
function. It returns you a graph whose vertices are strongly-connected components, and if any component contains more than a single vertex it is a cycle.
Here is one possible way to use is:
cycles :: Ord a => AdjacencyMap a -> [AdjacencyMap a]
cycles x = [ induce (`Set.member` c) x | c <- cs ]
where
cs = filter (\c -> Set.size c > 1) $ vertexList (scc x)
We obtain the list cs
which contains non-singleton components (i.e. cyclic subgraphs), and then compute corresponding induced subgraphs of the original graph. As a result you can see all cycles in isolation.
For example:
> cycles $ path [1, 2, 3]
[]
> cycles $ circuit [1, 2, 3]
[edges [(1,2),(2,3),(3,1)]]
> cycles $ circuit [1, 2, 3] + path [3, 4, 5] + circuit [5, 6, 7]
[edges [(1,2),(2,3),(3,1)],edges [(5,6),(6,7),(7,5)]]
from alga.
Alright, looking good! Thanks a lot, once again.
from alga.
Woops, my bad.
from alga.
Related Issues (20)
- Hackage Release HOT 5
- How to handle goodness inherited from other libraries HOT 2
- Bump upper bound for base-compat for version 0.4 on Hackage HOT 4
- Unable to use ghcid HOT 6
- Algorithms should be in terms of typeclasses not data structures HOT 15
- Acyclic graphs with Int labels HOT 5
- Tests failed to build with QuickCheck 2.14.2
- Multitree HOT 3
- Monoid instance HOT 6
- support for GraphViz "HTML strings" for node or edge labels HOT 1
- Add benchmarks to CI HOT 2
- Supporting different node and edge types HOT 7
- v0.6 fails to build with GHC 8.0 and 8.2 HOT 3
- Doubt about decorating a Graph HOT 4
- Compatibility with mtl-2.3 HOT 2
- Smart constructor for Symbol rather than requiring -XOverloadedLists HOT 1
- Proposal : foldgM HOT 2
- Algebra.Graph.Labelled.AdjacencyMap.edges appears to be broken HOT 2
- Semigroup version of Algebra.Graph.Labelled.AdjacencyMap HOT 7
- Bump "deepseq" dependency bounds to 1.5.0.0 HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from alga.