2010-05-17 5 views
0

J'écris un programme qui génère une représentation orthogonale d'un graphique planaire. Pour ce travail, j'utilise GHC 6.10.1. Mon code repose sur la bibliothèque FGL. Il utilise pour garder une structure graphique.aider à comprendre le comportement étrange dans un code paresseux

Récemment, j'ai trouvé une erreur que je ne peux pas expliquer. Si puis déposez le travail contextuel de mon programme:

 
main = let g = insEdge (0,1,()) $ buildGr [ ([], 0,(), []), ([], 1,(), []) ] 
      g' = delEdge (0,1) g 
     in if 1 `elem` suc g 0 
       then putStrLn "OK" 
       else putStrLn "ERROR " 

Ce programme doit imprimer « OK » mais le résultat est « erreur »

Voici plus de détails. Fonction prepareData possède un graphique avec des bords d'aide. Data BlockScheme conserve également les leurs dans la liste cyclesInfoBS. Ces bords sont requis un algorithme de la fonction dualGraph.

Fonction prepareG crée un nouveau graphique à partir de la suppression de ces arêtes. Et la valeur de la variable embeddedBSG doit être identique partout.

Mais une erreur se produit lorsque dualGraph fonctionne. Traçage à l'intérieur dit que le graphique n'a pas de bord d'aide (2,1) mais avant l'appel de dualGraph son argument graphique a des bords d'aide. Le module de dualGraph n'a ni delEdge ni delEdge, ni delNodes ni delNode et n'appelle pas une fonction qui devait le faire. Le module de dualGraph lit uniquement la variable graphique.

Si le code de commentaire supprime les bords d'aide, ils restent.

l'état du graphe avant dualGraph:

 
__+embeddedBSG = 
0:NodeLabel {typeLabel = Terminator, sizeLabel = (30.0,10.0), textLabel =(), foregroundLabel = 0x000000, backgroundLabel = 0xFFFFFF}->[((1,3),3)] 
1:NodeLabel {typeLabel = Terminator, sizeLabel = (30.0,10.0), textLabel =(), foregroundLabel = 0x000000, backgroundLabel = 0xFFFFFF}->[] 
2:NodeLabel {typeLabel = HelpNode, sizeLabel = (0.0,0.0), textLabel =(), foregroundLabel = 0x000000, backgroundLabel = 0xFFFFFF}->[((2,0),1)] 
3:NodeLabel {typeLabel = IfWhBlock, sizeLabel = (30.0,20.0), textLabel =(), foregroundLabel = 0x000000, backgroundLabel = 0xFFFFFF}->[((1,0),2),((2,2),1),((0,1),4)] 
4:NodeLabel {typeLabel = OpBlock, sizeLabel = (30.0,20.0), textLabel =(), foregroundLabel = 0x000000, backgroundLabel = 0xFFFFFF}->[((0,1),2)] 

l'état du graphe dans le module DualGraph:

 
0:(0.0,NodeLabel {typeLabel = Terminator, sizeLabel = (30.0,10.0), textLabel =(), foregroundLabel = 0x000000, backgroundLabel = 0xFFFFFF})->[((1,3),3)] 
1:(30.0,NodeLabel {typeLabel = Terminator, sizeLabel = (30.0,10.0), textLabel =(), foregroundLabel = 0x000000, backgroundLabel = 0xFFFFFF})->[] 
2:(45.0,NodeLabel {typeLabel = HelpNode, sizeLabel = (0.0,0.0), textLabel =(), foregroundLabel = 0x000000, backgroundLabel = 0xFFFFFF})->[] 
3:(15.0,NodeLabel {typeLabel = IfWhBlock, sizeLabel = (30.0,20.0), textLabel =(), foregroundLabel = 0x000000, backgroundLabel = 0xFFFFFF})->[((2,2),1),((1,0),2),((0,1),4)] 
4:(35.0,NodeLabel {typeLabel = OpBlock, sizeLabel = (30.0,20.0), textLabel =(), foregroundLabel = 0x000000, backgroundLabel = 0xFFFFFF})->[((0,1),2)] 
allEdges: = [(OutEdge,(2,(0,1))),(InEdge,(3,(0,1)))] 

