C:/CVUT/diplomka/Automata_editor/sources/drawAlgorithm.cpp

Go to the documentation of this file.

#include "constants.h"

#include "drawAlgorithm.h"
#include "editor.h"
#include "commands.h"
#include "stateManager.h"
#include "transitionManager.h"
#include "state.h"
#include "oneStateTransition.h"
#include "twoStatesTransition.h"
#include "automataCreator.h"
#include "transition.h"

#include "iautomaton.h"
#include "itransition.h"
#include "istate.h"

#include <QSharedPointer>
#include <QPoint>
#include <QUndoCommand>
#include <QQueue>
#include <QStack>
#include <QList>

#include <limits>

#include <queue> // priority queue
#include <vector>
#include <stack>
using namespace std;

#ifdef TESTING_DRAWING
#   define DBGLOG_DRAW(x) DBGLOG_("DRAWING", x)
#else
#   define DBGLOG_DRAW(x)
#endif

//<-- BaseDrawAlgorithm --------------------------------------------------------------------

const int BaseDrawAlgorithm::X_STEP = GRID_STEP*3;
const int BaseDrawAlgorithm::Y_STEP = GRID_STEP*3;

State* createState(Editor *editor, const QPoint &pos,
                   const QSharedPointer<IState> &state)
{
    StateManager *stateManager = StateManager::getInstance();
    TransitionManager *trManager = TransitionManager::getInstance();

    State *newState = stateManager->createState(state->isFinal() ? "FinalState" : "State",
                                                editor, pos,
                                                state->getLabel(), state->getName(), false);
        
    if (state->isInitial())
    {
        Transition *newTransition = trManager->createOneStateTransition("Initial", editor, 
                                                                        newState, "", NORTH_WEST, false);
        newTransition->assign();
    }    

    return newState;
}

IState::TIStateList BaseDrawAlgorithm::getBFSSortedStates
                        (const QSharedPointer<IAutomaton> &automaton) const
{
    IState::TIStateList sortedStateList;

    QQueue<QSharedPointer<IState> > openedStates;    
    openedStates << automaton->getInitialStates();
    
    IState::TIStateNameSet foundStates;
    QSharedPointer<IState> currentState;
    
    while (!openedStates.empty())
    {
        currentState = openedStates.dequeue();
        foundStates << currentState->getName();
        sortedStateList << currentState;
        
        foreach(const QSharedPointer<ITransition> &tr, currentState->getTransitions())
        {
            QString workState = tr->getDestinationState();
            if (foundStates.contains(workState)) continue;
            
            foundStates << workState;
            openedStates << automaton->getState(workState);
        }
    }
    
    return sortedStateList;
}


void BaseDrawAlgorithm::initPaths(const IState::TIStateList &states, const QString& fromStateName,
                                  TDistanceMap &distances, TPredecessorMap &predecessors) const
{
    foreach(const QSharedPointer<IState> &state, states)
    {
        distances[state->getName()] = std::numeric_limits<unsigned int>::max();
        predecessors[state->getName()] = "";
    }
    distances[fromStateName] = 0;
    DBGLOG_DRAW(DBGPAR(distances));
}

void BaseDrawAlgorithm::relax(const QString &u, const QString &v,
                              TDistanceMap &distances, TPredecessorMap &predecessors) const
{
    // weights are ever 1, 2nd condition needed to avoid UINT overflow
    if (distances[v] > distances[u] + 1 && distances[u] != std::numeric_limits<unsigned int>::max())
    {
        distances[v] = distances[u] + 1;
        predecessors[v] = u;
    }
}

class DistanceComparator
{
public:
    DistanceComparator(const BaseDrawAlgorithm::TDistanceMap &dist)
    : d(&dist)
    {}
    
    bool operator()(const QSharedPointer<IState> &s1, const QSharedPointer<IState> &s2) const
    {
        return (*d)[s1->getName()] > (*d)[s2->getName()];
    }
    
protected:
    const BaseDrawAlgorithm::TDistanceMap *d;
};

