Data.PlanarGraph.EdgeOracle

Data structure to represent a planar graph with which we can test in \(O(1)\) time if an edge between a pair of vertices exists.

Documentation

newtype EdgeOracle s w a

Edge Oracle:

main idea: store adjacency lists in such a way that we store an edge (u,v) either in u's adjacency list or in v's. This can be done s.t. all adjacency lists have length at most 6.

note: Every edge is stored exactly once (i.e. either at u or at v, but not both)

Constructors

EdgeOracle

Fields

• _unEdgeOracle :: Vector (Vector (VertexId s w :+ a))

Instances

Functor (EdgeOracle s w)

Defined in Data.PlanarGraph.EdgeOracle

Methods

fmap :: (a -> b) -> EdgeOracle s w a -> EdgeOracle s w b

(<$) :: a -> EdgeOracle s w b -> EdgeOracle s w a

Foldable (EdgeOracle s w)

Defined in Data.PlanarGraph.EdgeOracle

Methods

fold :: Monoid m => EdgeOracle s w m -> m

foldMap :: Monoid m => (a -> m) -> EdgeOracle s w a -> m

foldr :: (a -> b -> b) -> b -> EdgeOracle s w a -> b

foldr' :: (a -> b -> b) -> b -> EdgeOracle s w a -> b

foldl :: (b -> a -> b) -> b -> EdgeOracle s w a -> b

foldl' :: (b -> a -> b) -> b -> EdgeOracle s w a -> b

foldr1 :: (a -> a -> a) -> EdgeOracle s w a -> a

foldl1 :: (a -> a -> a) -> EdgeOracle s w a -> a

toList :: EdgeOracle s w a -> [a]

null :: EdgeOracle s w a -> Bool

length :: EdgeOracle s w a -> Int

elem :: Eq a => a -> EdgeOracle s w a -> Bool

maximum :: Ord a => EdgeOracle s w a -> a

minimum :: Ord a => EdgeOracle s w a -> a

sum :: Num a => EdgeOracle s w a -> a

product :: Num a => EdgeOracle s w a -> a

Traversable (EdgeOracle s w)

Defined in Data.PlanarGraph.EdgeOracle

Methods

traverse :: Applicative f => (a -> f b) -> EdgeOracle s w a -> f (EdgeOracle s w b)

sequenceA :: Applicative f => EdgeOracle s w (f a) -> f (EdgeOracle s w a)

mapM :: Monad m => (a -> m b) -> EdgeOracle s w a -> m (EdgeOracle s w b)

sequence :: Monad m => EdgeOracle s w (m a) -> m (EdgeOracle s w a)

Eq a => Eq (EdgeOracle s w a)

Defined in Data.PlanarGraph.EdgeOracle

Methods

(==) :: EdgeOracle s w a -> EdgeOracle s w a -> Bool

(/=) :: EdgeOracle s w a -> EdgeOracle s w a -> Bool

Show a => Show (EdgeOracle s w a)

Defined in Data.PlanarGraph.EdgeOracle

Methods

showsPrec :: Int -> EdgeOracle s w a -> ShowS

show :: EdgeOracle s w a -> String

showList :: [EdgeOracle s w a] -> ShowS

edgeOracle :: PlanarGraph s w v e f -> EdgeOracle s w (Dart s)

Given a planar graph, construct an edge oracle. Given a pair of vertices this allows us to efficiently find the dart representing this edge in the graph.

pre: No self-loops and no multi-edges!!!

running time: \(O(n)\)

buildEdgeOracle :: forall f s w e. Foldable f => [(VertexId s w, f (VertexId s w :+ e))] -> EdgeOracle s w e

Builds an edge oracle that can be used to efficiently test if two vertices are connected by an edge.

running time: \(O(n)\)

hasEdge :: VertexId s w -> VertexId s w -> EdgeOracle s w a -> Bool

Test if u and v are connected by an edge.

running time: \(O(1)\)

findEdge :: VertexId s w -> VertexId s w -> EdgeOracle s w a -> Maybe a

Find the edge data corresponding to edge (u,v) if such an edge exists

running time: \(O(1)\)

findDart :: VertexId s w -> VertexId s w -> EdgeOracle s w (Dart s) -> Maybe (Dart s)

Given a pair of vertices (u,v) returns the dart, oriented from u to v, corresponding to these vertices.

running time: \(O(1)\)