Graph class

Name

Graph class -- 

Synopsis


#include <gts.h>


#define     GTS_GNODE_CLASS                 (klass)
#define     GTS_GNODE                       (obj)
#define     GTS_IS_GNODE                    (obj)
#define     GTS_GNODE_NEIGHBOR              (n,e)
struct      GtsGNodeClass;
struct      GtsGNode;

GtsGNodeClass* gts_gnode_class              (void);
GtsGNode*   gts_gnode_new                   (GtsGNodeClass *klass);
guint       gts_gnode_degree                (GtsGNode *n,
                                             GtsGraph *g);
void        gts_gnode_foreach_edge          (GtsGNode *n,
                                             GtsGraph *g,
                                             GtsFunc func,
                                             gpointer data);
void        gts_gnode_foreach_neighbor      (GtsGNode *n,
                                             GtsGraph *g,
                                             GtsFunc func,
                                             gpointer data);
gfloat      gts_gnode_weight                (GtsGNode *n);
gfloat      gts_gnode_move_cost             (GtsGNode *n,
                                             GtsGraph *src,
                                             GtsGraph *dst);

#define     GTS_GEDGE_CLASS                 (klass)
#define     GTS_GEDGE                       (obj)
#define     GTS_IS_GEDGE                    (obj)
struct      GtsGEdgeClass;
struct      GtsGEdge;

GtsGEdgeClass* gts_gedge_class              (void);
GtsGEdge*   gts_gedge_new                   (GtsGEdgeClass *klass,
                                             GtsGNode *n1,
                                             GtsGNode *n2);
gfloat      gts_gedge_weight                (GtsGEdge *e);
#define     gts_gedge_connects              (e, a1, a2)

#define     GTS_GRAPH_CLASS                 (klass)
#define     GTS_GRAPH                       (obj)
#define     GTS_IS_GRAPH                    (obj)
struct      GtsGraphClass;
struct      GtsGraph;

GtsGraphClass* gts_graph_class              (void);
GtsGraph*   gts_graph_new                   (GtsGraphClass *klass,
                                             GtsGNodeClass *node_class,
                                             GtsGEdgeClass *edge_class);
guint       gts_graph_read                  (GtsGraph *g,
                                             GtsFile *fp);
guint       gts_graph_read_jostle           (GtsGraph *g,
                                             GtsFile *fp);
void        gts_graph_write                 (GtsGraph *g,
                                             FILE *fp);
void        gts_graph_write_dot             (GtsGraph *g,
                                             FILE *fp);
void        gts_graph_print_stats           (GtsGraph *g,
                                             FILE *fp);
void        gts_graph_foreach_edge          (GtsGraph *g,
                                             GtsFunc func,
                                             gpointer data);
struct      GtsGraphTraverse;
enum        GtsTraverseType;
GtsGraphTraverse* gts_graph_traverse_new    (GtsGraph *g,
                                             GtsGNode *n,
                                             GtsTraverseType type,
                                             gboolean reinit);
GtsGNode*   gts_graph_traverse_next         (GtsGraphTraverse *t);
GtsGNode*   gts_graph_traverse_what_next    (GtsGraphTraverse *t);
void        gts_graph_traverse_destroy      (GtsGraphTraverse *t);
guint       gts_graph_edges_cut             (GtsGraph *g);
gfloat      gts_graph_edges_cut_weight      (GtsGraph *g);
guint       gts_graph_distance_sum          (GtsGraph *g,
                                             GtsGNode *center);
GtsGNode*   gts_graph_farthest              (GtsGraph *g,
                                             GSList *gnodes);
gfloat      gts_graph_weight                (GtsGraph *g);

#define     GTS_FNODE_CLASS                 (klass)
#define     GTS_FNODE                       (obj)
#define     GTS_IS_FNODE                    (obj)
struct      GtsFNode;
struct      GtsFNodeClass;

GtsFNodeClass* gts_fnode_class              (void);
GtsFNode*   gts_fnode_new                   (GtsFNodeClass *klass,
                                             GtsFace *f);

GtsGraph*   gts_surface_graph_new           (GtsGraphClass *klass,
                                             GtsSurface *s);
GtsSurface* gts_surface_graph_surface       (GtsGraph *surface_graph,
                                             GtsSurface *s);