void BaseDrawAlgorithm::fillDijkstraShortestPaths(const QSharedPointer<IAutomaton> &automaton,
                                                  const QString &fromStateName,
                                                  TDistanceMap &distances, TPredecessorMap &predecessors) const
{    
    initPaths(automaton->getStates(), fromStateName, distances, predecessors);
  
    typedef priority_queue<QSharedPointer<IState>, vector<QSharedPointer<IState> >, DistanceComparator> TQueue;    
    TQueue stateQueue(DistanceComparator((const TDistanceMap&) distances));
    stack<QSharedPointer<IState> > stateStack;
    
    foreach(const QSharedPointer<IState> &state, automaton->getStates())
    {
        stateQueue.push(state);
    }
    
    while (!stateQueue.empty())
    {
        QSharedPointer<IState> uState = stateQueue.top();
        stateQueue.pop();
        
        while (!stateQueue.empty())
        {
            stateStack.push(stateQueue.top());
            stateQueue.pop();
        }
        
        IState::TIStateNameList adj = uState->getAdjacentStates();
        foreach(const QString &v, adj)
        {
            relax(uState->getName(), v, distances, predecessors);
        }
        
        while(!stateStack.empty())
        {
            stateQueue.push(stateStack.top());
            stateStack.pop();
        }
    }
}

IState::TIStateNameSet BaseDrawAlgorithm::getStatesInDistance
    (unsigned int distance, const TDistanceMap &distances) const
{
    IState::TIStateNameSet result;

    TDistanceMap::const_iterator it = distances.begin();
    while(it != distances.end())
    {
        if (it.value() == distance) result << it.key();
        ++it;
    }
    
    return result;
}

unsigned int BaseDrawAlgorithm::getMaxDistance(const TDistanceMap &distances) const
{
    unsigned int result = 0;
    
    TDistanceMap::const_iterator it = distances.begin();
    while(it != distances.end())
    {
        if (it.value() > result && it.value() != std::numeric_limits<unsigned int>::max())
            result = it.value();
        ++it;
    }
    
    return result;
}

int transitionCountBetween(const State &s1, const State &s2)
{
    int result = 0;
    
    QList<Transition*> trList = s1.getOutgoingTransitions();
    foreach(Transition *tr, trList)
    {
        if (tr->getDestinationState() == s2.getName())
            result++;
    }
    
    trList = s2.getOutgoingTransitions();
    foreach(Transition *tr, trList)
    {
        if (tr->getDestinationState() == s1.getName())
            result++;
    }
    
    return result;
}

void setParams(const State &s1, const State &s2,                                    // in
               const QPoint &startPos, const int xStep, const int yStep,            // in 
               QString &typeName, float &arcAngle, bool &leftOriented)              // out
{
    int count = transitionCountBetween(s1, s2);
    
    const bool leftToRight = s1.pos().x() <= s2.pos().x();
    
    if (count == 0 &&
        abs(s1.pos().x() - s2.pos().x()) <= xStep &&
        abs(s1.pos().y() - s2.pos().y()) <= yStep)
    {   // no other transitions between states and states are side-by-side
        typeName = "Edge";
        leftOriented = leftToRight ? s1.pos().y() <= startPos.y()
                                   : s1.pos().y() > startPos.y();
        return;
    }
    
    typeName = "VArc";
    
    const float angleStep = 30;
    
    if (s1.pos().y() <= startPos.y())
    {   // higher than backbone
        arcAngle = (count % 2 == 0) ? 
                        (leftToRight ? angleStep * (count/2 + 1) : -angleStep * (count/2 + 1)) :
                        (leftToRight ? -angleStep * ((count-1)/2 + 1) : angleStep * ((count-1)/2 + 1));
                        
        leftOriented = leftToRight ?
                        (count % 2 == 0) ? true : false
                                   :
                        (count % 2 == 0) ? false : true;
    }
    else
    {
        arcAngle = (count % 2 == 0) ? 
                        (leftToRight ? -angleStep * (count/2 + 1) : angleStep * (count/2 + 1)) :
                        (leftToRight ? angleStep * ((count-1)/2 + 1) : -angleStep * ((count-1)/2 + 1));
        
        leftOriented = leftToRight ?
                        (count % 2 == 0) ? false : true
                                   :
                        (count % 2 == 0) ? true : false;
    }    
}