arbre 2 du deuxième état n'a pas encore reçu de bords sortants.

Il existe un endroit où l'erreur est détectée dans la fonction lSortSuc dans DualGraph. LSortSuc vertexId graph = .... Il nécessite un sommet avec vertexId a au moins 1 bord entrant et 1 sortant ou il est nœud de puits. Le noeud récepteur est 1 dans ce cas.

Ensuite, On peut supposer que lSortSuc est appelé quelque part encore pour le graphique sans bords d'aide pour le nœud 2. Mais ce n'est pas vrai.

Quelqu'un a-t-il des idées? Que puis-je faire?

 
type BlockSchemeGraph = Gr NodeLabel() 

data CycleInfo = 
    CycleInfo { 
     reversedEdge :: Edge , 
     helpEdge :: Edge 
    } deriving (Show, Eq) 

data BlockScheme = BlockScheme { graphBS :: BlockSchemeGraph, 
           cyclesInfoBS :: [ CycleInfo ], 
           generalSchemeOptionsBS ::(), 
           backBonesBS :: [ [ Node ] ] 
           } deriving (Show, Eq) 


prepareData bs = 
let bsg = graphBS bs 
    [ sink, source ] = map head $ pam bsg [ getSinks, getSources ] 
    [ helpNode ] = newNodes 1 bsg 
    helpEdges = [ (source,helpNode), (helpNode, sink) ] 
    bsg' = insEdges [ (a,b,()) | (a,b) (l, 0.0)) 
          -- here help edges are deleted 
       $ foldr (\cinf g -> delEdge (helpEdge cinf) g) 
         (trace ("\n\nembG = " ++ show embG) embG) 
         cyclesInfo 
    f (v, height) g = 
     let fsuc (w, (order, weight)) g = 
       setELabel' (v,w) (order, weight + height/2) g 
      fpre (w, (order, weight)) g = 
       setELabel' (w,v) (order, weight + height/2) g 
      g' = foldr fsuc g $ lsuc g v 
     in foldr fpre g' $ lpre g' v 
    in emap (\(order, weight) -> (order, {-round-} weight)) 
      . foldr f embG' 
      . map (\n -> (n, snd . sizeLabel $ getVLabel n embG)) 
      $ nodes embG 

