How do you implemant a graph data structure?

100

Author

September 07, 2006 04:11 AM

i need to implement a graph for my AI for the ghosts in pacman. the 1st thing that i want to do is to make a graph data structure connecting the nodes together and I want the end product to look like this: -

i have created all the nodes like: -


//////////////////////////nodes.h
///////////////////////////////////

struct sNodes 
{
	D3DXVECTOR2 vNode1,vNode2,vNode3; // and more vectors to 
                                          // hold all 86 nodes
};
//////////////////////////nodes.cpp
///////////////////////////////////
sNodes pnode;
void nodes_Init()
{
	//Setup Node1
	pnode.vNode1.x = (Column2X(10,TILESIZE,MAPCOLUMNCOUNT))+XOFFSET;
	pnode.vNode1.y = (Row2Y(10,TILESIZE))+YOFFSET;
//and so on for 86 nodes
}

But where do i go from here to create a graph?

Emmanuel Deloget

1,382

September 07, 2006 05:37 AM

First, if you plane to create a list of vectors, why don't you use a container for such list? You don't want to create 86 variables that are named vNodeXX, do you? A simpler way to do it is to use a std::vector - like this:

struct sNodes{  std::vector<D3DXVECTOR2> mNodes;  sNodes() : mModes(NUMBER_OF_NODES) { }};

Anyway, you don't create a graph data structure like this. A simple graph data structure can be created by thinking to what a node is. Clearly, a node is connected to other nodes through a path. Thus, a node have to hold a list of nodes.

class GraphNode{  std::vector<GraphNode*> mNodes;public:  GraphNode() { }  virtual ~GraphNode() { /* does nothing */ }  void add(GraphNode *node) { mNodes.push_back(node); }  void remove(GraphNode *node)  {    mNodes.erase(std::remove(mNodes.begin(), mNodes.end(), node), mNodes.end());  }  const std::vector<GraphNode*>& next() const { return mNodes; }};

Now, a graph contains nodes, one of them being the root node.

class Graph{  GraphNode *mRoot;  std::vector<GraphNode*> mNodes;public:  Graph() : mRoot(NULL) { }  virtual ~Graph() { /* delete the registered nodes! */ }  GraphNode* addNode(GraphNode *node) { mNodes.push_back(node); return node; }  GraphNode *getRoot() { return mRoot; }  void setRoot(GraphNode *root) { mRoot = root; }};

You code is now a lot more generic:

class MyNode : public GraphNode{  D3DXVECTOR2 mPosition;public:  MyNode(const D3DXVECTOR2& v) : mPosition(v) { }  virtual ~MyNode() { }  const D3DXVECTOR2& getPosition() const { return mPosition; }};int main(){  Graph graph;  // node 1  MyNode *node1 = graph.addNode(new MyNode(D3DXVECTOR2(...)));  graph.setRoot(node1);  // node 2  MyNode *node2 = graph.addNode(new MyNode(D3DXVECTOR2(...)));  node1->add(node2);  node2->add(node1);    // and so on...}

Of course, this is a very simple graph, with a lot of missing features but I hope you get the point.

Regards,

-- Emmanuel D. [blog, in French] [blog, very bad googlized translation]

Rasmadrak

196

September 07, 2006 06:25 AM

And in the future, link nodes with a link-"node" i.e

NodeA - Link - NodeB.

This allows you to set costs between nodes, and different AI behaviours per link etc.

Cheers!

"Game Maker For Life, probably never professional thou." =)

Replicon

306

September 07, 2006 09:50 AM