#ifdef USE_TRANSITION_GROUPING_IN_DRAWING_ALGORITHM

ITransition::TITransitionList BaseDrawAlgorithm::getGroupedTransitions(const QSharedPointer<IAutomaton> &automaton) const
{
    ITransition::TITransitionList transitions = automaton->getTransitions();

    typedef QPair<QString, QString>                             TNamePair;
    typedef QMap<TNamePair, QSharedPointer<TransitionImpl> >    TTransitionMap;
    TTransitionMap transitionMap;
    QSharedPointer<TransitionImpl> groupedTr(NULL);

    // merge transitions between same states
    foreach(const QSharedPointer<ITransition> &transition, transitions)
    {
        TNamePair namePair(transition->getSourceState(), transition->getDestinationState());

        if (transitionMap.contains(namePair))
        {
            groupedTr = transitionMap[namePair];
            groupedTr->setCharacters(groupedTr->getCharacters() | transition->getCharacters());
        }

        if (!groupedTr)
        {
            groupedTr = QSharedPointer<TransitionImpl>(
                new TransitionImpl(transition->getSourceState(),
                                    transition->getDestinationState(),
                                    transition->getCharacters(),
                                    NULL));
        }

        Q_ASSERT(groupedTr);
        transitionMap[namePair] = groupedTr;

        groupedTr.clear();
        Q_ASSERT(groupedTr == NULL);
    }

    ITransition::TITransitionList groupedTransitions;
    // fill result list and dismember epsilon transition from other
    for (TTransitionMap::Iterator trIt = transitionMap.begin();
         trIt != transitionMap.end();
         ++trIt)
    {
        if ((*trIt)->passOn(automaton->getEpsilonSymbol()))
        {
            groupedTransitions << QSharedPointer<TransitionImpl>(
                new TransitionImpl((*trIt)->getSourceState(), (*trIt)->getDestinationState(),
                                   ITransition::TCharSet() << automaton->getEpsilonSymbol(), NULL));

            if ((*trIt)->getCharacters().count() == 1) continue; // just epsilon transition
        }

        Q_ASSERT(!((*trIt)->getCharacters()-(ITransition::TCharSet() << automaton->getEpsilonSymbol())).isEmpty());

        groupedTransitions << QSharedPointer<TransitionImpl>(
                new TransitionImpl((*trIt)->getSourceState(), (*trIt)->getDestinationState(),
                                   (*trIt)->getCharacters()-(ITransition::TCharSet() << automaton->getEpsilonSymbol()),
                                   NULL));
    }

    return groupedTransitions;
}

#endif