----------------------------------------------------------------------- 
{-# LANGUAGE ScopedTypeVariables #-} 
module GraphVisualiser 
#if defined(MYDEBUG) 
#else 
(visualiseScheme, BlockSchemeImage) 
#endif 
    where 

import SimpleUtil (map2,swap,pam, vopt, compareDouble) 
import Data.Maybe (fromJust,isJust) 
import Data.List (foldl',find, nubBy, deleteFirstsBy, maximumBy) 
import qualified Data.Map as Map 
import SchemeCompiler 
import InductivePlus 
import GraphEmbedder 
import DualGraph 
import TopologicalNumbering 
import Text.Printf (printf) 
import Debug.Trace 

type NodePosition = (Double,Double) 
type EdgePosition = [ NodePosition ] 

type BSIG = Gr (NodePosition, NodeLabel) EdgePosition 
newtype BlockSchemeImage = BlkScmImg BSIG deriving Eq 

getWeight = fst 
visualiseScheme :: BlockScheme -> BlockSchemeImage 
visualiseScheme bs = 
let (numEmbBsg, numDualBsg, emf, nmf, source, sink) = prepareData bs 

    xCoords = map (calcXForBackBone (numEmbBsg, numDualBsg, emf, nmf)) $ backBonesBS bs 
    calcedNodes = calcNodePositions numEmbBsg numDualBsg nmf emf source sink xCoords 
    calcedEdges = calcEdgePositions numEmbBsg numDualBsg nmf emf source sink calcedNodes xCoords 
    scaledG = scaleGraph calcedEdges 
    -- 
    g' = reverseFeedBacks scaledG $ cyclesInfoBS bs 
    in BlkScmImg g' -- -- calcedEdges 

calcXForBackBone (numEmbBsg, numDualBsg, emf, nmf) idsOfNodes = 
-- 
let (_, (xleft, xright)) = 
     maximumBy (\ (v1, (xleft1, xright1)) (v2, (xleft2, xright2)) -> 
         compare (xright1 - xleft1) (xright2 - xleft2)) 
        $ map (\ v -> (v, fidsToWeights numDualBsg $ Map.lookup v nmf)) 
         idsOfNodes 
    in ((xright + xleft)/2.0 , idsOfNodes) 
-- g :: Gr (NodePosition, NodeLabel) [ NodePositions ] 
reverseFeedBacks g cyclesInfo = foldr fEdge g cyclesInfo 
where fEdge cinfo g = 
     let elbl = getELabel e g 
      e = reversedEdge cinfo 
      (v,w) = e 
      g' = delEdge e g 
     in insEdge (w,v, reverse elbl) g' 
calcEdgePositions numEmbBsg numDualBsg nmf emf source sink calcedNodes backBones = 
let fEdge [email protected](v,w) g = 
     let xOfe = case find (\ (x, lst) -> 
           if v `elem` lst && w `elem` lst 
            then True 
            else False 
          ) backBones of 
        Nothing -> halfSumEdge numDualBsg emf e 
        Just (x,_) -> x 
      [startY, endY] = map (\n -> getWeight $ getVLabel n numEmbBsg) [ v, w ] 
      coords = [ (xOfe, startY), (xOfe, endY) ] 
      g' = setELabel' (v,w) coords g 
     in trace ("\n\ncoords = " ++ show coords ++ "\ncalc edge " ++ show (v,w) ++ "\nemf = " 
              ++ show emf ++ "\nnmf = " ++ show nmf 
              ++ "\nnumDualBsg = " ++ show numDualBsg 
              ++ "\nnumEmbBsg = " ++ show numEmbBsg) 
       g' 
    outEdgesOfSource = map fst $ lSortSuc numEmbBsg source 
    inEdgesOfSink = map fst $ lSortPre numEmbBsg sink 
    fixFouthEdgeLbl v lst yModifier g = 
     case lst of 
       [ _ ] -> g 
       [ _, _ ] -> (trace "\nFixFouth\n" g) 
       [ _, _, _ ] -> g 
       [ _, _, _, w ] -> 
       let [ (x1,y1), p2 ] = getELabel (v,w) g 
        (xv, yv) = fst $ getVLabel v g 
       in setELabel' (v,w) 
           [ (xv, yModifier y1), (x1, yModifier y1), p2 ] 
           g 
       _ -> error $ "visualiseScheme.fixFouthEdgeLbl: lst has more than 4 edges!!!\n" 
          ++ show lst 
    calcedUsualEdges = foldr fEdge 
           calcedNodes 
           $ edges calcedNodes 
    calcedAll = fixFouthEdgeLbl sink inEdgesOfSink (+1) 
        $ fixFouthEdgeLbl source outEdgesOfSource (\a -> a - 1) calcedUsualEdges 

    in trace ("\ncalcedAll = " ++ show calcedAll) calcedAll 

scaleGraph g = 
let 
    factor = 3.0 
    marginLT = 10 
    modifyCoord = (marginLT +) . (*factor) -- marginLeft и marginTop 
    modifyCoords a = map2 modifyCoord . vopt (-) a $ minCoordinates g 
    in emap (map modifyCoords) 
       $ nmap (\(coords, lbl) -> (modifyCoords coords, lbl)) 
         g 
prepareData bs = 
let bsg = graphBS bs 
    [ sink, source ] = map head $ pam bsg [ getSinks, getSources ] 
    [ helpNode ] = newNodes 1 bsg 
    helpEdges = [ (source,helpNode), (helpNode, sink) ] 
    bsg' = insEdges [ (a,b,()) | (a,b) (l, 0.0)) 
       $ foldr (\cinf g -> {- g) --- -} delEdge (helpEdge cinf) g) 
         (trace ("\n\nembG = " ++ show embG) embG) 
         cyclesInfo 
    f (v, height) g = 
     let fsuc (w, (order, weight)) g = 
       setELabel' (v,w) (order, weight + height/2) g 
      fpre (w, (order, weight)) g = 
       setELabel' (w,v) (order, weight + height/2) g 
      g' = foldr fsuc g $ lsuc g v 
     in foldr fpre g' $ lpre g' v 
    in emap (\(order, weight) -> (order, {-round-} weight)) 
      . foldr f embG' 
      . map (\n -> (n, snd . sizeLabel $ getVLabel n embG)) 
      $ nodes embG 

prepareDualG dg g = 
let dg' = emap (\lbl -> (lbl, 0.0)) dg 
    widthElement v sucOrPre = 
     let width = fst . sizeLabel $ getVLabel v g 
     in width/(fromIntegral . length $ sucOrPre g v) 
    -- node is face   
    fNodes v (dg :: Gr Face (Edge, Double))= 
     let fEdge (w, ([email protected](origV, origW), weight)) dg = 
      let wV = widthElement origV lsuc 
       wW = widthElement origW lpre 
      in setELabel' (v,w) (orig, weight + wV + wW) dg 
      outgoing :: [ (Node, (Edge, Double)) ] 
      outgoing = lsuc dg v 
     in foldr fEdge dg outgoing 
    in emap (\(e, weight) -> (e, {-round-} weight)) 
      . foldr fNodes dg' 
      $ nodes dg 

calcNodePositions numEmbBsg numDualBsg nmf emf source sink backBones {- :: [ (Double, [ Node ]) -} = 
let fNode v (g :: Gr (NodePosition, NodeLabel) [ NodePosition ]) = 
     if v == source -- s 
     then calcSorT v id g lSortSuc numEmbBsg numDualBsg emf backBones 
     else if v == sink -- t 
       then calcSorT v swap g lSortPre numEmbBsg numDualBsg emf backBones 
       else let vlbl = getVLabel v numEmbBsg 
          xCoord = case find (\ (x, lst) -> 
               if v `elem` lst 
                then True 
                else False 
              ) backBones of 
            Nothing -> halfSumNode numDualBsg nmf v 
            Just (x,_) -> x 
         in setVLabel' v ((xCoord, getWeight vlbl), snd vlbl) g 
    g' :: Gr (NodePosition, NodeLabel) [ NodePosition ] 
    g' = emap (\_ -> []) $ nmap (\(weight, lbl) -> ((0.0,0.0), lbl)) 
            numEmbBsg 
    result :: Gr (NodePosition, NodeLabel) [ NodePosition ]      
    result = foldr fNode 
        g' 
        $ nodes numEmbBsg 
    in result 

calcSorT v selector (g :: Gr (NodePosition, NodeLabel) [ NodePosition ]) edgeSelector numEmbBsg numDualBsg emf backBones = 
    let calcSTDegree4 w = 
     let (weight , vlbl) = getVLabel v numEmbBsg 
     in setVLabel' v ((halfSumEdge numDualBsg emf $ selector (v,w) , 
          weight), 
         vlbl) 
         g 
    in case map fst $ edgeSelector numEmbBsg v of 
      [ ] -> error $ "calcSorT: node " ++ show v 
         ++ " hasn't got any suc edges!\nGraph:\n" ++ show g 
         ++ "\nnumEmbBsg = \n" ++ show numEmbBsg 

      [ w ] -> let (weight, vlbl) = getVLabel v numEmbBsg 
         xCoord = case find (\ (x, lst) -> 
               if v `elem` lst 
               then True 
               else False 
             ) backBones of 
            Nothing -> halfSumEdge numDualBsg emf $ selector (v,w) 
              -----halfSumNode numDualBsg nmf v 
            Just (x,_) -> x 
        in setVLabel' v ((xCoord , weight), vlbl) 
           g 
      [ w1, _ ] -> let (weight , vlbl) = getVLabel v numEmbBsg 
         in setVLabel' v ((snd . fidsToWeights numDualBsg 
               $ Map.lookup (selector (v, w1)) emf, 
              weight), 
              vlbl 
             ) 
             g 
      [ _, w, _ ] -> calcSTDegree4 w 
      [ _, w, _, _ ] -> calcSTDegree4 w 
      moreEdges -> error $ "calcSorT: node " ++ show v ++ "has got too may edges!:\n" 
           ++ show moreEdges ++ "\nGraph:" ++ show g 
           ++ "\nnumEmbBsg = " ++ show numEmbBsg 

