outil/src/hypergraphlib_dijkstra.cpp

#include "gestionversion.h"
#include "HypergraphLib_Dijkstra.h"

#include "HypergraphLib_Graph.h"
#include "HypergraphLib_Node.h"
#include "HypergraphLib_Arc.h"

#include <stdio.h>

using namespace HypergraphLib;

//---------------------------------------------------------------------------
struct DJNode {
    int nbVisit;
    double d;
    Node * n;
    Node * previous;
    Arc * prevArc;
};

//---------------------------------------------------------------------------
//Calcule le chemin le plus court entre les noeuds a et b, selon la
//fonction de coût distanceFunc
double
HypergraphLib::Dijkstra(Graph * __G, Node * source, Node * destination, double (* distanceFunc)  (HypergraphLib::Node*, HypergraphLib::Node*, HypergraphLib::Arc*) , std::vector<Node *> & path, std::vector<Arc*> & pathArcs)
{
    int i,j,k;

#define djnode(xtmp) ((DJNode*)xtmp->GetUserData(50))


    Graph::MapNodesById graphNodes = __G->GetNodes();
    for (Graph::MapNodesById::iterator itNode = graphNodes.begin();
         itNode != graphNodes.end();
         itNode ++ )
        {
                Node * n = itNode->second;
            struct DJNode * dj = new struct DJNode;
            dj->previous = NULL;
            dj->n = n;
            dj->nbVisit = 0;
            dj->d = 1E300;
            dj->prevArc = 0;

            n->SetUserData(50,dj);
        }

  if (__G->GetNode(source->Id()) != source || __G->GetNode(destination->Id()) != destination )
      return 1E300; 

  djnode(source)->d = 0;
   
    typedef std::pair < double, DJNode * > DJElement;
  std::set < DJElement > Q;
  std::set < DJElement >::iterator itQ;
  DJNode* djSource=djnode(source);
  DJNode* djDestination=djnode(destination);
  Q.insert(DJElement(djSource->d,djSource));

  while ( ! Q.empty() )
  {
    struct DJNode * current = NULL;

    DJElement top = *Q.begin();
    Q.erase(Q.begin());
    current = top.second;

    if ( current == NULL )
        break;

    current->nbVisit++;

    for ( Node::MultimapArcsById::iterator itArc1 = current->n->IncidentArcs().begin();
        itArc1 != current->n->IncidentArcs().end();
        itArc1 ++    )
    {
        Arc * arc = itArc1->second;
        for ( Arc::MultimapNodesById::iterator itNode = arc->Nodes().begin();
        itNode != arc->Nodes().end();
        itNode ++    )
        {
            Node * child = itNode->second;
            if (child == current->n)
                continue;
                
            struct DJNode * sDJNodeChild = djnode(child);
            double dist_child = distanceFunc(child, current->n, arc);

            if ( sDJNodeChild->d > current->d + dist_child)
            {             
                if(sDJNodeChild->d < 1E100) {
                      itQ =  Q.find(DJElement(sDJNodeChild->d,sDJNodeChild));
                      if (itQ != Q.end())
                        Q.erase(itQ);
                }
                
                sDJNodeChild->d = current->d + dist_child;
                sDJNodeChild->previous = current->n;
                sDJNodeChild->prevArc = arc;

                Q.insert(DJElement(sDJNodeChild->d,sDJNodeChild));                
            }
        }
    }
  }

  struct DJNode * n = djDestination;
  double length = n->d;

  int nb_node = __G->GetNodes().size();

  for (i=0; i<nb_node ; i++)
  {                        
      path.insert(path.begin(), n->n);
      if (n->prevArc)
          pathArcs.insert(pathArcs.begin(), n->prevArc);
      if ( n->n == source )
            break;
      else
      {
        if (n->previous)
            n = djnode(n->previous);
        else
            break;
      }
  }
  if (i == nb_node)
      length = 1E300;

    for (Graph::MapNodesById::iterator itNode = graphNodes.begin();
         itNode != graphNodes.end();
         itNode ++ )
     {
                Node * node = itNode->second;
                struct DJNode * djtmp = djnode(node);
                delete djtmp;
                node->SetUserData(50,0);
        }
#undef djnode    
  
  return length;
}