void BaseDrawAlgorithm::drawTransitions(Editor *editor,
                                        const Editor::TStateMap &states,
                                        const QSharedPointer<IAutomaton> &automaton,
                                        const ITransition::TITransitionList &transitions,
                                        const QPoint &startPoint) const
{
    TransitionManager *trManager = TransitionManager::getInstance();
    Transition *newTransition;

    DBGLOG_DRAW(DBGPAR(states));

    foreach(const QSharedPointer<ITransition> &tr, transitions)
    {
        State *s1 = editor->getStateByName(states, tr->getSourceState());
        DBGLOG_DRAW(DBGPAR(tr->getSourceState()));
        Q_ASSERT(s1);

        QString label = charactersToLabel(automaton, tr);

        if (tr->getSourceState() == tr->getDestinationState())
        {
            newTransition = trManager->createOneStateTransition(
                "Loop",
                editor,
                s1,
                label,
                s1->pos().y() < startPoint.y() ? NORTH : SOUTH,
                false);
        }
        else
        {
            State *s2 = editor->getStateByName(states, tr->getDestinationState());
            Q_ASSERT(s2);

            float arcAngle = 30;
            bool  leftOriented = true;
            QString typeName = "Edge";
            setParams(*s1, *s2, startPoint, X_STEP, Y_STEP, typeName, arcAngle, leftOriented);

            newTransition = trManager->createTwoStatesTransition
                (typeName,
                 editor,
                 s1,
                 s2,
                 label,
                 leftOriented,
                 false);

            newTransition->setArcAngle(arcAngle);
        }

        newTransition->adjust();
        newTransition->assign();
    }
}

QString BaseDrawAlgorithm::charactersToLabel(const QSharedPointer<IAutomaton> &automaton,
                                             const QSharedPointer<ITransition> &transition) const
{
    const int charCount = transition->getCharacters().count();
    const int alphCount = automaton->getAlphabet().count();
    QString label = charCount == alphCount ? "A" :  // whole alphabet
                                     charCount > alphCount/2 ? QString("A - \\{%1\\}").arg( // better to use alphabet minus syntax
                                         QStringList((automaton->getAlphabet()-transition->getCharacters()).toList()).join(",")) :
                                         QStringList(transition->getCharacters().toList()).join(","); // normal syntax

    return label;
}

//-------------------------------------------------------------------- BaseDrawAlgorithm -->



//<-- NaiveDrawAlgorithm -------------------------------------------------------------------

QList<State*> NaiveDrawAlgorithm::drawAutomaton(Editor *editor, const QSharedPointer<IAutomaton> &automaton)
{
    StateManager *stateManager = StateManager::getInstance();
    TransitionManager *trManager = TransitionManager::getInstance();        

    IState::TIStateList automataStates = getBFSSortedStates(automaton);
    QPoint statePos(QPoint(1,1));
    int i = 0;

    Editor::TStateMap states;
    State *newState;
    Transition *newTransition;
    foreach(const QSharedPointer<IState> &state, automataStates)
    {
        newState = stateManager->createState("State", editor, statePos, 
                                             state->getLabel(), state->getName(), false);
        
        if (state->isInitial())
        {
            newTransition = trManager->createOneStateTransition("Initial", editor, newState, "", WEST, false);
            newTransition->assign();
        }

        if (state->isFinal())
            newState->setDoubleBorder(true);

        states[newState->getName()] = newState;
        
        statePos += QPoint(GRID_STEP*2,GRID_STEP*2);
        ++i;
    }

    foreach(const QSharedPointer<IState> &state, automataStates)
    {
        foreach(const QSharedPointer<ITransition> &tr, state->getTransitions())
        {
            State *s1 = editor->getStateByName(states, state->getName());
            QString label = QStringList(tr->getCharacters().toList()).join(",");
            if (tr->getSourceState() == tr->getDestinationState())
            {
                newTransition = trManager->createOneStateTransition("Loop", editor, s1, label, NORTH, false);
            }
            else
            {
                State *s2 = editor->getStateByName(states, tr->getDestinationState());
                newTransition = trManager->createTwoStatesTransition("Edge", editor, s1, s2, label, true, false);
            }
                            
            newTransition->adjust();
            newTransition->assign();
        }
    }

    return states.values();
}

//------------------------------------------------------------------- NaiveDrawAlgorithm -->



//<-- FarthestFinalDrawAlgorithm -----------------------------------------------------------