There are many ways to represent a graph, and depending on the density of your graph, one may be better than another. Having a list of nodes, each of which contains a list of nodes it connects to (and perhaps the distance), sounds like a good start, since you have lots of nodes, but a maz degree of 3 (unless I'm not seeing a 4 hehe).

The other question is, what will you be doing with this graph structure? Preprocessing the all-pairs-shortest-paths? Since this is a fairly static graph, you might even get away with a simple adjacency matrix.

Doggan

528

September 07, 2006 12:01 PM

Two of the most common ways to represent a graph are matrix form and adjaceny list form.

Matrix form is the easier of the two to program, but it is a waste of space for a large and sparse graph. For example, a value of 7 in row 2 column 3 says that the weight from node 2 to node 3 is 7. If it's an undirected graph (as would be the case in a Pacman game), row 3 column 2 of the matrix would also have a value of 7. Notice the waste of space due to duplication. Also, if a connection from 3 to 4 doesn't exist, you still need to represent it with a weight of 0 (or -1) in [3][4] of your matrix.

An adjacency list is an array of linked lists. So in row 2, you can have a struct type containing 3 (the node we are pointing to) and 7 (the value of the node). Notice here, we don't need to create entries for connections that don't exist. (here's a good figure).

I would also suggest taking a look at the Boost graph library. Aside from an already efficient/refined/tested graph representation, it also has all of the algorithms that you will need for a Pacman game (Dijkstra's, etc).

Prog101

100

Author

September 07, 2006 12:08 PM

Cheers, i am trying to implement the code you said but i get 3 errors

GraphNode.h

#ifndef GRAPHNODE_H#define GRAPHNODE_H#include <windows.h>#include <d3d9.h>#include <d3dx9.h>#include <dxerr9.h>#include <stdio.h>#include <vector>class GraphNode{		std::vector<GraphNode*> mNodes;public:		GraphNode() { }		virtual ~GraphNode() 	{ 		/* does nothing */ 	}	void add(GraphNode *node) 	{ 		mNodes.push_back(node); 	}		void remove(GraphNode *node)	{		mNodes.erase(std::remove(mNodes.begin(), mNodes.end(), node), mNodes.end());	}		const std::vector<GraphNode*>& next() const 	{ 		return mNodes; 	}};#endif

Graph.h

#ifndef GRAPH_H#define GRAPH_H#include <windows.h>#include <d3d9.h>#include <d3dx9.h>#include <dxerr9.h>#include <stdio.h>#include "graphNode.h"#include <vector>class Graph{	GraphNode *mRoot;	std::vector<GraphNode*> mNodes;public:	Graph() : mRoot(NULL) 	{ 		}	virtual ~Graph() 	{ 		/* delete the registered nodes! */ 	}		GraphNode* addNode(GraphNode *node) 	{ 		mNodes.push_back(node); return node; 	}		GraphNode *getRoot() 	{ 		return mRoot; 	}		void setRoot(GraphNode *root) 	{ 		mRoot = root; 	}};#endif

MyNode.h

#ifndef MYNODE_H#define MYNODE_H#include <windows.h>#include <d3d9.h>#include <d3dx9.h>#include <dxerr9.h>#include <stdio.h>#include "graphNode.h"class MyNode : public GraphNode{	D3DXVECTOR2 mPosition;public:	MyNode(const D3DXVECTOR2& v) : mPosition(v) 	{ 	}		virtual ~MyNode() 	{ 	}	const D3DXVECTOR2& getPosition() const 	{ 		return mPosition; 	}};#endif

main.cpp

//=========== Includes#include <windows.h>#include <d3d9.h>#include <d3dx9.h>#include <dxerr9.h>#include <stdio.h>#include "myNode.h"#include "graph.h"Graph graph;sNodes pnode;void nodes_Init(){	// node 1	MyNode *node1 = graph.addNode(new MyNode(D3DXVECTOR2((Column2X(10,TILESIZE,MAPCOLUMNCOUNT))+XOFFSET,(Row2Y(10,TILESIZE))+YOFFSET)));	graph.setRoot(node1);	// node 2	MyNode *node2 = graph.addNode(new MyNode(D3DXVECTOR2((Column2X(10,TILESIZE,MAPCOLUMNCOUNT))+XOFFSET,(Row2Y(10,TILESIZE))+YOFFSET)));	node1->add(node2);	node2->add(node1);}

//I get two errors in my main.cpp
1)PacMan2D error C2440: 'initializing' : cannot convert from 'GraphNode *' to 'MyNode *' Cast from base to derived requires dynamic_cast or static_cast
2)PacMan2D error C2440: 'initializing' : cannot convert from 'GraphNode *' to 'MyNode *' Cast from base to derived requires dynamic_cast or static_cast

//And an error for GraphNode.h
3)PacMan2D error C2660: 'remove' : function does not take 3 arguments

Doggan

528

September 07, 2006 12:52 PM

1). Use <cstdio> instead of <stdio.h>. The latter is 'deprecated' in C++.

