| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
Cycles.Findcy
- edgeAdjacent :: [Int] -> [Int] -> Bool -> Bool
- eadjpos :: [Int] -> [[Int]] -> Bool -> [Int]
- max2 :: [[Int]] -> Int
- edgeAdjacencyLists :: [[Int]] -> Bool -> [[Int]]
- vadjpos :: Int -> [[Int]] -> Bool -> [Int]
- vertexAdjacencyLists :: [[Int]] -> Bool -> [[Int]]
- generateFindCyCode :: [[Int]] -> String -> Bool -> Bool -> String
Documentation
edgeAdjacent :: [Int] -> [Int] -> Bool -> Bool
Given two edges and whether the graph is directed, this function gives whether they are adjacent
eadjpos :: [Int] -> [[Int]] -> Bool -> [Int]
Given an edge, graph and whether it is directed, this function returns the list of indices of edges adjacent to the given edge
edgeAdjacencyLists :: [[Int]] -> Bool -> [[Int]]
This gives a list = [[Int]] such that (list !! i) !! j = the jth edge adjacent to the ith edge
vadjpos :: Int -> [[Int]] -> Bool -> [Int]
This is the analogous function to eadjpos, except for vertex adjacency instead of edge adjacency
vertexAdjacencyLists :: [[Int]] -> Bool -> [[Int]]
This is the analogous function to edgeAdjacencyLists, except for vertex adjacency instead of edge adjacency
generateFindCyCode :: [[Int]] -> String -> Bool -> Bool -> String
Following is the generator for a one-time use C program to find all cycles in a graph.
The general program will work with directed and undirected graphs and will find all *directed* cycles in the graph I plan to modify the original program to work with graphs and digraphs and each modification to optinally only count cycles instead of listing them This cannot be solved in O(V+E) time because even planar graphs can have O(2^v) cycles and listing/counting a graph cycle takes at least 1 CPU cycle
The algorithm performs a depth first search from an arbitrary vertex, marking seen vertices on the way, and only outputting cycles through the initial vertex. As all cycles through that vertex have been found by the end, it is removed and the process repeated. This way, there is no need to check if a cycle has been found yet and there are no sources of repetition.
The only weaknesses of this algorithm that I know are: 1) It requires full out-adjacency lists for each vertex (best fit for directed, sparse graphs) 2) For undirected graphs, if the cycles are considered to be undirected, it outputs one "forward" and one "backward" copy of each cycle N.B. For the purposes of inputting the cycles into the Max-Cycles part of the code, this is a strength as the algorithm needs both 3) Although the output file is formatted, it is annoying to integrate generating, compiling, running, and parsing into a single function 4) The generated code is in C. Yeah, I said it. On the plus side, unless you're running this on very big graphs (where it would take an obscene amount of time to finish), you shouldn't run into overflow issues.
The biggest plus? This algorithm is stupid-fast. The last big test I ran outputted ~1.5GB of cycles from ~2k strongly-connected graphs, |E|<=36 in under 30s.
Note: graph (edgelist), cfilename, are assumed variables