QList<State*> FarthestFinalDrawAlgorithm::drawAutomaton
    (Editor *editor, const QSharedPointer<IAutomaton> &automaton)
{
    DBGLOG_DRAW("state count=" << automaton->getStates().count());
    if (automaton->getStates().isEmpty()) return QList<State*>();

    Editor::TStateMap states;
    QPoint startPoint(editor->toScenePos(QPoint(1,1)));
    
    // first find farthest final states -> it will be backbone
    TDistanceMap        distances;
    TPredecessorMap     predecessors;
    
    IState::TIStateList initialStates = automaton->getInitialStates();
    QSharedPointer<IState> initialState = initialStates.isEmpty() ? automaton->getStates()[0] // hack if no initial state exists!
                                                                  : initialStates[0];

    fillDijkstraShortestPaths(automaton, initialState->getName(), distances, predecessors);
    
    DBGLOG_DRAW(DBGPAR(distances));
    DBGLOG_DRAW(DBGPAR(predecessors));
    
    QSharedPointer<IState> farthestFinalState(initialState); // even if not final it's ok (if some final state is accessible, it has greater distatnce than 0)
    unsigned int farthest = 0;
    IState::TIStateList finalStates = automaton->getFinalStates();
    if (finalStates.isEmpty())
    {
        finalStates = automaton->getStates();
    }

    foreach(const QSharedPointer<IState> &state, finalStates)
    {
        const unsigned int &distance = distances[state->getName()];
        if (distance > farthest &&
            distance != UINT_MAX) // UINT_MAX has inaccessible states!!!
        {
            farthest = distance;
            farthestFinalState = state;
        }
    }    
    
    DBGLOG_DRAW(DBGPAR(farthestFinalState->getName()));

    QSharedPointer<IState> currentState;
    QString currentStateName;
    QPoint statePos(0,0);
    
    QStack<QSharedPointer<IState> > statesToBeDraw;
    statesToBeDraw << farthestFinalState;
    currentStateName = farthestFinalState->getName();
    while(predecessors[currentStateName] != "")
    {        
        currentState = automaton->getState(predecessors[currentStateName]);
        statesToBeDraw << currentState;
        currentStateName = currentState->getName();
    }
    
#ifndef QT_NO_DEBUG_OUTPUT
    foreach(const QSharedPointer<IState> &state, statesToBeDraw)
    {
        DBGLOG_DRAW("draw:" << state->getName());
    }
#endif
    
    unsigned int i = 0;
    State *newState;
        
    const unsigned int maxDistance = getMaxDistance(distances);
    Q_ASSERT(maxDistance != UINT_MAX);
    
    // draw backbone
    while(!statesToBeDraw.empty())
    {
        currentState = statesToBeDraw.pop();
        newState = createState(editor, statePos + startPoint, currentState);

        states[newState->getName()] = newState;        
        
        if (statesToBeDraw.count() == 1) // last state on backbone should be most on right
            statePos = QPoint(X_STEP * maxDistance, 0);
        else
            statePos += QPoint(X_STEP, 0);

        ++i;
    }
    
    int max_j = 1;
    // draw left accessible states
    for (unsigned int d = 1; d <= maxDistance; ++d)
    {
        IState::TIStateNameSet levelStates = getStatesInDistance(d, distances);
        foreach(const QString &stateName, levelStates)
        {
            if (!states.contains(stateName))
                statesToBeDraw << automaton->getState(stateName);
        }
        // TODO: sort states according to predecessor state position
     
        int j = 1;
           
        while(!statesToBeDraw.empty())
        {
            QPoint curStatePos(X_STEP * d,
                               Y_STEP * (j % 2 ? -j : j-1));
            DBGLOG_DRAW(DBGPAR(curStatePos));
            
            currentState = statesToBeDraw.pop();
            newState = createState(editor, curStatePos + startPoint, currentState);

            states[newState->getName()] = newState;
            
            ++j;
            ++i;
        }

        if (j > max_j) max_j = j;
    }
    
    // draw inaccessible states
    IState::TIStateNameSet inaccessibleStates = automaton->getStateNameList().toSet();
    inaccessibleStates -= states.keys().toSet();
    DBGLOG_DRAW(DBGPAR(inaccessibleStates));

    // minimal count of unrelated states in single row (side-by-side)
    const unsigned int minimalSBS = 5; // TODO: should this be global constant in constants.h?
    const unsigned int sbs = (maxDistance > minimalSBS) ? maxDistance : minimalSBS;

    int row = max_j;
    i = 0;
    foreach(const QString &stateName, inaccessibleStates)
    {
        QSharedPointer<IState> state = automaton->getState(stateName);
        Q_ASSERT(state);

        QPoint curStatePos(X_STEP * i,
                           Y_STEP * ( row % 2 ? -row : row-1));
        DBGLOG_DRAW(DBGPAR(curStatePos));

        newState = createState(editor, curStatePos + startPoint, state);
        states[newState->getName()] = newState;

        ++i;
        if (i >= sbs) { i = 0; row++; }
    }

#ifdef USE_TRANSITION_GROUPING_IN_DRAWING_ALGORITHM
    drawTransitions(editor, states, automaton, getGroupedTransitions(automaton), startPoint);
#else
    drawTransitions(editor, states, automaton, automaton->getTransitions(), startPoint);
#endif

    return states.values();
}

