Graph.c

Go to the documentation of this file.

#include <stdlib.h>
#include "errors.h"
#include "Inventory.h"
 
#include <stdio.h>
 
//                            edge
// source vertex -----------------------------> target vertex
//               source tail        target head
//
// +--------+------------+---------------+------------+------------+---------------+-----------+
// |        | ONE        | TWO           | THREE      | FOUR       | FIVE          | SIX       |
// +--------+------------+---------------+------------+------------+---------------+-----------+
// | VERTEX | identifier | successor     | tail count | head count | last tail     | last head |
// +--------+------------+---------------+------------+------------+---------------+-----------+
// | EDGE   | source     | previous tail | next tail  | target     | previous head | next head |
// +--------+------------+---------------+------------+------------+---------------+-----------+
 
 
struct Graph {
    struct Inventory *one;
    struct Inventory *two;
    struct Inventory *three;
    struct Inventory *four;
    struct Inventory *five;
    struct Inventory *six;
};
 
struct Graph *Graph_construct(unsigned int length, int *error)
{
    struct Graph * this = malloc(sizeof(struct Graph));
 
    if (0 == this) {
        *error = ERROR_NO_MEMORY;
        return 0;
    }
 
    this->one = Inventory_construct(length, error);
 
    if (0 == this) {
        *error = ERROR_NO_MEMORY;
        return 0;
    }
 
    this->two = Inventory_construct(length, error);
 
    if (0 == this) {
        *error = ERROR_NO_MEMORY;
        return 0;
    }
 
    this->three = Inventory_construct(length, error);
 
    if (0 == this) {
        *error = ERROR_NO_MEMORY;
        return 0;
    }
 
    this->four= Inventory_construct(length, error);
 
    if (0 == this) {
        *error = ERROR_NO_MEMORY;
        return 0;
    }
 
    this->five = Inventory_construct(length, error);
 
    if (0 == this) {
        *error = ERROR_NO_MEMORY;
        return 0;
    }
 
    this->six = Inventory_construct(length, error);
 
    if (0 == this) {
        *error = ERROR_NO_MEMORY;
        return 0;
    }
 
    // install gauge
 
    Inventory_append(this->one, 1, error);
 
    if (*error) {
        return 0;
    }
 
    Inventory_append(this->two, 2, error);
 
    if (*error) {
        return 0;
    }
 
    Inventory_append(this->three, 3, error);
 
    if (*error) {
        return 0;
    }
 
    Inventory_append(this->four, 4, error);
 
    if (*error) {
        return 0;
    }
 
    Inventory_append(this->five, 5, error);
 
    if (*error) {
        return 0;
    }
 
    Inventory_append(this->six, 6, error);
 
    if (*error) {
        return 0;
    }
 
    return this;
}
 
struct Graph *Graph_destruct(struct Graph *this)
{
    if (0 != this) {
        free(this->one);
        free(this->two);
        free(this->three);
        free(this->four);
        free(this->five);
        free(this->six);
        free(this);
    }
 
    return 0;
}
 
unsigned int Graph_addVertex(struct Graph *this, int *error)
{
    unsigned int vertex = Inventory_getNext(this->one);
 
    Inventory_append(this->one, vertex, error);
 
    if (*error) {
        return 0;
    }
 
    Inventory_append(this->two, 0, error);
 
    if (*error) {
        return 0;
    }
 
    Inventory_append(this->three, 0, error);
 
    if (*error) {
        return 0;
    }
 
    Inventory_append(this->four, 0, error);
 
    if (*error) {
        return 0;
    }
 
    Inventory_append(this->five, 0, error);
 
    if (*error) {
        return 0;
    }
 
    Inventory_append(this->six, 0, error);
 
    if (*error) {
        return 0;
    }
 
    return vertex;
}
 
