3 Replies - 194 Views - Last Post: 28 January 2018 - 04:53 AM Rate Topic: -----

#1 Eth11674  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 29-September 17

Weighted DAG problem

Posted 27 January 2018 - 08:24 AM

Hello everyone, i implemented a DAG graph using adjacency list:

struct node
{
	int data;
	node *link;
};


struct vertex_list
{
	 node *vlisthead;
};


struct Graph
{
	int v;
	 vertex_list *vl;
	 vertex_list *delay;
};


Graph* Create_Graph(int n)
{
	int i;
	Graph *vlist = new Graph;
	vlist->v = n;

	// declare a list for n vertex.
	vlist->vl = new vertex_list[n + 1];
	vlist->delay = new vertex_list[n + 1];
	// Assign vertex listhead to NULL.
	for (i = 0; i < n + 1; i++)
	{
		vlist->vl[i].vlisthead = NULL;
		vlist->delay[i].vlisthead = NULL;
	}

	return vlist;
}


node* New_Node(int value)
{
    node *new_node = new node;
	new_node->data = value;
	new_node->link = NULL;

	return new_node;
}


void Insert_Node(Graph *G, int v1, int v2, int d)
{
	node *new_node1 = New_Node(v1);
	node *new_node2 = New_Node(v2);
	node *temp = new node;

	if (G->vl[v2].vlisthead == NULL)
	{
		// If the head is null insert the node to the head.
		G->vl[v2].vlisthead = new_node1;
		G->delay[v2].vlisthead = New_Node(d);
	}
	else
	{
		// Otherwise, add the node at the list.
		new_node1->link = G->vl[v2].vlisthead;
		G->vl[v2].vlisthead = new_node1;
		G->delay[v2].vlisthead = New_Node(d);
	}
}



My objective is reading some data from file and store those data in graph
my problem is after reading file and printing the graph. there is identical weight(delay) for each link in adjacency list for each vertex.

and in main function:

int delay;
delay = rand() % 11;
Insert_Node(G, edge[parent_indx][edge_number], parent_indx, delay);



and here how i print the graph:
	for (i = 0; i < vertex_number; i++)
	{
		cout << "\n\tV(" << node[i] << ") -> {  ";

		while (G->vl[i].vlisthead != NULL)
		{
			cout << node[G->vl[i].vlisthead->data] << ", d: " 
                             << G->delay[i].vlisthead->data << ",  ";
			G->vl[i].vlisthead = G->vl[i].vlisthead->link;
		}
		cout << "}";
	}



So how should i define the weight(delay) structure to assign different random number for each link?

The printed graph in console:
        V(G1gat) -> {  }
        V(G2gat) -> {  }
        V(G3gat) -> {  }
        V(G6gat) -> {  }
        V(G7gat) -> {  }
        V(G22gat) -> {  G16gat, d: 0,  G10gat, d: 0,  } 
        V(G23gat) -> {  G19gat, d: 7,  G16gat, d: 7,  }
        V(G10gat) -> {  G3gat, d: 9,  G1gat, d: 9,  }
        V(G11gat) -> {  G6gat, d: 1,  G3gat, d: 1,  }
        V(G16gat) -> {  G11gat, d: 5,  G2gat, d: 5,  }
        V(G19gat) -> {  G7gat, d: 10,  G11gat, d: 10,  }


i just want diffrenet delays (d) for each edge


I'm new to graphs,any suggestions will be greatly appreciated
thank you

Best Regards

Is This A Good Question/Topic? 0
  • +

Replies To: Weighted DAG problem

#2 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 6010
  • View blog
  • Posts: 20,661
  • Joined: 05-May 12

Re: Weighted DAG problem

Posted 27 January 2018 - 09:21 AM

First, you have to decide if you are writing C or C++ code.

C code would look like:
Insert_Node(G, edge[parent_indx][edge_number], parent_indx, delay);



C++ code would look like:
G->Insert_Node(edge[parent_indx][edge_number], parent_indx, delay);



Next, trying to be cheap (and again writing code in the C "efficient" style) where you are trying to make your node.data act double duty leads to confusion. You are making the same field hold vertex numbers when in the vl vertex list and delays when in the delay vertex list makes your code really hard to understand.

Next, trying to maintain parallel lists in general is a bad idea. If there are related pieces of information, put them together in a class or struct.
Was This Post Helpful? 1
  • +
  • -

#3 Eth11674  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 29-September 17

Re: Weighted DAG problem

Posted 28 January 2018 - 02:59 AM

thanks for your time

could you please put your words into code?
i dont get your suggestions really ?? i'm really new to graphs
so please give me more details i can post all of the code if you need it

thank you sir
Was This Post Helpful? 0
  • +
  • -

#4 Skydiver  Icon User is online

  • Code herder
  • member icon

Reputation: 6010
  • View blog
  • Posts: 20,661
  • Joined: 05-May 12

Re: Weighted DAG problem

Posted 28 January 2018 - 04:53 AM

Every thing I noted above is not specific to graphs. They are simply good software engineering practices that make code easier to read and maintain.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1