//----------------------------------------------------------- FarthestFinalDrawAlgorithm -->



//<-- GraphVizDrawAlgorithm ----------------------------------------------------------------

GraphVizDrawAlgorithm::GraphVizDrawAlgorithm(IGraphViz *graphVizWrapper)
:   m_graphVizWrapper(graphVizWrapper)
{

}

QList<State*> GraphVizDrawAlgorithm::drawAutomaton
    (Editor *editor, const QSharedPointer<IAutomaton> &automaton)
{
    DBGLOG_DRAW("state count=" << automaton->getStates().count());
    if (automaton->getStates().isEmpty()) return QList<State*>();

    QSharedPointer<IGVGraph> graph = m_graphVizWrapper->createGraph();

    IState::TIStateList states = automaton->getStates();
    foreach(const QSharedPointer<IState> &state, states)
    {
        graph->addNode(state->getName());
    }

    ITransition::TITransitionList transitions = automaton->getTransitions();
    foreach(const QSharedPointer<ITransition> &transition, transitions)
    {
        graph->addEdge(transition->getSourceState(), transition->getDestinationState(),
                       charactersToLabel(automaton, transition));
    }

    graph->layoutGraphUsingDot();

#ifdef TESTING_GRAPHVIZDRAWER
    graph->renderToFile("testGraphVizDrawer.png");
#endif

    Editor::TStateMap newStates;

    foreach(const QSharedPointer<IState> &state, states)
    {
        QPoint pos = graph->getNode(state->getName())->getPos();
        pos.setY(editor->scene()->height() - pos.y());

        State *newState = createState(editor, pos , state);
        newStates[newState->getName()] = newState;
    }

    drawTransitionsAccordingToGV(editor, newStates, automaton, graph);

    return newStates.values();
}

