~~~~~~~~~~~~~~~Graph.cpp~~~~~~~~~~~~~~~~~~

#include <stdlib.h>
#include "Graph.h"
#include <float.h>

struct Vertex {
    AdjacencyList adjacency_list;
    double           distance;
    int           predecessor;
};

void Graph_construct( Graph *object )
{
    object->vertex_count = 0;
    object->vertices = NULL;
}


void Graph_add_vertex( Graph *object, int vertex_id )
{
	object->vertex_count += 1;
	object->vertices[vertex_id];
	//add vertex to graph some how
}


void Graph_add_edge( Graph *object, int start_vertex, int end_vertex, double weight )
{
	//make sure they exist first.
	//Shouldnt break anything if it exists.
	Graph_add_vertex(object, start_vertex);
	Graph_add_vertex(object, end_vertex);

	//since they are all bi directional, add both vertexes to each others adjacency list somehow.

	object->vertices[start_vertex].adjacency_list; //some other magic here to finish the code

	//or maybe this but it has to be a pointer but its not
	object->vertices[start_vertex].adjacency_list->EdgeInfo->vertex_id=end_vertex;

	//maybe this
	object->vertices[start_vertex].adjacency_list.count += 1;
		//someother stuff somehow

	//then
	//also add the weight somewhere to the edge's info somehow, probably EdgeInfo from AdjacencyList. somehow

	//should be done after that.
}


void Graph_destroy( Graph *object )
{
    if( object->vertices != NULL ) {
        for( int i = 0; i < object->vertex_count; ++i ) {
            AdjacencyList_destroy( &object->vertices[i].adjacency_list );
        }
        free( object->vertices );
    }
}


int bellman_ford( Graph *object, int start_vertex )
{
	// Step 1: initialize graph
	for (int i = 0; i < object->vertex_count; ++i) {
		object->vertices[i].distance = DBL_MAX;
		object->vertices[i].predecessor = -1; // -1 is no predecessor
	}
	object->vertices[start_vertex].distance = 0.0;

	// Step 2: relax edges repeatedly //44.40
	for (int i = 0; i < object->vertex_count; ++i) {
		//for each edge figure out weight
			//if new weight cost < current weight cost
				//current weight cost = new weight cost
				//predecessor = the cheaper vertex from the new weight cost
	}
	// Step 3: check for negative-weight cycles
	//code for that; something if

    return 0;


}


void print_path_to( Graph *object, int destination_vertex )
{

}
~~~~~~~~~~~~Graph.h~~~~~~~~~~~~~~~~~

#ifndef GRAPH_H
#define GRAPH_H

#include "AdjacencyList.h"

struct Vertex;

typedef struct {
    int vertex_count;
    struct Vertex *vertices;
} Graph;

void Graph_construct( Graph *object );
void Graph_add_vertex( Graph *object, int vertex_id );
void Graph_add_edge( Graph *object, int start_vertex, int end_vertex, double weight );
void Graph_destroy( Graph *object );

// Executes the Bellman-Ford algorithm on the graph using the given start vertex to find the
// shortest path to all other vertices. This function mutates the graph object by updating
// distance and predecessor information on the vertices of the graph. Returns true if the
// algorithm is successful, false if the graph contains a negative weight cycle reachable from
// the start vertex.
//
int bellman_ford( Graph *object, int start_vertex );

// Outputs to stdout a representation of the path from to the destination vertex starting from
// the previously supplied start vertex. This function can only be used after a successful call
// to bellman_ford. The precise format of the output is unspecified.
//
void print_path_to( Graph *object, int destination_vertex );

#endif

~~~~~~~~~~~~~~AdjacencyList.cpp~~~~~~~~~~~~~~~~

#include <assert.h>
#include <stdlib.h>
#include "AdjacencyList.h"

struct AdjacencyListNode {
    EdgeInfo data;
    struct AdjacencyListNode *next;
};


void AdjacencyList_construct( AdjacencyList *object )
{
    assert( object != NULL );

    object->first = NULL;
    object->last  = NULL;
    object->count = 0;
}


