Graph.c

// Graph.c
// Seung Hoon Park

// Type Synonums

typedef unsigned int nat;
typedef int enat; // negative numbers will be treated as infinity for this purpose
// typedef float ereal; // the INFINITY constnat in math.h will be used for infinity

typedef nat IVertex;
typedef nat IEdge_Id;
typedef nat ICost;
typedef enat IDist; // use enat for now to avoid messy float calculations
typedef enat IPEdge;
typedef enat INum;

typedef struct IEdge {
	IVertex first;
	IVertex second;
} IEdge;

typedef struct IGraph {
	nat num_vertices;
	nat num_edges;
	IEdge *arcs;
} IGraph;

// Abbreviations

#define ivertex_cnt(g) g->num_vertices

#define iedge_cnt(g) g->num_edges

#define iarcs(g, e) g->arcs[e]

// Procedures

int is_wellformed(IGraph *g) {
	IEdge e;
	nat i;
	for(i = 0; i < iedge_cnt(g); i++) {
		e = iarcs(g, i);
		if(ivertex_cnt(g) <= e.first) return 0;
		if(ivertex_cnt(g) <= e.second) return 0;
	}
	return 1;
}

int trian(IGraph *g, IDist *dist, ICost *c) {
	IEdge_Id edge_id;
	for(edge_id = 0; edge_id < iedge_cnt(g); edge_id++) {
		if (dist[iarcs(g, edge_id).second] > dist[iarcs(g, edge_id).first] + c[edge_id]) return 0;
	}
	return 1;
}

int just(IGraph *g, IDist *dist, ICost *c, IVertex s, INum *enu, IPEdge *pred) {
	IEdge_Id edge_id;
	IVertex v;
	for(v = 0; v < ivertex_cnt(g); v++) {
		edge_id = pred[v];
		if(v != s) {
			if(enu[v] >= 0) {
				if(edge_id >= iedge_cnt(g)) return 0;
				if(iarcs(g, edge_id).second != v) return 0;
				if(dist[v] != dist[iarcs(g, edge_id).first] + c[edge_id]) return 0;
				if(enu[v] != enu[iarcs(g, edge_id).first] + 1) return 0; // onum
			}
		}
	}
	return 1;
}

int no_path(IGraph *g, IDist *dist, INum *enu) {
	for(IVertex v = 0; v < ivertex_cnt(g); v++) {
		if(dist[v] < 0) {
			if(enu[v] >= 0) return 0;
		}
		else {
			if(enu[v] < 0) return 0;
		}
	}
	return 1;
}

int pos_cost(IGraph *g, ICost *c) {
	IEdge_Id edge_id;
	for(edge_id = 0; edge_id < iedge_cnt(g); edge_id++) {
		if(c[edge_id] < 0) return 0;
	}
	return 1;
}

int check_basic_just_sp(IGraph *g, IDist *dist, ICost *c, IVertex s, INum *enu, IPEdge *pred) {
	if(!is_wellformed(g)) return 0;
	if(dist[s] > 0) return 0;
	if(!trian(g, dist, c)) return 0;
	if(!just(g, dist, c, s, enu, pred)) return 0;
	return 1;
}

int check_sp(IGraph *g, IDist *dist, ICost *c, IVertex s, INum *enu, IPEdge *pred) {
	if(!check_basic_just_sp(g, dist, c, s, enu, pred)) return 0;
	if(s >= ivertex_cnt(g)) return 0;
	if(dist[s] != 0) return 0;
	if(!no_path(g, dist, enu)) return 0;
	if(!pos_cost(g, c)) return 0;
	return 1;
}

int main(int argc, char **argv) {
	return 0;
}