--- fidsToWeights :: Maybe EdgeFaces -> NodePosition 
fidsToWeights numDualBsg = map2 (\fid -> getWeight $ getVLabel fid numDualBsg) . fromJust 

halfSum numDualBsg fids = (uncurry (+) (fidsToWeights numDualBsg fids)/2.0) :: Double 
halfSumNode numDualBsg nmf v = (halfSum numDualBsg) $ Map.lookup v nmf      
halfSumEdge numDualBsg emf e = (halfSum numDualBsg) $ Map.lookup e emf 


----------------------------------------------------------------------- 

module DualGraph 
#if defined(MYDEBUG) 
#else 
(dualGraph, Face(..), leftFace, rightFace, FaceId, EdgeFaces, EdgeMapFaces,NodeMapFaces, DualGraph, lSortSuc, lSortPre) 
#endif 
     where 
import qualified Data.Set as Set 
import qualified Data.Map as Map 
import Data.Maybe (fromJust,isJust) 
import SimpleUtil (apa,swap,map2) 
import Data.List (foldl', sortBy, find) 
import InductivePlus 
import GraphEmbedder 
import Debug.Trace 

type FaceId = Int 
type EdgeFaces = (FaceId, FaceId) 
type EdgeMapFaces = Map.Map Edge EdgeFaces 

type NodeMapFaces = Map.Map Node EdgeFaces 

leftFace :: EdgeFaces -> FaceId 
leftFace = fst 
rightFace :: EdgeFaces -> FaceId 
rightFace = snd 

data Face = Face { sourceNode, sinkNode :: Node, 
        leftContour, rightContour :: Set.Set Edge --- [ Node ], 
       } | 
      OuterFace { 
         leftContour, rightContour :: Set.Set Edge --- [ Node ], 
         } deriving (Show, Eq) 

nodePathToEdgePath :: Ord a => [ a ] -> Set.Set (a,a) 
nodePathToEdgePath (h:rest) = Set.fromList . snd 
           $ foldl' (\ (current,result) next -> 
             (next, (current, next) : result)) 
             (h, []) 
             rest 

