paths.c File Reference

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "MALLOC.h"
#include "machine.h"
#include "paths.h"

Include dependency graph for paths.c:

Go to the source code of this file.

Functions
void cerro	__PARAMS ((char *str))
void	NodesToPath (int *nodes, int **p, int *psize, int *la, int *lp, int *ls)
void C2F()	prevn2p (int *i, int *j, int *m, int *n, int *la, int *lp, int *ls, int *direct, int *pln, int **p, int *psize)
void C2F()	ns2p (int *nodes, int *nsize, int **p, int *psize, int *la, int *lp, int *ls, int *n)
void C2F()	p2ns (int *p, int *psize, int **nodes, int *nsize, int *la, int *lp, int *ls, int *direct, int *m, int *n)
void C2F()	edge2st (int *n, int *alpha, int **tree, int *treesize)
void C2F()	prevn2st (int *n, int *nodes, int **tree, int *treesize, int *la, int *lp, int *ls)
Variables
static char	str [80]

---

Function Documentation

void cerro __PARAMS

(

(char *str)

)

void C2F() edge2st	(	int *	n,
		int *	alpha,
		int **	tree,
		int *	treesize
	)

edge2st_ computes a spanning tree (root = node 1) from an array alpha of connecting edge numbers

Definition at line 189 of file paths.c.

References cerro(), MALLOC, and NULL.

{
  int i;
  *treesize = *n - 1;
  if ((*tree = (int *)MALLOC(*treesize * sizeof(int))) == NULL) {
    cerro("Running out of memory");
    return;
  }
  for (i = 1; i <= *n - 1; i++) {
    if (alpha[i] < 0) {
      *treesize=0;
      return;
    }
    (*tree)[i-1] = alpha[i];
  }
}

Here is the call graph for this function:

void NodesToPath	(	int *	nodes,
		int **	p,
		int *	psize,
		int *	la,
		int *	lp,
		int *	ls
	)

NodesToPath converts a vector with node numbers into a path: NODES = [Nn,...,N2,N1] => PATH = [A1,A2,...,An-1] with Ai = (Ni,Ni+1) n = *psize + 1

Parameters:

	nodes
	p
	psize
	la
	lp
	ls

Definition at line 13 of file paths.c.

References a, i, j, n1, and n2.

Referenced by prevn2p().

{
  int a,i,j,n1,n2;
  for (i = 1; i <= *psize; i++) {
    n1 = nodes[*psize-i+1]; n2 = nodes[*psize-i];
    a = 0;
    for (j = lp[n1-1]; j <= lp[n1]-1; j++) {
      if (n2 == ls[j-1]) {
        a = la[j-1];
        break;
      }
    }
    if (a == 0) {
      *psize = 0;
      return;
    }
    (*p)[i-1] = a;
  }
}

Here is the caller graph for this function:

void C2F() ns2p	(	int *	nodes,
		int *	nsize,
		int **	p,
		int *	psize,
		int *	la,
		int *	lp,
		int *	ls,
		int *	n
	)

ns2p_ converts a node set into a path: NODES = [N1,N2,...,Nn] => PATH = [A1,A2,...,An-1] with Ai = (Ni,Ni+1) *psize = *nsize - 1

Definition at line 75 of file paths.c.

References a, cerro(), MALLOC, n1, n2, and NULL.

{
  int a,i,j,n1,n2;
  *psize = *nsize - 1;
  if ((*p = (int *)MALLOC(*psize * sizeof(int))) == NULL) {
    cerro("Running out of memory");
    return;
  }
  for (i = 1; i <= *psize; i++) {
    n1 = nodes[i-1];
    if ((i == 1) && (n1 < 0 || n1 > *n)) {
      sprintf(str,"Bad internal node number %d",n1);
      cerro(str);
      return;
    }
    n2 = nodes[i];
    if (n2 < 0 || n2 > *n) {
      sprintf(str,"Bad internal node number %d",n2);
      cerro(str);
      return;
    }
    a = 0;
    for (j = lp[n1-1]; j <= lp[n1]-1; j++) {
      if (n2 == ls[j-1]) {
        a = la[j-1];
        break;
      }
    }
    if (a == 0) {
      *psize = 0;
      return;
    }
    (*p)[i-1] = a;
  }
}

Here is the call graph for this function:

void C2F() p2ns	(	int *	p,
		int *	psize,
		int **	nodes,
		int *	nsize,
		int *	la,
		int *	lp,
		int *	ls,
		int *	direct,
		int *	m,
		int *	n
	)

p2ns_ converts a path into a node set: PATH = [A1,A2,...,An] => NODES = [N1,N2,...,Nn+1] => with Ai = (Ni,Ni+1) with *nsize = *psize + 1

Definition at line 111 of file paths.c.

References a, cerro(), ma, MALLOC, n1, n2, and NULL.

{
  int ma,a,i,j,k,n1,n2;
  *nsize = *psize + 1;
  if ((*nodes = (int *)MALLOC(*nsize * sizeof(int))) == NULL) {
    cerro("Running out of memory");
    return;
  }
  if (*direct == 1) ma = *m; else ma = *m / 2;
  for (i = 1; i <= *psize; i++) {
    a = p[i-1];
    if (a < 0 || a > ma) {
      sprintf(str,"Bad internal arc number %d",a);
      cerro(str);
      return;
    }
    /* find nodes n1 and n2 of arc a */
    n1 = 0; n2 = 0;
    for (j = 1; j <= *n; j++) {
      for (k = lp[j-1]; k <= lp[j]-1; k++)
        if (la[k-1] == a) {
          n1 = j; n2 = ls[k-1];
          break;
        }
      if (n1 != 0) break;
    }
    if (n1 == 0) {
      *nsize = 0;
      return;
    }
    /* directed graph */
    if (*direct == 1) {
      if (i == 1) (*nodes)[i-1] = n1;
      if (i!= 1 && (*nodes)[i-1] != n1) {
        *nsize = 0;
        return;
      }
      (*nodes)[i] = n2;
    }
    /* undirected graph */
    else {
      if (i == 1) {
        (*nodes)[0] = n1; (*nodes)[1] = n2;
      }
      else if (i == 2) {
        if (n1 == (*nodes)[0]) {
          (*nodes)[0] = (*nodes)[1];
          (*nodes)[1] = n1;
          (*nodes)[2] = n2;
        }
        else if (n1 == (*nodes)[1]) {
          (*nodes)[2] = n2;
        }
        else if (n2 == (*nodes)[0]) {
          (*nodes)[0] = (*nodes)[1];
          (*nodes)[1] = n2;
          (*nodes)[2] = n1;
        }
        else if (n2 == (*nodes)[1]) {
          (*nodes)[2] = n1;
        }
        else {
          *nsize = 0;
          return;
        }
      }
      else {
        if (n1 == (*nodes)[i-1]) (*nodes)[i] = n2;
        else if (n2 == (*nodes)[i-1]) (*nodes)[i] = n1;
        else {
          *nsize = 0;
          return;
        }
      }
    }
  }
}

Here is the call graph for this function:

void C2F() prevn2p	(	int *	i,
		int *	j,
		int *	m,
		int *	n,
		int *	la,
		int *	lp,
		int *	ls,
		int *	direct,
		int *	pln,
		int **	p,
		int *	psize
	)

prevn2p_ computes a path from node i to node j from a vector describing the previous nodes in path: node i belongs to path if pln[i] > 0 pln[i] is then the previous node in the sequence

Definition at line 33 of file paths.c.

References cerro(), FREE, MALLOC, NodesToPath(), and NULL.

{
  int *nodes;
  int k,nn;
  if (*i < 0 || *i > *n) {
    sprintf(str,"Bad internal node number %d",*i);
    cerro(str);
    return;
  }
  if (*j < 0 || *j > *n) {
    sprintf(str,"Bad internal node number %d",*j);
    cerro(str);
    return;
  }
  if ((nodes = (int *)MALLOC((*m + 1) * sizeof(int))) == NULL) {
    cerro("Running out of memory");
    return;
  }
  nn = 0;
  nodes[nn++] = *j;
  k = 0;
  /* the first time, the test must be always verified for dealing with
     circuits */
  while (k != *i) {
    if (nn == 1) k = *j;
    k = pln[k-1];
    nodes[nn++] = k;
    if (k <= 0 || k > *n || nn > *n + 1) {
      /* there is no path */
      *psize = 0;
      return;
    }
  }
  *psize = nn - 1;
  if ((*p = (int *)MALLOC(*psize * sizeof(int))) == NULL) {
    cerro("Running out of memory");
    return;
  }
  NodesToPath(nodes,p,psize,la,lp,ls);
  FREE(nodes);
}

Here is the call graph for this function:

void C2F() prevn2st	(	int *	n,
		int *	nodes,
		int **	tree,
		int *	treesize,
		int *	la,
		int *	lp,
		int *	ls
	)

prevn2st_ computes a spanning tree (root = node i0) from a vector nodes describing the previous nodes in tree

Definition at line 206 of file paths.c.

References cerro(), MALLOC, and NULL.

{
  int i,in,j,nt,indic;
  *treesize = *n - 1;
  if ((*tree = (int *)MALLOC(*treesize * sizeof(int))) == NULL) {
    cerro("Running out of memory");
    return;
  }
  nt = 0;
  indic=0;
  for (i = 1; i <= *n; i++) {
    in = nodes[i-1];
    if (in == 0) continue;
    /* arc (in,i) belongs to tree */
    indic=1;
    for (j = lp[in-1]; j <= lp[in]-1; j++) {
      if (ls[j-1] == i) {
        (*tree)[nt++] = la[j-1];
        break;
      }
    }
  }
  if (indic == 0) *treesize=0;
}

Here is the call graph for this function:

---

Variable Documentation

char str[80] [static]

Definition at line 11 of file paths.c.

---