Quote:1)PacMan2D error C2440: 'initializing' : cannot convert from 'GraphNode *' to 'MyNode *' Cast from base to derived requires dynamic_cast or static_cast
2)PacMan2D error C2440: 'initializing' : cannot convert from 'GraphNode *' to 'MyNode *' Cast from base to derived requires dynamic_cast or static_cast

2). These errors mean just what they read. addNode() is looking for a GraphNode object, but you are passing it a MyNode object. Since MyNode is derived from GraphNode, you need to explicitly cast it. The appropriate C++ way to cast pointers is through dynamic casts: addNode( dynamic_cast<GraphNode*>(new MyNode(...)) );

3). I cannot be certain as this is only a sample of your code, but keep an eye out for memory leaks as you definitely have some potential for that in the code posted.

Quote://And an error for GraphNode.h
3)PacMan2D error C2660: 'remove' : function does not take 3 arguments

4). #include <algorithm>

NotAYakk

876

September 07, 2006 01:18 PM

To make some of the errors go away, change:

	GraphNode* addNode(GraphNode *node) 	{ 		mNodes.push_back(node); return node; 	}

to:

		template<typename AnyNode>	AnyNode* addNode(AnyNode *node) 	{ 		mNodes.push_back(node); return node; 	}

I don't know if I approve of the technique, but the above will remove some errors.

...

Personally, I'd be more comphy with:

	void addNode(GraphNode *node) 	{ 		mNodes.push_back(node);	}

Set up and build your node before you add it to the graph.

Yet another option would be making your graph a graph of arbitrary node types:
Change:
class Graph
to

template<typename AnyNode>class Graph

and change all references to "GraphNode" in the Graph class to "AnyNode".

Finally, when you create your Graph, create

Graph<MyNode> graph;

and you have created a graph of "MyNode"s.

Prog101

100

Author

September 07, 2006 03:03 PM

Cheers guys it now compiles, but can some one please give me a run through as to what is actually happening here with the code. also in main.cpp i have added 2 nodes how do i add a 3rd?

Graph.h

#ifndef GRAPH_H#define GRAPH_H#include <windows.h>#include <d3d9.h>#include <d3dx9.h>#include <dxerr9.h>#include <cstdio>#include "graphNode.h"#include <vector>template<typename AnyNode>class Graph{	AnyNode *mRoot;	std::vector<GraphNode*> mNodes;public:	Graph() : mRoot(NULL) 	{ 		}	virtual ~Graph() 	{ 		/* delete the registered nodes! */ 	}		template<typename AnyNode>		AnyNode* addNode(AnyNode *node) 	{ 		mNodes.push_back(node); return node; 	}	AnyNode *getRoot() 	{ 		return mRoot; 	}		void setRoot(AnyNode *root) 	{ 		mRoot = root; 	}};#endif

MyNode.h

#ifndef MYNODE_H#define MYNODE_H#include <windows.h>#include <d3d9.h>#include <d3dx9.h>#include <dxerr9.h>#include <cstdio>#include "graphNode.h"class MyNode : public GraphNode{	D3DXVECTOR2 mPosition;public:	MyNode(const D3DXVECTOR2& v) : mPosition(v) 	{ 	}		virtual ~MyNode() 	{ 	}	const D3DXVECTOR2& getPosition() const 	{ 		return mPosition; 	}};#endif

GraphNode.h

#ifndef GRAPHNODE_H#define GRAPHNODE_H#include <windows.h>#include <d3d9.h>#include <d3dx9.h>#include <dxerr9.h>#include <cstdio>#include <vector>#include <algorithm>class GraphNode{		std::vector<GraphNode*> mNodes;public:		GraphNode() { }		virtual ~GraphNode() 	{ 		/* does nothing */ 	}	void add(GraphNode *node) 	{ 		mNodes.push_back(node); 	}		void remove(GraphNode *node)	{		mNodes.erase(std::remove(mNodes.begin(), mNodes.end(), node), mNodes.end());	}		const std::vector<GraphNode*>& next() const 	{ 		return mNodes; 	}};#endif

main.cpp