newFace src leftC rightC = 
    Face { sourceNode = src, 
     sinkNode = last leftC, 
     leftContour = nodePathToEdgePath $ src : leftC, 
     rightContour = nodePathToEdgePath $ src : rightC -- , 
     } 

newOuterFace embG edgeSelector slotModifier = 
case filter (\v -> null $ lpre embG v) $ nodes embG of 
    [] -> error $ "newOuterFace: the graph hasn't got any source vertex\n" 
       ++ show embG 
    [ v ] -> slotModifier emptyOuterFace 
         . nodePathToEdgePath 
         $ findContour v 
    sourceVertexes -> 
    error $ "newOuterFace: the graph has got more than one source vertex:" 
      ++ show sourceVertexes 
      ++ "\nThe Graph:\n" ++ show embG 
where 
    emptyOuterFace = OuterFace { leftContour = Set.empty, 
           rightContour = Set.empty 
          } 
    findContour v = 
    case lSortSuc embG v of 
    [] -> [ v ] 
    someEdges -> v : (findContour . fst $ edgeSelector someEdges) 

setRightContour face con = face { rightContour = con } 
setLeftContour face con = face { leftContour = con } 


type DualGraph = Gr Face Edge 

dualGraph :: BlockSchemeEmbeddedGraph -> (DualGraph, EdgeMapFaces, NodeMapFaces) 

checkm msg g = if 1 `notElem` suc g 2 
        then error $ "\ncheckm: " ++ msg ++ "\nthe G = " ++ show g 
        else trace ("\n\nsuc g 2 = " ++ show (suc g 2)) g 