int Graph_hasEdge(const struct Graph *this, unsigned int source, unsigned int target, int *error)
{
    unsigned int sourceIdentifier = Inventory_read(this->one, source, error);
 
    if (*error) {
        return 0;
    }
 
    if (sourceIdentifier != source) {
        *error = ERROR_NOT_A_VERTEX;
        return 0;
    }
 
    unsigned int targetIdentifier = Inventory_read(this->one, target, error);
 
    if (*error) {
        return 0;
    }
 
    if (targetIdentifier != target) {
        *error = ERROR_NOT_A_VERTEX;
        return 0;
    }
 
    unsigned int tailCount = Inventory_read(this->three, source, error);
 
    if (*error) {
        return 0;
    }
    unsigned int headCount = Inventory_read(this->four, target, error);
 
    if (*error) {
        return 0;
    }
 
    if (tailCount < headCount) {
 
        unsigned int tail = Inventory_read(this->five, source, error);
 
        if (*error) {
            return 0;
        }
 
        if (0 == tail) {
            return 0;
        }
 
        unsigned int tailTarget = Inventory_read(this->four, tail, error);
 
        if (tailTarget == target) {
            return 1;
        }
 
        while (1) {
 
            tail = Inventory_read(this->two, tail, error);
 
            if (*error) {
                return 0;
            }
 
            if (0 == tail) {
                return 0;
            }
            
            tailTarget = Inventory_read(this->four, tail, error);
 
            if (*error) {
                return 0;
            }
 
            if (tailTarget == target) {
                return 1;
            }
        }
 
    } else {
 
        unsigned int head = Inventory_read(this->six, target, error);
 
        if (*error) {
            return 0;
        }
 
        if (0 == head) {
            return 0;
        }
 
        unsigned int headSource = Inventory_read(this->one, head, error);
 
        if (headSource == source) {
            return 1;
        }
 
        while (1) {
 
            head = Inventory_read(this->five, head, error);
 
            if (*error) {
                return 0;
            }
 
            if (0 == head) {
                return 0;
            }
            
            headSource = Inventory_read(this->one, head, error);
 
            if (*error) {
                return 0;
            }
 
            if (headSource == source) {
                return 1;
            }
        }
    }
}
 
void Graph_addEdge(struct Graph *this, unsigned int source, unsigned int target, int *error)
{
    if (Graph_hasEdge(this, source, target, error)) { // checks for identifiers as well
        return;
    }
 
    // start edge
 
    unsigned int edge = Inventory_getNext(this->one);
 
    Inventory_append(this->one, source, error);
 
    if (*error) {
        return;
    }
 
    Inventory_append(this->three, 0, error);
 
    if (*error) {
        return;
    }
 
    Inventory_append(this->four, target, error);
 
    if (*error) {
        return;
    }
 
    Inventory_append(this->six, 0, error);
 
    if (*error) {
        return;
    }
 
    // update counters
 
    unsigned int tailCounter = Inventory_read(this->three, source, error);
 
    if (*error) {
        return;
    }
 
    Inventory_update(this->three, source, tailCounter + 1, error);
 
    if (*error) {
        return;
    }
 
    unsigned int headCounter = Inventory_read(this->four, target, error);
 
    if (*error) {
        return;
    }
 
    Inventory_update(this->four, target, headCounter + 1, error);
 
    if (*error) {
        return;
    }
 
    // get last edges
 
    unsigned int lastTail = Inventory_read(this->five, source, error);
 
    if (*error) {
        return;
    }
 
    unsigned int lastHead = Inventory_read(this->six, target, error);
 
    if (*error) {
        return;
    }
 
    if (0 == lastTail && 0 == lastHead) {
 
        // finish edge
 
        Inventory_append(this->two, 0, error);
 
        if (*error) {
            return;
        }
 
        Inventory_append(this->five, 0, error);
 
        if (*error) {
            return;
        }
 
    } else if (0 != lastTail && 0 == lastHead) {
 
        // finish edge
 
        Inventory_append(this->two, lastTail, error);
 
        if (*error) {
            return;
        }
 
        Inventory_append(this->five, 0, error);
 
        if (*error) {
            return;
        }
 
        // update previous
 
        Inventory_update(this->three, lastTail, edge, error);
 
        if (*error) {
            return;
        }
 
    } else if (0 == lastTail && 0 != lastHead) {
 
        // finish edge
 
        Inventory_append(this->two, 0, error);
 
        if (*error) {
            return;
        }
 
        Inventory_append(this->five, lastHead, error);
 
        if (*error) {
            return;
        }
 
        // update previous
 
        Inventory_update(this->six, lastHead, edge, error);
 
        if (*error) {
            return;
        }
 
    } else if (0 != lastTail && 0 != lastHead) {
 
        // finish edge
 
        Inventory_append(this->two, lastTail, error);
 
        if (*error) {
            return;
        }
 
        Inventory_append(this->five, lastHead, error);
 
        if (*error) {
            return;
        }
 
        // update previous
 
        Inventory_update(this->three, lastTail, edge, error);
 
        if (*error) {
            return;
        }
 
        Inventory_update(this->six, lastHead, edge, error);
 
        if (*error) {
            return;
        }
    }
 
    // connect edge to vertices
 
    Inventory_update(this->five, source, edge, error);
 
    if (*error) {
        return;
    }
 
    Inventory_update(this->six, target, edge, error);
 
    if (*error) {
        return;
    }
}
 
unsigned int Graph_countSources(const struct Graph *this, unsigned int target, int *error)
{
    unsigned int identifier = Inventory_read(this->one, target, error);
 
    if (*error) {
        return 0;
    }
 
    if (identifier != target) {
        *error = ERROR_NOT_A_VERTEX;
        return 0;
    }
 
    unsigned int headCount = Inventory_read(this->four, target, error);
 
    if (*error) {
        return 0;
    }
 
    return headCount;
}
 