GtsGraph*   gts_segments_graph_new          (GtsGraphClass *klass,
                                             GSList *segments);

Description

Details

GTS_GNODE_CLASS()

#define     GTS_GNODE_CLASS(klass)

klass :


GTS_GNODE()

#define     GTS_GNODE(obj)

obj :


GTS_IS_GNODE()

#define     GTS_IS_GNODE(obj)

obj :


GTS_GNODE_NEIGHBOR()

#define GTS_GNODE_NEIGHBOR(n,e)   (GTS_GEDGE (e)->n1 == n ? GTS_GEDGE (e)->n2 : GTS_GEDGE (e)->n2 == n ? GTS_GEDGE (e)->n1 : NULL)

n :

e :


struct GtsGNodeClass

struct GtsGNodeClass {

  GtsSListContainerClass parent_class;

  gfloat (* weight) (GtsGNode *);
  void   (* write)  (GtsGNode *, FILE *);
};


struct GtsGNode

struct GtsGNode {

  GtsSListContainer container;

  guint level;
};


gts_gnode_class ()

GtsGNodeClass* gts_gnode_class              (void);

Returns :

the GtsGNodeClass.


gts_gnode_new ()

GtsGNode*   gts_gnode_new                   (GtsGNodeClass *klass);

klass :

a GtsGNodeClass.

Returns :

a new GtsGNode.


gts_gnode_degree ()

guint       gts_gnode_degree                (GtsGNode *n,
                                             GtsGraph *g);

n :

a GtsGNode.

g :

a GtsGraph or NULL.

Returns :

the number of neighbors of n (belonging to g if g is not NULL).


gts_gnode_foreach_edge ()

void        gts_gnode_foreach_edge          (GtsGNode *n,
                                             GtsGraph *g,
                                             GtsFunc func,
                                             gpointer data);