dualGraph embGr = 
let embG = checkm "dualGraph: " embGr 
    usualFaces = snd . foldr (findFaces embG) 
           (2, buildGr []) --- Map.empty) 
           $ nodes embG 

    sFace = newOuterFace embG head setRightContour 
    tFace = newOuterFace embG last setLeftContour 
    allFaces = insNodes [ (0,sFace), (1,tFace) ] usualFaces 
    allNodes = map (\n -> (n, getVLabel n allFaces)) 
        $ nodes allFaces 
    linkedFaces = foldr linkage 
         allFaces 
         [ (f1, f2) | [email protected](fid1,_) fid1 
         ] 
    emf = foldr (\(fid,f) m -> let comb fun conSel m = Set.fold (\e m -> Map.insertWith fun 

       e 

       (fid,fid) 

       m) 
                   m 
                   $ conSel f 
           in comb (\ (_,r) (l,_) -> (l,r)) 
             leftContour 
             $ comb (\ (l,_) (_,r) -> (l,r)) 
               rightContour 
               m 
       ) 
       Map.empty 
       allNodes 

    fNMF n m = let (lFace,rFace) = case lSortSuc embG n of 
          [] -> let ls = lSortPre embG n 
            lFace = leftFace 
               . fromJust 
               $ Map.lookup (fst $ head ls, n) -- last ls, n) 
                  emf 
            rFace = rightFace 
               . fromJust 
               $ Map.lookup (fst $ last ls, n) -- head ls, n) 
                  emf 
            in (lFace, rFace) 
          ls -> let lFace = leftFace 
               . fromJust 
               $ Map.lookup (n, fst $ head ls) 
                  emf 
             rFace = rightFace 
               . fromJust 
               $ Map.lookup (n, fst $ last ls) 
                  emf 
            in (lFace, rFace) 
       in Map.insert n (lFace, rFace) m 
    nmf = foldr fNMF Map.empty $ nodes embG 
    in trace ("\nDualGrapn: (linkedFaces, emf, nmf) \n" ++ show (linkedFaces, emf, nmf)) (linkedFaces, emf, nmf) 


findFaces embG v st = 
    case map fst $ lSortSuc (checkm "findFaces: " embG) v of 
    [] -> st -- вершина не может образовать грань 
    [_] -> st 
    (firstOut:outgoing) -> snd $ foldl' (findFace embG v) 
             (firstOut,st) 
             outgoing 

data EdgeType = InEdge | OutEdge deriving (Show,Eq) 

lSortEdges gren v = 
let g = trace ("\nlSortEdges: g = " ++ show gren) (checkm ("lSortEdges: v = " ++ show v)gren) 
    getEdgeNumber (OutEdge, (_, (n,_))) = n 
    getEdgeNumber (InEdge, (_, (_,n))) = n 

    oute = lsuc g v 
    ine = lpre g v 
    allEdges = sortBy (apa compare getEdgeNumber) 
       $ concat [ map (\lbl -> (OutEdge, lbl)) oute, 
          map (\lbl -> (InEdge, lbl)) ine ] 

    cAllEdges = cycle allEdges 

    zeroEdge = head (trace ("allEdges: = " ++ show allEdges) allEdges) 
    spanE e = span ((e ==) . fst) 
    outEdges = case fst zeroEdge of 

        OutEdge -> fst . spanE OutEdge 
           . snd . spanE InEdge 
           . snd $ spanE OutEdge cAllEdges 
        _  -> fst . spanE OutEdge . snd $ spanE InEdge cAllEdges 
    inEdges = case fst zeroEdge of 
        InEdge -> fst . spanE InEdge 
           . snd . spanE OutEdge 
           . snd $ spanE InEdge cAllEdges 
        _  -> fst . spanE InEdge . snd $ spanE OutEdge cAllEdges 

    in if null ine || null oute 
     then let [ sv ] = getSources g 
       findContour prew w = 
        if w /= v 
         then findContour (Just w) . fst . head $ (trace ("\n\nlSortSuc g w = " ++ show w 

    ++ " lsortSuc = " ++ show (lSortSuc g w)) 
                     (lSortSuc g w)) 
         else prew 
       wOfFirstEdge = fromJust $ findContour Nothing sv 
       sine = sortBy (apa notCompare (snd . snd)) ine 
       (beforeW, withW) = span ((wOfFirstEdge /=) . fst) sine 
       in (sortBy (apa compare (fst . snd)) oute, 
        withW ++ sortBy (apa compare (snd . snd)) beforeW 
       ) 
     else map2 (map snd) 
        (outEdges, inEdges) 
where notCompare a b = case compare a b of 
          EQ -> EQ 
          LT -> GT 
          GT -> LT 

lSortPre g v = let res = snd $ lSortEdges g v in 
        trace ("\n\nlSortPre(" ++ show v ++ ") = " ++ show res) res 