void AdjacencyList_destroy( AdjacencyList *object )
{
    assert( object != NULL );

    // NOTE: The ability to declare variables after executable statements is a C99 (or C++) feature.
    struct AdjacencyListNode *current = object->first;
    while( current != NULL ) {
        struct AdjacencyListNode *temp = current->next;

        // NOTE: This assumes EdgeInfo has no special destruction needs.
        free( current );
        current = temp;
    }

    // Put the SingleList object into a well defined state.
    AdjacencyList_construct( object );
}


void AdjacencyList_copy( AdjacencyList *destination, const AdjacencyList *source )
{
    assert( destination != NULL && source != NULL );

    AdjacencyList_destroy( destination );

    AdjacencyListNode *current = source->first;
    while( current != NULL ) {
        AdjacencyList_push_back( destination, &current->data );
        current = current->next;
    }
}


size_t AdjacencyList_size( const AdjacencyList *object )
{
    assert( object != NULL );

    return object->count;
}


EdgeInfo AdjacencyList_front( const AdjacencyList *object )
{
    assert( object != NULL && object->first != NULL );

    return object->first->data;
}


EdgeInfo AdjacencyList_back( const AdjacencyList *object )
{
    assert( object != NULL && object->last != NULL );

    return object->last->data;
}


int AdjacencyList_equal( const AdjacencyList *object_1, const AdjacencyList *object_2 )
{
    assert( object_1 != NULL && object_2 != NULL );

    if( object_1->count != object_2->count ) return 0;

    // The counts are equal...
    AdjacencyListNode *current_1 = object_1->first;
    AdjacencyListNode *current_2 = object_2->first;

    while( current_1 != NULL ) {
        // NOTE: Too bad EdgeInfo can't be compared with !=.
        if( current_1->data.vertex_id != current_2->data.vertex_id ||
            current_1->data.weight  != current_2->data.weight) return 0;
        current_1 = current_1->next;
        current_2 = current_2->next;
    }
    return 1;
}


void AdjacencyList_push_front( AdjacencyList *object, const EdgeInfo *item )
{
    assert( object != NULL && item != NULL );

    struct AdjacencyListNode *new_node =
        ( struct AdjacencyListNode * )malloc( sizeof( struct AdjacencyListNode ) );

    // TODO: Maybe return an error indication if the allocation fails?
    if( new_node == NULL ) return;

    // NOTE: This assumes EdgeInfo can be copied with assignment.
    new_node->data = *item;
    new_node->next = object->first;
    object->first = new_node;

    // If the list was empty, it must be handled in a special way.
    if( object->last == NULL ) {
        object->last = object->first;
    }
    object->count++;
}


EdgeInfo AdjacencyList_pop_front( AdjacencyList *object )
{
    assert( object != NULL && object->first != NULL );

    // NOTE: This assumes EdgeInfo can be initialized with assignment.
    EdgeInfo temp_item = object->first->data;
    struct AdjacencyListNode *temp = object->first;
    object->first = object->first->next;

    // NOTE: This assumes EdgeInfo has no special destruction needs.
    free( temp );
    object->count--;
    return temp_item;
}


void AdjacencyList_push_back( AdjacencyList *object, const EdgeInfo *item )
{
    assert( object != NULL && item != NULL );

    struct AdjacencyListNode *new_node =
        ( struct AdjacencyListNode * )malloc( sizeof( struct AdjacencyListNode ) );

    // TODO: Maybe return an error indication if the allocation fails?
    if( new_node == NULL ) return;

    // NOTE: This assumes EdgeInfo can be copied with assignment.
    new_node->data = *item;
    new_node->next = NULL;

    if( object->count == 0 ) {
        object->first = new_node;
    }
    else {
        object->last->next = new_node;
    }
    object->last = new_node;
    object->count++;
}


AdjacencyListIterator AdjacencyList_begin( AdjacencyList *object )
{
    assert( object != NULL );

    AdjacencyListIterator result;
    result.object = object;
    result.current = object->first;
    return result;
}


