graph.h

Go to the documentation of this file.

#ifndef CMR_GRAPH_H
#define CMR_GRAPH_H
 
#include <cmr/env.h>
#include <cmr/element.h>
 
#include <stdio.h>
 
#ifdef __cplusplus
extern "C" {
#endif
 
typedef int CMR_GRAPH_NODE; 
typedef int CMR_GRAPH_EDGE; 
typedef int CMR_GRAPH_ITER; 
typedef struct
{
  int prev;     
  int next;     
  int firstOut; 
} CMR_GRAPH_NODE_DATA;
 
typedef struct
{
  int target; 
  int prev;   
  int next;   
} CMR_GRAPH_ARC_DATA;
 
typedef struct
{
  size_t numNodes;            
  size_t memNodes;            
  CMR_GRAPH_NODE_DATA* nodes; 
  int firstNode;              
  int freeNode;               
  size_t numEdges;            
  size_t memEdges;            
  CMR_GRAPH_ARC_DATA* arcs;   
  int freeEdge;               
} CMR_GRAPH;
 
static inline
size_t CMRgraphMemNodes(
  CMR_GRAPH* graph 
)
{
  assert(graph);
 
  return graph->memNodes;
}
 
static inline
size_t CMRgraphNumNodes(
  CMR_GRAPH* graph 
)
{
  assert(graph);
 
  return graph->numNodes;
}
 
static inline
size_t CMRgraphMemEdges(
  CMR_GRAPH* graph 
)
{
  assert(graph);
 
  return graph->memEdges;
}
 
static inline
size_t CMRgraphNumEdges(
  CMR_GRAPH* graph 
)
{
  assert(graph);
 
  return graph->numEdges;
}
 
static inline
CMR_GRAPH_NODE CMRgraphEdgeU(
  CMR_GRAPH* graph,  
  CMR_GRAPH_EDGE e   
)
{
  assert(graph);
 
  return graph->arcs[2*e+1].target;
}
 
static inline
CMR_GRAPH_NODE CMRgraphEdgeV(
  CMR_GRAPH* graph,  
  CMR_GRAPH_EDGE e   
)
{
  assert(graph);
 
  return graph->arcs[2*e].target;
}
 
CMR_EXPORT
CMR_ERROR CMRgraphCreateEmpty(
  CMR* cmr,             
  CMR_GRAPH** pgraph,  
  int memNodes,       
  int memEdges        
);
 
CMR_EXPORT
CMR_ERROR CMRgraphFree(
  CMR* cmr,           
  CMR_GRAPH** pgraph 
);
 
CMR_EXPORT
CMR_ERROR CMRgraphClear(
  CMR* cmr,         
  CMR_GRAPH* graph 
);
 
CMR_EXPORT
CMR_ERROR CMRgraphAddNode(
  CMR* cmr,               
  CMR_GRAPH* graph,      
  CMR_GRAPH_NODE* pnode  
);
 
CMR_EXPORT
CMR_ERROR CMRgraphAddEdge(
  CMR* cmr,               
  CMR_GRAPH* graph,      
  CMR_GRAPH_NODE u,      
  CMR_GRAPH_NODE v,      
  CMR_GRAPH_EDGE* pedge  
);
 
CMR_EXPORT
CMR_ERROR CMRgraphDeleteNode(
  CMR* cmr,           
  CMR_GRAPH* graph,  
  CMR_GRAPH_NODE v   
);
 
CMR_EXPORT
CMR_ERROR CMRgraphDeleteEdge(
  CMR* cmr,           
  CMR_GRAPH* graph,  
  CMR_GRAPH_EDGE e   
);
 
static inline
CMR_GRAPH_NODE CMRgraphNodesFirst(
  CMR_GRAPH* graph 
)
{
  assert(graph);
 
  return graph->firstNode;
}
 
static inline
bool CMRgraphNodesValid(
  CMR_GRAPH* graph,  
  CMR_GRAPH_NODE v   
)
{
  CMR_UNUSED(graph);
 
  assert(graph);
 
  return v >= 0;
}
 
static inline
CMR_GRAPH_NODE CMRgraphNodesNext(
  CMR_GRAPH* graph,  
  CMR_GRAPH_NODE v   
)
{
  assert(graph);
 
  return graph->nodes[v].next;
}
 
static inline
CMR_GRAPH_ITER CMRgraphIncFirst(
  CMR_GRAPH* graph,  
  CMR_GRAPH_NODE v   
)
{
  assert(graph);
 
  CMR_GRAPH_ITER i = graph->nodes[v].firstOut;
  while (true)
  {
    if (i < 0)
      return -1;
    if ((graph->arcs[i].target != (graph)->arcs[i ^ 1].target) || !(i & 0x1))
      return i;
    i = graph->arcs[i].next;
  }
}
 
static inline
bool CMRgraphIncValid(
  CMR_GRAPH* graph,  
  CMR_GRAPH_ITER i   
)
{
  CMR_UNUSED(graph);
 
  assert(graph);
 
  return i >= 0;
}
 
static inline
CMR_GRAPH_ITER CMRgraphIncNext(
  CMR_GRAPH* graph,  
  CMR_GRAPH_ITER i   
)
{
  assert(graph);
 
  while (true)
  {
    i = graph->arcs[i].next;
    if (i < 0)
      return -1;
    if (((graph)->arcs[i].target != (graph)->arcs[i ^ 1].target) || !(i & 0x1))
      return i;
  }
}
 
static inline
CMR_GRAPH_EDGE CMRgraphIncEdge(
  CMR_GRAPH* graph,  
  CMR_GRAPH_ITER i   
)
{
  CMR_UNUSED(graph);
 
  assert(graph);
 
  return i/2;
}
 
static inline
CMR_GRAPH_NODE CMRgraphIncSource(
  CMR_GRAPH* graph,  
  CMR_GRAPH_ITER i   
)
{
  return graph->arcs[i^1].target;
}
 
static inline
CMR_GRAPH_NODE CMRgraphIncTarget(
  CMR_GRAPH* graph,  
  CMR_GRAPH_ITER i   
)
{
  return graph->arcs[i].target;
}
 
static inline
CMR_GRAPH_ITER CMRgraphEdgesNext(
  CMR_GRAPH* graph,  
  CMR_GRAPH_ITER i   
)
{
  CMR_GRAPH_NODE source = graph->arcs[i ^ 1].target;
  CMR_GRAPH_ITER j = graph->arcs[i].next;
  while (true)
  {
    while (j >= 0)
    {
      if (!(j & 0x1))
        return j;
      j = graph->arcs[j].next;
    }
    source = graph->nodes[source].next;
    if (source < 0)
      return -1;
 
    j = graph->nodes[source].firstOut;
  }
}
 
static inline
CMR_GRAPH_ITER CMRgraphEdgesFirst(
  CMR_GRAPH* graph 
)
{
  assert(graph);
 
  for (CMR_GRAPH_NODE v = CMRgraphNodesFirst(graph); CMRgraphNodesValid(graph, v);
    v = CMRgraphNodesNext(graph, v))
  {
    CMR_GRAPH_ITER i = graph->nodes[v].firstOut;
    if (i >= 0)
    {
      /* We found some node with an incident edge. */
      if (i & 0x1)
        i = CMRgraphEdgesNext(graph, i);
      return i;
    }
  }
  return -1;
}
 
static inline
bool CMRgraphEdgesValid(
  CMR_GRAPH* graph,  
  CMR_GRAPH_ITER i   
)
{
  CMR_UNUSED(graph);
 
  assert(graph);
 
  return i >= 0;
}
 
static inline
CMR_GRAPH_EDGE CMRgraphEdgesEdge(
  CMR_GRAPH* graph,  
  CMR_GRAPH_ITER i   
)
{
  CMR_UNUSED(graph);
 
  assert(graph);
 
  return i/2;
}
 
CMR_EXPORT
CMR_ERROR CMRgraphPrint(
  CMR_GRAPH* graph, 
  FILE* stream      
);
 
CMR_EXPORT
CMR_ERROR CMRgraphMergeNodes(
  CMR* cmr,           
  CMR_GRAPH* graph,  
  CMR_GRAPH_NODE u,  
  CMR_GRAPH_NODE v   
);
 
 
CMR_EXPORT
CMR_ERROR CMRgraphCreateFromEdgeList(
  CMR* cmr,                   
  CMR_GRAPH** pgraph,        
  CMR_ELEMENT** pedgeElements,  
  char*** pnodeLabels,      
  FILE* stream              
);
 
#ifdef __cplusplus
}
#endif
 
#endif /* CMR_GRAPH_H */