Grafos (empty) → 0.1.0.0

raw patch · 7 files changed

+236/−0 lines, 7 filesdep +basesetup-changed

Dependencies added: base

Files

ChangeLog.md +5/−0
Grafos.cabal +24/−0
Graph.hs +65/−0
LICENSE +30/−0
Set.hs +64/−0
Setup.hs +2/−0
ValGraph.hs +46/−0

+ ChangeLog.md view

@@ -0,0 +1,5 @@+# Revision history for Grafos
+
+## 0.1.0.0  -- YYYY-mm-dd
+
+* First version. Released on an unsuspecting world.

+ Grafos.cabal view

@@ -0,0 +1,24 @@+-- Initial Grafos.cabal generated by cabal init.  For further 
+-- documentation, see http://haskell.org/cabal/users-guide/
+
+name:                Grafos
+version:             0.1.0.0
+synopsis:            Grafos Haskell
+-- description:         
+license:             BSD3
+license-file:        LICENSE
+author:              jppianta83
+maintainer:          porcoaranha83@gmail.com
+-- copyright:           
+-- category:            
+build-type:          Simple
+extra-source-files:  ChangeLog.md
+cabal-version:       >=1.10
+
+library
+  exposed-modules:     ValGraph, Set, Graph
+  -- other-modules:       
+  -- other-extensions:    
+  build-depends:       base >=4.9 && <4.10
+  -- hs-source-dirs:      
+  default-language:    Haskell2010

+ Graph.hs view

@@ -0,0 +1,65 @@+module Graph (
+   Graph,
+   graph,
+   addVertice,
+   addVertices,
+   addEdge,
+   addEdges
+    ) where
+
+import Set
+
+type Graph a = (Set a, Set (a, a))
+
+graph::Graph a
+graph = (eset, eset)
+
+addVertice::(Eq a, Ord a)=>a->Graph a->Graph a
+addVertice x (n, y) = (add x n, y)
+
+addEdge::(Eq a, Ord a)=>(a,a)->Graph a->Graph a
+addEdge (x, v) (n, y) = if exists x n && exists v n then (n, add (x,v) y) else (n,y)
+
+removeEdge::(Eq a)=>(a,a)->Graph a->Graph a
+removeEdge x (n, e) = (n, remove x e) 
+
+addVertices::(Eq a, Ord a)=>[a]->Graph a->Graph a
+addVertices [] (x,y) = (x,y)
+addVertices (x:xs) (n, y) = addVertices xs (addVertice x (n,y))
+
+addEdges::(Eq a, Ord a)=>[(a,a)]->Graph a->Graph a
+addEdges [] (x,y) = (x,y)
+addEdges (x:xs) (n, v) = addEdges xs (addEdge x (n,v))
+
+removeEdges::(Eq a, Ord a)=>[(a,a)]->Graph a->Graph a
+removeEdges [] (x,y) = (x,y)
+removeEdges (x:xs) (n, v) = removeEdges xs (removeEdge x (n,v))
+
+sEntrada2::(Eq a, Ord a)=>Graph a->Set a
+sEntrada2 (Set x, Set []) = Set []
+sEntrada2 (Set [], Set x) = Set []
+sEntrada2 (Set (x:xs), Set (y:ys)) = if exists (snd y) (Set (x:xs)) then add (snd y) (sEntrada2 (Set (x:xs), Set ys)) else sEntrada2 (Set (x:xs), Set ys)
+
+sEntrada::(Eq a, Ord a)=>Graph a->Set a
+sEntrada x = dif (fst x) (sEntrada2 x)
+
+ord::(Eq a, Ord a)=>Graph a->[a]
+ord x = ord2 x (sEntrada x) where
+ord2::(Eq a, Ord a)=>Graph a->Set a->[a]
+ord2 x (Set []) = []
+ord2 x (Set (y:ys)) = [y]++(ord2 (removeEdges (to x y) x) (remove y (ord3 x (to x y) (Set (y:ys)))))
+
+to::(Eq a)=>Graph a->a->[(a,a)]
+to (x, Set []) y = []
+to (x, Set (y:ys)) v = if v==(fst y) then [y]++(to (x, Set ys) v) else to (x, Set ys) v
+
+ord3::(Eq a, Ord a)=>Graph a->[(a,a)]->Set a->Set a
+ord3 x [] v = v
+ord3 (x, v) (y:ys) k = if exists (snd y) (sEntrada (removeEdge y (x, v))) then (ord3 (removeEdge y (x, v)) ys (addr (snd y) k)) else ord3 (removeEdge y (x, v)) ys k
+
+
+g = addEdges [(1,2),(1,3),(2,4),(2,6),(3,2),(3,4),(3,6),(3,8),(4,5),(4,6),(5,7),(6,8),(6,9),(6,5),(6,9),(7,9),(8,7),(8,9)] $ addVertices [1,2,3,4,5,6,7,8,9] $ graph
+
+
+
+

+ LICENSE view