unsigned int Graph_countTargets(const struct Graph *this, unsigned int source, int *error)
{
    unsigned int identifier = Inventory_read(this->one, source, error);
 
    if (*error) {
        return 0;
    }
 
    if (identifier != source) {
        *error = ERROR_NOT_A_VERTEX;
        return 0;
    }
 
    unsigned int tailCount = Inventory_read(this->three, source, error);
 
    if (*error) {
        return 0;
    }
 
    return tailCount;
}
 
void Graph_readSources(const struct Graph *this, unsigned int target, unsigned int length, unsigned int *sources, int *error)
{
    if (0 == length) {
        return;
    }
 
    unsigned int identifier = Inventory_read(this->one, target, error);
 
    if (*error) {
        return;
    }
 
    if (identifier != target) {
        *error = ERROR_NOT_A_VERTEX;
        return;
    }
 
    unsigned int headCount = Inventory_read(this->four, target, error);
 
    if (*error) {
        return;
    }
 
    if (0 == headCount) {
        return;
    }
 
    if (headCount > length) {
        *error = ERROR_GRAPH_BUFFER_TOO_SMALL;
        return;
    }
 
    unsigned int head = Inventory_read(this->six, target, error);
 
    if (*error) {
        return;
    }
 
    if (0 == head) {
        return;
    }
 
    unsigned int headSource = Inventory_read(this->one, head, error);
 
    unsigned int index = 0;
 
    sources[index] = headSource;
 
    while (1) {
 
        if (index == length) {
            *error = ERROR_GRAPH_BUFFER_TOO_SMALL;
            return;
        }
 
        head = Inventory_read(this->five, head, error);
 
        if (*error) {
            return;
        }
 
        if (0 == head) {
            return;
        }
        
        headSource = Inventory_read(this->one, head, error);
 
        if (*error) {
            return;
        }
 
        index++;
 
        sources[index] = headSource;
    }
}
 
void Graph_readTargets(const struct Graph *this, unsigned int source, unsigned int length, unsigned int *targets, int *error)
{
    if (0 == length) {
        return;
    }
 
    unsigned int identifier = Inventory_read(this->one, source, error);
 
    if (*error) {
        return;
    }
 
    if (identifier != source) {
        *error = ERROR_NOT_A_VERTEX;
        return;
    }
        
    unsigned int tailCount = Inventory_read(this->three, source, error);
 
    if (*error) {
        return;
    }
        
    if (0 == tailCount) {
        return;
    }
 
    if ( tailCount > length) {
        *error = ERROR_GRAPH_BUFFER_TOO_SMALL;
        return;
    }
 
    unsigned int tail = Inventory_read(this->five, source, error);
 
    if (*error) {
        return;
    }
 
    if (0 == tail) {
        return;
    }
 
    unsigned int tailTarget = Inventory_read(this->four, tail, error);
        
    unsigned int index = 0;
 
    targets[index] = tailTarget;
 
    while (1) {
 
        if (index == length) {
            *error = ERROR_GRAPH_BUFFER_TOO_SMALL;
            return;
        }
 
        tail = Inventory_read(this->two, tail, error);
 
        if (*error) {
            return;
        }
 
        if (0 == tail) {
            return;
        }
        
        tailTarget = Inventory_read(this->four, tail, error);
 
        if (*error) {
            return;
        }
 
        index++;
 
        targets[index] = tailTarget;
    }
}
 
unsigned int Graph_readLastSource(const struct Graph *this, unsigned int target, int *error)
{
    unsigned int identifier = Inventory_read(this->one, target, error);
 
    if (*error) {
        return 0;
    }
 
    if (identifier != target) {
        *error = ERROR_NOT_A_VERTEX;
        return 0;
    }
 
    unsigned int head = Inventory_read(this->six, target, error);
 
    if (*error) {
        return 0;
    }
 
    if (0 == head) {
        return 0;
    }
 
    unsigned int headSource = Inventory_read(this->one, head, error);
 
    if (*error) {
        return 0;
    }
 
    return headSource;
}
 
unsigned int Graph_readLastTarget(const struct Graph *this, unsigned int source, int *error)
{
    unsigned int identifier = Inventory_read(this->one, source, error);
 
    if (*error) {
        return 0;
    }
 
    if (identifier != source) {
        *error = ERROR_NOT_A_VERTEX;
        return 0;
    }
 
    unsigned int tail = Inventory_read(this->five, source, error);
 
    if (*error) {
        return 0;
    }
 
    if (0 == tail) {
        return 0;
    }
 
    unsigned int tailTarget = Inventory_read(this->four, tail, error);
 
    if (*error) {
        return 0;
    }
 
    return tailTarget;
}
 