Revision:	176
Committed:	Tue May 19 20:56:11 2009 UTC (15 years, 11 months ago) by foucault
Original Path:	*magic/lib/outil/outil/src/HypergraphLib_Dijkstra.cpp*
File size:	4057 byte(s)
Error occurred while calculating annotation data.
Log Message:	Mise Ã jour : * CAD4FE * outil : HypergraphLib qui est maintenant compilable sous Linux (essais mois aout 2008) * outil : ot_mathematique.cpp suppression d'une mÃ©thode de classe inutile nÃ©cessaire pour compiler avec CodeGear Builder 2006 OT_VECTEUR_3D::OT_VECTEUR_3D(OT_VECTEUR_3D& mdd)
#	Content
1	#include "gestionversion.h"
2	#include "HypergraphLib_Dijkstra.h"
3
4	#include "HypergraphLib_Graph.h"
5	#include "HypergraphLib_Node.h"
6	#include "HypergraphLib_Arc.h"
7
8	#include <stdio.h>
9
10	using namespace HypergraphLib;
11
12	//---------------------------------------------------------------------------
13	struct DJNode {
14	int nbVisit;
15	double d;
16	Node * n;
17	Node * previous;
18	Arc * prevArc;
19	};
20
21	//---------------------------------------------------------------------------
22	//Calcule le chemin le plus court entre les noeuds a et b, selon la
23	//fonction de coût distanceFunc
24	double
25	HypergraphLib::Dijkstra(Graph * __G, Node * source, Node * destination, double (* distanceFunc) (HypergraphLib::Node, HypergraphLib::Node, HypergraphLib::Arc) , std::vector<Node > & path, std::vector<Arc*> & pathArcs)
26	{
27	int i,j,k;
28
29	#define djnode(xtmp) ((DJNode*)xtmp->GetUserData(50))
30
31
32	Graph::MapNodesById graphNodes = __G->GetNodes();
33	for (Graph::MapNodesById::iterator itNode = graphNodes.begin();
34	itNode != graphNodes.end();
35	itNode ++ )
36	{
37	Node * n = itNode->second;
38	struct DJNode * dj = new struct DJNode;
39	dj->previous = NULL;
40	dj->n = n;
41	dj->nbVisit = 0;
42	dj->d = 1E300;
43	dj->prevArc = 0;
44
45	n->SetUserData(50,dj);
46	}
47
48	if (__G->GetNode(source->Id()) != source \|\| __G->GetNode(destination->Id()) != destination )
49	return 1E300;
50
51	djnode(source)->d = 0;
52
53	typedef std::pair < double, DJNode * > DJElement;
54	std::set < DJElement > Q;
55	std::set < DJElement >::iterator itQ;
56	DJNode* djSource=djnode(source);
57	DJNode* djDestination=djnode(destination);
58	Q.insert(DJElement(djSource->d,djSource));
59
60	while ( ! Q.empty() )
61	{
62	struct DJNode * current = NULL;
63
64	DJElement top = *Q.begin();
65	Q.erase(Q.begin());
66	current = top.second;
67
68	if ( current == NULL )
69	break;
70
71	current->nbVisit++;
72
73	for ( Node::MultimapArcsById::iterator itArc1 = current->n->IncidentArcs().begin();
74	itArc1 != current->n->IncidentArcs().end();
75	itArc1 ++ )
76	{
77	Arc * arc = itArc1->second;
78	for ( Arc::MultimapNodesById::iterator itNode = arc->Nodes().begin();
79	itNode != arc->Nodes().end();
80	itNode ++ )
81	{
82	Node * child = itNode->second;
83	if (child == current->n)
84	continue;
85
86	struct DJNode * sDJNodeChild = djnode(child);
87	double dist_child = distanceFunc(child, current->n, arc);
88
89	if ( sDJNodeChild->d > current->d + dist_child)
90	{
91	if(sDJNodeChild->d < 1E100) {
92	itQ = Q.find(DJElement(sDJNodeChild->d,sDJNodeChild));
93	if (itQ != Q.end())
94	Q.erase(itQ);
95	}
96
97	sDJNodeChild->d = current->d + dist_child;
98	sDJNodeChild->previous = current->n;
99	sDJNodeChild->prevArc = arc;
100
101	Q.insert(DJElement(sDJNodeChild->d,sDJNodeChild));
102	}
103	}
104	}
105	}
106
107	struct DJNode * n = djDestination;
108	double length = n->d;
109
110	int nb_node = __G->GetNodes().size();
111
112	for (i=0; i<nb_node ; i++)
113	{
114	path.insert(path.begin(), n->n);
115	if (n->prevArc)
116	pathArcs.insert(pathArcs.begin(), n->prevArc);
117	if ( n->n == source )
118	break;
119	else
120	{
121	if (n->previous)
122	n = djnode(n->previous);
123	else
124	break;
125	}
126	}
127	if (i == nb_node)
128	length = 1E300;
129
130	for (Graph::MapNodesById::iterator itNode = graphNodes.begin();
131	itNode != graphNodes.end();
132	itNode ++ )
133	{
134	Node * node = itNode->second;
135	struct DJNode * djtmp = djnode(node);
136	delete djtmp;
137	node->SetUserData(50,0);
138	}
139	#undef djnode
140
141	return length;
142	}
143
144