func (g *MixedMap) CheckEdgeType(tail VertexId, head VertexId) MixedConnectionType {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Check edge type in mixed graph.", e)
			err.AddV("tail", tail)
			err.AddV("head", head)
			panic(err)
		}
	}()

	connectedVertexes, ok := g.connections[tail]
	if !ok {
		panic(erx.NewError("Fist node doesn't exist."))
	}

	if _, ok = g.connections[head]; !ok {
		panic(erx.NewError("Second node doesn't exist."))
	}

	direction, ok := connectedVertexes[head]
	if !ok {
		direction = CT_NONE
	}

	return direction
}

func (gr *MixedMatrix) getConnectionId(node1, node2 VertexId, create bool) int {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Calculating connection id.", e)
			err.AddV("node 1", node1)
			err.AddV("node 2", node2)
			panic(err)
		}
	}()

	var id1, id2 int
	node1Exist := false
	node2Exist := false
	id1, node1Exist = gr.VertexIds[node1]
	id2, node2Exist = gr.VertexIds[node2]

	// checking for errors
	{
		if node1 == node2 {
			panic(erx.NewError("Equal nodes."))
		}
		if !create {
			if !node1Exist {
				panic(erx.NewError("First node doesn't exist in graph"))
			}
			if !node2Exist {
				panic(erx.NewError("Second node doesn't exist in graph"))
			}
		} else if !node1Exist || !node2Exist {
			if node1Exist && node2Exist {
				if gr.size-len(gr.VertexIds) < 2 {
					panic(erx.NewError("Not enough space to create two new nodes."))
				}
			} else {
				if gr.size-len(gr.VertexIds) < 1 {
					panic(erx.NewError("Not enough space to create new node."))
				}
			}
		}
	}

	if !node1Exist {
		id1 = int(len(gr.VertexIds))
		gr.VertexIds[node1] = id1
	}

	if !node2Exist {
		id2 = int(len(gr.VertexIds))
		gr.VertexIds[node2] = id2
	}

	// switching id1, id2 in order to id1 < id2
	if id1 > id2 {
		id1, id2 = id2, id1
	}

	// id from upper triangle matrix, stored in vector
	connId := id1*(gr.size-1) + id2 - 1 - id1*(id1+1)/2
	return connId
}

// Removing arrow  'from' and 'to' nodes
func (g *MixedMap) RemoveArc(from, to VertexId) {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Remove arc from graph.", e)
			err.AddV("tail", from)
			err.AddV("head", to)
			panic(err)
		}
	}()

	if _, ok := g.connections[from]; ok {
		panic(erx.NewError("Tail node doesn't exist."))
	}

	if _, ok := g.connections[to]; ok {
		panic(erx.NewError("Head node doesn't exist."))
	}

	if dir, ok := g.connections[from][to]; !ok || dir != CT_DIRECTED {
		panic(erx.NewError("Arc doesn't exist."))
	}

	g.connections[from][to] = CT_NONE, false
	g.connections[to][from] = CT_NONE, false
	g.arcsCnt--

	return
}

// Adding edge to graph.
func (g *MixedMap) AddEdge(from, to VertexId) {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Add edge to graph.", e)
			err.AddV("node 1", from)
			err.AddV("node 2", to)
			panic(err)
		}
	}()

	g.touchNode(from)
	g.touchNode(to)

	if direction, ok := g.connections[from][to]; ok {
		err := erx.NewError("Duplicate connection.")
		err.AddV("connection type", direction)
		panic(err)
	}

	g.connections[from][to] = CT_UNDIRECTED
	g.connections[to][from] = CT_UNDIRECTED
	g.edgesCnt++

	return
}

// Getting node predecessors
func (g *MixedMap) GetPredecessors(node VertexId) VertexesIterable {
	iterator := func() <-chan VertexId {
		ch := make(chan VertexId)

		go func() {
			defer func() {
				if e := recover(); e != nil {
					err := erx.NewSequent("Getting node predecessors.", e)
					err.AddV("node id", node)
					panic(err)
				}
			}()

			accessorsMap, ok := g.connections[node]
			if !ok {
				panic(erx.NewError("Node doesn't exists."))
			}

			for VertexId, connType := range accessorsMap {
				if connType == CT_DIRECTED_REVERSED {
					ch <- VertexId
				}
			}

			close(ch)
		}()

		return ch
	}

	return VertexesIterable(&nodesIterableLambdaHelper{iterFunc: iterator})
}

// Getting node predecessors
func (g *DirectedMap) GetPredecessors(node VertexId) VertexesIterable {
	iterator := func() <-chan VertexId {
		ch := make(chan VertexId)

		go func() {
			defer func() {
				if e := recover(); e != nil {
					err := erx.NewSequent("Get node accessors in mixed graph.", e)
					err.AddV("node", node)
					panic(err)
				}
			}()
			accessorsMap, ok := g.reversedArcs[node]
			if !ok {
				panic(erx.NewError("Node doesn't exists."))
			}

			for VertexId, _ := range accessorsMap {
				ch <- VertexId
			}
			close(ch)
		}()

		return ch
	}

	return VertexesIterable(&nodesIterableLambdaHelper{iterFunc: iterator})
}

// Getting all nodes, connected to given one
func (g *UndirectedMatrix) GetNeighbours(node VertexId) VertexesIterable {
	iterator := func() <-chan VertexId {
		ch := make(chan VertexId)
		go func() {

			if _, ok := g.VertexIds[node]; !ok {
				panic(erx.NewError("Unknown node."))
			}

			var connId int
			for aNode, _ := range g.VertexIds {
				if aNode == node {
					continue
				}
				connId = g.getConnectionId(node, aNode, false)

				if g.nodes[connId] {
					ch <- aNode
				}
			}

			close(ch)
		}()
		return ch
	}

	return VertexesIterable(&nodesIterableLambdaHelper{iterFunc: iterator})
}

// Removing edge, connecting node1 and node2
func (g *UndirectedMatrix) RemoveEdge(node1, node2 VertexId) {
	makeError := func(err interface{}) (res erx.Error) {
		res = erx.NewSequentLevel("Remove edge from graph.", err, 1)
		res.AddV("node 1", node1)
		res.AddV("node 2", node2)
		return
	}

	defer func() {
		// warning! such code generates wrong file/line info about error!
		// see http://groups.google.com/group/golang-nuts/browse_thread/thread/66bd57dcdac63aa
		// for details
		if err := recover(); err != nil {
			panic(makeError(err))
		}
	}()

	conn := g.getConnectionId(node1, node2, false)

	if !g.nodes[conn] {
		panic(erx.NewError("Edge doesn't exist."))
	}

	g.nodes[conn] = false
	g.edgesCnt--

	return
}

// Getting node predecessors
func (g *MixedMap) GetNeighbours(node VertexId) VertexesIterable {
	iterator := func() <-chan VertexId {
		ch := make(chan VertexId)

		go func() {
			defer func() {
				if e := recover(); e != nil {
					err := erx.NewSequent("Get node neighbours.", e)
					err.AddV("node id", node)
					panic(err)
				}
			}()

			if connectedMap, ok := g.connections[node]; ok {
				for VertexId, connType := range connectedMap {
					if connType == CT_UNDIRECTED {
						ch <- VertexId
					}
				}
			} else {
				panic(erx.NewError("Node doesn't exists."))
			}

			close(ch)
		}()

		return ch
	}

	return VertexesIterable(&nodesIterableLambdaHelper{iterFunc: iterator})
}

func (gr *MixedMatrix) TypedConnectionsIter() <-chan TypedConnection {
	ch := make(chan TypedConnection)
	go func() {
		for from, _ := range gr.VertexIds {
			for to, _ := range gr.VertexIds {
				if from >= to {
					continue
				}

				conn := gr.getConnectionId(from, to, false)
				switch gr.nodes[conn] {
				case CT_NONE:
				case CT_UNDIRECTED:
					ch <- TypedConnection{Connection: Connection{Tail: from, Head: to}, Type: CT_UNDIRECTED}
				case CT_DIRECTED:
					ch <- TypedConnection{Connection: Connection{Tail: from, Head: to}, Type: CT_DIRECTED}
				case CT_DIRECTED_REVERSED:
					ch <- TypedConnection{Connection: Connection{Tail: to, Head: from}, Type: CT_DIRECTED}
				default:
					err := erx.NewError("Internal error: wrong connection type in mixed graph matrix")
					err.AddV("connection type", gr.nodes[conn])
					err.AddV("connection id", conn)
					err.AddV("tail node", from)
					err.AddV("head node", to)
					panic(err)
				}
			}
		}
		close(ch)
	}()
	return ch
}

func topologicalSortHelper(gr DirectedGraphReader, curNode VertexId, nodes []VertexId, status map[VertexId]bool) (pos int, hasCycles bool) {
	if isBlack, ok := status[curNode]; ok {
		err := erx.NewError("Internal error in topological sort: node already in status map")
		err.AddV("node id", curNode)
		err.AddV("status in map", isBlack)
		panic(err)
	}
	hasCycles = false
	status[curNode] = false
	pos = len(nodes)
	for accessor := range gr.GetAccessors(curNode).VertexesIter() {
		if isBlack, ok := status[accessor]; ok {
			if !isBlack {
				// cycle detected!
				hasCycles = true
				return
			} else {
				// we have already visited this node
				continue
			}
		}
		pos, hasCycles = topologicalSortHelper(gr, accessor, nodes[0:pos], status)
		if hasCycles {
			return
		}
	}
	status[curNode] = true
	pos--
	nodes[pos] = curNode
	return
}

// Adding new edge to graph
func (g *UndirectedMatrix) AddEdge(node1, node2 VertexId) {
	makeError := func(err interface{}) (res erx.Error) {
		res = erx.NewSequentLevel("Add edge to graph.", err, 1)
		res.AddV("node 1", node1)
		res.AddV("node 2", node2)
		return
	}

	defer func() {
		// warning! such code generates wrong file/line info about error!
		// see http://groups.google.com/group/golang-nuts/browse_thread/thread/66bd57dcdac63aa
		// for details
		if err := recover(); err != nil {
			panic(makeError(err))
		}
	}()

	var conn int
	conn = g.getConnectionId(node1, node2, true)

	if g.nodes[conn] {
		err := erx.NewError("Duplicate edge.")
		err.AddV("connection id", conn)
		panic(makeError(err))
	}
	g.nodes[conn] = true
	g.edgesCnt++

	return
}

// Adding directed arc to graph
func (gr *MixedMatrix) AddArc(tail, head VertexId) {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Add arc to mixed graph.", e)
			err.AddV("tail", tail)
			err.AddV("head", head)
			panic(err)
		}
	}()

	conn := gr.getConnectionId(tail, head, true)
	if gr.nodes[conn] != CT_NONE {
		err := erx.NewError("Duplicate edge.")
		err.AddV("connection id", conn)
		err.AddV("type", gr.nodes[conn])
		panic(err)
	}

	if tail < head {
		gr.nodes[conn] = CT_DIRECTED
	} else {
		gr.nodes[conn] = CT_DIRECTED_REVERSED
	}

	gr.arcsCnt++
}

// Removding directed arc
func (gr *MixedMatrix) RemoveArc(tail, head VertexId) {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Remove arc from mixed graph.", e)
			err.AddV("tail", tail)
			err.AddV("head", head)
			panic(err)
		}
	}()

	conn := gr.getConnectionId(tail, head, true)
	expectedType := CT_NONE
	if tail < head {
		expectedType = CT_DIRECTED
	} else {
		expectedType = CT_DIRECTED_REVERSED
	}

	if gr.nodes[conn] != expectedType {
		err := erx.NewError("Arc doesn't exists.")
		err.AddV("connection id", conn)
		err.AddV("type", gr.nodes[conn])
		panic(err)
	}

	gr.nodes[conn] = CT_NONE
	gr.arcsCnt--
}

func (g *MixedMap) TypedConnectionsIter() <-chan TypedConnection {
	ch := make(chan TypedConnection)
	go func() {
		for from, connectedVertexes := range g.connections {
			for to, connType := range connectedVertexes {
				switch connType {
				case CT_NONE:
				case CT_UNDIRECTED:
					if from < to {
						ch <- TypedConnection{Connection: Connection{Tail: from, Head: to}, Type: CT_UNDIRECTED}
					}
				case CT_DIRECTED:
					ch <- TypedConnection{Connection: Connection{Tail: from, Head: to}, Type: CT_DIRECTED}
				case CT_DIRECTED_REVERSED:
				default:
					err := erx.NewError("Internal error: wrong connection type in mixed graph matrix")
					err.AddV("connection type", connType)
					err.AddV("tail node", from)
					err.AddV("head node", to)
					panic(err)
				}
			}
		}
		close(ch)
	}()
	return ch
}

// Generic function to check if graph contain specific path.
//
// First argument gr is an interface with two functions to check node existance and
// connection existance between two nodes in graph.
//
// unexistNodePanic flag is used to point wether or not to panic if we figure out that
// one of the nodes in path doesn't exist in graph. If unexistNodePanic is false, then
// result of the function will be false.
func ContainPath(gr NodeAndConnectionChecker, path []VertexId, unexistNodePanic bool) bool {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Checking if graph contain path", e)
			err.AddV("path", path)
			err.AddV("panic if node doesn't exist in graph", unexistNodePanic)
			panic(err)
		}
	}()
	if len(path) == 0 {
		// emty path always exists
		return true
	}

	prev := path[0]
	if !gr.CheckNode(prev) {
		if unexistNodePanic {
			err := erx.NewError("Node doesn't exist in graph.")
			err.AddV("node", prev)
			panic(err)
		}
		return false
	}

	if len(path) == 1 {
		return true
	}

	for i := 1; i < len(path); i++ {
		cur := path[i]
		if !gr.CheckNode(cur) {
			if unexistNodePanic {
				err := erx.NewError("Node doesn't exist in graph.")
				err.AddV("node", cur)
				panic(err)
			}
			return false
		}
		if !gr.CheckConnection(prev, cur) {
			return false
		}
		prev = cur
	}
	return true
}

func NewMixedMatrix(size int) *MixedMatrix {
	if size <= 0 {
		panic(erx.NewError("Trying to create mixed matrix graph with zero size"))
	}
	g := new(MixedMatrix)
	g.nodes = make([]MixedConnectionType, size*(size-1)/2)
	g.size = size
	g.VertexIds = make(map[VertexId]int)
	return g
}

// Adding single node to graph
func (gr *MixedMatrix) AddNode(node VertexId) {
	defer func() {
		if e := recover(); e != nil {
			err := erx.NewSequent("Add node to graph.", e)
			err.AddV("node id", node)
			panic(err)
		}
	}()

	if _, ok := gr.VertexIds[node]; ok {
		panic(erx.NewError("Node already exists."))
	}

	if len(gr.VertexIds) == gr.size {
		panic(erx.NewError("Not enough space to add new node"))
	}

	gr.VertexIds[node] = len(gr.VertexIds)
}

func (g *UndirectedMap) CheckEdge(from, to VertexId) (isExist bool) {
	makeError := func(err interface{}) (res erx.Error) {
		res = erx.NewSequentLevel("Check edge existance in graph.", err, 1)
		res.AddV("node 1", from)
		res.AddV("node 2", to)
		return
	}

	connectedVertexes, ok := g.edges[from]
	if !ok {
		panic(makeError(erx.NewError("Fist node doesn't exist.")))
	}

	if _, ok = g.edges[to]; !ok {
		panic(makeError(erx.NewError("Second node doesn't exist.")))
	}

	_, isExist = connectedVertexes[to]

	return
}

func (g *DirectedMap) CheckArc(from, to VertexId) (isExist bool) {
	makeError := func(err interface{}) (res erx.Error) {
		res = erx.NewSequentLevel("Checking arc existance in graph.", err, 1)
		res.AddV("tail", from)
		res.AddV("head", to)
		return
	}

	connectedVertexes, ok := g.directArcs[from]
	if !ok {
		panic(makeError(erx.NewError("From node doesn't exist.")))
	}

	if _, ok = g.reversedArcs[to]; !ok {
		panic(makeError(erx.NewError("To node doesn't exist.")))
	}

	_, isExist = connectedVertexes[to]

	return
}