AdjacencyListIterator AdjacencyList_end( AdjacencyList *object )
{
    assert( object != NULL );

    AdjacencyListIterator result;
    result.object = object;
    result.current = NULL;
    return result;
}


int AdjacencyList_equal_iterator( AdjacencyListIterator it_1, AdjacencyListIterator it_2 )
{
    // We really want to say the iterators are valid. This doesn't completely do that.
    assert( it_1.object != NULL && it_2.object != NULL );

    return (it_1.object == it_2.object) && (it_1.current == it_2.current);
}


AdjacencyListIterator AdjacencyList_next( AdjacencyListIterator it )
{
    // We'd also like to say that it.current points into the list controlled by object.
    assert( it.object != NULL  && it.current != NULL );

	AdjacencyListIterator result;
	result.object = it.object;
	result.current = it.current->next;
	return result;
}


EdgeInfo *AdjacencyList_get( AdjacencyListIterator it )
{
    assert( it.object != NULL && it.current != NULL );
	return &it.current->data;
}


void AdjacencyList_insert_after( AdjacencyListIterator it, const EdgeInfo *item )
{
    assert( it.object != NULL && it.current != NULL && item != NULL );
	struct AdjacencyListNode *new_node =
		( struct AdjacencyListNode * )malloc( sizeof( struct AdjacencyListNode ) );

	// TODO: Maybe return an error indication if the allocation fails?
	if( new_node == NULL ) return;

	// This assumes EdgeInfo can be copied with assignment.
	new_node->data = *item;
	new_node->next = it.current->next;

	it.current->next = new_node;
	it.object->count++;

    // If we are inserting after the last node (appending), we need to update the last pointer.
    if( it.current == it.object->last ) {
        it.object->last = new_node;
    }
}

~~~~~~~~~~~~~~~~~~~~~~AdjacencyList.h~~~~~~~~~~~~~~~~~~~~

#ifndef ADJACENCYLIST_H
#define ADJACENCYLIST_H

#include <stddef.h>

struct EdgeInfo {
    int vertex_id;  // The edge "points" at this vertex.
    double weight;  // The weight on the edge.
};

typedef struct EdgeInfo EdgeInfo;

struct AdjacencyListNode;

typedef struct {
    struct AdjacencyListNode *first;
    struct AdjacencyListNode *last;
    size_t count;
} AdjacencyList;

typedef struct {
    AdjacencyList *object;
    struct AdjacencyListNode *current;
} AdjacencyListIterator;

// Lifecycle operations...
void      AdjacencyList_construct( AdjacencyList *object );
void      AdjacencyList_destroy( AdjacencyList *object );
void      AdjacencyList_copy( AdjacencyList *destination, const AdjacencyList *source );

// Non-modifying list operations...
size_t    AdjacencyList_size( const AdjacencyList *object );
EdgeInfo  AdjacencyList_front( const AdjacencyList *object );
EdgeInfo  AdjacencyList_back( const AdjacencyList *object );
int       AdjacencyList_equal( const AdjacencyList *object_1, const AdjacencyList *object_2 );

// Modifying list operations...
void      AdjacencyList_push_front( AdjacencyList *object, const EdgeInfo *item );
EdgeInfo  AdjacencyList_pop_front( AdjacencyList *object );
void      AdjacencyList_push_back( AdjacencyList *object, const EdgeInfo *item );

// Iterator operations...
AdjacencyListIterator AdjacencyList_begin( AdjacencyList *object );
AdjacencyListIterator AdjacencyList_end( AdjacencyList *object );
int                   AdjacencyList_equal_iterator( AdjacencyListIterator it_1, AdjacencyListIterator it_2 );
AdjacencyListIterator AdjacencyList_next( AdjacencyListIterator it );
EdgeInfo             *AdjacencyList_get( AdjacencyListIterator it );
void                  AdjacencyList_insert_after( AdjacencyListIterator it, const EdgeInfo *item );

#endif