KiCad PCB EDA Suite
from_to_cache.cpp File Reference
#include <cstdio>
#include <memory>
#include <reporter.h>
#include <board.h>
#include <string_utils.h>
#include <pcb_expr_evaluator.h>
#include <connectivity/connectivity_data.h>
#include <connectivity/connectivity_algo.h>
#include <connectivity/from_to_cache.h>

Go to the source code of this file.

Enumerations

enum  PATH_STATUS { PS_OK = 0 , PS_MULTIPLE_PATHS = -1 , PS_NO_PATH = -2 }
 

Functions

static bool isVertexVisited (CN_ITEM *v, const std::vector< CN_ITEM * > &path)
 
static PATH_STATUS uniquePathBetweenNodes (CN_ITEM *u, CN_ITEM *v, std::vector< CN_ITEM * > &outPath)
 

Enumeration Type Documentation

◆ PATH_STATUS

Enumerator
PS_OK 
PS_MULTIPLE_PATHS 
PS_NO_PATH 

Definition at line 53 of file from_to_cache.cpp.

53 {
54 PS_OK = 0,
56 PS_NO_PATH = -2
57};
@ PS_OK
@ PS_MULTIPLE_PATHS
@ PS_NO_PATH

Function Documentation

◆ isVertexVisited()

static bool isVertexVisited ( CN_ITEM v,
const std::vector< CN_ITEM * > &  path 
)
static

Definition at line 60 of file from_to_cache.cpp.

61{
62 for( auto u : path )
63 {
64 if ( u == v )
65 return true;
66 }
67
68 return false;
69}

References path.

Referenced by uniquePathBetweenNodes().

◆ uniquePathBetweenNodes()

static PATH_STATUS uniquePathBetweenNodes ( CN_ITEM u,
CN_ITEM v,
std::vector< CN_ITEM * > &  outPath 
)
static

Definition at line 72 of file from_to_cache.cpp.

73{
74 using Path = std::vector<CN_ITEM*>;
75 std::deque<Path> Q;
76
77 Path pInit;
78 bool pathFound = false;
79 pInit.push_back( u );
80 Q.push_back( pInit );
81
82 while( Q.size() )
83 {
84 Path path = Q.front();
85 Q.pop_front();
86 CN_ITEM* last = path.back();
87
88 if( last == v )
89 {
90 outPath = path;
91
92 if( pathFound )
93 return PS_MULTIPLE_PATHS;
94
95 pathFound = true;
96 }
97
98 for( auto ci : last->ConnectedItems() )
99 {
100 bool vertexVisited = isVertexVisited( ci, path );
101
102 for( auto& p : Q )
103 if( isVertexVisited( ci, p ) )
104 {
105 vertexVisited = true;
106 break;
107 }
108
109 if( !vertexVisited )
110 {
111 Path newpath( path );
112 newpath.push_back( ci );
113 Q.push_back( newpath );
114 }
115 }
116 }
117
118 return pathFound ? PS_OK : PS_NO_PATH;
119};
CN_ITEM represents a BOARD_CONNETED_ITEM in the connectivity system (ie: a pad, track/arc/via,...
const std::vector< CN_ITEM * > & ConnectedItems() const
static bool isVertexVisited(CN_ITEM *v, const std::vector< CN_ITEM * > &path)
#define Q()

References CN_ITEM::ConnectedItems(), isVertexVisited(), path, PS_MULTIPLE_PATHS, PS_NO_PATH, PS_OK, and Q.

Referenced by FROM_TO_CACHE::cacheFromToPaths().