DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Page 2 of 2 FirstFirst 12
Results 16 to 27 of 27

Thread: Adjacecny Lists C++

  1. #16
    Join Date
    May 2007
    Posts
    843
    This is the picture form of the representation i looking for.

    Code:
    #include<stdio.h>
    #include<ctype.h>
    #include<stdlib.h>
    #include<assert.h>
    #include<math.h>
    
    #include "AdjacencyList.h"
    
    // -------------------------------------------------------
    
    // -------------------------------------------------------
    
    int main(int argc, char *argv[])
    {
    	struct vertex *root_Vertice = 0;
    	struct vertex *vertices = 0;
    
    	root_Vertice = root_vertex_allocate(&root_Vertice);
    	vertices = vertex_allocate(vertices);
    
    	root_Vertice = InsertVertex(&root_Vertice, vertices, 1);
    
    	printf("%d", (*root_Vertice).next_Vertices->valueOfVertices);
    	
    	return 0;
    }
    // -------------------------------------------------------
    struct vertex* root_vertex_allocate(struct vertex **root_vertice)
    {
    	(*root_vertice) = (struct vertex*)malloc(sizeof(struct vertex));
    
    	assert(*root_vertice != 0);
    
    	(*root_vertice)->next_Vertices = NULL;
    	
    	return *root_vertice;
    }
    // -------------------------------------------------------
    struct vertex* vertex_allocate(struct vertex *myVertex)
    {
    	myVertex = (struct vertex *)malloc(sizeof(struct vertex));
    	assert(myVertex != 0);
    
    	myVertex->next_Vertices = NULL;
    
    	return myVertex;
    }
    // --------------------------------------------------------
    void vertex_deallocate(struct vertex *myVertex)
    {
    	if (myVertex != NULL)
    	{
    		free(myVertex);
    	}
    }
    // --------------------------------------------------------
    struct vertex* InsertVertex(struct vertex **root_vertice, 
    							struct vertex *vertex, 
    							int value)
    {
    	struct vertex *traversal;
    
    	if ( (*root_vertice)->next_Vertices == NULL )
    	{
    		(*root_vertice)->next_Vertices = vertex;
    		vertex->valueOfVertices = value;
    	}
    	else
    	{
    		traversal = (*root_vertice)->next_Vertices;
    
    		while(traversal->next_Vertices != NULL)
    		{	
    			traversal = traversal->next_Vertices;
    		}
    
    		traversal->next_Vertices = vertex;
    		vertex->valueOfVertices = value;
    	}
    	
    	return *root_vertice;
    }
    // --------------------------------------------------------
    struct edge* edge_allocate(struct edge *myEdge)
    {
    	myEdge = (struct edge *)malloc(sizeof(struct edge));
    	assert(myEdge != 0);
    
    	return myEdge;
    }
    // --------------------------------------------------------
    void edge_deallocate(struct edge *myEdge)
    {
    	if (myEdge != NULL)
    	{
    		assert(myEdge != 0);
    		free(myEdge);
    	}
    }
    // --------------------------------------------------------
    
    
    #ifndef _AdjacencyList_ 
    #define _AdjacencyList_
    
    struct vertex
    {
    	int valueOfVertices;           // Value of vertices 
    	struct vertex *next_Vertices;    
    };
    
    struct edge
    {
    	int weightage;                 // Weightage of a edge 
    	struct edge *edges;            // 
    };
    
    // -----------------------Vertex Function----------------
    
    struct vertex* root_vertex_allocate(struct vertex **);
    struct vertex* vertex_allocate(struct vertex *);
    void vertex_deallocate(struct vertex *);
    
    struct vertex* InsertVertex(struct vertex **, struct vertex *, int);
    struct vertex* RemoveVertex(struct vertex *);
    
    void displayGraph(struct vertex *);
    
    // -------------------------------------------------------
    
    // -----------------------Edge Function-------------------
    
    struct edge* edge_allocate(struct edge *);
    void edge_deallocate(struct edge *);
    
    // -------------------------------------------------------
    
    
    
    #endif
    This is what i have did so far.

  2. #17
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    You need to tie your edges which originate at a particular vertex to that vertex. Therefore, I suggest that your vertex struct also contain a reference to a list of the edges which originate there.

    For the use of edges in any manipulation of the graph with data, I think it would be helpful to have two references to the vertices which are the terminal points of that edge - so that the edges are self-referential.

    To "display" the graph use a queue, push all of the edges which originate at vertex 0, then vertex 1, etc., into the queue, then pop them off one at a time and build your display (however it is that you are doing that). A common use of weight is to find the shortest path from one point to another, so you could use a priority queue to help you with that task.

  3. #18
    Join Date
    May 2007
    Posts
    843
    Thanks for your help.

    Code:
    struct vertex
    {
    	int valueOfVertices;           // Value of vertices 
    	struct vertex *next_Vertices; 
    	struct vertex *list_edges;    
    	
    	/* 
    		A pointer to list of edges 
    		originate from the specific vertex 0, 1, and 2
    	*/
    };
    
    struct edge
    {
    	int weightage;                 // Weightage of a edge 
    	struct edge *edges;           
    	struct vertex *verticeFrom;
    	struct vertex *verticeTo;
    	
    	/*
    		To indicate edge pointed by and pointed from
    	*/
    };
    How to build graph from there ?

    If A vertex pointed to B and C vertices. Is it consider a multi graph ?

    Then, i need to add another next_vertex.

    Sorry for my stupidity.

    If two edges go parallel to same vertex , then what graph this called ?


    A billion thanks for your help.
    Last edited by Peter_APIIT; 03-23-2008 at 06:54 AM. Reason: Add some information

  4. #19
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    If, in starting at vertex A, you can traverse to either B or C, you would made a list of edge objects AB and AC which is pointed at by *edges in your A vertex struct (if *edges points to the first node of a list of edge structs).

    A multigraph has several edges which have the same origination and destination edges - many edges connecting A and B - as a representation of all of the scheduled commercial air flights between Los Angeles and New York would be.

    If your two edges going parallel to the same vertex have the same origination vertex, it would be a multigraph. If different vertices, then just a graph. [how you draw an edge doesn't matter - whether lines are curved or straight and parallel or even wiggly - what matters in the manipulation and analysis of a graph edge (or set of graph edges) is where the edge originates and where it terminates and, if weighted, its weight and other identifying information]
    Last edited by nspils; 03-23-2008 at 08:52 AM.

  5. #20
    Join Date
    May 2007
    Posts
    843
    If, in starting at vertex A, you can traverse to either B or C, you would made a list of edge objects AB and AC which is pointed at by *edges in your A vertex struct (if *edges points to the first node of a list of edge structs).
    I think i understand what u mentioned here.

    A: B->C

    I create Vertex struct A object and pointing by struct vertex *list_edges; to struct edge.

    In struct edge, struct vertex *verticeFrom; pointed by A vertex object and struct vertex *verticeTo; pointed to vertex B object and finally, struct edge *edges; pointed to AC object.

    Please correct me if i wrong.

    How about my representation in post 18.

    If i asked more help from you, then i am a spoon feeding person.

    Due to i learning this by myself, i hope you don't have bad feeling about me.

    A billion thanks for your help.

    Thanks again.

  6. #21
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    I agree with what you have said in explaining the structure of your graph with edges AB and AC. Perhaps it would be cleaner and more thorough to write (using your notation):

    A: AB->AC

    that is, the A vertex struct holds (refers to) a list of edge structs, the list holding the edge structs AB and AC. The list_edges data member of the A vetex struct would point to AB (or AC, which ever is the first in the list) and the first in the list would point to the next in the list.

    I don't know whether I would use pointers for the verticeFrom or verticeTo data members - but you need to decide what your implementation requires you to actually use those vertices or just to know that edge AB originates at A and terminates at B. For most uses I would use a char/int/string datatype (depending on how many vertices I might be using and the nature of the problem being represented by the graph), here, rather than a vertex pointer.

    Graph theory is not an easy topic. Why would I harbor bad feelings about your effort to learn it?

  7. #22
    Join Date
    May 2007
    Posts
    843
    Thanks for your help. I think i understand.

    I will start coding and come back here with a specific question.

  8. #23
    Join Date
    May 2007
    Posts
    843
    I have code the graph and come back here with a specific question.

    Code:
    #ifndef _AdjacencyList_ 
    #define _AdjacencyList_
    
    struct vertex
    {
    	int valueOfVertices;           // Value of vertices 
    	struct vertex *next_Vertices; 
    	struct edge *list_edges;    
    	
    	/* 
    		A pointer to list of edges 
    		originate from the specific vertex 0, 1, and 2
    	*/
    };
    
    struct edge
    {
    	int weightage;                 // Weightage of a edge 
    	struct edge *next_edges;           
    	struct vertex *verticeFrom;
    	struct vertex *verticeTo;
    	
    	/*
    		To indicate edge pointed by and pointed from
    	*/
    };
    
    // ------------------------Graph Function----------------
    
    void Graph_deallocate(struct vertex **, int *);
    
    // ------------------------------------------------------
    
    // -----------------------Vertex Function----------------
    
    struct vertex* root_vertex_allocate(struct vertex **);
    void root_vertex_deallocate(struct vertex **);
    
    struct vertex* vertex_allocate(struct vertex *);
    void vertex_deallocate(struct vertex *);
    
    struct vertex* InsertVertex(struct vertex **, struct vertex *
    							, struct edge *edges, int);
    struct vertex* RemoveVertex(struct vertex **);
    
    void displayGraph(struct vertex **);
    
    // -------------------------------------------------------
    
    // -----------------------Edge Function-------------------
    
    struct edge* edge_allocate(struct edge *);
    void edge_deallocate(struct edge *);
    
    // -------------------------------------------------------
    
    
    // ----------------------Utility Function-----------------
    
    // To check an edges consists of vertice in list of vertice  
    int* isExist_Vertex_ListVertice(struct vertex *, 
    								struct edge *,
    								int *);
    
    // To check a vertice in list of edges
    struct vertex** isExist_Vertex_InListEdges(struct vertex **,
    										   struct vertex *);
    
    
    int* isExist_Ptr_Allocate(int *);
    void isExist_Ptr_Deallocate(int *);
    
    // -------------------------------------------------------
    #endif



    What i code here is a directed graph with weightage within the edges.

    Input :
    1,2,2,3,1,4,3


    I have remove vertex 3 because it doesn't have any list of edges but when i remove vertice with list of edges. Then memory leak is happen and i lost the list of edges pointed by a particular vertice.

    My question is how to avoid this ?

    Unlike undirected graph, for instance :

    1 : 12(2) -> 14(4) -> *
    2 : 21(2)
    3:
    4: 41(4) -> **

    When i remove vertex number 4, i can remove this(*) and **. Please correct me if i wrong.

    Then, how about in directed graph.

    Headache.

    Thanks for your help.

    Your help is greatly appreciated by me and others.
    Attached Images Attached Images
    Attached Files Attached Files

  9. #24
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    Remember what you have learned about lists. To call a destructor of a list you must destruct each element of the list, in turn, until you get to the end of the list. If all you do is deallocate the pointer to the head node and not the remaining elements of the list, you leave all of those elements out there occupying memory.

    Also, each of your vertex and edge structs contain several pointers to objects. You need to release the memory referred to by each of those pointers, as well (one of the drawbacks to using so many pointers). Takes careful planning and execution for each of your structs.
    Last edited by nspils; 04-04-2008 at 09:43 PM.

  10. #25
    Join Date
    May 2007
    Posts
    843
    I remermber how link list work in term of destruction.

    Apply the same concept to it.

    For instance,

    1: 12(2)->14(4)
    2: 23(3)
    3:

    That means if i remove vertex number , then i also need to remove vertex 3 cause 2 is refer to 3 also.

    Please correct me if i wrong.

  11. #26
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    From the graph point of view, yes, you need to identify and remove any edge which starts or ends with the vertex you are removing. However, I was referring to your use of pointers within the edges and within the vertices. Your use of pointers means that you need to have a destructor for your edge struct and for your vertex struct which properly deallocates the memory pointed to by those pointers.

  12. #27
    Join Date
    May 2007
    Posts
    843
    You really a helpful guys.

    Thanks for your help.

    I understand what u mentioned here.

Similar Threads

  1. Linked Lists - hard exercise(help needed)
    By parallel in forum Java
    Replies: 6
    Last Post: 08-13-2013, 05:50 AM
  2. Replies: 0
    Last Post: 09-19-2005, 07:21 AM
  3. Replies: 0
    Last Post: 01-11-2002, 05:46 AM
  4. How do you Export Owners of Distribution Lists ?
    By Patrick in forum Enterprise
    Replies: 2
    Last Post: 04-09-2001, 11:48 PM
  5. automating distribution lists
    By Jamie Harsevoort in forum Enterprise
    Replies: 0
    Last Post: 11-30-2000, 05:34 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center