void GraphVizDrawAlgorithm::drawTransitionsAccordingToGV(
        Editor *editor,                                        // in
        const Editor::TStateMap &states,                       // in
        const QSharedPointer<IAutomaton> &automaton,           // in
        const QSharedPointer<IGVGraph> &graph) const           // in
{
    // TODO: implement detection of labels positions (maybe right dir will be good enough)

    TransitionManager *trManager = TransitionManager::getInstance();

    QSharedPointer<IGVNode> node = graph->getFirstNode();
    while(node)
    {
        int e_idx = 0;
        QSharedPointer<IState> state = automaton->getState(node->getName());
        int outTrSize = state->getTransitions().size();
        QSharedPointer<IGVEdge> edge = node->getFirstOutEdge();
        while(edge)
        {
            IGVEdge::TCPList bezierCP = convertCPToBezierCP(edge);
            Transition *newTr = NULL;
            Q_ASSERT(e_idx < outTrSize); Q_UNUSED(outTrSize)
            QString label = edge->getLabel();
            bool dir;
            ETransitionType type = getTransitionType(edge, bezierCP);

            State *s1 = states[edge->getTailName()];
            State *s2 = states[edge->getHeadName()];

            switch (type)
            {
            case eLoop:
                DBGLOG_DRAW("eLoop");
                dir = bezierCP[0].y() < bezierCP[1].y() ? NORTH : SOUTH;
                newTr = trManager->createOneStateTransition("Loop", editor, s1, label, dir, false);
                break;
            case eLine:
                DBGLOG_DRAW("eLine");
                dir = bezierCP[0].x() < bezierCP[1].x();
                newTr = trManager->createTwoStatesTransition("Edge", editor, s1, s2, label, dir, false);
                break;
            case eCurve:
                DBGLOG_DRAW("eCurve");
                {
                    dir = false;
                    newTr = trManager->createTwoStatesTransition("VCurve", editor, s1, s2, label, dir, false);

                    const QPoint p11 = QPoint(s1->pos().x(), s1->pos().y());
                    const QPoint p21 = QPoint(s2->pos().x(), s2->pos().y());
                    const QPoint p12 = QPoint(bezierCP[0].x(), editor->scene()->height()-bezierCP[0].y());
                    const QPoint p22 = QPoint(bezierCP[3].x(), editor->scene()->height()-bezierCP[3].y());

                    const int arcAngle = qRound(QLineF(p11, p12).angle());
                    const int arcAngleB = qRound(QLineF(p21, p22).angle());
                    newTr->setArcAngle(arcAngle);
                    newTr->setArcAngleB(arcAngleB);

                    newTr->setNCurv(0.8f);
                }
                break;
            default:
                Q_ASSERT(0 && "undefined value!");
                break;
            }

            newTr->adjust();
            newTr->assign();
            e_idx++;
            edge = edge->getNextOutEdge();
        }
        node = node->getNextNode();
    }
}

IGVEdge::TCPList GraphVizDrawAlgorithm::convertCPToBezierCP(const QSharedPointer<IGVEdge> &edge) const
{
    IGVEdge::TCPList controlPoints = edge->getControlPoints();
    Q_ASSERT(controlPoints.size() >= 4);
    DBGLOG_DRAW(DBGPAR(controlPoints));

    IGVEdge::TCPList bezierCP;
    bezierCP << controlPoints[0];

    // number of control points is equal 3n+1 (n >= 1)
    const int pos = controlPoints.size() / 4 + (controlPoints.size() % 4 ? 1 : 0);
    Q_ASSERT(controlPoints.size() > pos);
    bezierCP << controlPoints[pos];
    bezierCP << controlPoints[controlPoints.size()-pos-1];

    bezierCP << controlPoints[controlPoints.size()-1];
    DBGLOG_DRAW(DBGPAR(bezierCP));

    return bezierCP;
}

GraphVizDrawAlgorithm::ETransitionType GraphVizDrawAlgorithm::getTransitionType
    (const QSharedPointer<IGVEdge> &edge, const IGVEdge::TCPList &bezierCP) const
{
    // try if it's on the same line
    if (edge->getHeadName() == edge->getTailName()) return eLoop;
    QLineF line = QLineF(bezierCP.first(), bezierCP.last());
    const qreal angle = line.angle();
    const int bound = 2;
    for(int i=1; i<bezierCP.size()-1; ++i)
    {
        line.setP2(bezierCP[i]);
        const qreal angle2 = line.angle();
        if (angle < angle2-bound || angle > angle2+bound) return eCurve;
    }
    return eLine;
}

//---------------------------------------------------------------- GraphVizDrawAlgorithm -->