Calls func for each GtsGEdge connecting n to another GtsGNode (belonging to g if g is not NULL.

n :

a GtsGNode.

g :

a GtsGraph or NULL.

func :

a GtsFunc.

data :

user data to be passed to func.


gts_gnode_foreach_neighbor ()

void        gts_gnode_foreach_neighbor      (GtsGNode *n,
                                             GtsGraph *g,
                                             GtsFunc func,
                                             gpointer data);

Calls func for each neighbor GtsGNode of n (belonging to g if g is not NULL.

n :

a GtsGNode.

g :

a GtsGraph or NULL.

func :

a GtsFunc.

data :

user data to be passed to func.


gts_gnode_weight ()

gfloat      gts_gnode_weight                (GtsGNode *n);

n :

a GtsGNode.

Returns :

the weight of n as defined by the weight() method of the GtsGNodeClass.


gts_gnode_move_cost ()

gfloat      gts_gnode_move_cost             (GtsGNode *n,
                                             GtsGraph *src,
                                             GtsGraph *dst);

n :

a GtsGNode.

src :

a GtsGraph containing n.

dst :

another GtsGraph.

Returns :

the cost (increase in the sum of the weights of the edges cut) of moving n from src to dst.


GTS_GEDGE_CLASS()

#define     GTS_GEDGE_CLASS(klass)

klass :


GTS_GEDGE()

#define     GTS_GEDGE(obj)

obj :


GTS_IS_GEDGE()

#define     GTS_IS_GEDGE(obj)

obj :


struct GtsGEdgeClass

struct GtsGEdgeClass {

  GtsContaineeClass parent_class;

  GtsGEdge * (* link)   (GtsGEdge * e, GtsGNode * n1, GtsGNode * n2);
  gfloat     (* weight) (GtsGEdge * e);
  void       (* write)  (GtsGEdge * e, FILE * fp);
};


struct GtsGEdge

struct GtsGEdge {

  GtsContainee containee;

  GtsGNode * n1;
  GtsGNode * n2;
};


gts_gedge_class ()

GtsGEdgeClass* gts_gedge_class              (void);

Returns :

the GtsGEdgeClass.


gts_gedge_new ()

GtsGEdge*   gts_gedge_new                   (GtsGEdgeClass *klass,
                                             GtsGNode *n1,
                                             GtsGNode *n2);

klass :

a GtsGEdgeClass.

n1 :

a GtsGNode.

n2 :

another GtsGNode.

Returns :

a new GtsGEdge linking n1 and n2.


gts_gedge_weight ()

gfloat      gts_gedge_weight                (GtsGEdge *e);

e :

a GtsGEdge.

Returns :

the weight of edge e as defined by the weight() method of GtsGEdgeClass.


gts_gedge_connects()

#define     gts_gedge_connects(e, a1, a2)

e :

a1 :

a2 :


GTS_GRAPH_CLASS()

#define     GTS_GRAPH_CLASS(klass)

klass :


GTS_GRAPH()

#define     GTS_GRAPH(obj)

obj :


GTS_IS_GRAPH()

#define     GTS_IS_GRAPH(obj)

obj :


struct GtsGraphClass

struct GtsGraphClass {

  GtsHashContainerClass parent_class;

  gfloat (* weight) (GtsGraph *);
};


struct GtsGraph

struct GtsGraph {

  GtsHashContainer object;

  GtsGNodeClass * node_class;
  GtsGEdgeClass * edge_class;
};


gts_graph_class ()

GtsGraphClass* gts_graph_class              (void);

Returns :

the GtsGraphClass.


gts_graph_new ()

GtsGraph*   gts_graph_new                   (GtsGraphClass *klass,
                                             GtsGNodeClass *node_class,
                                             GtsGEdgeClass *edge_class);

klass :

a GtsGraphClass.

node_class :

a GtsGNodeClass.

edge_class :

a GtsGEdgeClass.

Returns :

a new GtsGraph using node_class and edge_class as node types.


gts_graph_read ()

guint       gts_graph_read                  (GtsGraph *g,
                                             GtsFile *fp);

Adds to g the data read from fp. The format of the file pointed to by fp is as described in gts_graph_write().

g :

a GtsGraph.

fp :

a GtsFile.

Returns :

0 if successful or the line number at which the parsing stopped in case of error (in which case the error field of fp is set).


gts_graph_read_jostle ()

guint       gts_graph_read_jostle           (GtsGraph *g,
                                             GtsFile *fp);

Adds to g the nodes and edges defined in the file pointed to by fp. This file must use the Jostle "graph" ASCII format. The nodes created are of type GtsNGNode and their identities are the line number at which they appear in fp.

g :

a GtsGraph.

fp :

a GtsFile.

Returns :

0 if the lecture was successful, the line number at which an error occured otherwise (in which case the error field of fp is set).


gts_graph_write ()

void        gts_graph_write                 (GtsGraph *g,
                                             FILE *fp);

Writes in the file fp an ASCII representation of g. The file format is as follows.

All the lines beginning with GTS_COMMENTS are ignored. The first line contains two unsigned integers separated by spaces. The first integer is the number of nodes, nn, the second is the number of edges, ne.

Follows nn lines containing node description. Follows ne lines containing the two indices (starting from one) of the nodes of each edge.

The format described above is the least common denominator to all GTS files. Consistent with an object-oriented approach, the GTS file format is extensible. Each of the lines of the file can be extended with user-specific attributes accessible through the read() and write() virtual methods of each of the objects written (graph, nodes or edges). When read with different object classes, these extra attributes are just ignored.

g :

a GtsGraph.

fp :

a file pointer.


gts_graph_write_dot ()

void        gts_graph_write_dot             (GtsGraph *g,
                                             FILE *fp);

Writes in the file fp an ASCII representation of g in the dot format of AT&T Bell Labs.

g :

a GtsGraph.

fp :

a file pointer.


gts_graph_print_stats ()

void        gts_graph_print_stats           (GtsGraph *g,
                                             FILE *fp);

Writes to fp a summary of the properties of g.

g :

a GtsGraph.

fp :

a file pointer.


gts_graph_foreach_edge ()

void        gts_graph_foreach_edge          (GtsGraph *g,
                                             GtsFunc func,
                                             gpointer data);

Calls func for each GtsEdge of g.

g :

a GtsGraph.

func :

a GtsFunc.

data :

user data to be passed to func.


struct GtsGraphTraverse

struct GtsGraphTraverse;


enum GtsTraverseType

typedef enum   { GTS_BREADTH_FIRST
               }   GtsTraverseType;


gts_graph_traverse_new ()

GtsGraphTraverse* gts_graph_traverse_new    (GtsGraph *g,
                                             GtsGNode *n,
                                             GtsTraverseType type,
                                             gboolean reinit);

g :

a GtsGraph.

n :

a GtsGNode belonging to g.

type :

the type of traversal.

reinit :

if TRUE, the traversal is reinitialized.

Returns :

a new GtsGraphTraverse initialized for the traversal of g of type type, starting from n.


gts_graph_traverse_next ()

GtsGNode*   gts_graph_traverse_next         (GtsGraphTraverse *t);

t :

a GtsGraphTraverse.

Returns :

the next GtsGNode of the traversal defined by t or NULL if the traversal is complete.


gts_graph_traverse_what_next ()

GtsGNode*   gts_graph_traverse_what_next    (GtsGraphTraverse *t);

t :

a GtsGraphTraverse.

Returns :

the next GtsGNode of the traversal defined by t or NULL if the traversal is complete but without advancing the traversal.


gts_graph_traverse_destroy ()

void        gts_graph_traverse_destroy      (GtsGraphTraverse *t);

Frees all the memory allocated for t.

t :

a GtsGraphTraverse.


gts_graph_edges_cut ()

guint       gts_graph_edges_cut             (GtsGraph *g);

g :

a GtsGraph.

Returns :

the number of edges of g connecting nodes belonging to g to nodes not belonging to g.


gts_graph_edges_cut_weight ()

gfloat      gts_graph_edges_cut_weight      (GtsGraph *g);

g :

a GtsGraph.

Returns :

the sum of the weights of the edges of g connecting nodes belonging to g to nodes not belonging to g.


gts_graph_distance_sum ()

guint       gts_graph_distance_sum          (GtsGraph *g,
                                             GtsGNode *center);

g :

a GtsGraph.

center :

a GtsGNode of g.

Returns :

the sum of the distances between all the other GtsGNode of g and center.


gts_graph_farthest ()

GtsGNode*   gts_graph_farthest              (GtsGraph *g,
                                             GSList *gnodes);

g :

a GtsGraph.

gnodes :

a list of GtsGNode belonging to g.

Returns :

the GtsGNode belonging to g and farthest from all the nodes in gnodes (hmmm, definition of "farthest"?).


gts_graph_weight ()

gfloat      gts_graph_weight                (GtsGraph *g);

g :

a GtsGraph.

Returns :

the weight of graph g as defined by the weight() method of GtsGraphClass.


GTS_FNODE_CLASS()

#define     GTS_FNODE_CLASS(klass)

klass :


GTS_FNODE()

#define     GTS_FNODE(obj)

obj :


GTS_IS_FNODE()

#define     GTS_IS_FNODE(obj)

obj :


struct GtsFNode

struct GtsFNode {

  GtsGNode node;

  GtsFace * f;
};


struct GtsFNodeClass

struct GtsFNodeClass {

  GtsGNodeClass parent_class;
};


gts_fnode_class ()

GtsFNodeClass* gts_fnode_class              (void);

Returns :

the GtsFNodeClass.


gts_fnode_new ()

GtsFNode*   gts_fnode_new                   (GtsFNodeClass *klass,
                                             GtsFace *f);

klass :

a GtsFNodeClass.

f :

a GtsFace.

Returns :

a new GtsFNode associated with face f.


gts_surface_graph_new ()

GtsGraph*   gts_surface_graph_new           (GtsGraphClass *klass,
                                             GtsSurface *s);

klass :

a GtsGraphClass.

s :

a GtsSurface.

Returns :

a new GtsGraph representing the connectivity of the faces of s. This graph uses GtsFGNode as nodes which allows to store the dependencies between nodes and faces of s.


gts_surface_graph_surface ()

GtsSurface* gts_surface_graph_surface       (GtsGraph *surface_graph,
                                             GtsSurface *s);

surface_graph :

a GtsGraph using GtsFGNode as nodes.

s :

a GtsSurface.

Returns :

a new GtsSurface using the same classes as s and composed of the faces defined by surface_graph.


gts_segments_graph_new ()

GtsGraph*   gts_segments_graph_new          (GtsGraphClass *klass,
                                             GSList *segments);

klass :

a GtsGraphClass.

segments :

a list of GtsSegment.

Returns :

a new GtsGraph representing the connectivity of the segments in segments.