lSortSuc g v = let res = fst $ lSortEdges g v in 
        trace ("\n\nlSortSuc(" ++ show v ++ ", g= " ++ show g ++ ") = " ++ show res) res 

findFace embG v (wi, [email protected] (freeFID, mf)) wj = 
    let findContour v w pStop selectEdge = 
     let preEdges = lSortPre (checkm ("findFace: v = " ++ show v ++ " wi = " 
              ++ show wi ++ " v = " ++ show v 
              ++ " w = " ++ show w ++ " wj = " 
              ++ show wj) embG) w 
      sucEdges = lSortSuc embG w 
      nextW = selectEdge sucEdges 
      res = if null sucEdges || (not (null preEdges) && pStop v preEdges) -- w is t-node 
         then [ w ] 
         else w : findContour w nextW pStop selectEdge 
      in trace ("findContour: v = " ++ show v ++ " w = " ++ show w ++ " suc = " ++ show sucEdges ++ " pre = " ++ show preEdges) 
        res 

     leftCon = findContour v wi 
          (\v -> (v /=) . fst . head) -- last) 
          (fst . last) 
     rightCon = findContour v wj 
          (\v -> (v /=) . fst . last) -- head) 
          (fst . head) 
     tr = trace ("\nfindFace v = " ++ show v ++ " wi = " ++ show wi ++ " wj = " ++ show wj ++ " freeFID = " ++ show freeFID) 
       leftCon 
     res = (wj, (freeFID + 1, 
        insNode (freeFID, newFace v tr rightCon) mf 
       ) 
      ) 
    in trace ("\nfindFace: " ++ show res) res 

linkage ((fid1, f1), (fid2, f2)) g = 
let getC f = (leftContour f, rightContour f) 
    [ (lc1, rc1), (lc2, rc2) ] = map getC [f1,f2] 
    foldIntersection res selector = 
     let (ff1, ff2) = selector (fid1, fid2) in 
      foldr (\[email protected](v,w) g -> insEdge (ff1,ff2,e) g) 
       g 
       res 
    in case Set.toList $ lc1 `Set.intersection` rc2 of 
     [] -> 
     case Set.toList $ rc1 `Set.intersection` lc2 of 
      [] -> g 
      -- из f2 в f1 
      res  -> foldIntersection res id 
     res  -> foldIntersection res swap 

Répondre

1

Dans votre exemple:

main = let g = insEdge (0,1,()) $ buildGr [ ([], 0,(), []), ([], 1,(), []) ] 
      g' = delEdge (0,1) g 
     in if 1 `elem` suc g 0 
       then putStrLn "OK" 
       else putStrLn "ERROR " 

la g' variable est jamais utilisé. L'expression suc g 0 doit-elle être suc g' 0? Il me semble que cela devrait faire imprimer OK ...

+0

Je suppose que 'g' contient le bord" 0-> 1 ", et' g'' est l'endroit où il a été enlevé. Je suppose que 'suc g 0' génère une liste de nœuds qui est directement accessible depuis le nœud" 0 "(il y a le bord" 0-> x "). Donc, il devrait produire la liste '[1]' et imprimer "OK" (ce qui est vu maintenant). l'ajout de guillemets à 'g' le fera imprimer" ERROR ". – ony

+0

@ony - Vous avez raison, les erreurs/erreurs sont inverses. Je suppose que je faisais confiance à la question quand il dit que le résultat est ERREUR!Je suppose que nous avons besoin de plus de clarification de l'interrogateur sur ce qu'il veut dire exactement :-) – psmears

+0

Je suis d'accord mon exemple dans la question de tête n'est pas clair. Parce que g et g 'doivent être utilisés alors pour construire la représentation visuelle. E.i. g et g 'sont des arguments une fonction:

visualRepres :: WeightedDualGraph -> WeightedGraph -> VisualRepresentation --------------- rewritten demo: main = let g = insEdge (0,1,()) $ buildGr [ ([], 0,(), []), ([], 1,(), []) ] g' = delEdge (0,1) g useBoth g1 g2 = edges g1 ++ edges g2 in putStrLn $ "Unioned edges: " ++ show (useBoth g g') 
Il imprime simplement "Les bords unis: []" –

Questions connexes