//=========== Includes#include <windows.h>#include <d3d9.h>#include <d3dx9.h>#include <dxerr9.h>#include <cstdio>#include "nodes.h"#include "../graph/myNode.h"#include "../graph/graph.h"Graph<MyNode> graph;void nodes_Init(){	// node 1	MyNode *node1 = graph.addNode(new MyNode(D3DXVECTOR2((Column2X(10,TILESIZE,MAPCOLUMNCOUNT))+XOFFSET,(Row2Y(10,TILESIZE))+YOFFSET)));	graph.setRoot(node1);	// node 2	MyNode *node2 = graph.addNode(new MyNode(D3DXVECTOR2((Column2X(10,TILESIZE,MAPCOLUMNCOUNT))+XOFFSET,(Row2Y(10,TILESIZE))+YOFFSET)));	node1->add(node2);	node2->add(node1);}

Prog101

100

Author

September 08, 2006 10:10 AM

I have found this class would i be able to use this one by itself to make a graph and apply edges to it?

#ifndef SPARSEGRAPH_H#define SPARSEGRAPH_H#pragma warning (disable:4786)//------------------------------------------------------------------------////  Name:   SparseGraph.h////  Desc:   Graph class using the adjacency list representation.////  Author: Mat Buckland (fup@ai-junkie.com)////------------------------------------------------------------------------#include <vector>#include <list>#include <cassert>#include <string>#include <iostream>#include "2D/Vector2D.h"#include "misc/utils.h" #include "graph/NodeTypeEnumerations.h"template <class node_type, class edge_type>   class SparseGraph                                 {public:  //enable easy client access to the edge and node types used in the graph  typedef edge_type                EdgeType;  typedef node_type                NodeType;    //a couple more typedefs to save my fingers and to help with the formatting  //of the code on the printed page  typedef std::vector<node_type>   NodeVector;  typedef std::list<edge_type>     EdgeList;  typedef std::vector<EdgeList>    EdgeListVector; private:    //the nodes that comprise this graph  NodeVector      m_Nodes;  //a vector of adjacency edge lists. (each node index keys into the   //list of edges associated with that node)  EdgeListVector  m_Edges;   //is this a directed graph?  bool            m_bDigraph;  //the index of the next node to be added  int             m_iNextNodeIndex;        //returns true if an edge is not already present in the graph. Used  //when adding edges to make sure no duplicates are created.  bool  UniqueEdge(int from, int to)const;  //iterates through all the edges in the graph and removes any that point  //to an invalidated node  void  CullInvalidEdges();  public:    //ctor  SparseGraph(bool digraph): m_iNextNodeIndex(0), m_bDigraph(digraph){}  //returns the node at the given index  const NodeType&  GetNode(int idx)const;  //non const version  NodeType&  GetNode(int idx);  //const method for obtaining a reference to an edge  const EdgeType& GetEdge(int from, int to)const;  //non const version  EdgeType& GetEdge(int from, int to);      //retrieves the next free node index  int   GetNextFreeNodeIndex()const{return m_iNextNodeIndex;}    //adds a node to the graph and returns its index  int   AddNode(node_type node);  //removes a node by setting its index to invalid_node_index  void  RemoveNode(int node);  //Use this to add an edge to the graph. The method will ensure that the  //edge passed as a parameter is valid before adding it to the graph. If the  //graph is a digraph then a similar edge connecting the nodes in the opposite  //direction will be automatically added.  void  AddEdge(EdgeType edge);  //removes the edge connecting from and to from the graph (if present). If  //a digraph then the edge connecting the nodes in the opposite direction   //will also be removed.  void  RemoveEdge(int from, int to);  //sets the cost of an edge  void  SetEdgeCost(int from, int to, double cost);  //returns the number of active + inactive nodes present in the graph  int   NumNodes()const{return m_Nodes.size();}    //returns the number of active nodes present in the graph (this method's  //performance can be improved greatly by caching the value)  int   NumActiveNodes()const  {    int count = 0;    for (unsigned int n=0; n<m_Nodes.size(); ++n) if (m_Nodes[n].Index() != invalid_node_index) ++count;    return count;  }  //returns the total number of edges present in the graph  int   NumEdges()const  {    int tot = 0;    for (EdgeListVector::const_iterator curEdge = m_Edges.begin();         curEdge != m_Edges.end();         ++curEdge)    {      tot += curEdge->size();    }    return tot;  }  //returns true if the graph is directed  bool  isDigraph()const{return m_bDigraph;}  //returns true if the graph contains no nodes  bool	isEmpty()const{return m_Nodes.empty();}  //returns true if a node with the given index is present in the graph  bool isNodePresent(int nd)const;  //returns true if an edge connecting the nodes 'to' and 'from'  //is present in the graph  bool isEdgePresent(int from, int to)const;  //methods for loading and saving graphs from an open file stream or from  //a file name   bool  Save(const char* FileName)const;  bool  Save(std::ofstream& stream)const;  bool  Load(const char* FileName);  bool  Load(std::ifstream& stream);  //clears the graph ready for new node insertions  void Clear(){m_iNextNodeIndex = 0; m_Nodes.clear(); m_Edges.clear();}  void RemoveEdges()  {    for (EdgeListVector::iterator it = m_Edges.begin(); it != m_Edges.end(); ++it)    {      it->clear();    }  }      //non const class used to iterate through all the edges connected to a specific node.       class EdgeIterator      {      private:                                                                        typename EdgeList::iterator         curEdge;        SparseGraph<node_type, edge_type>&  G;        const int                           NodeIndex;      public:        EdgeIterator(SparseGraph<node_type, edge_type>& graph,                     int                                node): G(graph),                                                               NodeIndex(node)        {          /* we don't need to check for an invalid node index since if the node is             invalid there will be no associated edges         */          curEdge = G.m_Edges[NodeIndex].begin();        }        EdgeType*  begin()        {                  curEdge = G.m_Edges[NodeIndex].begin();              return &(*curEdge);        }        EdgeType*  next()        {          ++curEdge;              return &(*curEdge);        }        //return true if we are at the end of the edge list        bool end()        {          return (curEdge == G.m_Edges[NodeIndex].end());        }      };  friend class EdgeIterator;  //const class used to iterate through all the edges connected to a specific node.       class ConstEdgeIterator      {      private:                                                                        typename EdgeList::const_iterator        curEdge;        const SparseGraph<node_type, edge_type>& G;        const int                                NodeIndex;      public:        ConstEdgeIterator(const SparseGraph<node_type, edge_type>& graph,                          int                           node): G(graph),                                                               NodeIndex(node)        {          /* we don't need to check for an invalid node index since if the node is             invalid there will be no associated edges         */          curEdge = G.m_Edges[NodeIndex].begin();        }        const EdgeType*  begin()        {                  curEdge = G.m_Edges[NodeIndex].begin();              return &(*curEdge);        }        const EdgeType*  next()        {          ++curEdge;              return &(*curEdge);        }        //return true if we are at the end of the edge list        bool end()        {          return (curEdge == G.m_Edges[NodeIndex].end());        }      };  friend class ConstEdgeIterator;  //non const class used to iterate through the nodes in the graph    class NodeIterator    {    private:      typename NodeVector::iterator         curNode;            SparseGraph<node_type, edge_type>&    G;      //if a graph node is removed, it is not removed from the       //vector of nodes (because that would mean changing all the indices of       //all the nodes that have a higher index). This method takes a node      //iterator as a parameter and assigns the next valid element to it.      void GetNextValidNode(typename NodeVector::iterator& it)      {        if ( curNode == G.m_Nodes.end() || it->Index() != invalid_node_index) return;        while ( (it->Index() == invalid_node_index) )        {          ++it;          if (curNode == G.m_Nodes.end()) break;        }      }    public:            NodeIterator(SparseGraph<node_type, edge_type> &graph):G(graph)      {        curNode = G.m_Nodes.begin();      }      node_type* begin()      {              curNode = G.m_Nodes.begin();        GetNextValidNode(curNode);        return &(*curNode);      }      node_type* next()      {        ++curNode;        GetNextValidNode(curNode);        return &(*curNode);      }      bool end()      {        return (curNode == G.m_Nodes.end());      }    };       friend class NodeIterator;    //const class used to iterate through the nodes in the graph    class ConstNodeIterator    {    private:      typename NodeVector::const_iterator			curNode;      const SparseGraph<node_type, edge_type>&      G;      //if a graph node is removed or switched off, it is not removed from the       //vector of nodes (because that would mean changing all the indices of       //all the nodes that have a higher index. This method takes a node      //iterator as a parameter and assigns the next valid element to it.      void GetNextValidNode(typename NodeVector::const_iterator& it)      {        if ( curNode == G.m_Nodes.end() || it->Index() != invalid_node_index) return;        while ( (it->Index() == invalid_node_index) )        {          ++it;          if (curNode == G.m_Nodes.end()) break;        }      }    public:      ConstNodeIterator(const SparseGraph<node_type, edge_type> &graph):G(graph)      {        curNode = G.m_Nodes.begin();      }      const node_type* begin()      {              curNode = G.m_Nodes.begin();        GetNextValidNode(curNode);        return &(*curNode);      }      const node_type* next()      {        ++curNode;        GetNextValidNode(curNode);        return &(*curNode);      }      bool end()      {        return (curNode == G.m_Nodes.end());      }    };  friend class ConstNodeIterator;};//--------------------------- isNodePresent --------------------------------////  returns true if a node with the given index is present in the graph//--------------------------------------------------------------------------template <class node_type, class edge_type>bool SparseGraph<node_type, edge_type>::isNodePresent(int nd)const{    if ( (m_Nodes[nd].Index() == invalid_node_index) || (nd >= m_Nodes.size()))    {      return false;    }    else return true;}//--------------------------- isEdgePresent --------------------------------////  returns true if an edge with the given from/to is present in the graph//--------------------------------------------------------------------------template <class node_type, class edge_type>bool SparseGraph<node_type, edge_type>::isEdgePresent(int from, int to)const{    if (isNodePresent(from) && isNodePresent(from))    {       for (EdgeList::const_iterator curEdge = m_Edges[from].begin();            curEdge != m_Edges[from].end();            ++curEdge)        {          if (curEdge->To() == to) return true;        }        return false;    }    else return false;}//------------------------------ GetNode -------------------------------------////  const and non const methods for obtaining a reference to a specific node//----------------------------------------------------------------------------template <class node_type, class edge_type>const node_type&  SparseGraph<node_type, edge_type>::GetNode(int idx)const{    assert( (idx < (int)m_Nodes.size()) &&            (idx >=0)              &&           "<SparseGraph::GetNode>: invalid index");    return m_Nodes[idx];}  //non const versiontemplate <class node_type, class edge_type>node_type&  SparseGraph<node_type, edge_type>::GetNode(int idx){    assert( (idx < (int)m_Nodes.size()) &&            (idx >=0)             &&          "<SparseGraph::GetNode>: invalid index");        return m_Nodes[idx];}//------------------------------ GetEdge -------------------------------------////  const and non const methods for obtaining a reference to a specific edge//----------------------------------------------------------------------------template <class node_type, class edge_type>const edge_type& SparseGraph<node_type, edge_type>::GetEdge(int from, int to)const{  assert( (from < m_Nodes.size()) &&          (from >=0)              &&           m_Nodes[from].Index() != invalid_node_index &&          "<SparseGraph::GetEdge>: invalid 'from' index");  assert( (to < m_Nodes.size()) &&          (to >=0)              &&          m_Nodes[to].Index() != invalid_node_index &&          "<SparseGraph::GetEdge>: invalid 'to' index");  for (EdgeList::const_iterator curEdge = m_Edges[from].begin();       curEdge != m_Edges[from].end();       ++curEdge)  {    if (curEdge->To() == to) return *curEdge;  }  assert (0 && "<SparseGraph::GetEdge>: edge does not exist");}//non const versiontemplate <class node_type, class edge_type>edge_type& SparseGraph<node_type, edge_type>::GetEdge(int from, int to){  assert( (from < m_Nodes.size()) &&          (from >=0)              &&           m_Nodes[from].Index() != invalid_node_index &&          "<SparseGraph::GetEdge>: invalid 'from' index");  assert( (to < m_Nodes.size()) &&          (to >=0)              &&          m_Nodes[to].Index() != invalid_node_index &&          "<SparseGraph::GetEdge>: invalid 'to' index");  for (EdgeList::iterator curEdge = m_Edges[from].begin();       curEdge != m_Edges[from].end();       ++curEdge)  {    if (curEdge->To() == to) return *curEdge;  }  assert (0 && "<SparseGraph::GetEdge>: edge does not exist");}//-------------------------- AddEdge ------------------------------------------////  Use this to add an edge to the graph. The method will ensure that the//  edge passed as a parameter is valid before adding it to the graph. If the//  graph is a digraph then a similar edge connecting the nodes in the opposite//  direction will be automatically added.//-----------------------------------------------------------------------------template <class node_type, class edge_type>void SparseGraph<node_type, edge_type>::AddEdge(EdgeType edge){  //first make sure the from and to nodes exist within the graph   assert( (edge.From() < m_iNextNodeIndex) && (edge.To() < m_iNextNodeIndex) &&          "<SparseGraph::AddEdge>: invalid node index");  //make sure both nodes are active before adding the edge  if ( (m_Nodes[edge.To()].Index() != invalid_node_index) &&        (m_Nodes[edge.From()].Index() != invalid_node_index))  {    //add the edge, first making sure it is unique    if (UniqueEdge(edge.From(), edge.To()))    {      m_Edges[edge.From()].push_back(edge);    }    //if the graph is undirected we must add another connection in the opposite    //direction    if (!m_bDigraph)    {      //check to make sure the edge is unique before adding      if (UniqueEdge(edge.To(), edge.From()))      {        EdgeType NewEdge = edge;        NewEdge.SetTo(edge.From());        NewEdge.SetFrom(edge.To());        m_Edges[edge.To()].push_back(NewEdge);      }    }  }}//----------------------------- RemoveEdge ---------------------------------template <class node_type, class edge_type>void SparseGraph<node_type, edge_type>::RemoveEdge(int from, int to){  assert ( (from < (int)m_Nodes.size()) && (to < (int)m_Nodes.size()) &&           "<SparseGraph::RemoveEdge>:invalid node index");  EdgeList::iterator curEdge;    if (!m_bDigraph)  {    for (curEdge = m_Edges[to].begin();         curEdge != m_Edges[to].end();         ++curEdge)    {      if (curEdge->To() == from){curEdge = m_Edges[to].erase(curEdge);break;}    }  }  for (curEdge = m_Edges[from].begin();       curEdge != m_Edges[from].end();       ++curEdge)  {    if (curEdge->To() == to){curEdge = m_Edges[from].erase(curEdge);break;}  }}//-------------------------- AddNode -------------------------------------////  Given a node this method first checks to see if the node has been added//  previously but is now innactive. If it is, it is reactivated.////  If the node has not been added previously, it is checked to make sure its//  index matches the next node index before being added to the graph//------------------------------------------------------------------------template <class node_type, class edge_type>int SparseGraph<node_type, edge_type>::AddNode(node_type node){  if (node.Index() < (int)m_Nodes.size())  {    //make sure the client is not trying to add a node with the same ID as    //a currently active node    assert (m_Nodes[node.Index()].Index() == invalid_node_index &&      "<SparseGraph::AddNode>: Attempting to add a node with a duplicate ID");        m_Nodes[node.Index()] = node;    return m_iNextNodeIndex;  }    else  {    //make sure the new node has been indexed correctly    assert (node.Index() == m_iNextNodeIndex && "<SparseGraph::AddNode>:invalid index");    m_Nodes.push_back(node);    m_Edges.push_back(EdgeList());    return m_iNextNodeIndex++;  }}//----------------------- CullInvalidEdges ------------------------------------////  iterates through all the edges in the graph and removes any that point//  to an invalidated node//-----------------------------------------------------------------------------template <class node_type, class edge_type>void SparseGraph<node_type, edge_type>::CullInvalidEdges(){  for (EdgeListVector::iterator curEdgeList = m_Edges.begin(); curEdgeList != m_Edges.end(); ++curEdgeList)  {    for (EdgeList::iterator curEdge = (*curEdgeList).begin(); curEdge != (*curEdgeList).end(); ++curEdge)    {      if (m_Nodes[curEdge->To()].Index() == invalid_node_index ||           m_Nodes[curEdge->From()].Index() == invalid_node_index)      {        curEdge = (*curEdgeList).erase(curEdge);      }    }  }}  //------------------------------- RemoveNode -----------------------------////  Removes a node from the graph and removes any links to neighbouring//  nodes//------------------------------------------------------------------------template <class node_type, class edge_type>void SparseGraph<node_type, edge_type>::RemoveNode(int node)                                   {  assert(node < (int)m_Nodes.size() && "<SparseGraph::RemoveNode>: invalid node index");  //set this node's index to invalid_node_index  m_Nodes[node].SetIndex(invalid_node_index);  //if the graph is not directed remove all edges leading to this node and then  //clear the edges leading from the node  if (!m_bDigraph)  {        //visit each neighbour and erase any edges leading to this node    for (EdgeList::iterator curEdge = m_Edges[node].begin();          curEdge != m_Edges[node].end();         ++curEdge)    {      for (EdgeList::iterator curE = m_Edges[curEdge->To()].begin();           curE != m_Edges[curEdge->To()].end();           ++curE)      {         if (curE->To() == node)         {           curE = m_Edges[curEdge->To()].erase(curE);           break;         }      }    }    //finally, clear this node's edges    m_Edges[node].clear();  }  //if a digraph remove the edges the slow way  else  {    CullInvalidEdges();  }}//-------------------------- SetEdgeCost ---------------------------------////  Sets the cost of a specific edge//------------------------------------------------------------------------template <class node_type, class edge_type>void SparseGraph<node_type, edge_type>::SetEdgeCost(int from, int to, double NewCost){  //make sure the nodes given are valid  assert( (from < m_Nodes.size()) && (to < m_Nodes.size()) &&        "<SparseGraph::SetEdgeCost>: invalid index");  //visit each neighbour and erase any edges leading to this node  for (EdgeList::iterator curEdge = m_Edges[from].begin();        curEdge != m_Edges[from].end();       ++curEdge)  {    if (curEdge->To() == to)    {      curEdge->SetCost(NewCost);      break;    }  }}  //-------------------------------- UniqueEdge ----------------------------////  returns true if the edge is not present in the graph. Used when adding//  edges to prevent duplication//------------------------------------------------------------------------template <class node_type, class edge_type>bool SparseGraph<node_type, edge_type>::UniqueEdge(int from, int to)const{  for (EdgeList::const_iterator curEdge = m_Edges[from].begin();       curEdge != m_Edges[from].end();       ++curEdge)  {    if (curEdge->To() == to)    {      return false;    }  }  return true;}//-------------------------------- Save ---------------------------------------template <class node_type, class edge_type>bool SparseGraph<node_type, edge_type>::Save(const char* FileName)const{  //open the file and make sure it's valid  std::ofstream out(FileName);  if (!out)  {    throw std::runtime_error("Cannot open file: " + std::string(FileName));    return false;  }  return Save(out);}//-------------------------------- Save ---------------------------------------template <class node_type, class edge_type>bool SparseGraph<node_type, edge_type>::Save(std::ofstream& stream)const{  //save the number of nodes  stream << m_Nodes.size() << std::endl;  //iterate through the graph nodes and save them  NodeVector::const_iterator curNode = m_Nodes.begin();  for (curNode; curNode!=m_Nodes.end(); ++curNode)  {    stream << *curNode;  }  //save the number of edges  stream << NumEdges() << std::endl;  //iterate through the edges and save them  for (unsigned int nodeIdx = 0; nodeIdx < m_Nodes.size(); ++nodeIdx)  {    for (EdgeList::const_iterator curEdge = m_Edges[nodeIdx].begin();         curEdge!=m_Edges[nodeIdx].end(); ++curEdge)    {      stream << *curEdge;    }    }  return true;}//------------------------------- Load ----------------------------------------//-----------------------------------------------------------------------------template <class node_type, class edge_type>bool SparseGraph<node_type, edge_type>::Load(const char* FileName){  //open file and make sure it's valid  std::ifstream in(FileName);  if (!in)  {    throw std::runtime_error("Cannot open file: " + std::string(FileName));    return false;  }  return Load(in);}//------------------------------- Load ----------------------------------------//-----------------------------------------------------------------------------template <class node_type, class edge_type>bool SparseGraph<node_type, edge_type>::Load(std::ifstream& stream){  Clear();  //get the number of nodes and read them in  int NumNodes, NumEdges;  stream >> NumNodes;  for (int n=0; n<NumNodes; ++n)  {    NodeType NewNode(stream);      //when editing graphs it's possible to end up with a situation where some    //of the nodes have been invalidated (their id's set to invalid_node_index). Therefore    //when a node of index invalid_node_index is encountered, it must still be added.    if (NewNode.Index() != invalid_node_index)    {      AddNode(NewNode);    }    else    {      m_Nodes.push_back(NewNode);      //make sure an edgelist is added for each node      m_Edges.push_back(EdgeList());            ++m_iNextNodeIndex;    }  }  //now add the edges  stream >> NumEdges;  for (int e=0; e<NumEdges; ++e)  {    EdgeType NextEdge(stream);    m_Edges[NextEdge.From()].push_back(NextEdge);  }  return true;}   #endif

How do you implemant a graph data structure?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

How do you implemant a graph data structure?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines