source: trunk/Softwares/MiBench/src/c/dijkstra-dijkstra.c @ 136

Last change on this file since 136 was 117, checked in by rosiere, 15 years ago

1) Platforms : add new organization for test
2) Load_Store_Unit : add array to count nb_check in store_queue
3) Issue_queue and Core_Glue : rewrite the issue network
4) Special_Register_Unit : add reset value to register CID
5) Softwares : add multicontext test
6) Softwares : add SPECINT
7) Softwares : add MiBench?
7) Read_queue : inhib access for r0
8) Change Core_Glue (network) - dont yet support priority and load balancing scheme

  • Property svn:executable set to *
  • Property svn:keywords set to Id
File size: 3.1 KB
Line 
1#include <stdio.h>
2#include <stdlib.h>
3
4#define NUM_NODES                          100
5#define NONE                               9999
6
7struct _NODE
8{
9  int iDist;
10  int iPrev;
11};
12typedef struct _NODE NODE;
13
14struct _QITEM
15{
16  int iNode;
17  int iDist;
18  int iPrev;
19  struct _QITEM *qNext;
20};
21typedef struct _QITEM QITEM;
22
23QITEM *qHead = NULL;
24
25             
26             
27             
28int AdjMatrix[NUM_NODES][NUM_NODES];
29
30int g_qCount = 0;
31NODE rgnNodes[NUM_NODES];
32int ch;
33int iPrev, iNode;
34int i, iCost, iDist;
35
36
37void print_path (NODE *rgnNodes, int chNode)
38{
39  if (rgnNodes[chNode].iPrev != NONE)
40    {
41      print_path(rgnNodes, rgnNodes[chNode].iPrev);
42    }
43  printf (" %d", chNode);
44  fflush(stdout);
45}
46
47
48void enqueue (int iNode, int iDist, int iPrev)
49{
50  QITEM *qNew = (QITEM *) malloc(sizeof(QITEM));
51  QITEM *qLast = qHead;
52 
53  if (!qNew) 
54    {
55      fprintf(stderr, "Out of memory.\n");
56      exit(1);
57    }
58  qNew->iNode = iNode;
59  qNew->iDist = iDist;
60  qNew->iPrev = iPrev;
61  qNew->qNext = NULL;
62 
63  if (!qLast) 
64    {
65      qHead = qNew;
66    }
67  else
68    {
69      while (qLast->qNext) qLast = qLast->qNext;
70      qLast->qNext = qNew;
71    }
72  g_qCount++;
73  //               ASSERT(g_qCount);
74}
75
76
77void dequeue (int *piNode, int *piDist, int *piPrev)
78{
79  QITEM *qKill = qHead;
80 
81  if (qHead)
82    {
83      //                 ASSERT(g_qCount);
84      *piNode = qHead->iNode;
85      *piDist = qHead->iDist;
86      *piPrev = qHead->iPrev;
87      qHead = qHead->qNext;
88      free(qKill);
89      g_qCount--;
90    }
91}
92
93
94int qcount (void)
95{
96  return(g_qCount);
97}
98
99void dijkstra(int chStart, int chEnd) 
100{
101 
102
103 
104  for (ch = 0; ch < NUM_NODES; ch++)
105    {
106      rgnNodes[ch].iDist = NONE;
107      rgnNodes[ch].iPrev = NONE;
108    }
109
110  if (chStart == chEnd) 
111    {
112      printf("Shortest path is 0 in cost. Just stay where you are.\n");
113    }
114  else
115    {
116      rgnNodes[chStart].iDist = 0;
117      rgnNodes[chStart].iPrev = NONE;
118     
119      enqueue (chStart, 0, NONE);
120     
121     while (qcount() > 0)
122        {
123          dequeue (&iNode, &iDist, &iPrev);
124          for (i = 0; i < NUM_NODES; i++)
125            {
126              if ((iCost = AdjMatrix[iNode][i]) != NONE)
127                {
128                  if ((NONE == rgnNodes[i].iDist) || 
129                      (rgnNodes[i].iDist > (iCost + iDist)))
130                    {
131                      rgnNodes[i].iDist = iDist + iCost;
132                      rgnNodes[i].iPrev = iNode;
133                      enqueue (i, iDist + iCost, iNode);
134                    }
135                }
136            }
137        }
138     
139      printf("Shortest path is %d in cost. ", rgnNodes[chEnd].iDist);
140      printf("Path is: ");
141      print_path(rgnNodes, chEnd);
142      printf("\n");
143    }
144}
145
146int main_dijkstra(int argc, char *argv[]) {
147  int i,j,k;
148  int nb_path;
149  FILE *fp;
150 
151  if (argc<3) {
152    fprintf(stderr, "Usage: dijkstra <filename> <nb_path>\n");
153    fprintf(stderr, "Only supports matrix size is #define'd.\n");
154  }
155
156  /* open the adjacency matrix file */
157  fp = fopen (argv[1],"r");
158  nb_path = atoi(argv[2]);
159 
160  /* make a fully connected matrix */
161  for (i=0;i<NUM_NODES;i++) {
162    for (j=0;j<NUM_NODES;j++) {
163      /* make it more sparce */
164      fscanf(fp,"%d",&k);
165                        AdjMatrix[i][j]= k;
166    }
167  }
168
169  /* finds 10 shortest paths between nodes */
170  for (i=0,j=NUM_NODES/2;i<nb_path;i++,j++) {
171                        j=j%NUM_NODES;
172      dijkstra(i,j);
173  }
174  exit(0);
175}
Note: See TracBrowser for help on using the repository browser.