@@ -0,0 +1,30 @@+Copyright (c) 2016, jppianta83
+
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are met:
+
+    * Redistributions of source code must retain the above copyright
+      notice, this list of conditions and the following disclaimer.
+
+    * Redistributions in binary form must reproduce the above
+      copyright notice, this list of conditions and the following
+      disclaimer in the documentation and/or other materials provided
+      with the distribution.
+
+    * Neither the name of jppianta83 nor the names of other
+      contributors may be used to endorse or promote products derived
+      from this software without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

+ Set.hs view

@@ -0,0 +1,64 @@+module Set (
+    Set (Set),
+    eset,
+    set, 
+    add,
+    addr,
+    remove,
+    union,
+    inter,
+    dif,
+    isEmpty,
+    exists
+) where 
+
+data Set a = Set [a]
+
+instance (Show a)=>Show (Set a) where
+    show (Set a)= show a
+
+set::a->Set a
+set x = Set [x]
+
+eset::Set a
+eset = Set []
+
+addl::a->Set a->Set a
+addl x (Set []) = Set [x]
+addl x (Set (y:ys)) = Set ([x]++(y:ys))
+
+addr::a->Set a->Set a
+addr x (Set []) = Set [x]
+addr x (Set (y:ys)) = Set ((y:ys)++[x])
+
+add::(Eq a, Ord a)=>a->Set a->Set a
+add x (Set []) = Set [x]
+add y (Set (x:xs)) = if x==y then Set (x:xs) else if x<y then addl x (add y (Set xs)) else Set ([y]++(x:xs))
+
+union::(Eq a, Ord a)=>Set a->Set a->Set a
+union (Set x) (Set []) = Set x
+union (Set []) (Set y) = Set y
+union (Set (x:xs)) (Set (y:ys)) = if x==y then union (Set (x:xs)) (Set ys) else if x<y then addl x (union (Set xs) (Set (y:ys))) else addl y (union (Set (x:xs)) (Set ys))
+
+
+remove::(Eq a)=>a->Set a->Set a
+remove x (Set []) = Set []
+remove y (Set (x:xs)) = if x==y then Set xs else addl x (remove y (Set xs))
+
+isEmpty::Set a->Bool
+isEmpty (Set []) = True
+isEmpty (Set (x:xs)) = False
+
+exists::(Eq a)=>a->Set a->Bool
+exists x (Set []) = False
+exists x (Set (y:ys)) = if x==y then True else exists x (Set ys)
+
+inter::(Eq a, Ord a)=>Set a->Set a->Set a
+inter (Set []) x = Set []
+inter x (Set []) = Set []
+inter (Set (x:xs)) (Set (y:ys)) = if x==y then addl x (inter (Set xs) (Set ys)) else if x<y then inter (Set xs) (Set (y:ys)) else inter (Set (x:xs)) (Set ys)
+
+dif::(Eq a, Ord a)=>Set a->Set a->Set a
+dif (Set x) (Set []) = Set x
+dif (Set []) x = Set []
+dif (Set (x:xs)) (Set (y:ys)) = if x==y then dif (Set xs) (Set ys) else if x<y then addl x (dif (Set xs) (Set (y:ys))) else addl x (dif (Set (x:xs)) (Set ys))

+ Setup.hs view

@@ -0,0 +1,2 @@+import Distribution.Simple
+main = defaultMain

+ ValGraph.hs view

@@ -0,0 +1,46 @@+module ValGraph (
+    ValGraph,
+    valgraph,
+    addVertice,
+    addVertices,
+    addEdge,
+    addEdges
+) where
+
+import Set
+
+type ValGraph a b = (Set a, Set (a, a, b))
+
+
+-----------------------Construtor----------------------------------
+
+valgraph::ValGraph a b
+valgraph = (eset, eset)
+
+-------------------------------------------------------------------
+
+-----------------------AddVerticesOps------------------------------
+
+addVertice::(Eq a, Ord a)=>a -> ValGraph a b -> ValGraph a b
+addVertice x (y, z) = (add x y, z)
+
+addVertices::(Eq a, Ord a)=>[a] -> ValGraph a b -> ValGraph a b
+addVertices [] x = x
+addVertices (x:xs) (y, z) = addVertices xs (addVertice x (y, z))  
+
+-------------------------------------------------------------------
+
+-----------------------AddEdgesOps---------------------------------
+
+addEdge::(Eq a, Eq b, Ord a, Ord b)=>(a,a,b) -> ValGraph a b -> ValGraph a b
+addEdge (m, n, o) (x, y) = if (exists m x) && (exists n x) then (x, add (m,n,o) y) else (x,y)
+
+addEdges::(Eq a, Eq b, Ord a, Ord b)=>[(a,a,b)] -> ValGraph a b -> ValGraph a b
+addEdges [] x = x
+addEdges (x:xs) y = addEdges xs (addEdge x y)
+
+-------------------------------------------------------------------
+
+-----------------------TESTE---------------------------------------
+
+g = addEdges [(1,2,10),(1,3,10),(2,4,10),(2,6,10),(3,2,10),(3,4,10),(3,6,10),(3,8,10),(4,5,10),(4,6,10),(5,7,10),(6,8,10),(6,9,10),(6,5,10),(6,9,10),(7,9,10),(8,7,10),(8,9,10)] $ addVertices [1,2,3,4,5,6,7,8,9] $ valgraph