void Graph_addCluster(struct Graph *this, unsigned int length, unsigned int *vertices, int *error)
{
    if (0 == length) {
        return;
    }
 
    if (1 == length) {
        vertices[0] = Graph_addVertex(this, error);
        return;
    }
 
    for (unsigned int index = 0; index < length; index++) {
 
        vertices[index] = Graph_addVertex(this, error);
 
        if (*error) {
            return;
        }
 
        if (index > 0) {
 
            Inventory_update(this->two, vertices[index] - 1, vertices[index], error);
 
            if (*error) {
                return;
            }
        }
    }
 
    Inventory_update(this->two, vertices[length - 1], vertices[0], error);
}
 
void Graph_readCluster(const struct Graph *this, unsigned int predecessor, unsigned int length, unsigned int *vertices, int *error)
{
    if (0 == length) {
        return;
    }
 
    unsigned int identifier = Inventory_read(this->one, predecessor, error);
 
    if (*error) {
        return;
    }
 
    if (identifier != predecessor) {
        *error = ERROR_NOT_A_VERTEX;
        return;
    }
 
    if (1 == length) {
        vertices[0] = predecessor;
        return;
    }
 
    unsigned int count = 0;
    unsigned int vertex = predecessor;
 
    while (1) {
 
        vertices[count] = vertex;
 
        vertex = Inventory_read(this->two, vertex, error);
 
        if (*error) {
            return;
        }
 
        if (vertex == predecessor) {
            return;
        }
 
        count++;
 
        if (count >= length) {
            *error = ERROR_GRAPH_BUFFER_TOO_SMALL;
            return;
        }
    }
}
 
unsigned int Graph_protrudeCluster(struct Graph *this, unsigned int predecessor, int *error)
{
    unsigned int identifier = Inventory_read(this->one, predecessor, error);
 
    if (*error) {
        return 0;
    }
 
    if (identifier != predecessor) {
        *error = ERROR_NOT_A_VERTEX;
        return 0;
    }
 
    unsigned int successor = Inventory_read(this->two, predecessor, error);
 
    if (*error) {
        return 0;
    }
 
    if (0 == successor) {
 
        successor = Graph_addVertex(this, error);
 
        if (*error) {
            return 0;
        }
 
        Inventory_update(this->two, predecessor, successor, error);
 
        if (*error) {
            return 0;
        }
 
        Inventory_update(this->two, successor, predecessor, error);
 
        if (*error) {
            return 0;
        }
 
        return successor;
    }
 
    while (1) {
 
        unsigned int nextSuccessor = Inventory_read(this->two, successor, error);
 
        if (*error) {
            return 0;
        }
 
        if (nextSuccessor != predecessor) {
            successor = nextSuccessor;
            continue;
        }
 
        unsigned int newVertex = Graph_addVertex(this, error);
 
        if (*error) {
            return 0;
        }
 
        Inventory_update(this->two, predecessor, newVertex, error);
 
        if (*error) {
            return 0;
        }
 
        Inventory_update(this->two, newVertex, successor, error);
 
        return newVertex;
    }
}
 
unsigned int Graph_getLength(const struct Graph *this)
{
    return Inventory_getNext(this->one);
}
 
void Graph_import(struct Graph *this, unsigned int index, unsigned int one, unsigned int two, unsigned int three, unsigned int four, unsigned int five, unsigned int six, int *error)
{
    Inventory_appendUnchecked(this->one, one, error);
 
    if (*error) {
        return;
    }
    
    Inventory_appendUnchecked(this->two, two, error);
 
    if (*error) {
        return;
    }
    
    Inventory_appendUnchecked(this->three, three, error);
 
    if (*error) {
        return;
    }
    
    Inventory_appendUnchecked(this->four, four, error);
 
    if (*error) {
        return;
    }
    
    Inventory_appendUnchecked(this->five, five, error);
 
    if (*error) {
        return;
    }
    
    Inventory_appendUnchecked(this->six, six, error);
}
 
void Graph_export(struct Graph *this, unsigned int index, unsigned int *one, unsigned int *two, unsigned int *three, unsigned int *four, unsigned int *five, unsigned int *six, int *error)
{
    *one = Inventory_read(this->one, index, error);
 
    if (*error) {
        return;
    }
 
    *two = Inventory_read(this->two, index, error);
 
    if (*error) {
        return;
    }
 
    *three = Inventory_read(this->three, index, error);
 
    if (*error) {
        return;
    }
 
    *four = Inventory_read(this->four, index, error);
 
    if (*error) {
        return;
    }
 
    *five = Inventory_read(this->five, index, error);
 
    if (*error) {
        return;
    }
 
    *six = Inventory_read(this->six, index, error);
}