| Copyright | (c) Masahiro Sakai 2020 |
|---|---|
| License | BSD-style |
| Maintainer | masahiro.sakai@gmail.com |
| Stability | provisional |
| Portability | non-portable |
| Safe Haskell | Safe-Inferred |
| Language | Haskell2010 |
ToySolver.Graph.Base
Description
Synopsis
- type EdgeLabeledGraph a = Array Vertex (IntMap a)
- type Graph = EdgeLabeledGraph ()
- type Vertex = Int
- type VertexSet = IntSet
- type Edge a = (Vertex, Vertex, a)
- graphFromEdges :: HasCallStack => Int -> [Edge a] -> EdgeLabeledGraph a
- graphFromEdgesWith :: HasCallStack => (a -> a -> a) -> Int -> [Edge a] -> EdgeLabeledGraph a
- graphToEdges :: EdgeLabeledGraph a -> [Edge a]
- graphFromUnorderedEdges :: HasCallStack => Int -> [Edge a] -> EdgeLabeledGraph a
- graphFromUnorderedEdgesWith :: HasCallStack => (a -> a -> a) -> Int -> [Edge a] -> EdgeLabeledGraph a
- graphToUnorderedEdges :: EdgeLabeledGraph a -> [Edge a]
- converseGraph :: EdgeLabeledGraph a -> EdgeLabeledGraph a
- complementGraph :: EdgeLabeledGraph a -> EdgeLabeledGraph ()
- complementSimpleGraph :: EdgeLabeledGraph a -> EdgeLabeledGraph ()
- numVertexes :: EdgeLabeledGraph a -> Int
- isSimpleGraph :: EdgeLabeledGraph a -> Bool
- isIndependentSet :: EdgeLabeledGraph a -> VertexSet -> Bool
- isIndependentSetOf :: VertexSet -> EdgeLabeledGraph a -> Bool
- isCliqueOf :: VertexSet -> EdgeLabeledGraph a -> Bool
Graph data types
type EdgeLabeledGraph a = Array Vertex (IntMap a) Source #
Labelled directed graph without multiple edges
We also represent undirected graphs as symmetric directed graphs.
type Graph = EdgeLabeledGraph () Source #
Directed graph without multiple edges
We also represent undirected graphs as symmetric directed graphs.
Conversion
Directed graphs
graphFromEdges :: HasCallStack => Int -> [Edge a] -> EdgeLabeledGraph a Source #
Construct a directed graph from edges.
If there are multiple edges with the same starting and ending vertexes, the last label is used.
graphFromEdgesWith :: HasCallStack => (a -> a -> a) -> Int -> [Edge a] -> EdgeLabeledGraph a Source #
Construct a directed graph from edges.
If there are multiple edges with the same starting and ending vertexes, the labels are combined using the given function.
graphToEdges :: EdgeLabeledGraph a -> [Edge a] Source #
Set of edges of directed graph
Undirected graphs
graphFromUnorderedEdges :: HasCallStack => Int -> [Edge a] -> EdgeLabeledGraph a Source #
Construct a symmetric directed graph from unordered edges.
If there are multiple edges with the same starting and ending vertexes, the last label is used.
graphFromUnorderedEdgesWith :: HasCallStack => (a -> a -> a) -> Int -> [Edge a] -> EdgeLabeledGraph a Source #
Construct a symmetric directed graph from unordered edges.
If there are multiple edges with the same starting and ending vertexes, the labels are combined using the given function.
graphToUnorderedEdges :: EdgeLabeledGraph a -> [Edge a] Source #
Set of edges of undirected graph represented as a symmetric directed graph.
Operations
converseGraph :: EdgeLabeledGraph a -> EdgeLabeledGraph a Source #
Converse of a graph.
It returns another directed graph on the same set of vertices with all of the edges reversed. This is also called transpose or reverse of a graph.
complementGraph :: EdgeLabeledGraph a -> EdgeLabeledGraph () Source #
Complement of a graph
Note that applying it to a graph with no self-loops results in a graph with self-loops on all vertices.
complementSimpleGraph :: EdgeLabeledGraph a -> EdgeLabeledGraph () Source #
Complement of a simple graph
It ignores self-loops in the input graph and also does not add self-loops to the output graph.
Properties
numVertexes :: EdgeLabeledGraph a -> Int Source #
Number of vertexes of a graph
isSimpleGraph :: EdgeLabeledGraph a -> Bool Source #
A graph is simple if it contains no self-loops.
isIndependentSet :: EdgeLabeledGraph a -> VertexSet -> Bool Source #
Deprecated: Use isIndependentSetOf instead
Alias of isIndependentSetOf
isIndependentSetOf :: VertexSet -> EdgeLabeledGraph a -> Bool Source #
An independent set of a graph is a set of vertices such that no two vertices in the set are adjacent.
This function ignores self-loops in the input graph.
isCliqueOf :: VertexSet -> EdgeLabeledGraph a -> Bool Source #
A clique of a graph is a subset of vertices such that every two distinct vertices in the clique are adjacent.