Copyright	Thodoris Papakonstantinou 2017-2026
License	LGPL-3
Maintainer	dev@tpapak.com
Stability	experimental
Portability	POSIX
Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.Graph.AdjacencyList.DFS

Contents

Types
get longest path from a vertex to another

Description

Depth-first search (DFS) on directed graphs. Produces a topological ordering, a visited-order list, and the set of discovered vertices. Also provides longestPath on DAGs and connectivity queries.

Synopsis

data DFS = DFS {
- topsort :: [Vertex]
- visited :: [Vertex]
- discovered :: IntSet
- called :: Int
}
dfs :: Graph -> Vertex -> DFS
type DAG = Graph
type Distances = IntMap Vertex
longestPath :: Graph -> Vertex -> Vertex -> [Edge]
postordering :: DFS -> [Vertex]
areConnected :: Distances -> Vertex -> Vertex -> Bool
distances :: DAG -> DFS -> Vertex -> Distances

Documentation

data DFS Source #

Result of a depth-first search from a single source vertex.

Constructors

DFS
Fields topsort :: [Vertex] Vertices in reverse post-order (topological sort for DAGs). visited :: [Vertex] Vertices in DFS visit order. discovered :: IntSet Set of all discovered vertices. called :: Int Number of DFS calls made.

Instances

Instances details

Show DFS Source #
Instance details Defined in Data.Graph.AdjacencyList.DFS Methods showsPrec :: Int -> DFS -> ShowS # show :: DFS -> String # showList :: [DFS] -> ShowS #
Eq DFS Source #
Instance details Defined in Data.Graph.AdjacencyList.DFS Methods (==) :: DFS -> DFS -> Bool # (/=) :: DFS -> DFS -> Bool #

dfs :: Graph -> Vertex -> DFS Source #

Depth first search

Types

type DAG = Graph Source #

:)

type Distances = IntMap Vertex Source #

Map from vertex to its distance (number of edges) from the source in a DAG.

get longest path from a vertex to another

longestPath :: Graph -> Vertex -> Vertex -> [Edge] Source #

Longest path from tail to nose

postordering :: DFS -> [Vertex] Source #

Post-order traversal (reverse of topsort).

areConnected :: Distances -> Vertex -> Vertex -> Bool Source #

Check whether vertex v is reachable from vertex u according to the given distance map (distance > 0 means reachable; u is reachable from itself).

distances :: DAG -> DFS -> Vertex -> Distances Source #

Ginen a DAG and a vertex you get the distances